# 2025q1 Homework1 (lab0)
contributed by < `Jackiempty` >

### Reviewed by `jimmy01240397`
1. 善用巨集展開以減少重複的程式碼，例如：

    #define q_remove_base(head, sp, bufsize, from)                          \
        if (!head || list_empty(head))                                      \
            return NULL;                                                    \
        element_t *rm_element = list_##from##_entry(head, element_t, list); \
        if (sp) {                                                           \
            strncpy(sp, rm_element->value, bufsize - 1);                    \
            sp[bufsize - 1] = '\0';                                         \
        }                                                                   \
        list_del(head->next);                                               \
        return rm_element;

    element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
    {
        q_remove_base(head, sp, bufsize, first);
    }

    element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
    {
        q_remove_base(head, sp, bufsize, last);
    }

- q_remove_head
- q_remove_tail
2. [q_delete_dup](#q_delete_dup)：可使用變數儲存比較結果來減少多餘的分支

-   bool is_dup = false;
+   bool is_dup = false, now_dup = false;

+       now_dup = c->list.next != head &&
+                 memcmp(c->value, n->value, len) == 0;
+       if (now_dup || is_dup) {
-       if (c->list.next != head &&
-           memcmp(c->value, n->value, len) == 0)
-       {
            list_del(&c->list);  // delete node
            q_release_element(c);
+           is_dup = now_dup;
-           is_dup = true;
-       } else if (is_dup) {
-           list_del(&c->list);
-           q_release_element(c);
-           is_dup = false;
        }

> 量化分析上述更動到底可省下多少次分支，工程人員說話要有證據。 :notes: jserv

## 開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:           aarch64
  CPU op-mode(s):       64-bit
  Byte Order:           Little Endian
CPU(s):                 4
  On-line CPU(s) list:  0-3
Vendor ID:              Apple
  Model name:           -
    Model:              0
    Thread(s) per core: 1
    Core(s) per socket: 4
    Socket(s):          1
    Stepping:           0x0
    BogoMIPS:           48.00

## 在開始前發現的問題
我在寫的過程中發生了一件事，那就是即便我已經做了 clang-format 的校正，以及單獨用 cppcheck 做了靜態測試，卻還是在提交 commit 時跳出了 Failed to pass static analysis

information: valueflow analysis is limited in log2_lshift16. use --check-level=exhaustive if full analysis is wanted. [checklevelnormal]

於是我和同學討論可能的原因並互相比對 cppcheck 的版本後，發現同學的是 2.7 版，而我的則是 2.11 版，且看見了 lab0 的 commit message: `Fix cppcheck failed since after version 2.9
`，猜測有可能又是 cppcheck 版本的問題後，在重新安裝 cppcheck 至 2.7 版，就沒有再發生了。

## 指定的佇列操作
我將單純照著原始碼底下排列的順序做修改
### `q_new`
先說我一開始的做法，由於我是在一知半解的情況下跌跌撞撞地開始寫這份作業，所以在我看到註解中對於這個函式的說明之後我當下馬上想到的作法如下：

struct list_head *q_new()
{
    struct list_head *new_q = malloc(sizeof(struct list_head));
    if (!new_q){
        free(new_q);
        return NULL;
    }
    new_q->prev = new_q;
    new_q->next = new_q;
    return new_q;       
}

:::danger
command 的翻譯是「命令」，而非「指令」(instruction)
:::

然後我就很不爭氣地去看了<s>歷屆同學們</s> 的實作方式看看我的想法有沒有問題，不出意外我馬上注意到`INIT_LIST_HEAD(list_head)`這個函式的存在，並使用`grep` <s>指令</s> 命令找到了這段：

:::danger
列出你參照過的 GitHub 帳號名稱。
:::

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

原來將頭尾的指標指向自身的功能居然是用另一個函式實作，於是我調整程式碼如下：
> commit [6a92331](https://https://github.com/Jackiempty/lab0-c/commit/6a92331c07562a9e3ca815a00ccf07def6b7d05e)

struct list_head *q_new()
{
-   struct list_head *new_q = melloc(sizeof(list_head));
-   if (!new_q) {
-       free(new_q);
+   struct list_head *head = malloc(sizeof(struct list_head));
+   if (!head) {
+       free(head);
        return NULL;
    }
-   INIT_LIST_HEAD(new_q);
+   INIT_LIST_HEAD(head);

-   return new_q;
+   return head;
}

修改的有以下三點
* 將`sizeof()`裡面的資料型態加上宣告
* 使用`INIT_LIST_HEAD()`
* 原本的將變數名稱有點誤用，將其更正為比較沒有爭議的`head`

### `q_free`
在一開始，我並不知道`list_for_each_safe`的存在，所以差點自身從頭寫一個語法非常初級的 for 迴圈去逐一 free 整個佇列的記憶體

:::danger
列出你參照過的 GitHub 帳號名稱。
:::

好在我會<s>參考古聖先賢</s> ，在得知的`list_for_each_safe`的存在之後，便只需要處理兩種例外，剩下的都可以交由這個函式解決

說到兩種例外，這兩種例外分別是：
* list 是壞掉的狀態
* list 是空的狀態

面對這兩種狀態，我使出了在 Linus 口中沒有品味的解決方法：if 判斷式
[d3f63ac](https://https://github.com/Jackiempty/lab0-c/commit/d3f63ac8fd9355ed6a6013e1e111b75376be7483)

{
    if (!l)
        return;
+   if (list_empty(l)) {
+       free(l);
+       return;
+   }   
    struct list_head *c, *n;
+   c = NULL;
+   n = NULL;
-   list_for_each_safe (c, n, l, list) {
-       list_del(&c->list);
-       q_release_element(c);
+   list_for_each_safe (c, n, head) {
+       element_t *e = container_of(c, element_t, list);
+       free(e->value);
+       free(e);
    }
    
    free(l);  // q_new function has malloced it
+   return;
}

在今年的測試中

### q_insert_head()

:::danger
列出你參照過的 GitHub 帳號名稱。
:::

我觀摩 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_insert_head-%E5%92%8C-q_insert_tail-%E5%AF%A6%E4%BD%9C) 和 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_insert_head) 的兩種實作方式，由於在這個函式裡面後要 construct 出新的節點，所以有同學將建構節點的功能獨立出來寫成一個函式，並且可以在不同個需要建構節點的其他函式中重複使用；同時，也有同學為了整體架構的乾淨簡潔，選擇將建構節點的功能嵌入在每個獨立的函式裡面，雖然這樣會寫到重複的程式碼，卻能夠避免標頭檔函式組成的更動。而我個人也是偏好後者，所以會採取後者的做法。

最後，在實作的部分，我所參考的寫法是這個：

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));    // new head element
    if(!new_element)   // If allocate failed
        return false;
    size_t len = strlen(s) + 1; // plus 1 for `\0`
    new_element->value = malloc(len * sizeof(char));
    if (!new_element->value) {   // If allocate failed
        free(new_element);
        return false;
    }
-   memcpy(new_element->value, s, len);
+   for (int i = 0; i <= len; i++) // when i == len, the char is \0
+       *(new_element->value + i) = *(s + i);
    list_add(&new_element->list, head);
    return true;
}

我先是將`memcpy()`的功能以<s>更白話</s> 的方式寫了出來，希望能藉由不直接使用既有的函式來增加可閱讀性。

:::danger
何謂「更白話」？與前後文的關聯在哪？
:::

然而，上次的評論中老師說不要使用 `memcpy()` 來實作複製內容的功能，於是那位同學變將多個功能像是計算 `len` 還有手動 `malloc` 記憶體的空間以及複製值的功能全部整合進 `strdup()`，而既然 `strdup()` 是同個專案裡面的函式，並且還將那麼多功能都整合進去了，沒有不用的理由，所以我後來也選擇使用 `strdup()` 來使程式碼更精練。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));    // new head element
    if(!new_element)   // If allocate failed
        return false;
-   size_t len = strlen(s) + 1; // plus 1 for `\0`
-   new_element->value = malloc(len * sizeof(char));
+   new_element->value = strdup(s);
    if (!new_element->value) {   // If allocate failed
        free(new_element);
        return false;
    }
-   for (int i = 0; i <= len; i++)
-       *(new_element->value + i) = *(s + i);
    list_add(&new_element->list, head);
    return true;
}

### q_insert_tail()
在一開始我選擇直接從 `q_insert_head()`複製整段的程式碼過來只修改最後一行：

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));    // new head element
    if(!new_element)   // If allocate failed
        return false;

    new_element->value = strdup(s);
    if (!new_element->value) {   // If allocate failed
        free(new_element);
        return false;
    }

    list_add_tail(&new_element->list, head);
    return true;
}

然後我就在 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_insert_tail)底下的老師評論中看見老師的提醒，所以變使用了同樣的手法，既然功能都和`q_insert_head()`雷同，何不直接使用它來完成這個函式。當然，要能夠區別這兩者的差別，就得要修改函式所使用的引數。

關於這點，由於這個專案所使用的`linked list`是以頭尾相連的方式實作的，所以技術上我只要調換`q_insert_head()`的引數，將其換成 `head->prev`就可以巧妙地讓本該完成在佇列頭部的工作套用在尾部上。

bool q_insert_head(struct list_head *head, char *s)
{
-   if (!head)
-   ......
-   return true;
+   return q_insert_head(head->prev, s);
}

像這樣

:::danger
明確列出參考的 GitHub 帳號名稱
:::

另外，我發現<s>我所參考的對象</s> 他在使用`q_insert_head()`之前保留了`if (!head){return false;}`，但其實這個功能在`q_insert_head()`裡面就有了，只要`head`是壞掉的，不用在外面先排除，到內部函式裡面照樣會回傳我們本要回傳的`false`，所以我就不多此一舉了。

### `q_remove_head`

:::danger
不理解就說不理解，不要不懂裝懂，沒有「不太懂」這回事。
:::

關於這題，我很慚愧地說在沒有參考來源的情況下，我沒有頭緒，我<s>不太理解</s> 為什麼這個函式的參數裡面會有` bufsize`，在將節點從佇列移出的過程中，我不理解為什麼會需要一個 buffer，自然就不了解 `bufsize` 的功能為何。

所以我看了一下 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_remove_head)的程式碼：

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *rm_element = container_of(head->next, element_t, list);
    if (sp) {
        strncpy(sp, rm_element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(head->next);
    return rm_element;
}

從他的程式碼中，我看出幾件事情
1. sp 是用來裝原本佇列中節點的`value`的
2. `bufsize`是該節點的`value`的尺寸
3. `bufsize`會在使用`q_remove_head`的另外一個函式中先算好再傳進去

第三點是因為看見`qtest.c`中的`string_length`，是使用者可以自訂的，不然就是在`queue.c`裡面預設為`max_buffer_size`

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)。

留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。
:::

### q_remove_tail()
同`q_remove_head()`，唯獨將原本傳入值為`head`的部分改成跟`tail`有關：

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head || list_empty(head))
        return NULL;
    element_t *rm_element = list_last_entry(head, element_t, list);
    if(sp) {
        strncpy(sp, rm_element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(head->prev);
    return rm_element;
}

另外，我發現就算將 sp 的判斷移到上面的 if 條件式也過得了測資，雖然在標頭檔裡面只有註明說如果 sp 非 NULL 的情況下就將要被移除的節點值給放進去，但我不確定的是這段程式的初衷有沒有包含如果 sp 是 NULL 的情況下需不需要報錯。

由於測試資料沒有 sp 是 NULL 的情況讓我驗證，所以我只能以我的理解去實作這部分的判斷，最後我決定維持讓 sp 是 NULL 的情況下不回傳 NULL，並讓它正常移除節點，雖然我覺得移到上面比較好看。

如果 sp 的判斷式上移（e.g., `q_remove_tail`）：

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
-   if(!head || list_empty(head))
+   if(!sp || !head || list_empty(head))
        return NULL;
    element_t *rm_element = list_last_entry(head, element_t, list);
-   if(sp) {
-       strncpy(sp, rm_element->value, bufsize - 1);
-       sp[bufsize - 1] = '\0';
-   }
+   strncpy(sp, rm_element->value, bufsize - 1);
+   sp[bufsize - 1] = '\0';
    list_del(head->prev);
    return rm_element;
}

### q_delete_mid()
我參考了兩種實作方式，分別為：
1. [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_delete_mid-%E5%AF%A6%E4%BD%9C)：同時從頭開始，讓兩個 local 變數分別用不同速度從頭開始跑，當比較快的跑到底時，比較慢的就會是在中間，就可以對移動較慢的變數指標操作
2. [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_delete_mid)：分別從頭尾開始，以同樣速率向中間靠齊，當兩者重疊時重疊的那個點就是中間的了

而我選擇了後者：
:::danger
列出你的考量因素，你如何做這樣的決策？你的洞見又在哪？
:::

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
-   struct list_head *tail = head->prev, *fast = head->next, *slow = fast;
-   while (fast != tail && fast->next != tail) {
-       fast = fast->next->next;
-       slow = slow->next;
-   }
-   list_del(slow);
-   q_release_element(container_of(slow, element_t, list));
+   struct list_head *n = head->next;
+   for(struct list_head *p = head->prev; n->next != p && n != p; ) {
+       n = n->next;
+       p = p->prev;
+   }
+   list_del(n);
+   q_release_element(container_of(n, element_t, list));
    return true;
}

### q_delete_dup()

這個函式我參考 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_delete_dup-%E5%AF%A6%E4%BD%9C) 並針對他所得到的建議進行了調整，拿掉`strcmp`並用`strlen`和`memcmp`取代，目前看起來功能是沒有損失的。

bool q_delete_dup(struct list_head *head)
{
  if (!head)
        return false;
    struct list_head *cur = head->next;
    while (cur != head) {
        if (cur->next != head) {
            struct list_head *safe = cur->next;
            element_t *c = container_of(cur, element_t, list),
                      *n = container_of(cur->next, element_t, list);
            if (!strcmp(c->value, n->value)) {
                do {
                    struct list_head *next = n->list.next;
                    list_del(&n->list);
                    q_release_element(n);
                    if (next == head)
                        break;
                    n = container_of(next, element_t, list);
                } while (!strcmp(c->value, n->value));
                safe = cur->next;
                list_del(&c->list);
                q_release_element(c);
            }
            cur = safe;
        }
    }
    return true;
}

### q_swap()

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *n = head->next;
    while (n != head && n->next != head) {
        struct list_head *t = n;
        list_move(n, t->next);
        n = n->next;
    }
}

原本也是想要自己宣告一堆 local variables 硬幹，但參考 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_swap) 後發現 list API 很好用，所以就照用了。
### q_reverse()
參考 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_reverse) 的方法，非常直觀簡潔

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *n, *s, *t;
    list_for_each_safe (n, s, head) {
        t = n->next;
        n->next = n->prev;
        n->prev = t;
    }
    t = head->next;
    head->next = head->prev;
    head->prev = t;
}

### q_reversek
參考 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_reverseK) 使用內建的`list_cut_position()`和`list_splice_init()`來實作，<s>我覺得很聰明</s>。

:::danger
工程人員說話要精準，當你發現好的做法，要說出其好在哪？是否有副作用 (side effect) 呢？你是否可做更好？
:::

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;
    struct list_head *n, *s, iter, *tmp_head = head;
    int i = 0;
    INIT_LIST_HEAD(&iter);
    list_for_each_safe (n, s, head) {
        i++;
        if (i == k) {
            list_cut_position(&iter, tmp_head, n);
            q_reverse(&iter);
            list_splice_init(&iter, tmp_head);
            i = 0;
            tmp_head = s->prev;
        }
    }
}

### q_sort
參考 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_sort) 並改進程式碼外觀，並且加上當初沒有的 `descend` 參數來決定排序的升降。

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return;
    // disconnect the circular structure
    head->prev->next = NULL;
    head->next = merge_recur(head->next);
    if (!descend) {
        // reconnect the list (prev and circular)
        struct list_head *c = head, *n = head->next;
        while (n) {
            n->prev = c;
            c = n;
            n = n->next;
        }
        c->next = head;
        head->prev = c;
    } else {
        struct list_head *c = head, *n = head->next, *b = head->next->next;
        while (b) {
            n->next = c;
            n->prev = b;
            c = n;
            n = b;
            b = b->next;
        }
        n->next = c;
        n->prev = head;
        head->next = n;
    }
}

// local function implementation
struct list_head *merge_two_list(struct list_head *left,
                                 struct list_head *right)
{
    struct list_head head;
    struct list_head *h = &head;
    if (!left && !right) {
        return NULL;
    }
    while (left && right) {
        if (strcmp(list_entry(left, element_t, list)->value,
                   list_entry(right, element_t, list)->value) <= 0) {
            h->next = left;
            left = left->next;
            h = h->next;
        } else {
            h->next = right;
            right = right->next;
            h = h->next;
        }
    }
    // after merge, there are still one node still not connect yet
    h->next = left ? left : right;
    return head.next;
}

struct list_head *merge_recur(struct list_head *head)
{
    if (!head->next)
        return head;

    struct list_head *slow = head;
    // split list
    for (struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next) {
        slow = slow->next;
    }

    struct list_head *mid = slow->next;  // the start node of right part
    slow->next = NULL;

    struct list_head *left = merge_recur(head);
    struct list_head *right = merge_recur(mid);

    return merge_two_list(left, right);
}

### q_ascend/q_descend
這邊也是直接參考 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_descend) 的實作方式。有趣的是，由於這次多了 ascend 的功能，於是我是將其 descend 的功能中的所有 `prev` 和 `next` 對調達成了 ascend 的功能，並且是確定可以執行的。

int q_ascend(struct list_head *head)
{
    if (!head)
        return 0;
    struct list_head *c = head->next;
    element_t *c_ele = list_entry(c, element_t, List);
    while (c_ele->list.next != head) {
        element_t *n_ele = list_entry(c_ele-›list.next, element_t, list);
        if （strcmp（n_ele->value,C_ele->value） <0）｛
            list_del(&n_ele-›list);
            q_release_elementn_ele);
        } else {
            c_ele = n_ele;
        ｝
    ｝
    return q_size(head);
}

接著來到`q_descend`的部分，這部分我原本以為可以像`reversek`那邊一樣在裡面使用`ascend`之後再反轉就可以達到`descend`的效果。然而，經過一番嘗試之後，我發現了以下問題：
* 我如果用寫好的 ascend 實作 descend 會跑不過測資 6
* 反過來如果用寫好的 descend 實作 ascend 就過得了測資 6
* 藉由`grep 'ascend' ./traces/`命令找不到東西可知測資中沒有測試到 ascend 功能

由以上發現可以推論幾件事情：
* 由於兩函式都是藉由將節點和右邊的節點比較後移除，所以無法透過`reverse`來達到用一個函式實作另一個函式的功能，因為會刪到相反邊的節點
* ascend 沒有測資，有可能在功能不正確的情況下通過`make test`

### q_merge
運用上次實作好的 `sort` 來實作這次的`merge`，並搭配在 qtest 裡的呼叫方式做前後處理。

/* Merge all the queues into one sorted queue, which is in ascending/descending
 * order */
int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;
    queue_contex_t *fir = container_of(head->next, queue_contex_t, chain);
    if (head->next == head->prev)
        return fir->size;
    for (struct list_head *cur = head->next->next; cur != head;
         cur = cur->next) {
        queue_contex_t *que = container_of(cur, queue_contex_t, chain);
        list_splice_init(que->q, fir->q);
        que->size = 0;
    }
    q_sort(fir->q, descend);
    fir->size = q_size(fir->q);
    return fir->size;
}

### Valgrind 測試結果
到目前為止，make test 已經可以達到 95/100 了，剩下的第 17 個測試要去修改 dutect 才能通過，在此先跳過。接著，我用 Valgrind 去做動態測試，看有沒有雖然功能有通過測試但卻存在著邏輯和記憶體管理漏洞的地方，而就在我測到第 14 和 16 時出現了以下訊息：

ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient

這很奇怪，照理來說同一個功能都已經通過其他測資的 valgrind 測試了，沒道理到這邊會突然壞掉。

讓我們先來看看測試的內容為何：

# Test performance of insert_tail, reverse, and sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
reverse
sort

由於壞掉的斷點是發生在`new`完之後的`ih dolphin 1000000`，隨後便跳出許多 memory leak 的錯誤訊息。看到一百萬這個數字和`Time limit exceeded`的錯誤訊息，我不由得地想到會不會是執行一百萬次導致時間太長被系統認定為 runtime error，所以我就將測資修改了一下，將原本的一百萬一口氣降到一萬，隨後再執行一次 valgrind 測試，而這次就有通過。

看來我的推測沒有錯，於是我便開始來回測試他大概要多少的資料才不會觸發 runtime error，而我最後測出來的數據為：
* ih/it: 180000/170000
* reverse/sort: 140000

這離測資所要求的 1000000 還有一段距離，我不確定這是有意的還是測試以外的內容，因為如果這是有意的話我勢必得要去修改上述幾個函式使其效率提升才能通過 runtime pass，若這並不在原本測試的範圍的話，實際上 make test 是有辦法通過的，所以 valgrind 的測試問題可以忽略，而我決定相信後者，畢竟 valgrind 只是一個除錯工具而已，並不是一個我們要通過的測試。

### 目前分數：`95/100`
時間複雜度無法通過，應研究 論文 後改進 dudect 。
評分 95/100。

## 研讀論文並改進 dudect
雖然說作業要求只要我們修改`queue.[ch]`，但要解決第 17 筆測試要去修改`dudect`的檔案內容，並搭配研讀論文〈Dude, is my code constant time?〉，引用論文內容改進程式碼，使其通過第 17 筆測試案例。

:::danger
明確列出你參照的 GitHub 帳號名稱。
:::

在<s>讀了一些同學的筆記</s> 之後，我瞭解了幾件事情：
* dudect 也是研讀了上述論文所實作出來的專案
* dudect 檔案的參考源是一個時間檢查工具，[原始連結在這](https://github.com/oreparaz/dudect/blob/master/src/dudect.h)
* lab0 專案裡面的 dudect 有一部分的缺失要由我們去補足，才能通過 make test

我直接找出了兩者程式碼的相同處，並把 lab0 缺失的部分補足，並順利通過 make test

### to do:
* ~~ascend/descend 測資有缺陷~~
* swap：指標的指標 vs list_move() 效率
* ~~Valgrind test 14 & 16 有問題~~
* merge：先 merge 再 sort vs 用 merge_list 效率

## 在 qtest 提供新的命令 `shuffle`

在這個部分要做兩件事情：
* 加入 shuffle 的 qtest API
* 實作 shuffle

### **qtest API**

透過觀察其它的 command 實作方式我們可以發現 qtest 裡面的 command 主要是由幾個要素所組成：

* `console init`裡面的`ADD_COMMAND`
* 由`do_##cmd`來展該函式名稱並辨識`qtest.c`裡面的函式

第二點可以由位於`console.h`的巨集得知：

#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)

後續的`do_shuffle`是參考了 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#%E5%9C%A8%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E4%B8%AD%E6%96%B0%E5%A2%9E%E5%91%BD%E4%BB%A4-shuffle) 的 handler

void q_shuffle(struct list_head *head);

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

    if (!current || !current->q)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();

    if (exception_setup(true))
        q_shuffle(current->q);
    exception_cancel();

    set_noallocate_mode(false);

    q_show(3);
    return !error_check();
}

### **實作 shuffle**

由於`queue.h` 是無法編輯的，所以無法像其他的函式一樣先在`queue.h`定義完之後再實作在`queue.c`，於是就要作在`qtest.c`裡面

最一開始的實作方式是想實作[作業說明](https://hackmd.io/@sysprog/linux2024-lab0-d#%E5%9C%A8-qtest-%E6%8F%90%E4%BE%9B%E6%96%B0%E7%9A%84%E5%91%BD%E4%BB%A4-shuffle)裡所解釋的方法，也就是 Fisher–Yates shuffle 裡面的 [Modern method](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modern_method)，但嘗試了幾次之後都是失敗的，結果要不是會記憶體操作錯誤不然就是 shuffle 出來的結果並沒有徹底打亂，會有固定位置的字元不會被操作到，以下分享兩個失敗的例子：

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    int size = q_size(head);
    // shuffle
    for (int i = 1; i < size;) {  // not iterate i , iterate size
        struct list_head *start = head->next;
        int rand_idx = rand() % size;  // random number in range 0~ (size-1)
        for (int j = 0; j < rand_idx; j++) {
            start = start->next;
        }
        struct list_head *end = head->prev;
        list_del(end);
        end->next = start->next;
        end->prev = start->prev;
        list_move_tail(start, head);
        end->prev->next = end;
        end->next->prev = end;
        size--;
    }
    return;
}

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    int size = q_size(head);
    // shuffle
    for (int i = 1; i < size;) {  // not iterate i , iterate size
        struct list_head *start = head->next;
        int rand_idx = rand() % size;  // random number in range 0~ (size-1)
        for (int j = 1; j < rand_idx; j++) {
            start = start->next;
        }
        struct list_head *next = start->next, *prev = start->prev;
        struct list_head *end = mov_end;
        mov_end = mov_end->prev;
        list_del(end);
        list_move_tail(start, head);
        end->next = next;
        end->prev = prev;
        end->prev->next = end;
        end->next->prev = end;
        size--;
    }
    return;
}

:::danger
何謂「連結佇列」？工程人員說話要精準。
用字要精準，你仍未改好。
:::

乍看下邏輯好像沒有什麼問題，但實際逐行將數字帶進去手算之後，發現由於<s>連結串列</s> 雙向鏈結串列的特性，在做被抽到的節點與尾部的節點交換的時候，我必須要用一個變數紀錄從後面開始往前走訪的尾部節點，而這個變數會在該迴圈時前後連結的節點資訊被紀錄之後就繼續往下一個節點前進

:::danger
改進你的漢語表達。
:::

問題就是出在這裡，由於被它在進行交換前所紀錄的節點有可能是該次迴圈被抽到要去跟尾部交換的節點，所以這個要走訪尾部節點的變數就會錯誤地指向被交換到的最尾端的位置，而不是應該所要在的還沒被交換過的尾部位置，進而導致錯誤

解決的方法也很簡單，在 Fisher–Yates shuffle 裡面除了有 Modern method 以外也有一個方法叫 [Pencil-and-paper method](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Pencil-and-paper_method)，而這個方法就對 List API 非常地友善，完全可以利用現成的函式就可以完成這個方法所需要的操作，實作的方法如下：

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    int size = q_size(head);

    // shuffle
    for (int i = 0; i < size;) {  // not iterate i , iterate size
        struct list_head *start = head->next;
        int rand_idx = rand() % size;  // random number in range 0~ (size-1)
        for (int j = 0; j < rand_idx; j++) {
            start = start->next;
        }
        list_move_tail(start, head);
        size--;
    }
    return;
}

:::danger
1. 無論標題和內文中，中文和英文字元之間要有空白字元
2. 改進你的漢語表達
3. 參照他人的實作時，應該標注 GitHub 名稱。將心比心，你希望以後學弟妹用「這個人」來稱呼你嗎？
:::