2022q1 Homework1 (lab0)

contributed by < cy023 >

實驗環境

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

$ uname -a
Linux cy023-e14 5.13.0-28-generic #31~20.04.1-Ubuntu SMP Wed Jan 19 14:08:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

$ 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):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz
Stepping:                        12
CPU MHz:                         2300.000
CPU max MHz:                     4900.0000
CPU min MHz:                     400.0000
BogoMIPS:                        4599.93
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        8 MiB
NUMA node0 CPU(s):               0-7

作業要求

截止日期：
- Mar 1, 2022 (含) 之前
- 越早在 GitHub 上有動態、越早接受 code review 並持續改進者，評分越高

開發紀錄

q_new

建立一個佇列起點 (struct list_head 型態)。
佇列內不含其他資料，並將起點的 prev, next 指向自己。

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

一開始配置 element_t 型態大小的空間給 queue head, 並將 element_t 的 value 元素指向 NULL。

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

    ele->value = NULL;
    INIT_LIST_HEAD(&ele->list);

    return &ele->list;
}

但後來發現完全不必要額外浪費不使用的空間(一個字元指標大小)，queue head 設定為 struct list_head 即可。
(若在其他應用場景可以將queue head 型態改為包含 stuct list_head 與其他佇列額外資訊的結構型態，在使用 container_of 取得需要的資訊)

並使用 list.h 中 Linux Kernel 風格 API INIT_LIST_HEAD() 初始化 queue head。

INIT_LIST_HEAD

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

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;

    INIT_LIST_HEAD(head);
    return head;
}

除了張貼程式碼，你應該解釋其作用，並探討後續的改進空間。

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

q_free

釋放所有佇列使用到的空間。

q_free 函式傳入參數為 struct list_head * 型態，但佇列中用來儲存資料的節點型態是 element_t，需要注意所有佇列中的字串都要被釋放，以防 memory leak。

typedef struct {
    /* Pointer to array holding string.
     * This array needs to be explicitly allocated and freed
     */
    char *value;
    struct list_head list;
} element_t;

需要實作利用結構成員實際位址，找出該結構物件的起始位址的操作。
參考 list.h 中，container_of。

container_of

/**
 * container_of() - Calculate address of object that contains address ptr
 * @ptr: pointer to member variable
 * @type: type of the structure containing ptr
 * @member: name of the member variable in struct @type
 *
 * Return: @type pointer of object containing ptr
 */
#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

使用標準 API list_empty() 檢查佇列是否為空，如果佇列內還有資料，使用 list_first_entry() 取出第一筆資料 (element_t 型態)， list_del() 將第一筆資料移出 queue，然後釋放掉該節點使用的空間，最後釋放 queue head。

list_empty()

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

list_first_entry()

#define list_entry(node, type, member) container_of(node, type, member)

#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

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
}

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

    while (!list_empty(l)) {
        element_t *tmp = list_first_entry(l, element_t, list);
        list_del(l->next);
        free(tmp->value);
        free(tmp);
    }
    free(l);
}

將疊代迭代方式改為標準 API，list_for_each_entry_safe()。

list_for_each_entry_safe()

#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *li, *safe;

    list_for_each_entry_safe (li, safe, l, list) {
        list_del(&li->list);
        free(li->value);
        free(li);
    }
    free(l);
}

q_insrt_head

配置 element_t 型態空間當作新節點，另外配置傳入字串長度的空間用來存放節點的字串資料。
複製字串時考慮 buffer overflow 議題，使用 strncpy() 函式。

設定好新節點後，用標準 API 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;
}

/*
 * 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)
        return false;

    size_t slen = strlen(s);
    element_t *ele = malloc(sizeof(element_t));
    if (!ele)
        return false;

    INIT_LIST_HEAD(&ele->list);

    ele->value = malloc(slen + 1);
    if (!ele->value) {
        free(ele);
        return false;
    }

    strncpy(ele->value, s, slen + 1);
    list_add(&ele->list, head);

    return true;
}

q_insert_tail

與 q_insert_head 類似，將新增節點利用 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;
}

/*
 * 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;

    size_t slen = strlen(s);
    element_t *ele = malloc(sizeof(element_t));
    if (!ele)
        return false;

    INIT_LIST_HEAD(&ele->list);

    ele->value = malloc(slen + 1);
    if (!ele->value) {
        free(ele);
        return false;
    }

    strncpy(ele->value, s, slen + 1);
    list_add_tail(&ele->list, head);

    return true;
}

q_remove_head

利用前述提到的 list_first_entry() 取出佇列中的第一個節點，並使用 list_del() 從佇列中移除 (remove)。

在將被移除節點字串內容複製出來時，使用 strncpy() 函式，根據 man strncpy

The strcpy() function copies the string pointed to by src, including the terminating null byte ('\0'), to the buffer pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive the copy. Beware of buffer overruns! (See BUGS.)

The strncpy() function is similar, except that at most n bytes of src are copied. Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.

需要注意，當被移除節點字串長度大於 buffer 長度時，strncpy() 並不會在 buffer 最後一位補上 '\0' 結尾，需要幫忙加上。

/*
 * 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 *q = list_first_entry(head, element_t, list);
    if (!q)
        return NULL;

    list_del(head->next);

    if (sp) {
        strncpy(sp, q->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    return q;
}

q_remove_tail

與 q_remove_head 類似，以 list_last_entry() 取出佇列中的最後一個節點，並使用 list_del() 從佇列中移除 (remove)。

list_last_entry()

#define list_last_entry(head, type, member) \
    list_entry((head)->prev, type, member)

/*
 * 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 *q = list_last_entry(head, element_t, list);
    if (!q)
        return NULL;

    list_del(head->prev);

    if (sp) {
        strncpy(sp, q->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    return q;
}

q_size

list_for_each() 走訪所有節點，並計算長度。

list_for_each()

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

/*
 * 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;

    size_t len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;

    return len;
}

q_delete_mid

LeetCode 2095. Delete the Middle Node of a Linked List

藉由 Cycle detection 演算法的機制，找出 queue 的中間節點，並將其 delete (不只是 remove)。

如果節點數量為奇數，移除第 ⌊n / 2⌋ 個節點。

/*
 * 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 NULL if list is NULL or empty.
 */
bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return NULL;

    struct list_head *slow = head->next;
    struct list_head *fast = head->next;

    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    list_del(slow);

    element_t *mid = list_entry(slow, element_t, list);
    free(mid->value);
    free(mid);

    return true;
}

q_delete_dup

LeetCode 82. Remove Duplicates from Sorted List II

TODO: 探討與 quiz1 遞迴版本的差異

/*
 * 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)
{
    if (!head || list_empty(head))
        return NULL;

    struct list_head *tmp = head->next;
    struct list_head *end;

    while (tmp != head) {
        end = tmp->next;
        element_t *q1 = list_entry(tmp, element_t, list);
        element_t *q2 = list_entry(end, element_t, list);

        while (end != head && !strcmp(q1->value, q2->value)) {
            struct list_head *next = end->next;
            list_del(end);
            free(q2->value);
            free(q2);
            end = next;
            q2 = list_entry(end, element_t, list);
        }
        tmp = end;
    }
    return true;
}

在看 quiz1 的時候，突然發現這裡寫錯了…
重複的節點需要全部移除，但以上的實作，重複的節點會有一個被保留下來。
回頭看 ./qtest 的 do_dedup() 只有檢查是否存在重複節點，若留一個重複節點下來，./qtest 並不會發現。

改成

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;

    struct list_head *tmp = head->next;
    struct list_head *end;

    while (tmp != head) {
        end = tmp->next;

        bool isdup = 0;
        element_t *q1 = list_entry(tmp, element_t, list);
        element_t *q2 = list_entry(end, element_t, list);

        while (end != head && !strcmp(q1->value, q2->value)) {
            end = end->next;
            list_del(end->prev);
            free(q2->value);
            free(q2);
            q2 = list_entry(end, element_t, list);
            isdup = 1;
        }
        if (isdup) {
            tmp = tmp->next;
            list_del(tmp->prev);
            free(q1->value);
            free(q1);
        }
        tmp = end;
    }
    return true;
}

q_swap

LeetCode 24. Swap Nodes in Pairs

~~一次跨兩步~~ 剛開始將 node 指向 head，先檢查是否存在下下個節點 (node->next 不等於 head 且 node->next->next 不等於 head)。
若下下個節點存在，使用 list_move() 將當下節點 (node) 與下一個節點 (node->next) 交換，再將 node 指向下下個節點。
按照這個順序走訪並交換，直到下次執行會回到 head 或超前 head。

list_move()

static inline void list_move(struct list_head *node, struct list_head *head)
{
    list_del(node);
    list_add(node, head);
}

當節點有奇數個，代表迴圈會因為 node->next 等於 head 而停下，此時最後一個落單的節點不會被交換。
當節點有偶數個，代表迴圈會因為 node->next->next 等於 head 而停下，在停下前，迴圈會交換每對的節點。

/*
 * Attempt to swap every two adjacent nodes.
 */
void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *node = head;
    while (node->next != head && node->next->next != head) {
        struct list_head *tmp = node->next->next;
        list_move(tmp, node);
        node = node->next->next;
    }
}

q_reverse

LeetCode 206. Reverse Linked List

/*
 * 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;

    struct list_head *node = head;
    struct list_head *tmp;

    do {
        tmp = node->next;
        node->next = node->prev;
        node->prev = tmp;
        node = node->next;
    } while (node != head);
}

q_sort

bubble sort

效能分數當然拿不到 XD，留個紀錄。

/*
 * 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 || list_empty(head))
        return;

    size_t len = q_size(head);
    for (int i = 0; i < len; i++) {
        struct list_head *li = head->next;
        for (; li->next != head && li != head; li = li->next) {
            element_t *q1 = list_entry(li, element_t, list);
            element_t *q2 = list_entry(li->next, element_t, list);
            if (strcmp(q1->value, q2->value) > 0) {
                list_del(li);
                list_add(li, li->next);
            }
        }
    }
}

merge sort

/*
 * 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 || list_empty(head))
        return;

    head->prev->next = NULL;
    head->next = list_merge_sort(head->next);

    struct list_head *prev = head;
    struct list_head *tmp = prev->next;

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

// Doubly-linked list (not circular)
struct list_head *list_merge_sort(struct list_head *head)
{
    if (!head || !head->next)
        return head;

    struct list_head *fast = head->next;
    struct list_head *slow = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    fast = slow->next;
    slow->next = NULL;

    struct list_head *l1 = list_merge_sort(head);
    struct list_head *l2 = list_merge_sort(fast);

    return merge(l1, l2);
}

參考案例探討: LeetCode 21. Merge Two Sorted Listssw34，改進成比較有品味的程式。

struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
    struct list_head *head = NULL;
    struct list_head **ptr = &head;
    struct list_head **node;

    for (node = NULL; l1 && l2; *node = (*node)->next) {
        element_t *q1 = list_entry(l1, element_t, list);
        element_t *q2 = list_entry(l2, element_t, list);
        node = strcmp(q1->value, q2->value) < 0 ? &l1 : &l2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
    return head;
}

新增命令 `shuffle`

在 qtest.c 內新增函式 do_shuffle()，

static bool do_shuffle(int argc, char *argv[]);

並在 static void console_init() 函式內新增 shuffle 命令。

ADD_COMMAND(shuffle, "                | Shuffle nodes in queue");

修改後就能使用 help 查詢到 shuffle 命令了：）

$ ./qtest
cmd> help
Commands:
	#	 ...            | Display comment
	dedup	                | Delete all nodes that have duplicate string
	dm	                | Delete middle node in queue
	free	                | Delete queue
	help	                | Show documentation
	ih	 str [n]        | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
	it	 str [n]        | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
	log	 file           | Copy output to file
	new	                | Create new queue
	option	 [name val]     | Display or set options
	quit	                | Exit program
	reverse	                | Reverse queue
	rh	 [str]          | Remove from head of queue.  Optionally compare to expected value str
	rhq	                | Remove from head of queue without reporting value.
	rt	 [str]          | Remove from tail of queue.  Optionally compare to expected value str
	show	                | Show queue contents
+	shuffle	                | Shuffle nodes in queue
	size	 [n]            | Compute queue size n times (default: n == 1)
	sort	                | Sort queue in ascending order
	source	 file           | Read commands from source file
	swap	                | Swap every two adjacent nodes in queue
	time	 cmd arg ...    | Time command execution
	web	                | Web server...
Options:
	echo	1	Do/don't echo commands
	error	5	Number of errors until exit
	fail	30	Number of times allow queue operations to return false
	length	1024	Maximum length of displayed string
	malloc	0	Malloc failure probability percent
	simulation	0	Start/Stop simulation mode
	verbose	4	Verbosity level

實作 shuffle 演算法，一開始想要擺在 queue.c，但 queue.h 不能改，結果最後直接放在 qtest.c 的 do_shuffle() 內。

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    srand(time(NULL));
    size_t len = q_size(head);
    struct list_head *trace = head->prev;
    while (--len) {
        int index = rand() % (len + 1);
        struct list_head *target = trace->prev;
        while (index--)
            target = target->prev;
        
        list_del(trace);
        list_add_tail(trace, target);
        trace = trace->prev;
    }
}

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");
    error_check();

    set_noallocate_mode(true);
    if (exception_setup(true)) {
        if (l_meta.l && !list_empty(l_meta.l)) {
            srand(time(NULL));
            size_t len = q_size(l_meta.l);
            struct list_head *trace = l_meta.l->prev;
            while (--len) {
                int index = rand() % (len + 1);
                struct list_head *target = trace->prev;
                while (index--)
                    target = target->prev;
                list_move(trace, target);
                trace = trace->prev;
            }
        }
    }
    exception_cancel();
    set_noallocate_mode(false);
    show_queue(3);
    return !error_check();
}

整合 `tiny-web-server`

參考資料

Linux 核心原始程式碼巨集: container_of
你所不知道的 C 語言: linked list 和非連續記憶體

:)
cat scripts/pikachu.raw