Try   HackMD

2022q1 Homework1 (lab0)

contributed by < StevenChou499 >

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              1
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           60
Model name:                      Intel(R) Core(TM) i5-4690 CPU @ 3.50GHz
Stepping:                        3
CPU MHz:                         2962.442
CPU max MHz:                     3900.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6983.77
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-3

queue.c 開發過程

q_new

創造一個空的佇列，先宣告一個指向 list_head 的指標變數 head ，再用 malloc 配置記憶體給 head ，透過 INIT_LIST_HEAD(head) 將 next 以及 prev 均指向自己。若 malloc 失敗則會回傳 NULL 至 head ，所以 malloc 成功會回傳真正的指標，失敗會回傳 NULL 。

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(head);
    return head;
}

修改程式碼：
之後再加上若 head 成功 malloc 再進入初始化，但之後在 make check 時，會一直跳出 there are n blocks still allocated ，目前懷疑是 head 記憶體配置失敗後不會進入初始化，但其實是有成功配置的，因此在配置失敗後再執行 free(head) 釋放記憶體，最後回傳 NULL 。

  • 以下為完整的程式碼：
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (head) {
        INIT_LIST_HEAD(head);
        return head;
    }
    free(head);
    return NULL;
}

其中有使用到 list.h 的 INIT_LIST_HEAD() ，其實做方式為下：

INIT_LIST_HEAD()

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

q_free

先定義一指標變數 tmp = l->next ，若 tmp 不等於 l ，則代表還沒回到 head ，因此定義一個指向 element_t 的指標變數 del_el ，由 container_of 找出相對應的 element_t *，再將 tmp 只向下一個節點，同時釋放 value 以及自己本身的記憶體空間，直到回到 head 為止。最後再 free(tmp)。

void q_free(struct list_head *l)
{
    if(!l)
        return;
    struct list_head *tmp = l->next;
    while (tmp != l) {
        element_t *del_el;
        del_el = container_of(tmp, element_t, list);
        tmp = tmp->next;
        free(del_el->value);
        free(del_el);
    }
    free(tmp);
}

修改程式碼：
之後修改了判斷式，先判斷 l 是否存在，存在後先依序訪問各個節點並將其刪除並釋放記憶體，直到 tmp 剛好與 head 相同時再跳出 while 判斷式，最後將自己也刪除並釋放記憶體。

  • 以下為完整的程式碼：
void q_free(struct list_head *l)
{
    if (l) {
        struct list_head *tmp = l->next;
        while (tmp != l) {
            element_t *del_el;
            del_el = container_of(tmp, element_t, list);
            tmp = tmp->next;
            q_release_element(del_el);
        }
        free(l);
    }
}

其中有使用到 list.h 的 container_of() ，其實做方式為下：

container_of()

#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
#else
#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif

q_insert_head

先透過 malloc 配置空間給指向 element_t 的指標變數 new_el ，若 malloc 成功，則配置記憶體給 new_el 的 value ，利用 strncpy 複製 s 的內容。最後藉由 list_add 加入 head 的下一個節點，回傳 true ，若 malloc 失敗則回傳 false 。

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *new_el = malloc(sizeof(element_t));
    if(new_el){
        new_el->value = (char *)malloc(strlen(s) + 1);
        strncpy(new_el->value, s, strlen(s) + 1);
        list_add(&new_el->list, head);
        return true;
    }
    return false;
}

修改程式碼：
先判斷 head 是否存在，若存在則配置一 element_t 的記憶體。若配置成功且 s 並不是 NULL 則配置記憶體空間給新節點的字串，複製字串內容並加入佇列的第一位，再回傳 true 。因為也會遇到配置失敗但 make check 時卻回傳 there are n blocks still allocated ，因次只要配置失敗都會再 free() 相關的指標變數，並回傳 false 。

  • 以下為完整的程式碼：
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_el = malloc(sizeof(element_t));
    if (new_el && s) {
        new_el->value = malloc(strlen(s) + 1);
        if (new_el->value) {
            strncpy(new_el->value, s, strlen(s));
            *(new_el->value + strlen(s)) = '\0';
            list_add(&new_el->list, head);
            return true;
        }
        free(new_el->value);
    }
    free(new_el);
    return false;
}

其中有使用到 list.h 的 list_add() ，其實做方式為下：

list_add()

static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}

q_insert_tail

先透過 malloc 配置空間給指向 element_t 的指標變數 new_el ，若 malloc 成功，則配置記憶體給 new_el 的 value ，利用 strncpy 複製 s 的內容。最後藉由 list_add 加入 head 的上一個節點，回傳 true ，若 malloc 失敗則回傳 false 。完整程式碼如下：

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *new_el = malloc(sizeof(element_t));
    if(new_el){
        new_el->value = (char *)malloc(strlen(s) + 1);
        strncpy(new_el->value, s, strlen(s) + 1);
        list_add(&new_el->list, head);
        return true;
    }
    return false;
}

修改程式碼：
先判斷 head 是否存在，若存在則配置一 element_t 的記憶體。若配置成功且 s 並不是 NULL 則配置記憶體空間給新節點的字串，複製字串內容並加入佇列的最後一位，再回傳 true 。因為也會遇到配置失敗但 make check 時卻回傳 there are n blocks still allocated ，因次只要配置失敗都會再 free() 相關的指標變數，並回傳 false 。

  • 以下為完整的程式碼：
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_el = malloc(sizeof(element_t));
    if (new_el && s) {
        new_el->value = malloc(strlen(s) + 1);
        if (new_el->value) {
            strncpy(new_el->value, s, strlen(s));
            *(new_el->value + strlen(s)) = '\0';
            list_add_tail(&new_el->list, head);
            return true;
        }
        free(new_el->value);
    }
    free(new_el);
    return false;
}

其中有使用到 list.h 的 list_add_tail() ，其實做方式為下：

list_add_tail()

static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
    struct list_head *prev = head->prev;

    prev->next = node;
    node->next = head;
    node->prev = prev;
    head->prev = node;
}

q_remove_head

先測試 head 是否為 NULL 或是空的，若符合以上規則則直接回傳 NULL 。再利用 container_of 找出 head 的下一個指標。計算出 bufsize 與 strlen(rem_el) + 1 誰比較小，代入 char_len 。若 sp 存在則重新配置記憶體並複製 rem_el->value 的內容，移除該節點並回傳。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head && !list_empty(head)) {
        element_t *rem_el = container_of(head->next, element_t, list);
        int char_len = strlen(rem_el->value) + 1 < bufsize
                           ? strlen(rem_el->value) + 1
                           : bufsize;
        if (sp) {
            sp = realloc(sp, char_len);
            strncpy(sp, rem_el->value, char_len - 1);
            *(sp + char_len - 1) = '\0';
            list_del(&rem_el->list);
            return rem_el;
        }
        return rem_el;
    }
    return NULL;
}

修改程式碼：
在進行 make test 時會 trace-07 會有 malloc(): mismatching next->prev_size (unsorted) 的錯誤產生，在將 realloc 去除掉後便沒有錯誤了。

  • 以下為完整的程式碼：
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head && !list_empty(head)) {
        element_t *rem_el = list_entry(head->next, element_t, list);
        int char_len = strlen(rem_el->value) < bufsize - 1
                           ? strlen(rem_el->value)
                           : bufsize - 1;
        if (sp && (char_len > 0)) {
            strncpy(sp, rem_el->value, char_len + 1);
            *(sp + char_len) = '\0';
        }
        list_del(&rem_el->list);
        return rem_el;
    }
    return NULL;
}

其中有使用到 list.h 的 list_del() 與 list_empty()，其實做方式為下：

list_del()

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;

#ifdef LIST_POISONING
    node->prev = (struct list_head *) (0x00100100);
    node->next = (struct list_head *) (0x00200200);
#endif
}

list_empty()

static inline int list_empty(const struct list_head *head)
{
    return (head->next == head);
}

q_remove_tail

先測試 head 是否為 NULL 或是空的，若符合以上規則則直接回傳 NULL 。再利用 container_of 找出 head 的上一個指標。計算出 bufsize 與 strlen(rem_el) + 1 誰比較小，代入 char_len 。若 sp 存在則重新配置記憶體並複製 rem_el->value 的內容，移除該節點並回傳。完整程式碼如下：

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head && !list_empty(head)) {
        element_t *rem_el = container_of(head->next, element_t, list);
        int char_len = strlen(rem_el->value) + 1 < bufsize
                           ? strlen(rem_el->value) + 1
                           : bufsize;
        if (sp) {
            sp = realloc(sp, char_len);
            strncpy(sp, rem_el->value, char_len - 1);
            *(sp + char_len - 1) = '\0';
            list_del(&rem_el->list);
            return rem_el;
        }
        return rem_el;
    }
    return NULL;
}

修改程式碼：
在進行 make test 時會 trace-07 會有 malloc(): mismatching next->prev_size (unsorted) 的錯誤產生，在將 realloc 去除掉後便沒有錯誤了。

  • 以下為完整的程式碼：
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head && !list_empty(head)) {
        element_t *rem_el = list_entry(head->prev, element_t, list);
        int char_len = strlen(rem_el->value) < bufsize - 1
                           ? strlen(rem_el->value)
                           : bufsize - 1;
        if (sp) {
            strncpy(sp, rem_el->value, char_len + 1);
            *(sp + char_len) = '\0';
        }
        list_del(&rem_el->list);
        return rem_el;
    }
    return NULL;
}

q_release_element

此函式不可更動

  • 以下為完整的程式碼：
void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

q_size

先定義一區域變數 i=0 ，利用 !list_empty(head) 確認佇列是否為空的，若為空的則定義一個指標變數 tmp 指向 head->next 。若 tmp 不等於 head 則 i++ 且 tmp 指向 tmp->next ，最後回傳 i 。

  • 以下為完整的程式碼：
int q_size(struct list_head *head)
{
    int i = 0;
    if(!list_empty(head)){
        struct list_head *tmp = head->next;
        while(tmp != head){
            i++;
            tmp = tmp->next;
        }
    }
    return i;
}

q_delete_mid

先找出佇列的總節點個數，除以2後建立一指向 struct list head 的指標變數 tmp ，一直跳入下一個節點直到走到中間，利用 list_del 移除該節點後回傳 true ，若 head 不存在或是為空佇列則回傳 false 。

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (head && !list_empty(head)) {
        int n = q_size(head) / 2;
        struct list_head *tmp = head;
        for (int i = 0; i != n; i++) {
            tmp = tmp->next;
        }
        list_del(tmp);
        return true;
    }
    return false;
}

思考避免呼叫 q_size 的方法，降低記憶體存取的數量。
:notes: jserv

好的，學生再想想看，謝謝老師。StevenChou43

修改程式碼：
為了不使用 q_size 計算總節點的數量，我使用一個一次移動一格的指標 slow 與一次移動兩格的指標 fast 。若 fast 已經與 head 重疊或是下一個是 head ，則停止移動並刪除 slow 的節點。最後回傳 true 。

  • 以下為完整的程式碼：
bool q_delete_mid(struct list_head *head)
{
    if (head && !list_empty(head)) {
        struct list_head *slow = head->next, *fast = slow->next;
        while(fast != head && fast->next != head){
            slow = slow->next;
            fast = fast->next->next;
        }
        list_del(slow);
        q_release_element(list_entry(slow, element_t, list));
        return true;
    }
    return false;
}

q_delete_dup

先確認 head 是否存在並且至少存在兩個以上的元素。接著創造三個指向 struct list_head 的指標變數， *tmp1 = head->next 、tmp2 = tmp1->next 和 tmp = NULL 。接著找出 tmp1 與 tmp2 分別代表的字串，若不同則分別至向下一個元素。若遇到字串內容相同，則鄉用 tmp = tmp1 將重複元素中的第一個位置記下來，再將 tmp2 元素刪掉並跳至下一個元素，繼續進行比較，直到不同或是 tmp2 已經與 head 重疊（代表已經完全比完了）則跳出 while 迴圈，並將 tmp1 與 tmp2 的位置各前進一格。此時 tmp 的位置仍是需要被刪除的，藉由 if(tmp != NULL) 可以知道是否有元素重複，若重負責刪除 tmp 的元素。此時仍必須再比較一次看使否 tmp2 與 head 的位置重疊。若重疊則直接跳出迴圈，回傳 true 。

  • 以下為完整的程式碼：
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (head && !list_empty(head) && !list_is_singular(head)) {
        struct list_head *tmp1 = head->next;
        struct list_head *tmp2 = tmp1->next;
        struct list_head *tmp = NULL;
        while (tmp1 != head) {
            element_t *del_el_1 = list_entry(tmp1, element_t, list);
            element_t *del_el_2 = list_entry(tmp2, element_t, list);
            while (!strcmp(del_el_1->value, del_el_2->value)) {
                tmp = tmp1;
                list_del(tmp2);
                q_release_element(list_entry(tmp2, element_t, list));
                tmp2 = tmp1->next;
                del_el_2 = list_entry(tmp2, element_t, list);
                if (tmp2 == head)
                    break;
            }
            tmp1 = tmp2;
            tmp2 = tmp1->next;
            if (tmp != NULL) {
                list_del(tmp);
                q_release_element(list_entry(tmp, element_t, list));
                tmp = NULL;
            }
            if (tmp2 == head)
                break;
        }
        return true;
    }
    return false;
}

其中有使用到 list.h 的 list_is_singular() ，其實做方法如下：

list_is_singular()

static inline int list_is_singular(const struct list_head *head)
{
    return (!list_empty(head) && head->prev == head->next);
}

q_swap

首先檢查 head 是否存在或是只有一個以下的元素，若為上述情況則直接跳出該程式。接著指標 curr 指向 head 的下一個 list_head ，進入迴圈，指標 tmp 指向 curr 的下一個 list_head 。先使用 list_del 除去 curr ，再將 curr 利用 list_add 加入 tmp 的下一個元素位置，接著將 curr 移至下下個位置。繼續上述的動作直到 curr 或是 curr 的下一個元素是 head 。

  • 以下為完整的程式碼：
void q_swap(struct list_head *head)
{
    if (head && !list_empty(head) && !list_is_singular(head)) {
        struct list_head *curr = head->next;
        for (; !(curr == head || curr->next == head); curr = curr->next) {
            struct list_head *tmp = curr->next;
            list_del(curr);
            list_add(curr, tmp);
        }
    }
    // https://leetcode.com/problems/swap-nodes-in-pairs/
}

q_reverse

首先先確認 head 是否存在或是只有一個以下的元素，若為上述情況則直接跳出該程式。接著先定義三個指向 list_head 的指標變數，分別是 prev 指向 head->prev ， curr 指向 head ， next 指向 head->next 。接著是將 curr->next 指向 prev ，curr->prev 指向 next 。並一起跳至下一個元素，直到 curr 再次與 head 重疊，代表已經反轉完畢，結束並返回。

  • 以下為完整的程式碼：
void q_reverse(struct list_head *head)
{
    if(!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *prev = head->prev;
    struct list_head *curr = head;
    struct list_head *next = head->next;
    do{
        curr->next = prev;
        curr->prev = next;
        prev = curr;
        curr = next;
        next = next->next;
    } while(curr != head);
}

q_sort

以下將分成 q_sort 原函式， merge_sort 真正的實做部份以及 find_mid 回傳該佇列的中間點。

  • 以下為完整的程式碼：

q_sort

先判斷傳入的 head 是否存在，若不存在則跳出函式。反之則將 head 拿出該佇列。並將剩下的佇列傳入 merge_sort 。

void q_sort(struct list_head *head)
{
    if (head == NULL)
        return;
    struct list_head *new_head = head->next;
    list_del(head);
    new_head = merge_sort(new_head);
    list_add_tail(head, new_head);
}

merge_sort

先確認是否只剩下一個節點，若為真則直接回傳自己。接著利用 find_mid 找出中間的節點，並將兩個佇列分離並各自形成一個環狀雙向佇列，並遞迴呼叫 merge_sort ，直到 left 與 right 都各自只剩下一個節點而已。接著開始進行接合，先將本身的 prev 的 next 指向 NULL ，並定義一個 tmp 指向 NULL ，接著若 left 以及 right 至少存在一個(代表可以進入迴圈)，則開始進行比較。若只有 left 存在或是 left 的字串比 right 的字串小，則將 left 的元素置入新的佇列中。若 tmp == NULL ，則代表佇列尚未建立，須將 new_head 指向這新的原點。反之則直接加入即可。最後若 right 以及 left 皆指向 NULL ，則代表已經接合完畢，回傳 new_head 即可。

struct list_head *merge_sort(struct list_head *new_head)
{
    if (new_head == new_head->next)
        return new_head;

    struct list_head *left = new_head;
    struct list_head *right = find_mid(new_head);

    if (list_is_singular(left)) {
        list_del_init(left);
        list_del_init(right);
    } else {
        right->prev->next = left;
        left->prev->next = right;
        struct list_head *tp = left->prev;
        left->prev = right->prev;
        right->prev = tp;
    }

    left = merge_sort(left);
    right = merge_sort(right);
    left->prev->next = NULL;
    right->prev->next = NULL;

    for (struct list_head *tmp = NULL; left || right;) {
        if (!right ||
            (left &&
             ((strcmp(list_entry(left, element_t, list)->value,
                      list_entry(right, element_t, list)->value)) < 0))) {
            if (!tmp) {
                tmp = new_head = left;
                left = left->next;
                if (left != NULL) {
                    left->prev = tmp->prev;
                }
                INIT_LIST_HEAD(tmp);
            } else {
                tmp = left;
                left = left->next;
                if (left != NULL) {
                    left->prev = tmp->prev;
                }
                list_add_tail(tmp, new_head);
            }
        } else {
            if (!tmp) {
                tmp = new_head = right;
                right = right->next;
                if (right != NULL) {
                    right->prev = tmp->prev;
                }
                INIT_LIST_HEAD(tmp);
            } else {
                tmp = right;
                right = right->next;
                if (right != NULL) {
                    right->prev = tmp->prev;
                }
                list_add_tail(tmp, new_head);
            }
        }
    }
    return new_head;
}

find_mid

先利用指標指向 head 與 head->next，接著各自向前與向後一步，直到兩者重疊或是相鄰，再回傳該指標即可。

struct list_head *find_mid(struct list_head *head)
{
    struct list_head *forw = head, *back = head->prev;
    while (forw != back && forw->next != back) {
        forw = forw->next;
        back = back->prev;
    }
    return back;
}

終於完成了～

qtest實做新命令：shuffle

先打開 qtest.c 並依照 lab-0 實做 do_hello 後，可以成功出現 Hello World 的訊息。

trace code

先打開 qtest.c 檔後，進入 main() 主程式找到 run_console(infile_name) 後，會發現 run_console() 這函式是位於 console.c 的檔案中。打開 console.c 後，找到 run_console 的函式，發現它傳入的引數為 infile_name ，我認為應該是傳入的檔案名稱。進入 run_console 後，會檢查是否有 has_infile ，若有則會進入 else 的區域，且會持續執行 cmd_select() 直到 cmd_done() 為止。

以下為 run_console 的程式碼：

bool run_console(char *infile_name)
{
    if (!push_file(infile_name)) {
        report(1, "ERROR: Could not open source file '%s'", infile_name);
        return false;
    }

    if (!has_infile) {
        char *cmdline;
        while ((cmdline = linenoise(prompt)) != NULL) {
            interpret_cmd(cmdline);
            linenoiseHistoryAdd(cmdline);       /* Add to the history. */
            linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
            linenoiseFree(cmdline);
        }
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }

    return err_cnt == 0;
}

接著也可以在 console.c 找到 cmd_select() ，在該函式中找到 /* Commandline input available */ 的註解。下面還有 if(has_infile) ，進入之後還有 cmdline = reeadline() 和 interpret_cmd(cmdline) ，我認為這應該是確認是否有輸入指令，若指令存在則開始進行翻譯的動作。

以下為 cmd_select() 部份的程式碼：

if (readfds && FD_ISSET(infd, readfds)) {
    /* Commandline input available */
    FD_CLR(infd, readfds);
    result--;
    if (has_infile) {
        char *cmdline;
        cmdline = readline();
        if (cmdline)
            interpret_cmd(cmdline);
    }
}

找到 interpret_cmd() 後，可以看到其中有 parse_args(cmdline, &argc); 與 bool ok = interpret_cmda(argc, argv);，我認為這兩個函式應該是先解析出共有幾個指令並且傳送出指向指令的位址。

以下為 interpret_cmd() 的程式瑪：

static bool interpret_cmd(char *cmdline)
{
    if (quit_flag)
        return false;

#if RPT >= 6
    report(6, "Interpreting command '%s'\n", cmdline);
#endif
    int argc;
    char **argv = parse_args(cmdline, &argc);
    bool ok = interpret_cmda(argc, argv);
    for (int i = 0; i < argc; i++)
        free_string(argv[i]);
    free_array(argv, argc, sizeof(char *));

    return ok;
}

接著找到 interpret_cmda() 的函式，其中會有 cmd_ptr 指向所有的指令，經過 while 迴圈一直尋找相同指令後，最後再進入該 next_cmd 的 operation 。執行相對應的指令動作，若沒有找到該指令則會印出 report(1, "Unknown command '%s'", argv[0]); ，印出剛剛輸入的指令名稱。

以下為 interpret_cmda() 的程式碼：

static bool interpret_cmda(int argc, char *argv[])
{
    if (argc == 0)
        return true;
    /* Try to find matching command */
    cmd_ptr next_cmd = cmd_list;
    bool ok = true;
    while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
        next_cmd = next_cmd->next;
    if (next_cmd) {
        ok = next_cmd->operation(argc, argv);
        if (!ok)
            record_error();
    } else {
        report(1, "Unknown command '%s'", argv[0]);
        record_error();
        ok = false;
    }

    return ok;
}

當輸入不存在的指令時（輸入 wrong 為指令）：

在大致了解程式運作流程後，為了增加 shuffle 的指令，我們必須先在 console_init() 中加入該程式碼:

add_cmd("shuffle", do_shuffle, "                | Shuffle every node on the list");

這樣在輸入 shuffle 該指令時便系統會自動去尋找 do_shuffle() 的函式，因此我們還需要在 qtest.c 中加入 do_shuffle() 的函式。

以下為 do_shuffle() 的完整程式碼：

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!l_meta.l) {
        report(3, "Warning: Try to access null queue");
        return false;
    }
    error_check();

    bool ok = false;
    set_noallocate_mode(true);
    if (exception_setup(true)) {
        ok = q_shuffle(l_meta.l);
    }
    exception_cancel();

    set_noallocate_mode(false);

    show_queue(3);
    return ok && !error_check();
}

程式碼中的前兩個判斷式是我複製檔案中其他函式的。第一個是確定傳入的引述個數只有一個，第二個是確認該佇列不是指向 NULL 。接著開始進行 q_shuffle() 的函式， shuffle() 完成後再使用 show_queue() 依序展現每個節點。

以下為 q_shuffle() 的完整程式碼：

bool q_shuffle(struct list_head *head)
{
    if (head == NULL)
        return false;

    if (list_empty(head))
        return true;

    if (list_is_singular(head))
        return true;

    int n = q_size(head);
    struct list_head *sorted = head->prev;
    struct list_head *to_swap = sorted;
    struct list_head *tmp = NULL;
    srand(time(NULL));
    for (; n > 1; n--) {
        int to_sort = rand() % (n - 1) + 1;
        for (int i = 0; i < to_sort; i++) {
            to_swap = to_swap->prev;
        }
        tmp = sorted->next;
        list_del(sorted);
        list_add_tail(sorted, to_swap);
        list_del(to_swap);
        list_add_tail(to_swap, tmp);
        to_swap = to_swap->prev;
        sorted = to_swap;
        to_swap = to_swap->prev;
        to_swap = sorted;
    }
    return true;
}

先確認傳入的佇列不是空節點或是只有一個以下的節點，接著找出佇列的節點數量。並依照 Fisher-Yates Shuffle 的方法先使用一個指標分開已經洗完牌與尚未洗牌的節點。接著隨機尋找要交換的節點，再使用 Linux 的內建的 API 實現交換的過程，最後回傳 true 。

測試結果

成功！！

利用 Valgrind 檢查記憶體

在終端機輸入 make valgrind 後，系統跳出了非常多的錯誤，且幾乎都是 still reachable 的情況。

先試著 valgrind ./qtest ，並沒有發現任何錯誤。
接著試著測試每個測試檔是否有記憶體的問題：

trace1

輸入 valgrind ./qtest -f ./traces/trace-01-ops.cmd 後，會出現三個問題，皆為 still reachable 的情況，且皆來自 linenoiseHistoryAdd 的函式。

以下為 linenoiseHistoryAdd 的原始程式碼： 

































int linenoiseHistoryAdd(const char *line)
{
    char *linecopy;

    if (history_max_len == 0)
        return 0;

    /* Initialization on first call. */
    if (history == NULL) {
        history = malloc(sizeof(char *) * history_max_len);
        if (history == NULL)
            return 0;
        memset(history, 0, (sizeof(char *) * history_max_len));
    }

    /* Don't add duplicated lines. */
    if (history_len && !strcmp(history[history_len - 1], line))
        return 0;

    /* Add an heap allocated copy of the line in the history.
     * If we reached the max length, remove the older line. */
    linecopy = strdup(line);
    if (!linecopy)
        return 0;
    if (history_len == history_max_len) {
        free(history[0]);
        memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
        history_len--;
    }
    history[history_len] = linecopy;
    history_len++;
    return 1;
}

可以看到在 1224 行的 strdup 與 1236 行的 malloc 皆有 still reachable 的情況。我想應該是因為在配置繼體後使用完畢沒有釋放造成的，因此我在程式 history_len++ 後方加上釋放記憶體的動作。

更改後的程式碼：








    history_len++;
    free(linecopy);
    for(int i = 0; i < history_len; i++){
        free(*history + i);
    }
    free(history);
    return 1;

執行結果：

引用Linux核心原始程式碼之 lib/list_sort.c

原始程式碼之效能：
新建一個 trace-time.cmd 檔，隨機插入 300000 個元素，以測試 sort 的效能。

option fail 0
option malloc 0
new
ih RAND 300000
time
sort
time

以自己撰寫的 q_sort.c 實測排序的效能，在終端機輸入 make check 可以得出排序的時間約為 0.263 秒。

Last changed by 
 
StevenChou43
0
644

Read more

Ring buffer 期末報告

contributed by < StevenChou499 > 進行 第 12 週測驗題第二題的延伸問題。過程中參照第 13 週測驗題第一/二題，嘗試開發出高效的 ring buffer。 相關資訊：[ ] ringbuffer 報告 [ ] Super Fast Circular Ring Buffer Using Virtual Memory trick [ ] Using black magic to make a fast circular buffer [ ] linear_ringbuffer/include/bev/linear_ringbuffer.hpp [ ] wuffs/script/mmap-ring-buffer.c

Feb 2, 2024
數位 IC 設計

ModelSim 在終端機使用方法 vlib <name> : 建立名為 name 的設計函式庫。 vlog <files> : 使用 ModelSim 編譯所有 files 的檔案。 vsim <top_level_module> : 使用 ModelSim 開啟編譯完成的檔案。 在 ModelSim 中輸入 run -all : 使用 vsim 開啟檔案後，輸入 run -all 可以執行模擬。 以下為範例 : PS C:\Users\StevenChou\Desktop\Verilog_practice\Chp5\Q3> vlib work ** Warning: (vlib-34) Library already exists at "work".

May 2, 2023
HW4 ATCONV

第一個成功版本 程式碼 : `timescale 1ns/10ps module ATCONV( input clk, input reset, output reg busy, input ready,

May 1, 2023
HDLBits 習題

HDLBits 連結 : https://hdlbits.01xz.net/wiki/Main_Page

Apr 19, 2023
Read more from StevenChou43
Published on HackMD