2022q1 Homework1 (lab0)

contributed by < Andy240881 >

作業要求

實驗環境

$ gcc --version
gcc (Ubuntu 6.5.0-2ubuntu1~18.04) 6.5.0

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              12
On-line CPU(s) list: 0-11
Thread(s) per core:  2
Core(s) per socket:  6
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               158
Model name:          Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
Stepping:            10
CPU MHz：            2267.463
CPU max MHz:         3201.0000
CPU min MHz:         800.0000
BogoMIPS:            6399.96
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            12288K
NUMA node0 CPU(s):   0-11

開發過程

q_new

檢查 malloc 是否成功。
觀摩同學 laneser 的開發紀錄後發現可以使用 INIT_LIST_HEAD() 使得程式碼更加簡潔。

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

q_free

檢查 l 是否為空。
利用 list.h 中的 list_for_each_entry_safe() 迭代刪除目標，並使用 queue.c 中既有的 q_release_element 釋放 queue 中的每個 node。
queue 的 head 也要記得釋放空間。

void q_free(struct list_head *l)
{
    if (l == NULL) {
        return;
    }
    element_t *iter, *tmp;

    list_for_each_entry_safe (iter, tmp, l, list)
        q_release_element(iter);
    free(l);
}

q_insert_head

檢查 head 是否為空。
建立要插入的 node，並將 s 複製到對應欄位。
使用 list_add 將新的節點連結至 queue 的開頭。

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

q_insert_tail

將 q_insert_head 中的 list_add 抽換成list_add_tail。

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

q_remove_head

需要加上 cppcheck-suppress nullPointer 的註解來關閉 cppcheck 的 null pointer 錯誤。
一開始誤以為 queue 的每個節點皆是 element_t ，但事實上 head 是不含 value 欄位的 list_head，因此在使用 container_of() 時第一個參數要填 head->next 才會得到正確的節點位址。
使用 list_del_init 移除queue的第一個節點，並讓該節點的 prev 與 next 指向自己。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    // cppcheck-suppress nullPointer
    element_t *q = container_of(head->next, element_t, list);
    if (!q) {
        return NULL;
    }
    list_del_init(head->next);
    if (sp != NULL) {
        strncpy(sp, q->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return q;
}

q_remove_tail

將 q_remove_head 中的操作對象 head->next (第一個節點) 換成 head->prev (最後一個節點) 即可。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    // cppcheck-suppress nullPointer
    element_t *q = container_of(head->prev, element_t, list);
    if (!q) {
        return NULL;
    }
    list_del_init(head->prev);
    if (sp != NULL) {
        strncpy(sp, q->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return q;
}

q_size

int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}

q_delete_mid

利用 q_size() 取得 queue 的長度。
使用 list.h 中的 list_for_each_entry_safe() 遍歷 queue 並刪除第 ⌊n / 2⌋ 個節點。
先 remove 節點後，再delete。

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    int len = q_size(head);
    if (len == 0)
        return NULL;
    int i = 0;
    element_t *iter, *tmp;
    list_for_each_entry_safe (iter, tmp, head, list)
        if (i != len / 2 ) {
            i++;
        } else {
            list_del_init(&iter->list);
            q_release_element(iter);
            break;
        }
    return true;
}

q_reverse

void q_reverse(struct list_head *head) 
{
    if (head == NULL)
        return;
    struct list_head *pre = head->prev;
    struct list_head *current = head;
    struct list_head *next = NULL;
    next = current->next;
    current->next = pre;
    current->prev = next;
    pre = current;
    current = next;
    while (current != head) {
        next = current->next;
        current->next = pre;
        current->prev = next;
        pre = current;
        current = next;
    }
}

思考 circular doubly-linked list 的特性，上述程式碼可更精簡，並善用 Linux List APIs

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

利用 circular doubly-linked list 可以反向遍歷的特性，從最後一個節點開始，以反向將每個節點用 list_move_tail 放到 list 的最後面，達到 reverse 的效果。

void q_reverse(struct list_head *head)
{
    if (head == NULL)
        return;
    if (list_empty(head))
        return;
    struct list_head *current = head->prev;
    struct list_head *next = NULL;
    next = current->prev;
    list_move_tail(current, head);
    current = next;
    while (current != head) {
        next = current->prev;
        list_move_tail(current, head);
        current = next;
    }
}

上方程式碼尚可更精簡，請繼續改進

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

參考同學 kevinshieh0225 的做法，使用 do-while 讓程式碼更加精簡。
加入 singular 的判斷，若 list 長度為 1 ，則不用 reverse 。

void q_reverse(struct list_head *head)
{
    if (head == NULL || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *current = head->prev;
    do{
        struct list_head *next = current->prev;
        list_move_tail(current, head);
        current = next;
    }while (current != head); 
}

q_swap

遍歷 list 的每個節點，且將節點倆倆交換（每個節點僅被交換一次）。
while 迴圈的終止條件會分別因為list長度為奇數或偶數而有不同的情況。

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *current = head->next;
    struct list_head *next = NULL;
    while (current != head && current->next != head) {
        next = current->next;
        list_move_tail(next, current);
        current = current->next;
    }
}

q_delete_dup

原本沒想清楚，只有單純比較相鄰的兩個節點，若相同則刪除，但沒有考慮到有兩個以上的節點重複的狀況。
參考同學 laneser的做法，用 flag 紀錄是否有重複的情形發生。
遍歷 list 時，若 flag = 1 （代表自己與上個節點相同）或是與隔壁節點 value 相同，就會刪除目前遍歷到的節點。

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    if (list_is_singular(head))
        return true;
    element_t *iter, *tmp;
    int flag = 0;
    list_for_each_entry_safe (iter, tmp, head, list)
        if ((iter->list.next != head) &&
            !strcmp(iter->value,
                    // cppcheck-suppress nullPointer
                    list_entry(iter->list.next, element_t, list)->value)) {
            list_del(&iter->list);
            q_release_element(iter);
            flag = 1;
        } else if (flag) {
            list_del(&iter->list);
            q_release_element(iter);
            flag = 0;
        }
    return true;
}

q_sort

利用 linux 現有的 list_sort。
TODO: 了解 linux 的 list_sort 原理。

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

2022q1 Homework1 (lab0)

實驗環境

開發過程

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_reverse

q_swap

q_delete_dup

q_sort

Read more

C 語言面試筆記

現代處理器設計：原理和關鍵特徵（筆記）

Linux 記憶體管理筆記