---
# System prepended metadata

title: 2022q1 Homework1 (lab0)

---

# 2022q1 Homework1 (lab0)
contributed by < [Nomad1230](https://github.com/Nomad1230) >



## 實驗環境
```
$ 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
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  1
  On-line CPU(s) list:   0
Vendor ID：           GenuineIntel
  Model name:            Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
    CPU family：           6
    Model：               158
    Thread(s) per core：     1
    Core(s) per socket：     1
    Socket(s):           1
    Stepping：               10
    BogoMIPS:            4608.00
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mc
                         a cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall n
                         x rdtscp lm constant_tsc rep_good nopl xtopology nonsto
                         p_tsc cpuid tsc_known_freq pni pclmulqdq monitor ssse3 
                         cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave a
                         vx rdrand hypervisor lahf_lm abm 3dnowprefetch invpcid_
                         single pti fsgsbase avx2 invpcid rdseed clflushopt md_c
                         lear flush_l1d
Virtualization features: 
  Hypervisor 供應商：    KVM
  虛擬型態：             全部
Caches (sum of all):     
  L1d:                   32 KiB (1 instance)
  L1i:                   32 KiB (1 instance)
  L2:                    256 KiB (1 instance)
  L3:                    8 MiB (1 instance)
NUMA:                    
  NUMA 節點：            1
  NUMA node0 CPU(s)：    0
Vulnerabilities:         
  Itlb multihit:         KVM: Mitigation: VMX unsupported
  L1tf:                  Mitigation; PTE Inversion
  Mds:                   Mitigation; Clear CPU buffers; SMT Host state unknown
  Meltdown:              Mitigation; PTI
  Spec store bypass:     Vulnerable
  Spectre v1:            Mitigation; usercopy/swapgs barriers and __user pointer
                          sanitization
  Spectre v2:            Mitigation; Full generic retpoline, STIBP disabled, RSB
                          filling
  Srbds:                 Unknown: Dependent on hypervisor status
  Tsx async abort:       Not affected

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

[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:
* q_new: 建立新的「空」佇列;
* q_free: 釋放佇列所佔用的記憶體;
* q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
* q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
* q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
* q_release_element: 釋放特定節點的記憶體空間;
* q_size: 計算目前佇列的節點總量;
* q_delete_mid: 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
* q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
* q_swap: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
* q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
* q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;

## 開發過程

### q_new
:::spoiler 程式碼

```c
struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    // check if malloc success
    if (!new)
        return NULL;
    else {
        INIT_LIST_HEAD(new);
        return new;
    }
}
```
:::

---

### q_free
:::spoiler 程式碼

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

---

### q_insert_head
:::spoiler 程式碼

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

---

### q_insert_tail
:::spoiler 程式碼

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


---

### q_remove_head
:::spoiler 程式碼

```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || head->next == head)
        return NULL;
    else {
        struct list_head *del = head->next;
        list_del_init(head->next);
        element_t *del_ele = list_entry(del, element_t, list);
        if (sp) {
            strncpy(sp, del_ele->value, bufsize - 1);
            *(sp + bufsize - 1) = '\0';
        }
        return del_ele;
    }
}
```
:::
---

### q_remove_tail
:::spoiler 程式碼

```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || head->next == head)
        return NULL;
    else {
        struct list_head *del = head->prev;
        list_del_init(head->prev);
        element_t *del_ele = list_entry(del, element_t, list);
        if (sp) {
            strncpy(sp, del_ele->value, bufsize - 1);
            *(sp + bufsize - 1) = '\0';
        }
        return del_ele;
    }
}
```
:::


---

### q_size
:::spoiler 程式碼

```c
int q_size(struct list_head *head)
{
    if (!head || head->next == head)
        return 0;
    int count = 0;
    struct list_head *node;
    list_for_each (node, head) {
        count++;
    }
    return count;
}
```
:::


---

### q_delete_mid
:::spoiler 程式碼

```c
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || head->next == head)
        return false;
    element_t *del;
    struct list_head **indir = &head;
    struct list_head *temp = head->prev;
    temp->next = NULL;
    for (struct list_head *fast = head; fast && fast->next;
         fast = fast->next->next)
        indir = &(*indir)->next;
    temp->next = head;
    del = list_entry(*indir, element_t, list);
    list_del_init(*indir);
    q_release_element(del);
    return true;
}
```
:::


---

### q_delete_dup
:::spoiler 程式碼

```c
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;
    element_t *node, *safe;
    list_for_each_entry_safe (node, safe, head, list) {
        // if &safe->list == head, safe->value will dereference a null pointer
        if (&safe->list != head) {
            if (node->value && safe->value) {
                if (!strcmp(node->value, safe->value)) {
                    list_del(&node->list);
                    q_release_element(node);
                }
            }
        }
    }
    return true;
}
```
:::


---

### q_swap
:::spoiler 程式碼

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


---

### q_reverse
原理是將每一個 list_head 中的 prev 跟 next 互相交換，當每一個 node 的 prev 跟 next 都交換完成，即可達成整個 list 的 reverse 。

先把 Linked list 中首尾相接的兩條指標設成NULL，讓 while 迴圈操作時可以順利中止並避免出錯，當最後一個 node 交換完成之後跳出迴圈，並把剛才移除的指標重新連結上。

:::spoiler

```c
void q_reverse(struct list_head *head)
{
    if (!head || head->next == head)
        return;
    struct list_head *node = head, *temp;
    head->prev->next = NULL;
    head->prev = NULL;
    while (1) {
        temp = node->next;
        node->next = node->prev;
        node->prev = temp;
        if (!node->prev)
            break;
        else
            node = node->prev;
    }
    node->prev = head;
    head->next = node;
}
```
:::

---

### q_sort
:::spoiler 程式碼

```c
void q_sort(struct list_head *head) 
{
    if (!head || head->next == head || head->next->next == head)
        return;
    int top = 0;
    int listsSize = 0;
    struct list_head *stack[10000] = {NULL};
    struct list_head *lists[100000] = {NULL};
    stack[top] = head->next;
    head->prev->next = NULL;
    INIT_LIST_HEAD(head);

    // divide to single node
    while (top >= 0) {
        struct list_head *left = stack[top--];

        if (left) {
            struct list_head *slow = left;
            struct list_head *fast;

            for (fast = left->next; fast && fast->next; fast = fast->next->next)
                slow = slow->next;
            struct list_head *right = slow->next;
            slow->next = NULL;

            stack[++top] = left;
            stack[++top] = right;
        } else {
            stack[top]->prev = stack[top];
            stack[top]->next = NULL;
            lists[listsSize++] = stack[top--];
        }
    }

    // merge K sorted lists
    while (listsSize > 1) {
        for (int i = 0, j = listsSize - 1; i < j; i++, j--)
            lists[i] = mergeTwoLists(lists[i], lists[j]);
        listsSize = (listsSize + 1) / 2;
    }
    struct list_head *node = lists[0];
    while (node->next) {
        node->next->prev = node;
        node = node->next;
    }
    node->next = head;
    head->next = lists[0];
    lists[0]->prev = head;
    head->prev = node;
}
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = (strcmp(list_entry(L1, element_t, list)->value, 
            list_entry(L2, element_t, list)->value) < 0) ? &L1: &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    if (!L1) {
        *ptr = L2;
        return head;
    }
    if (!L2) {
        *ptr = L1;
        return head;
    }
    return head;
}
```
:::

:::spoiler
```c
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = (strcmp(list_entry(L1, element_t, list)->value,
                       list_entry(L2, element_t, list)->value) < 0)
                   ? &L1
                   : &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((u_int64_t) L1 | (u_int64_t) L2);
    return head;
}

static struct list_head *mergesort(struct list_head *head)
{
    if (!head || !head->next)
        return head;

    struct list_head *slow = head, *fast = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }

    slow->prev->next = NULL;

    struct list_head *left = mergesort(head);
    struct list_head *right = mergesort(slow);
    return mergeTwoLists(left, right);
}

/*
 * 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 || head->next == head || head->next->next == head)
        return;
    head->prev->next = NULL;
    head->next = mergesort(head->next);
    struct list_head *node = head->next;
    node->prev = head;
    while (node->next) {
        node->next->prev = node;
        node = node->next;
    }
    node->next = head;
    head->prev = node;
}
```
:::