2022q1 Homework1 (lab0)

contributed by < asas1asas200 >

Reviewed by `jim12312321`

尋找中間值的時候可用快慢指標的技巧，可再進一步省去呼叫 q_size 的成本。
將結點移除時，可用 list_del_init 會更加安全，尤其當該移除節點還要再次運用時。

實驗環境

$ uname -r
5.16.11-zen1-1-zen

$ gcc --version
gcc (GCC) 11.2.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:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-5350U CPU @ 1.80GHz
    CPU family:          6
    Model:               61
    Thread(s) per core:  2
    Core(s) per socket:  2
    Socket(s):           1
    Stepping:            4
    CPU max MHz:         2900.0000
    CPU min MHz:         500.0000
    BogoMIPS:            3600.21
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe
                         1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_c
                         pl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand la
                         hf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase t
                         sc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm rdseed adx smap intel_pt xsaveopt dtherm ida arat pln pts md_clear flush_l1d
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   64 KiB (2 instances)
  L1i:                   64 KiB (2 instances)
  L2:                    512 KiB (2 instances)
  L3:                    3 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-3
Vulnerabilities:         
  Itlb multihit:         KVM: Mitigation: VMX disabled
  L1tf:                  Mitigation; PTE Inversion; VMX conditional cache flushes, SMT vulnerable
  Mds:                   Mitigation; Clear CPU buffers; SMT vulnerable
  Meltdown:              Mitigation; PTI
  Spec store bypass:     Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:            Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:            Mitigation; Full generic retpoline, IBPB conditional, IBRS_FW, STIBP conditional, RSB filling
  Srbds:                 Mitigation; Microcode
  Tsx async abort:       Mitigation; Clear CPU buffers; SMT vulnerable

佇列相關操作實作

q_new

/*
 * Create empty queue.
 * Return NULL if could not allocate space.
 */
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;

    INIT_LIST_HEAD(head);
    return head;
}

Return NULL if could not allocate space

觀察 man malloc 中的 RETURN VALUE 裡面提到：

RETURN VALUE
       The malloc() and calloc() functions return a pointer  to  the  allo‐
       cated  memory,  which is suitably aligned for any built-in type.  On
       error, these functions return NULL.  NULL may also be returned by  a
       successful  call to malloc() with a size of zero, or by a successful
       call to calloc() with nmemb or size equal to zero.

所以在一般情況下可以用 malloc() 的傳回值是否為 0 來判斷是否成功申請記憶體。

Create empty queue

參照 The Linux Kernel API 中的用法，核心中的 list API 使用了 dummy node 的方式實作，所以第一個 head 節點宣告成 struct list_head 型態即可，一開始寫成了 element_t 多用了一些空間：

commit 09dc366

q_free

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *iter, *tmp;
    list_for_each_entry_safe (iter, tmp, l, list) {
        if (iter->value)
            free(iter->value);
        if (iter)
            free(iter);
    }
    free(l);
}

對於 free 操作特別需要注意的為 list_for_each_entry_safe ，根據註解的說明，在遍歷時若有刪除操作要使用此帶有 safe 後綴的巨集，將其展開後會發現其多了一個 safe 成員用來暫存 next 的位址，便可以放心移除當前疊代的元素。

q_insert_head

/*
 * Attempt to insert element at head of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        goto ERR_LIST_NULL;

    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element)
        goto ERR_NEW_ELEMENT;

    size_t size = strlen(s) + 1;
    new_element->value = malloc(sizeof(char) * strlen(s) + 1);
    if (!new_element->value)
        goto ERR_NEW_VALUE;

    strncpy(new_element->value, s, size);
    list_add(&new_element->list, head);
    return true;

ERR_NEW_VALUE:
    free(new_element);
ERR_NEW_ELEMENT:
ERR_LIST_NULL:
    return false;
}

因為整個操作包含了一些物件的資源申請與釋放，所以採用 goto + label 的方式實作，不過對於現階段的程式碼而言也僅僅是一兩行的差別。

字串複製的部份原本使用 strcpy ，後來被 cppcheck 提醒這一系列的函數（ strcpy 、 strcat 、 strcmp ）都有著未檢查 buffer 的潛在問題： Common vulnerabilities guide for C programmers#strcpy 。

q_insert_tail

/*
 * Attempt to insert element at tail of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    struct list_head *last_entry = NULL;
    last_entry = &list_last_entry(head, element_t, list)->list;
    return q_insert_head(last_entry, s);
}

為了避免重複的程式碼，所以將 entry 移動到最後一個元素後呼叫 q_insert_head ，不確定這樣的寫法是否比較好。

q_remove_head 、 q_remove_tail

/*
 * Attempt to remove element from head of queue.
 * Return target element.
 * Return NULL if queue is NULL or empty.
 * If sp is non-NULL and an element is removed, copy the removed string to *sp
 * (up to a maximum of bufsize-1 characters, plus a null terminator.)
 *
 * NOTE: "remove" is different from "delete"
 * The space used by the list element and the string should not be freed.
 * The only thing "remove" need to do is unlink it.
 *
 * REF:
 * https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
 */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *first_element = list_first_entry(head, element_t, list);
    if (sp) {
        strncpy(sp, first_element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_del(&first_element->list);
    return first_element;
}

/*
 * Attempt to remove element from tail of queue.
 * Other attribute is as same as q_remove_head.
 */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *last_element = list_last_entry(head, element_t, list);
    if (sp) {
        strncpy(sp, last_element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_del(&last_element->list);
    return last_element;
}

此處根據描述實作了頭尾的移除，並且將其 value 根據要求複製給 sp 。

q_size

/*
 * Return number of elements in queue.
 * Return 0 if q is NULL or empty
 */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *iter;
    list_for_each (iter, head) {
        ++len;
    }
    return len;
}

複雜度為

O (n)

的長度計算，不過個人認為可以用 head 來存放長度資訊，用

O (1)

的空間來換取原本需要

O (n)

的時間是相當划算的。

q_delete_mid

/*
 * Delete the middle node in list.
 * The middle node of a linked list of size n is the
 * ⌊n / 2⌋th node from the start using 0-based indexing.
 * If there're six element, the third member should be return.
 * Return true if successful.
 * Return false if list is NULL or empty.
 */
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))
        return false;

    size_t len = (q_size(head) >> 1) + 1;
    while (len--) {
        head = head->next;
    }

    element_t *mid_element = list_entry(head, element_t, list);
    if (mid_element->value)
        free(mid_element->value);
    list_del(head);
    free(mid_element);
    return true;
}

q_delete_dup

/*
 * Delete all nodes that have duplicate string,
 * leaving only distinct strings from the original list.
 * Return true if successful.
 * Return false if list is NULL.
 *
 * Note: this function always be called after sorting, in other words,
 * list is guaranteed to be sorted in ascending order.
 */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;

    element_t *now, *tmp, *last = NULL;
    bool dup_flag = false;
    list_for_each_entry_safe (now, tmp, head, list) {
        if (last && !strcmp(last->value, now->value)) {
            list_del(&now->list);
            free(now->value);
            free(now);
            dup_flag = true;
        } else if (dup_flag) {
            list_del(&last->list);
            free(last->value);
            free(last);
            dup_flag = false;
            last = now;
        } else {
            last = now;
        }
    }
    if (dup_flag) {
        list_del(&last->list);
        free(last->value);
        free(last);
    }
    return true;
}

疊代每個元素，並將上一個元素標記為 last ，如果 last 和當前的元素值一樣的話將 dup_flag 標記為 true ，並且刪除當前元素繼續下一次的疊代。

而當前元素若和 last 不一樣且 dup_flag 為 true 的話代表 last 是 重複的元素 ，並且已經是當前 list 中沒有一樣的了，所以從 list 中清除 last 並設定 dup_flag 為 false 繼續疊代。

而 dup_flag 的意義即是 last 是否為 重複的元素 。

q_swap

/*
 * Attempt to swap every two adjacent nodes.
 */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;

    bool flag = true;
    element_t *now, *tmp;
    struct list_head *del;
    list_for_each_entry_safe (now, tmp, head, list) {
        if (flag) {
            list_del(&now->list);
            del = &now->list;
        } else {
            list_add(del, &now->list);
        }
        flag = !flag;
    }
    if (!flag)
        list_add_tail(del, head);
}

跟 q_delete_dup 的做法類似，在每次疊代中一次刪除，一次插入，達成 swap 的效果，這題限制不能改變 value 稍微想了一下。

q_reverse

/*
 * Reverse elements in queue
 * No effect if q is NULL or empty
 * This function should not allocate or free any list elements
 * (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
 * It should rearrange the existing ones.
 */
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    element_t *left = list_first_entry(head, element_t, list);
    element_t *right = list_last_entry(head, element_t, list);
    size_t cnt = q_size(head) >> 1;

    // Swap for size/2 times
    while (cnt--) {
        char *tmp = left->value;
        left->value = right->value;
        right->value = tmp;
        left = list_entry(left->list.next, element_t, list);
        right = list_entry(right->list.prev, element_t, list);
    }
}

這邊不像 swap 的時候有特別說不能改 value ，所以只要交換 q_size / 2 次就可以 reverse 了，具體操作如下：

最一開始的情形

這時候 LR 做交換，注意到這邊交換的是他們的 value 而非真正在 linked-list 上做交換，所以 left 和 right 不會變：

然後將 left 往 next 的方向前進並將 right 往 prev 的方向：

再進行一次交換：

對於每個長度為 n 的 list ，只要交換

⌊ n / 2 ⌋

次即可得到反轉後的結果。

q_sort

原本的做法

void merge_sort(struct list_head *l, struct list_head *r, size_t len)
{
    if (len <= 1 || l == r)
        return;
    struct list_head *mid = l;
    int cnt = len >> 1;
    int r_len = len - cnt;
    while (cnt--)
        mid = mid->next;
    merge_sort(l, mid->prev, len >> 1);
    merge_sort(mid, r, r_len);

    // sorting
    struct list_head *mid_iter = mid;
    struct list_head *l_iter = l;
    char *tmp[len];
    for (int i = 0; i < len; i++)
        tmp[i] = NULL;
    int idx = 0;
    while (l_iter != mid && mid_iter != r->next) {
        if (strcmp(list_entry(l_iter, element_t, list)->value,
                   list_entry(mid_iter, element_t, list)->value) <= 0) {
            tmp[idx++] = list_entry(l_iter, element_t, list)->value;
            l_iter = l_iter->next;
        } else {
            tmp[idx++] = list_entry(mid_iter, element_t, list)->value;
            mid_iter = mid_iter->next;
        }
    }

    // cleanup
    while (l_iter != mid) {
        tmp[idx++] = list_entry(l_iter, element_t, list)->value;
        l_iter = l_iter->next;
    }
    while (mid_iter != r->next) {
        tmp[idx++] = list_entry(mid_iter, element_t, list)->value;
        mid_iter = mid_iter->next;
    }

    // write back
    element_t *now = list_entry(l, element_t, list);
    for (idx = 0; idx < len; idx++) {
        now->value = tmp[idx];
        now = list_entry(now->list.next, element_t, list);
    }
}

/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(struct list_head *head)
{
    if (!head || q_size(head) <= 1)
        return;

    merge_sort(&list_first_entry(head, element_t, list)->list,
               &list_last_entry(head, element_t, list)->list, q_size(head));
}

因為限制了 malloc() 的使用，所以使用 VLA 並將 list 當成 array 來實作 merge sort ，但此方法不是很好所以不多做說明。

改良紀錄 commit 59650e0 。

一開始因為不想去動到 list 元素的排列，想嘗試只更改 value 指向來完成排序，奈何 linked-list 無法隨機訪問，所以有其困難，在實作 swap 的時候突然發現 list_add 和 list_add_tail 可以用在此處便回來改良程式：

void merge_sort(struct list_head *l, struct list_head *r, size_t len)
{
    if (len <= 1 || l == r)
        return;
    struct list_head *mid = l, *safe_l = l->prev, *safe_r = r->next;
    int cnt = len >> 1;
    int r_len = len - cnt;
    while (cnt--)
        mid = mid->next;
    merge_sort(l, mid->prev, len >> 1);
    l = safe_l->next;
    merge_sort(mid, r, r_len);
    mid = l;
    cnt = len >> 1;
    while (cnt--)
        mid = mid->next;

    struct list_head *r_iter = mid;
    struct list_head *l_iter = l;
    while (l_iter != r_iter && r_iter != safe_r) {
        if (strcmp(list_entry(l_iter, element_t, list)->value,
                   list_entry(r_iter, element_t, list)->value) <= 0) {
            l_iter = l_iter->next;
        } else {
            struct list_head *tmp = r_iter->next;
            list_del(r_iter);
            list_add_tail(r_iter, l_iter);
            r_iter = tmp;
        }
    }
}

/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(struct list_head *head)
{
    if (!head || q_size(head) <= 1)
        return;

    merge_sort(&list_first_entry(head, element_t, list)->list,
               &list_last_entry(head, element_t, list)->list, q_size(head));
}

實作採用的是 merge sort 演算法，為了方便畫圖及簡潔的畫面所以下面流程皆用 Singly-Linked List 表達，考慮一般情況：

其中 L 、 R 、 M 分別代表左界、右界以及中間。

根據 merge sort 的規則，這時候分別對

[L, M - 1]

、

[M, R]

做排序，會得到如下結果，用一樣的顏色代表該連續區塊保證已排序（後面會用到）：

這時候設定兩個疊代用的指標分別指向 L 和 M ：

比對 l_iter 和 r_iter 的值，這邊因為 1 < 3 所以將 1 先從 list 中移除再插進 3 的前面：

然後移動 r_iter 到原本的右邊，以這邊來說就是 2 的位址：

再做一次一樣的操作後會變成下圖：

此時 r_iter 會指向最右邊的下一個，這時候代表操作完成，看起來雖然只有把右半部做移動而已， l_iter 完全沒有移動，但是實際上他們早就是已排序的，所以到此就結束了，不用像陣列的時候做多餘的複製和寫入。

從這個案例可以看出其中一個邊界條件就是 r_iter != r->next 。

接下來看一個最簡單的例子：

在這個例子中，很明顯 l_iter 會一直往右跑，直到找到 3 ，也就是 r_iter 的位址，所以另一個邊界條件即為 l_iter != r_iter 。

在實作上只有一個要特別注意的地方：
傳入 merge_sort() 的 l 、 r 和在裡面計算的 mid 會因為移動元素的關係所以改變位址，目前的解決辦法是設定 l_safe 和 r_safe 在有需要的時候重新定位。

2022q1 Homework1 (lab0)

Reviewed by `jim12312321`

實驗環境

佇列相關操作實作

q_new

Return NULL if could not allocate space

Create empty queue

q_free

q_insert_head

q_insert_tail

q_remove_head 、 q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort

待補充

Fisher–Yates shuffle 演算法

整合 tiny-web-server

2022q1 Homework1 (lab0)

Reviewed by jim12312321

實驗環境

佇列相關操作實作

q_new

Return NULL if could not allocate space

Create empty queue

q_free

q_insert_head

q_insert_tail

q_remove_head 、 q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort

待補充

Fisher–Yates shuffle 演算法

整合 tiny-web-server

Reviewed by `jim12312321`