# 2022q1 Homework1 (lab0)
contributed by < `raysun0729` >
###### tags: `linux2022`

## 實驗環境

$ 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:                   39 bits physical, 48 bits virtual
CPU(s):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              2
Core(s) per socket:              2
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                     6
Model:                          61
Model name:                     Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz
Stepping:                       4
CPU MHz：                       1752.500
CPU max MHz:                    2700.0000
CPU min MHz:                    500.0000
BogoMIPS:                       4389.82
Virtualization:                 VT-x
L1d cache:                      64 KiB
L1i cache:                      64 KiB
L2 cache:                       512 KiB
L3 cache:                       3 MiB
NUMA node0 CPU(s)：             0-3

## queue.h
### 結構體說明

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

`struct list_head` 為 `list.h` 中定義的結構體，這個結構體中包含了 `prev` 與 `next` 兩個定義於 `list_head` 的指標，分別藉由指向前、後一個節點，以便實作出 circular doubly-linked list。

typedef struct {
    char *value;
    struct list_head list;
} element_t;

`struct element_t` 為 `queue.h` 中定義的結構體，而在這個結構體中，除了定義 `value` 來儲存資料之外，也定義了結構體 `list_head` 的變數，並讓 `list_head` 中定義的 `prev` 以及 `next` 分別指向前、後一個佇列節點中的 `list`，以便在佇列中的各個節點間移動。
## queue.c
### q_release_element

void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

### q_new

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

* ```INIT_LIST_HEAD(struct list_head *list)```用來進行list_head的初始化
* 為什麼要檢查q ! NULL? 根據[GNU C Library](https://www.gnu.org/software/libc/manual/html_node/Basic-Allocation.html) ```malloc```會在 size 為 0 或是無法分配空間時回傳 null

### q_free

void q_free(struct list_head *l)
{
    if (!l)
        return; /* queue is NULL */
    element_t *cur, *next;
    /* del, the element to be free. next, the next element of del */
    list_for_each_entry_safe (cur, next, l, list) {
        list_del(&cur->list);
        q_release_element(cur);
    }
    free(l);
    return;
}

* 釋放 queue 前務必先檢查 queue 是否為 NULL。之後，先釋放 queue 上的每個 element 所用的空間(包含字串 allocate 的)，再釋放掉 queue 本身。
* q_free要釋放佇列的所有空間，先用```list_for_each_entry_safe```走訪佇列中所有節點
* ```list_del```將節點移出佇列，```q_release_element```用以釋放空間
* 最後，釋放佇列```l```
### q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false; /* queue 不應該為 NULL */
    
    element_t *node = malloc(sizeof(element_t));
    
    if (!node)
        return NULL; /* could not allocate space */
    
    int len = strlen(s) + 1;
    
    node->value = malloc(len);
    
    if (!node->value) {
        free(node);
        return NULL; /* could not allocate space */
    }
    
    memcpy(node->value, s, len);
    
    INIT_LIST_HEAD(&node->list);
    
    list_add(&node->list, head); /* add element to queue head
    return true;
}

* 先建立一個新的 element_t。因為 element_t 裡的 value 也是指標，所以要供 value 一段空間來存字串，故使用了 ```strlen()``` 來計算需要多少 byte 來存 value。因為要把 '\0' 也算進去，所以要再 +1。
* 也就是以```malloc```取得字串```s```大小的記憶體空間，若失敗則釋放```node```的空間
* 配置完 value 需要的空間後就將字串複製過去，```memcpy()``` 從原本的指標 s 複製到新的指標 value 。
* 最後透過```INIT_LIST_HEAD```進行節點初始化，及用```list_add```將節點加入佇列的頭
### q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false; /* queue is NULL */
    
    element_t *node = malloc(sizeof(element_t));
    
    if (!node)
        return NULL; /* could not allocate space */
    
    int len = strlen(s) + 1;
    
    node->value = malloc(len);
    
    if (!node->value) {
        free(node);
        return NULL; /* could not allocate space */
    }
    
    memcpy(node->value, s, len);
    
    INIT_LIST_HEAD(&node->list);
    
    list_add_tail(&node->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 || q_size(head) == 0)
        return NULL;

    element_t *node = list_entry(head->next, element_t, list);
    list_del(head->next);
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return node;
}

* Remove 之前，首先要檢查 queue 是否為空，以及參數中的 sp 是否為具有空間的 buffer。q->head 指到的 element 是移除的目標，根據要求，先把目標中儲存字串複製到 sp 中，調整 q->head 指到的地方後，再釋放原本 q->head 的 element 所使用的空間。
* 如果佇列不為空，利用`list_first_entry()`取得佇列的第一個元素 node，用`list_del()`將這個 node 移除
* 再使用 `strncpy` copied `bufsize - 1` 個字元至 sp，最後回傳移除的節點node。
* 程式改善: 將`list_entry()`改為`list_first_entry(head, element_t, list)` `list_del()`改為`list_del_init(&node->list)`

### q_remove_tail

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || q_size(head) == 0)
        return NULL;
    element_t *node = list_entry(head->prev, element_t, list);
    //ptr redirect
    list_del(head->prev);
    // to copy a string
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return node;
}

* 與前題類似，差別在於本題利用```list_entry```取得last node再將其以```list_del```自佇列刪除
* 程式改善: 以`list_last_entry()`可以直接取得list中的last element取代`list_entry()`

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

### q_size

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

* 參考[作業要求](https://hackmd.io/@sysprog/linux2022-lab0#%E7%89%9B%E5%88%80%E5%B0%8F%E8%A9%A6)用```list_empty``` api，如果佇列為空，直接回傳0，否則透過```list_for_each```走訪所有節點，每經過一點將size+1
### q_delete_mid

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    struct list_head *front = head->next;
    struct list_head *back = head->prev;

    while (front != back) {
        back = back->prev;
        if (front == back)
            break;
        front = front->next;
    }

    list_del(front);
    q_release_element(list_entry(front, element_t, list));
    return true;
}

* 想法為藉由兩個指標*front, *back，一個從前往後走，一個從後往前走，當`front == back`(strlen is odd)時，即已走到中點，再將其刪去即可；若`front->next == back`(長度為偶數)，刪去front指標
### q_delete_dup

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    bool flag = false;
    element_t *cur, *safe;
    list_for_each_entry_safe (cur, safe, head, list) {
        if (&safe->list != head && !strcmp(cur->value, safe->value)) {
            list_del(&cur->list);
            q_release_element(cur);
            flag = true;
        } else if (flag) {
            list_del(&cur->list);
            q_release_element(cur);
            flag = false;
        
    }
    return true;
}

* 以```list_for_each_entry_safe```來traverse每個節點
* 用```strcmp```比較當前的節點與下一個節點之value是否相同，如果相同會return 0，否則return 非0
* 若value相同且目前節點不是最後一個，則刪除目前節點。
* 以```flag```紀錄走到的節點是否與已刪除之節點有相同之value
* 更新版本:因為list已排序，所以直接比較相鄰的點是否相同

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    element_t *cur, *safe;
    list_for_each_entry_safe (cur, safe, head, list) {
        if (&safe->list != head && !strcmp(cur->value, safe->value)) {
            list_del(&(cur->list));
            q_release_element(cur);
        }
    }
    return true;
}

### q_swap

void q_swap(struct list_head *head)
{
    struct list_head *prev, *cur;
    list_for_each_safe (prev, cur, head) {
        list_move_tail(cur, prev);
        cur = prev->next;
    }
}

* ```list_move_tail```可直接將2個節點交換位置
### q_reverse

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *cur = head;
    struct list_head *next = cur->next;
    do {
        cur->next = cur->prev;
        cur->prev = next;
        cur = next;
        next = cur->next;
    } while (cur != head);
}

* 想法為traverse整個佇列，將每個節點的prev及next交換，即完成整個佇列的reverse
### q_sort
* Linux Kernel API 中已有`list_sort`，該 function implements `merge_sort`，所以複雜度為O(nlg(n))

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    list_sort(NULL, head, sort_comp);
}

* 因為quicksort的複雜度可能到O(n^2)，所以這邊要用Mergesort來實作。參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/YA7RMqd6RE2UL8OmmjU9PQ?view)中案例研討的題目解答

/*
 * 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.
 */
struct list_head *sep_list(struct list_head *head);
struct list_head *merge_list(struct list_head *left, struct list_head *right);

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *new_head = head->next;
    list_del(head);
    new_head = sep_list(new_head);
    list_add_tail(head, new_head);
}

struct list_head *sep_list(struct list_head *head)
{
    if (head == head->next)
        return head;

    struct list_head *fast = head;
    struct list_head *mid = head->prev;
    while (fast != mid && fast->next != mid) {
        fast = fast->next;
        mid = mid->prev;
    }

    struct list_head *left = head;
    struct list_head *right = mid;
    struct list_head *node = left->prev;

    if (list_is_singular(left)) {
        list_del_init(left);
        list_del_init(right);

    } else {
        left->prev = right->prev;
        left->prev->next = left;
        node->next = right;
        right->prev = node;
    }
    return merge_list(sep_list(left), sep_list(right));
}

struct list_head *merge_list(struct list_head *left, struct list_head *right)
{
    struct list_head *head = NULL;
    struct list_head *tmp = NULL;

    left->prev->next = NULL;
    right->prev->next = NULL;

    while (left || right) {
        if (!right ||
            (left && strcmp(list_entry(left, element_t, list)->value,
                            list_entry(right, element_t, list)->value) < 0)) {
            if (!tmp) {
                head = tmp = left;
                left = left->next;
                if (left)
                    left->prev = tmp->prev;
                INIT_LIST_HEAD(tmp);
            } else {
                tmp = left;
                left = left->next;
                if (left)
                    left->prev = tmp->prev;
                list_add_tail(tmp, head);
            }
        } else {
            if (!tmp) {
                head = tmp = right;
                right = right->next;
                if (right)
                    right->prev = tmp->prev;
                INIT_LIST_HEAD(tmp);
            } else {
                tmp = right;
                right = right->next;
                if (right)
                    right->prev = tmp->prev;
                list_add_tail(tmp, head);
            }
        }
    }
    return head;
}