2023q1 Homework1 (lab0)

contributed by < zeddyuu >

開發環境

$ neofetch --stdout
zhenyu@zhenyu-HP-Laptop-15s-du2xxx
OS: Kubuntu 22.04.1 LTS x86_64 
Host: HP Laptop 15s-du2xxx 
Kernel: 5.15.0-43-generic 
Uptime: 53 mins 
Packages: 1993 (dpkg), 7 (snap) 
Shell: bash 5.1.16 
Resolution: 1920x1080 
DE: Plasma 5.24.4 
WM: KWin 
Theme: [Plasma], Breeze [GTK2/3] 
Icons: [Plasma], breeze-dark [GTK2/3] 
Terminal: konsole 
CPU: Intel i5-1035G1 (8) @ 3.600GHz 
GPU: NVIDIA GeForce MX330 
GPU: Intel Iris Plus Graphics G1 
Memory: 2089MiB / 11754MiB

$ gcc -v
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.3.0 (Ubuntu 11.3.0-1ubuntu1~22.04)

完成 `queue.[ch]` 程式

q_new

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (!q)
        return NULL;
    INIT_LIST_HEAD(q);
    return q;
}

q_free

void q_free(struct list_head *l) 
{
    if (!l)
        return;
    element_t *c, *n;
    list_for_each_entry_safe (c, n, l, list) {
        list_del(&c->list);
        q_release_element(c);
    }
    free(l);
}

釋放佇列所佔用的所有記憶體，這邊剛開始是使用 list_for_each ，但沒有考慮到刪除當前節點後，下個節點的位置就找不到了，需要一個額外暫存下個節點的指標，故改用 list_for_each_safe 完成。

q_insert_head

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

宣告一個新的 element 接著處理它的 value 成員，考慮到空字元，先分配此字串長度 + 1 的記憶體空間，再利用 memcpy 將參數 s 的內容複製到此空間， value 指向此空間，最後用 list_add 將 element 加入到佇列的開頭。
在分配記憶體空間給 s_new 時，須注意若分配失敗要將已分配給 element 的記憶體空間釋放掉，否則會引起 memory leak 的問題。

q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *element = malloc(sizeof(element_t));
    if (!element)
        return false;
    char *s_new = malloc((strlen(s) + 1) * sizeof(char));
    if (!s_new) {
        free(element);
        return false;
    }
    memcpy(s_new, s, strlen(s) + 1);
    element->value = s_new;
    list_add_tail(&element->list, head);
    return true;
}

做法和 q_insert_head 相同，差別在於使用 list_add_tail。

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 *element = list_first_entry(head, element_t, list);
    if (sp && bufsize != 0) {
        strncpy(sp, element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&element->list);
    return element;
}

先確認head是否為NULL以及empty，使用 list_first_entry 得到佇列第一個 element ，隨後確認參數 sp 以及 bufsize 是否合理，再用 strncpy 複製欲刪除 element 的 value 成員到 sp 中，記得加上空字元，最後用 list_del 刪除元素。

q_remove_tail

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

做法和 q_remove_head 相同，差別在於使用 list_last_entry。

q_size

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    int size = 0;
    struct list_head *c;
    list_for_each (c, head) {
        size++;
    }
    return size;
}

先確認 head 是否為NULL以及empty，使用 list_for_each 走訪佇列並計算 node 總數。

q_delete_mid

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;
    int size = q_size(head);
    element_t *c, *n;
    int cnt = -1;
    list_for_each_entry_safe (c, n, head, list) {
        cnt++;
        if (cnt == (size / 2)) {
            list_del(&c->list);
            q_release_element(c);
            break;
        }
    }
    return true;
}

還沒想到有沒有較快解法，目前只想到最直觀的解法是走訪過一次計算 node 總數，接著再走訪一次到中間 node ~~做指標操作~~(直接 list_del 就好)，時間複雜度是

O (n)

。

要注意刪除 node 的操作要配合 list_for_each_entry_safe。

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *fast = head->next, *slow = fast;
    while (fast->next != head && fast != head) {
        slow = slow->next;
        fast = fast->next->next;
    }
    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));
    return true;
}

看了你所不知道的 C 語言: linked list 和非連續記憶體中所提到的快慢指標的方法，利用兩個步數不同的指標 slow 和 fast，當 fast 走完整個 list，slow 的位置剛好指到中間的節點，再釋放 slow 指標所指到的記憶體位置即可完成更精簡的 q_delete_mid 操作。

q_delete_dup

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    element_t *c, *n;
    bool flag = false;
    list_for_each_entry_safe (c, n, head, list) {
        if (c->list.next != head && strcmp(c->value, n->value) == 0) {
            list_del(&c->list);
            q_release_element(c);
            flag = true;
        } else if (flag) {
            list_del(&c->list);
            q_release_element(c);
            flag = false;
        }
    }
    return true;
}

使用 list_for_each_entry_safe 每次迭代會紀錄下個節點，並且比較當前和下個節點的字串，利用一個 flag 去紀錄是否重複來決定下次迴圈是否要刪除節點，

q_swap

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

將 while 敘述改為 for 迴圈，撰寫更精簡的程式碼。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

使用 for 敘述取代 while，改成更精簡的程式碼。

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head))
        return;
    for (struct list_head *c = head->next; c->next != head && c != head;
        c = c->next) {
        list_move(c, c->next);
    }
}

從 head 後第一個 node 開始走訪每一個節點，使用 list_move 將當前 node 移到下個 node 後一位，此操作等同於交換兩個 node，再將當前指標移到下一個 node，重複此操作直到迴圈結束即完成 q_swap。

以 list_mov 將 Node1 移到 Node2 後。

移動指標 c 至下個節點，重複一樣的操作直到迴圈結束。

q_reverse

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *c, *n;
    list_for_each_safe (c, n, head) {
        list_del(c);
        list_add(c, head);
    }
}

逐一走訪每個節點，並依序搬移到 head 即可。

q_reverseK

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))
        return;
    struct list_head *c, *n, tmp, *tmp_head = head;
    INIT_LIST_HEAD(&tmp);
    int i = 0;
    list_for_each_safe (c, n, head) {
        i++;
        if (i == k) {
            list_cut_position(&tmp, tmp_head, c);
            q_reverse(&tmp);
            list_splice_init(&tmp, tmp_head);
            i = 0;
            tmp_head = n->prev;
        }
    }
    return;
}

每 k 個節點做一次 list_cut_position 切出一個欲進行 reverse 操作的 list，用先前實作好的 q_reverse 反轉再接回原來的串列。

q_sort

struct list_head *merge_two_list(struct list_head *l1, struct list_head *l2)
{
    struct list_head *head, *tmp;
    if (strcmp(list_entry(l1, element_t, list)->value,
               list_entry(l2, element_t, list)->value) <= 0) {
        head = l1;
        tmp = head;
        l1 = l1->next;
    } else {
        head = l2;
        tmp = head;
        l2 = l2->next;
    }
    while (l1 && l2) {
        if (strcmp(list_entry(l1, element_t, list)->value,
                   list_entry(l2, element_t, list)->value) <= 0) {
            tmp->next = l1;
            l1->prev = tmp;
            tmp = tmp->next;
            l1 = l1->next;
        } else {
            tmp->next = l2;
            l2->prev = tmp;
            tmp = tmp->next;
            l2 = l2->next;
        }
    }

    while (l2) {
        tmp->next = l2;
        l2->prev = tmp;
        tmp = tmp->next;
        l2 = l2->next;
    }
    while (l1) {
        tmp->next = l1;
        l1->prev = tmp;
        tmp = tmp->next;
        l1 = l1->next;
    }
    head->prev = tmp;
    return head;
}

struct list_head *mergesort(struct list_head *head)
{
    if (!head->next)
        return head;
    struct list_head *fast = head, *slow = fast, *nl, *nr;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    slow->prev->next = NULL;
    nl = mergesort(head);
    nr = mergesort(slow);
    return merge_two_list(nl, nr);
}

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    head->prev->next = NULL;
    head->next = mergesort(head->next);
    head->next->prev->next = head;
    head->prev = head->next->prev;
    head->next->prev = head;
}

先將最後節點的 next 設為 NULL 斷開和 head 間的連結，使用 mergesort 函式用快慢指標找出中間節點，分出左右兩段 list，一樣將左段最後節點的 next 設為 NULL 切斷鏈結以利後續 merge_two_list 的迴圈結束條件判斷(右段不用，因為最後一定是接到 NULL)，遞迴處理直到佇列中剩下一個節點，接著使用 merge_two_list 開始比較大小並合併兩個 list，最後回傳合併完成的佇列。

回到 q_sort 後會將原先 head 和合併完成的佇列連接起來，完成排序。

寫法上應該可以更有品味，且尚未完整研讀 list_sort.c，之後改進並嘗試引入 list_sort.c。

q_descend

int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    int len = 0;
    for (struct list_head *cur = head->prev; cur != head && cur->prev != head;
         len++) {
        element_t *c = container_of(cur, element_t, list);
        element_t *p = container_of(cur->prev, element_t, list);
        if (strcmp(c->value, p->value) > 0) {
            list_del(&p->list);
            q_release_element(p);
            len--;
        } else {
            cur = cur->prev;
        }
    }
    return len;
}

反向走訪佇列，若下個節點的 value 小於當前節點的 value，刪除下個節點。

q_merge

int q_merge(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    queue_contex_t *q1 = container_of(head->next, queue_contex_t, chain);
    if (list_is_singular(head))
        return q1->size;
    for (struct list_head *cur = head->next->next; cur != head;
         cur = cur->next) {
        queue_contex_t *q = container_of(cur, queue_contex_t, chain);
        list_splice_init(q->q, q1->q);
        q->size = 0;
    }
    q_sort(q1->q);
    q1->size = q_size(q1->q);
    return q1->size;
}

先前有先玩過 qtest，功能可以建立多個不同的佇列，沒有仔細去看實作內容，到要實作 q_merge 才覺得傳進來的參數 head 跟之前其他函式的 head 好像不同，原來 queue 之間也是有用另外一個 linked list 串起來的，所以拿到的參數是 queue 之間串列的 head，以此來走訪每個 queue。

typedef struct {
    struct list_head head;
    int size;
} queue_chain_t;

這裡就感受到 container_of 的強大，可以利用已知成員的記憶體位置去得到結構體的記憶體位置以存取成員，之後使用 list_splice_init 將每個佇列合併。

參考 komark06 的作法，將每個佇列都合併為一個佇列再利用實作的好的 q_sort 進行排序，確認是否只有一個節點可以改用 list_is_singular。

目前分數 95 / 100
時間複雜度有問題，看了課程討論區留言應該要改良 dudect。

以 Valgrind 分析程式執行的記憶體

$ valgrind --tool=massif ./qtest -f testcommand.sh
$ massif-visualizer massif.out.8735

testcommand.sh 用以開啟 simulation 模式



option simulation 1
it 
option simulation 0

視覺化的結果圖

給額外參數 max-snapshot 為 1000，可以看到更詳細的 heap memory 變化

研讀 lib/list_sort.c 原始程式碼

merge()

__attribute__((nonnull(2,3,4)))

第一行就看不懂，查了才發現這是一種函式屬性 (function attribute) 的用法，用來指定函式2、3、4的參數位置不可為NULL，注意是用於指標參數，避免空指標錯誤。

static struct list_head *merge(void *priv, list_cmp_func_t cmp,
				struct list_head *a, struct list_head *b)
{
	struct list_head *head, **tail = &head;

	for (;;) {
		/* if equal, take 'a' -- important for sort stability */
		if (cmp(priv, a, b) <= 0) {
			*tail = a;
			tail = &a->next;
			a = a->next;
			if (!a) {
				*tail = b;
				break;
			}
		} else {
			*tail = b;
			tail = &b->next;
			b = b->next;
			if (!b) {
				*tail = a;
				break;
			}
		}
	}
	return head;
}

此為合併兩個 list 的函式，這裡的關鍵是指標的指標變數 tail，存的是指標變數的記憶體位置，指標變數存的又是 list_head 這個結構體的記憶體位置，每一次迭代都會將 tail 指向 next 變數的記憶體位置，故使用取值運算子 * 可以更改此指標變數 next 存的 list_head 記憶體位置，以此更改下個節點為比較值小的節點，最後回傳 head。

list_sort()

先來看註解部分

 * This mergesort is as eager as possible while always performing at least
 * 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
 * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
 *
 * Thus, it will avoid cache thrashing as long as 3*2^k elements can
 * fit into the cache.  Not quite as good as a fully-eager bottom-up
 * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
 * the common case that everything fits into L1.
 *
 *
 * The merging is controlled by "count", the number of elements in the
 * pending lists.  This is beautifully simple code, but rather subtle.

一般合併的方法會將同一層相同大小的串列合併之後才合併更大的串列，此為 level order merge，在每一層都會讀取所有子串列。

但當欲排序的串列超過 L1 cache 的大小，在上層合併好的串列會從 cache 內搬出讓出空間給下個需要排序的序列，而到下一層，上層剛合併好的串列又要搬進 cahce，造成資料不斷重複進出 cache，多次發生 cache miss ，引發 thrashing，此時 CPU 每次都要去 memory 存取資料，速度變慢，cache 的存在就形同虛設。

因此此演算法的想法是以 depth-first order 去完成合併，這樣會有好的 cache locality，但 depth-first order 的方式可能會有不平衡的合併情況發生。

一般的 bottom-up mergesort 會在出現兩個大小為

2^{k}

的 list 時就進行比較合併，所以想法是不馬上進行合併，而是等有第三個大小為

2^{k}

的 list 出現才會進行比較合併，讓最差的合併情況會是以 2:1 的比例進行，只要這三個 list 可以被放進 cache，可以降低比較次數並且有效利用 cache locality，而這個比例會透過 count 變數來實作。

 * Each time we increment "count", we set one bit (bit k) and clear
 * bits k-1 .. 0.  Each time this happens (except the very first time
 * for each bit, when count increments to 2^k), we merge two lists of
 * size 2^k into one list of size 2^(k+1).
 *
 * This merge happens exactly when the count reaches an odd multiple of
 * 2^k, which is when we have 2^k elements pending in smaller lists,
 * so it's safe to merge away two lists of size 2^k.
 *
 * After this happens twice, we have created two lists of size 2^(k+1),
 * which will be merged into a list of size 2^(k+2) before we create
 * a third list of size 2^(k+1), so there are never more than two pending.

list_sort 的實作方式是使用一個 count 變數來記錄當前處理的節點數量，用二進位來看這個 count 變數，在

2^{k} - 1

時不用進行合併，以表格說明。
參考 DokiDokiPB 的表格

Decimal of count	Binary of count	Merge	Range	Size
0	00000	X	X	X
1	00001	X	X	X
2	00010	O	[0,1]	2
3	00011	X	X	X
4	00100	O	[2,3]	2
5	00101	O	[0,3]	4
6	00110	O	[4,5]	2
7	00111	X	X	X
8	01000	O	[6,7]	2
9	01001	O	[4,7]	4
10	01010	O	[8,9]	2
11	01011	O	[0,7]	8
12	01100	O	[10,11]	2
13	01101	O	[8,11]	4
14	01110	O	[12,13]	2
15	01111	X	X	X
16	10000	O	[14,15]	2

接著來看 list_sort 的實作細節。

__attribute__((nonnull(2,3)))

一樣是 function attribute 的用法，限制第二、三參數不能為NULL。

void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
    struct list_head *list = head->next, *pending = NULL;
	size_t count = 0;	/* Count of pending */

	if (list == head->prev)	/* Zero or one elements */
		return;

	/* Convert to a null-terminated singly-linked list. */
	head->prev->next = NULL;

一開始會先將最後節點跟 head 之間的鏈結切斷，發現我 qsort 實作方式和它有相同的地方。
























	do {
		size_t bits;
		struct list_head **tail = &pending;

		/* Find the least-significant clear bit in count */
		for (bits = count; bits & 1; bits >>= 1)
			tail = &(*tail)->prev;
		/* Do the indicated merge */
		if (likely(bits)) {
			struct list_head *a = *tail, *b = a->prev;

			a = merge(priv, cmp, b, a);
			/* Install the merged result in place of the inputs */
			a->prev = b->prev;
			*tail = a;
		}

		/* Move one element from input list to pending */
		list->prev = pending;
		pending = list;
		list = list->next;
		pending->next = NULL;
		count++;
	} while (list);

一開始有個疑問是，在函式開始後會先把 pending 指向 NULL，而這邊在找從右邊數起第一個出現的0 時，應該會存取到 NULL，發生 Segmetation fault，但後來發現 count 一開始是 0，跟 1 做完 AND 不會進入迴圈執行。

tail 這個指標在每次 do-while 敘述都會指向現在 pending 的記憶體位置。

第 6 行的 for 迴圈負責找出從右邊數起第一個出現的 bit 0，並且調整 tail 往前找出要合併的 sorted list，這裡的原理是利用 prev 成員連接每個不同的 sorted list，在這邊找到要合併的 list 位置後，就可以利用下個 if 敘述去做合併。

接著在第 9 行發現一個從來沒看過的東西–-likely，參考 Linux Kernel慢慢學 likely and unlikely macro 才發現是一種編譯器最佳化的方法，把分支的預測資訊告訴編譯器，以便對程式碼改變分支順序進行優化，之前念計組好像有類似的觀念叫做 Delay slot，也是預測分支常不常發生來進行組語程式碼的搬移。
這邊的 if 是用來判斷是否要進行 list 的合併，可以發現只有當 count 為

2^{k} - 1

時不會進入判斷式中進行合併，舉例來說像是

7_{2}

為 0…0111，做完 for 迴圈後 bits 為 0，就不會進入 if 敘述中進行合併。

最後 19 行會將 list 還有 pending 的指標往後推移，也就是把下一個元素放入 pending。

修改並引入 list_sort.c

struct list_head *merge(struct list_head *a, struct list_head *b)
static void merge_final(struct list_head *head, struct list_head *a, 
                        struct list_head *b)
void list_sort(struct list_head *head, list_cmp_func_t cmp)

if (strcmp(container_of(a, element_t, list)->value, 
           container_of(b, element_t, list)->value) <= 0)

把 list_sort.c 的函式放到 queue.c，之後把一些不會使用到的參數 priv 以及 cmp 拿掉，在函式內的 cmp 只要用 strcmp 取代即可。

# define likely(x)	__builtin_expect(!!(x), 1)            
# define unlikely(x)	__builtin_expect(!!(x), 0)

定義 likely(x) 以及 unlikely(x)

ADD_COMMAND(lsort, "Sort queue in ascending order with list_sort.c", "");

接著在 qtest.c 當中新增指令

if (current && exception_setup(true))
    list_sort(current->q);

實作 do_lsort 函式，大部份內容和 do_sort 一樣，只是差在會去呼叫定義在 queue.c 的 list_sort

TODO: 效能評測比較還在想如何做

在 qtest 中提供 shuffle 進行洗牌操作

ADD_COMMAND(shuffle, "Shuffle all the nodes in queue", "");

新增 shuffle 命令到 qtest.c

struct list_head *head = current->q;
        if (!head || list_empty(head))
            return false;
        srand(time(NULL));
        struct list_head *c, *n;
        int size = q_size(head);
        list_for_each_safe (c, n, head) {
            if (size == 1)
                break;
            int index = rand() % size;
            struct list_head *t = c;
            while (index--) {
                t = t->next;
            }   
            if (t == c) {
                size--;
                continue;
            } else {
                // swap node
                struct list_head *pos = t->prev;
                list_del(t);
                t->next = c->next;
                t->next->prev = t;
                t->prev = c->prev;
                t->prev->next = t;
                if (pos == c)
                    pos = t;
                list_add(c, pos);
            }
            size--;
        }

藉由 Fisher–Yates shuffle 演算法實作 shuffle 功能，使用 mod 可以隨機找到要往後找的步數，故要和當前節點交換的節點(步數會落於範圍

0 \leq j < s i z e

，故節點會落於範圍

n o d e_{i} \leq n o d e_{j} < n o d e_{n}

，

n o d e_{i}

為當前節點，

n o d e_{n}

為最後節點)。
因為是 linked list，不能隨機存取，只能逐一尋訪每個節點找到此節點，時間複雜度是

O (n^{2})

，演算法中的 swap 部份其實可以用 list_swap 去取代那些指標操作，但老師給的 list.h 裡面似乎把這個功能給拔了，應該是要我們用基本指標操作去實現 swap。