# 2022q1 Homework1 (lab0)
contributed by < `TimidCactus` >

> 目前 95 分，欠常數。
> 用 bitwise operator 用有寫程式的感覺。

## 實驗環境

> 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:                   43 bits physical, 48 bits virtual
CPU(s):                          128
On-line CPU(s) list:             0-127
Thread(s) per core:              2
Core(s) per socket:              64
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       AuthenticAMD
CPU family:                      23
Model:                           49
Model name:                      AMD Ryzen Threadripper 3990X 64-Core Processor
Stepping:                        0
Frequency boost:                 enabled
CPU MHz:                         1980.432
CPU max MHz:                     2900.0000
CPU min MHz:                     2200.0000
BogoMIPS:                        5789.17
Virtualization:                  AMD-V
L1d cache:                       2 MiB
L1i cache:                       2 MiB
L2 cache:                        32 MiB
L3 cache:                        256 MiB
NUMA node0 CPU(s):               0-127

## [作業要求](https://hackmd.io/@sysprog/2022-lab0)

依據指示著手修改 queue.[ch] 和連帶的檔案。
- [x] 完成 queue.c (雖只有95%，但我找不出來為什麼不是常時間，有時候他是有時候不是。)
- [x] 完成 queue.c 的開發過程
- [ ] 比較 list_sort.c 和自己實作的 q_sort 的差異

:::danger
使用完整漢語描述
:notes: jserv
:::

## 開發過程
### q_new()

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

* malloc 會回傳一個 void *，要把它轉成 struct list_head * 才能放進 struct list_head 的變數裡，被免未定義行為。
* INIT_LIST_HEAD 會把 list_head 的 prev 和 next 賦予自身的地址，即會實際操作到記憶體，而對 NULL 進行取值是未定義行為，故需要判別 head 是否為 NULL。

### q_free()

void q_free(struct list_head *l)
{
    if (!l)
        return;
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, l) {
        list_del(node);
        q_release_element(list_entry(node, element_t, list));
    }
    free(l);
}

* 對 NULL 取值是未定義行為，故要被免。
* 考慮到會刪除節點故使用 list_for_each_entry_safe 。
* 考慮到 list_for_each_entry_safe 會取下下個節點，到剩下一個的時候會存取已釋放的節點，這是未定義行為，故要使用 list_del 保持節點指向有效的記憶體位置。
* 把 list_head 釋放掉。

### q_insert_head()

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *node = (element_t *) malloc(sizeof(element_t));
    if (!node)
        return false;
    node->value = strdup(s);
    if (!node->value) {
        free(node);
        return false;
    }
    list_add(&node->list, head);
    return true;
}

* 當 q 或 malloc 失敗時回傳 false。
* strdup 回傳 pointer 指向已分配空間的 s 字串。
* 這個己經是O(1)了。

### q_insert_tail()

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *node = (element_t *) malloc(sizeof(element_t));
    if (!node)
        return false;
    node->value = strdup(s);
    if (!node->value) {
        free(node);
        return false;
    }
    list_add_tail(&node->list, head);
    return true;
}

* 當 q 或 malloc 失敗時回傳 false。
* strdup 回傳 pointer 指向已分配空間的 s 字串。

### 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 *node = list_entry(head->next, element_t, list);
    list_del(&node->list);
    int32_t len =
        min(min(bufsize - 1, strlen(node->value) + 1), abs((intptr_t) sp) - 1);
    size_t i = len;
    while (len >= 0) {
        intptr_t mask = (-!!(len ^ i));
        sp[len] = node->value[len] & mask;
        len--;
    }
    return node;
}

* 如果 list 為 NULL 或 list 為 empty 即回傳 NULL。
* sp 不為 NULL 且 remove 成功則寫入 del 的字串至sp。
* 用 len 來控制進去 while，len 的三個可能性分別是 bufsize - 1, strlen + 1, sp
* bufsize 和 strlen 取 min 能為上限。
* sp 可能為 NULL 或 任意值，任意值時可能會是 signed 的負值，所以取 abs ﹐主要是要他為 NULL 時輸出為 -1 不進 while 存取 NULL 被免 Segment fault。
* 在 while 裡的 len 判斷是不是最後一個的 '\0'，是則變為全零。
* 這個己經是O(1)了，我不能理解為什麼不是常數時間。

### 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 *node = list_entry(head->prev, element_t, list);
    list_del(&node->list);
    int32_t len =
        min(min(bufsize - 1, strlen(node->value) + 1), abs((intptr_t) sp) - 1);
    size_t i = len;
    while (len >= 0) {
        intptr_t mask = (-!!(len ^ i));
        sp[len] = node->value[len] & mask;
        len--;
    }
    return node;
}

* 如果 list 為 NULL 或 list 為 empty 即回傳 NULL。
* sp 不為 NULL 且 remove 成功則寫入 del 的字串至sp。

### q_size()

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

* 如果 list 為 NULL 或 list 為 empty 即回傳 0 。
* list_for_each_entry 跑一圈計算 size。

### 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;
    struct list_head *node = NULL, *next = head->next, *prev = head->prev;
    while (!node) {
        if (next == prev)
            node = next;
        if (next->next == prev)
            node = prev;
        next = next->next;
        prev = prev->prev;
    }
    list_del(node);
    q_release_element(list_entry(node, element_t, list));
    return true;
}

* 如果 list 為 NULL 或 list 為 empty 即回傳 NULL。
* next 和 prev 步距一致相匯時必為中間
* 奇數為 next == prev，del next
* 偶數為 next->next == prev ， del prev
> 有更好的寫法嗎? 這一點都不“good taste”
> 有辦法只用一個條件式嗎?

### q_delete_dup()

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;
    char *del_patten = NULL;
    element_t *node, *safe;
    for (node = list_entry(head->next, element_t, list),
        safe = list_entry(node->list.next, element_t, list);
         &safe->list != head;
         node = safe, safe = list_entry(node->list.next, element_t, list)) {
        intptr_t mask =
            -(!strcmp(node->value, safe->value)) | (node->value == del_patten);
        del_patten = (char *) ((intptr_t) safe->value & mask);
        if (del_patten && !strcmp(del_patten, node->value)) {
            list_del(&node->list);
            q_release_element(node);
        }
    }
    if (del_patten && !strcmp(del_patten, node->value)) {
        list_del(&node->list);
        q_release_element(node);
    }
    return true;
}

* mask 是指找到相同的字串則給出 -1 或 前一個刪除的字串所對照的地址給出 0 。
* 籍此控制 del_patten 的 pointer。
* 由於這方法會令 safe 碰到 head 的 entry，觸發 Segment fault 則先在前一個停下來再在外再做一遍。
* 有考慮過用 list_for_each 但覺得內容有簡單比較重要。

### q_swap()

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        if (safe == head)
            return;
        list_del(node);
        list_add(node, safe);
        safe = node->next;
    }
}

* list_for_each_safe 把現有的 node 取出再放到 safe 的前面，改變 safe 就會改到下一個 node。

### q_reverse()

void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        node->next = node->prev;
        node->prev = safe;
    }
    node->next = node->prev;
    node->prev = safe;
}

* 把每個 node 的 next 和 prev 交換。

### q_sort

struct list_head *merge(struct list_head *a, struct list_head *b)
{
    struct list_head *sorted, **temp, **tail = &sorted;
    while (a && b) {
        temp = (strcmp(list_entry(a, element_t, list)->value,
                       list_entry(b, element_t, list)->value) <= 0)
                   ? &a
                   : &b;
        *tail = *temp;
        *temp = (*temp)->next;
        tail = &((*tail)->next);
    }
    *tail = (struct list_head *) ((intptr_t) a | (intptr_t) b);
    return sorted;
}

struct list_head *merge_sort(struct list_head *head)
{
    if (!head->next)
        return head;
    struct list_head *mid, *last;
    for (mid = head, last = head->next; last && last->next;
         mid = mid->next, last = last->next->next)
        ;
    last = mid;
    mid = mid->next;
    last->next = NULL;
    head = merge_sort(head);
    mid = merge_sort(mid);
    return merge(head, mid);
}

void q_sort(struct list_head *head)
{
    if (!head || (head->next == head->prev))
        return;
    struct list_head *tail;
    head->prev->next = NULL;
    tail = merge_sort(head->next);
    head->next = tail;
    tail->prev = head;
    while (tail->next) {
        tail->next->prev = tail;
        tail = tail->next;
    }
    head->prev = tail;
    tail->next = head;
}

* 先把 list 能有結尾。
* 找出中間的節點，分至剩一個去做 merge，有一點值得留意是分段時找出中間往後一個肯定剩兩個要分出兩個來。
* 合併時找出符合的的節點，再放進去去。
* 再把有剩的接下來，直接或操作，因為其中一方必為 NULL。

## list_sort & q_sort
### list_sort
* 從比較次數方面的優化，這是以均衡分佈為前題，首先是相同大小的 merge，再來就是兩兩合到最後，最差情況為2:1。
* 這歸功於他 merge 的方法，有相同大小的才合併，因而不會出現過大的差距，而他發現這個規律能用一個位元流表示，我不太清楚想法的先後，但我覺得位元流的特性引發他的思考。
* 而這樣的合併方法的結果就是每一個合併過的 list 大小為二的次方，大小能和快取對齊，對快取友善。
* 還有一點就是，他不需要知到 list 的大小，直接 visit 到 NULL，省下 visit 的時間。

### q_sort
同上

### perf of this

## 參考資訊
* 共筆格式參考：[共筆示範](https://hackmd.io/@cccccs100203/linux2020-lab0)