2018q3 Homework2 (lab0)

contributed by < danielian1121 >

請同步更新原專案最新的 commit

commit message

Singly linked list 請遵循 commit message 的規範撰寫

Finish, add comments and make code cleaner 不需要寫出 Finish, 與您的修改無關

Change strdup to malloc 增加說明為什麼要抽換為 malloc，且此有一個 Makefile 的修改與此 commit 描述無關

課程助教

實驗環境

sukamo:~$ cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.1 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.1 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic

struct 架構

typedef struct ELE {
    char *value;
    struct ELE *next;
    struct ELE *prev;
} list_ele_t;

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    unsigned int count;
} queue_t;

You may add other fields to the structure list_ele, although you need not do so.

題目貌似沒有規定不能用 doubly linked list，但看到其他同學的共筆幾乎都沒有改到 list_ele_t 的架構，之後會開一個 branch 來實做 singly linked list

funtion 實做

q_new

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q == NULL) {
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->count = 0;
    return q;
}

q_free

void q_free(queue_t *q)
{
    if (q == NULL)
        return;
    list_ele_t *temp = q->head;
    list_ele_t *readyFree;
    while (temp) {
        readyFree = temp;
        temp = temp->next;
        //free(readyFree->value);
        free(readyFree);
    }
    free(q);
}

合理來說，註解掉的那一行應該要存在，否則每個 element 的 value 會沒有被 free 掉，但是加上去後 make test 又會跑不過，真的是很奇怪…
有看到同學的共筆也有提起這件事情(來源)
harness.h 有下列這段程式

/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free

因此我們程式中所用的 malloc and free 是使用測試程式中的某個函式，而我在 copy value 的時候使用了 strdup，此函式會在裡面呼叫 malloc ，因而繞過測試程式，因此在準備 free 的時候，也會誤判為此區段沒有事先 malloc 而發生錯誤

目前已改成用 malloc 搭配 strcpy 的方式來 copy value

q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    /** If q is NULL, return false. */
    if (q == NULL)
        return false;
 
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));

    /** If malloc failed, return false.  */
    if (newh == NULL)
        return false;

    char *s_copy = malloc(strlen(s) + 1);

    /** If malloc failed, return false. */
    if (s_copy == NULL) {
        free(newh);
        return false;
    }
    strcpy(s_copy, s);

    /** Set the new element. */
    newh->value = s_copy;
    newh->next = q->head;
    newh->prev = NULL;
    q->head = newh;

    /** If the new element is the first, set q->tail as q->head. */
    if (q->head->next == NULL)
        q->tail = q->head;
    else
        q->head->next->prev = q->head;

    /** Add count. */
    q->count++;
    return true;
}

q_insert_tail

作業有要求，此函式的時間複雜度必須為
$O (1)$ ，因此 queue_t 中才有一個指向 tail 的 pointer 存在
與 insert_head 大同小異，只是指標指向的位置要特別注意

bool q_insert_tail(queue_t *q, char *s)
{
    /** If q is NULL, return false. */
    if (q == NULL)
        return false;

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));

    /** If malloc failed, return false.  */
    if (newh == NULL)
        return false;

    char *s_copy = malloc(strlen(s) + 1);

    /** If malloc failed, return false. */
    if (s_copy == NULL) {
        free(newh);
        return false;
    }
    strcpy(s_copy, s);

    /** Set the new element. */
    newh->value = s_copy;
    newh->prev = q->tail;
    newh->next = NULL;
    q->tail = newh;


    /** If the new element is the first, set q->head as q->tail. */
    if (q->tail->prev == NULL)
        q->head = q->tail;
    else
        q->tail->prev->next = q->tail;

    /** Add count. */
    q->count++;
    return true;
}

q_remove_head

在刪除之際，也必須把即將刪除的 element 的 value 保存 bufsize 大小存到 sp 中
- 無法直接用 strcpy(q->head->value, sp) ，因為有可能會造成 Buffer Overflow
- 因此必須先知道 q->head->value 的長度，再依照結果來作不同的事情

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /** If q is NULL or q->head is NULL, return false. */
    if (q == NULL || q->head == NULL)
        return false;

    /** If len > bufsize, use strncpy to copy.
     * Otherwise, use strcpy.
     */
    if (sp != NULL) {
        size_t len = strlen(q->head->value);
        if (len > bufsize - 1) {
            strncpy(sp, q->head->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        } else {
            strcpy(sp, q->head->value);
        }
    }

    /** Check the element is the last or not. */
    if (q->head == q->tail)
        q->tail = NULL;

    /** Delete the head element. */
    list_ele_t *temp;
    temp = q->head;
    q->head = q->head->next;
    if (q->head != NULL)
        q->head->prev = NULL;

    /** Free the head element. */
    free(temp->value);
    free(temp);

    /** Subtract count. */
    q->count--;
    return true;
}

q_size

題目要求時間複雜度必須為
$O (1)$ ，因此也在 queue_t 中加入變數 count 來計算 size

int q_size(queue_t *q)
{
    return q ? q->count : 0;
}

q_reverse

在 doubly linked list 中，此函式實做比較簡單，只須交換 queue 中的 next and prev ，再交換 queue_t 的 head and tail 即可

void q_reverse(queue_t *q)
{
    if (q == NULL || q->head == NULL)
        return;
    list_ele_t *temp = q->head;
    list_ele_t *swap;
    /** Swap next and prev in every element from head to tail. */
    while (temp) {
        swap = temp->next;
        temp->next = temp->prev;
        temp->prev = swap;
        temp = swap;
    }
    /* swap head and tail */
    swap = q->head;
    q->head = q->tail;
    q->tail = swap;
}

Singly linked list

已有新 branch "singly"