# 2023q1 Homework1 (lab0)
contributed by < `PlusThousand0107` >

## 開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ 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):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         4100.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4399.99

## 開發過程

:::danger
開發紀錄著重於你的想法、觀察、中間遇到的難題和你如何克服，程式碼應是輔助性質，列出最關鍵的部分即可。
:notes: jserv
:::

### q_new
目標： 建立一個空佇列

:::danger
注意書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv
:::

流程：
1. 先用 `malloc` 對宣告一個大小為 `list_head` 的記憶體空間
2. 再利用 `INIT_LIST_HEAD()` 做初始化

### q_free
目標： 釋放佇列佔用的記憶體
流程：
1. 先確認傳入的 `list_head *l` 是否為 NULL，如果是的話就直接結束
2. 利用 `list_for_each_entry_safe` 進行走訪，每過一個節點就用 `list_del` 做移除並釋放該節點空間，程式碼如下所示

list_for_each_entry_safe (cur, n, l, list) {
    list_del(&cur->list);
    q_release_element(cur);
}

3. 都走訪完成最後才釋放 `*l` 的記憶體空間

### q_size
目標： 計算佇列中的節點數量
流程：
1. 先確認傳入的 `list_head *q_head` 是否為 NULL，如果是就直接回傳0
2. 宣告變數 `len` 紀錄當前節點數量，並用 `list_for_each` 進行走訪，每過一個節點就遞增 `len`
3. 都走訪完後會回傳 `len`

### q_insert_head
目標： 在佇列開頭插入新節點
流程：
1. 先用 `malloc` 對宣告一個大小為 `element_t` 的記憶體空間，並將位址傳給宣告的指標變數 `node`
2. 用 `strdup` 將字串複製給 `node->value`
3. 用 `list_add` 將節點加在 `head` 的後面一位，詳細程式碼如下所示

element_t *node = malloc(sizeof(*node));
node->value = strdup(s);
list_add(&node->list, head);

### q_insert_tail
目標： 在佇列結尾處插入新節點
流程：
1. 先用 `malloc` 對宣告一個大小為 `element_t` 的記憶體空間，並將位址傳給宣告的指標變數 `node`
2. 用 `strdup` 將字串複製給 `node->value`
3. 用 `list_add_tail` 將節點加在佇列最尾端，除了將 `list_add` 改成了 `list_add_tail` 外，其餘均與 `q_insert_head` 相同

### q_swap
目標： 將佇列中鄰近的節點兩兩交換
流程：
1. 宣告一個指標變數 `a` ，並指向 `head->next` ，再宣告一個指標變數 `b` ，使其指向 `head->next->next`
2. 只要 `a` 和 `b` 沒有指回到 `head` ，就會修改它們指的對象，將原先指向 `a` 的改成指向 `b`，指向 `b` 的改成指向 `a` ，詳細程式碼如下所示

while (a != head && b != head) {
    a->prev->next = b;
    a->next = b->next;
    b->prev = a->prev;
    a->prev = b;
    b->next->prev = a;
    b->next = a;

    a = a->next;
    b = a->next;
}

### q_reverse
目標： 將鏈結串列以反向順序重新排列
流程：
1. 宣告一個指標變數 `a` ，並指向 `head` ，再宣告一個指標變數 `b` ，使其指向 `head->next`
2. 主要操作以修改 `a` 的指標為主，將原本指向 `next` 的改成指向 `prev` ，將原本指向 `prev` 的改成指向 `next` ，以此方法將順序反轉，直到 `a` 又回到 `head` 為止，詳細程式碼如下所示

do {
    a->next = a->prev;
    a->prev = b;
    a = b;
    b = a->next;
} while (a != head);

### q_remove_head
目標： 將佇列開頭的節點移除 (remove)
流程：
1. 要移除的第一個元素為 `head->next`
2. 移除後須將 `head->next->value` 複製到 `buffer` 中，詳細程式碼如下所示

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

### q_remove_tail
目標： 將佇列結尾的節點移除 (remove)
流程：
1. 要移除的第一個元素為 `head->prev`
2. 移除後須將 `head->prev->value` 複製到 `buffer` 中，除了將 `head->next` 改成了 `head->prev` 外，其餘均與 `q_remove_head` 相同

### q_delete_mid
目標： 將佇列中間的節點刪除 (delete)
流程：
1. 宣告一個指標變數 `a` ，並指向 `head->next` ，再宣告一個指標變數 `b` ，使其指向 `head->prev`
2. 讓 `a` 往前走，再讓 `b` 往後走，直到 `a != b` 或者 `a->next != b` ，表示已找出中間節點，程式碼如下所示

while ((a != b) && (a->next != b)) {
    a = a->next;
    b = b->prev;
}

3. 刪除中間的節點並釋放其記憶體空間

### q_reverseK
目標： 將鏈結串列以每 k 個節點為一組，進行反向順序重新排列
流程：
1. 先確認傳入的 `list_head *head` 不為 NULL 且 k 不能小於 1 ，如果有一個不符就直接結束
2. 宣告變數 `cnt` 紀錄每組節點數量，用 `list_for_each_safe` 進行走訪，每過一個節點就遞增 `cnt`
3. 當 `cnt` 等於 k 時，會用 `list_cut_position` 進行切斷，並用上面實作出的 `q_reverse` 反轉順序，最後再用 `list_splice_init` 接合回原本的鏈結串列，詳細程式碼如下所示，這裡參考到了 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_reverseK-%E5%AF%A6%E4%BD%9C) 同學的程式碼

list_for_each_safe (cur, safe, head) {
    cnt++;
    if (cnt == k) {
        list_cut_position(&h, temp, cur);
        q_reverse(&h);
        list_splice_init(&h, temp);
        cnt = 0;
        temp = safe->prev;
    }
}

### q_delete_dup
目標： 再**已排序**的狀況下，刪除佇列中內容重複的節點
流程：
1. 先確認傳入的 `list_head *head` 是否為 NULL，如果是就直接回傳 false
2. 用 `list_for_each_entry_safe` 進行走訪，並用 `strcmp` 判斷元素的值是否相同，詳細程式碼如下所示，這裡參考到了 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_delete_dup) 同學的程式碼

list_for_each_entry_safe (it, safe, head, list) {
    if (&safe->list != head && strcmp(safe->value, it->value) == 0)
        continue;

    if (it->list.prev != cut) {
        LIST_HEAD(temp);
        list_cut_position(&temp, cut, &it->list);
        list_splice(&temp, &trash);
    }
    cut = safe->list.prev;
}

3. 最後會用 `list_for_each_entry_safe` 走訪蒐集到的重複元素，並用 `q_release_element` 進行刪除