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

開發過程

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

jserv

q_new

目標： 建立一個空佇列

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

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 同學的程式碼

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 同學的程式碼

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 進行刪除