2022q1 Homework1 (lab0)

contributed by < blue76815 >

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
架構：				86_64
CPU 作業模式：			32-bit, 64-bit
Byte Order:			Little Endian
Address sizes:			39 bits physical, 48 bits virtual
CPU(s):				12
On-line CPU(s) list:		0-11
每核心執行緒數：			2
每通訊端核心數：			6
Socket(s):			1
NUMA 節點：			1
供應商識別號：			GenuineIntel
CPU 家族：			6
型號：				158
Model name:			Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
製程：				10
CPU MHz：			900.049
CPU max MHz:			4100.0000
CPU min MHz:			800.0000
BogoMIPS:			4399.99
虛擬：				VT-x
L1d 快取：			192 KiB
L1i 快取：			192 KiB
L2 快取：			1.5 MiB
L3 快取：			9 MiB
NUMA node0 CPU(s)：		0-11

作業要求

清單

`queue.c` 實作

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
q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;

pointer to pointer 參考 Linked lists, pointer tricks and good taste 寫法

實做 queue.c 時參閱

linux/list.h
The Linux Kernel API
内核双链表遍历：带 safe 和不带 safe 的区别
Bidirect-list
你所不知道的 C 語言: linked list 和非連續記憶體
- Linked list 在 Linux 核心原始程式碼

q_new

此操作為建立新的「空」佇列，因此是建立 struct list_head head 頭端，而不是新建一個 element_t 節點

配置一個新 head
若配置失敗則回傳 NULL
調用 The Linux Kernel API INIT_LIST_HEAD()初始化head

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

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

已修正

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

q_free

調用 list_for_each_entry_safe 尋訪 struct list_head 環狀佇列
list_del() 只是將 node 從其原本的 linked list 連接移除
還得用 q_release_element(node) 才能將節點記憶體釋放

void q_free(struct list_head *l)
{
    if (l == NULL)
        return;

    element_t *node = NULL, *tmp_node = NULL;
    list_for_each_entry_safe (node, tmp_node, l, list) {
        list_del(&node->list);
        q_release_element(node);
    }
    free(l);
}

q_insert_head

malloc 配置新節點
將字串資料複製到 node->value
list_add() 將指定的 node 插入到 linked list struct list_head head 的開頭

bool q_insert_head(struct list_head *head, char *s)
{
    if (s == NULL || head == NULL)
        return false;
    element_t *node = malloc(sizeof(element_t));
    if (node == NULL)
        return false;

    node->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
    if (node->value == NULL) {
        q_release_element(node);
        return false;
    }
    memset(node->value, '\0', sizeof(char) * strlen(s) + 1);
    memcpy(node->value, s, sizeof(char) * strlen(s));
    list_add(&node->list, head);
    return true;
}

注意事項

節點插入data 資料時，得用 element_t 才能配置

typedef struct {
    /* Pointer to array holding string.
     * This array needs to be explicitly allocated and freed
     */
    char *value;
    struct list_head list;
} element_t;

圖片來源：你所不知道的 C 語言: linked list 和非連續記憶體

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

要訪問 linked list 各別節點內的資料，可調用

list_entry(node, type, member)
list_first_entry(head, type, member)
list_last_entry(head, type, member)

配置 strlen(s) + 1 是因為 Linux Programming Interface 查詢 strlen 有提到

DESCRIPTION

The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0').

RETURN VALUE

The strlen() function returns the number of bytes in the string pointed to by s.

strlen() 計算字元個數到 null byte ('\0') 就停止，因此字數不包含 null byte ('\0')。多加一格，是為了在字串結尾多填一格 NULL 值， 避免 strlen(const char str) 計算字串長度時，把字尾相鄰的記憶體殘值也列入字元個數

q_insert_tail

malloc 配置新節點
將字串資料複製到 node->value
差別只在插入 link-list 時，得用 list_add_tail(&node->list, head); 插入到尾端

bool q_insert_tail(struct list_head *head, char *s)
{
    if (head == NULL || s == NULL)
        return false;

    element_t *node = malloc(sizeof(element_t));

    if (node == NULL)
        return false;


    node->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
    if (node->value == NULL) {
        q_release_element(node);
        return false;
    }
    memset(node->value, '\0', sizeof(char) * strlen(s) + 1);
    memcpy(node->value, s, sizeof(char) * strlen(s));
    list_add_tail(&node->list, head);
    return true;
}

q_remove_head

調用 list_first_entry() ，取得 linked list 的開頭

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;

    element_t *node = list_first_entry(head, element_t, list);

    list_del_init(&(node->list));

    if (sp) {
        size_t length = strlen(node->value) + 1;
        length = length > bufsize ? bufsize : length;
        memset(sp, '\0', length);
        memcpy(sp, node->value, length - 1);
    }
    return node;
}

q_remove_tail

調用 list_last_entry() ，取得 linked list 的結尾

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;

    element_t *node = list_last_entry(head, element_t, list);

    list_del_init(&(node->list));

    if (sp) {
        size_t length = strlen(node->value) + 1;
        length = length > bufsize ? bufsize : length;
        memset(sp, '\0', length);
        memcpy(sp, node->value, length - 1);
    }

    return node;
}

q_release_element

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

q_size

調用 list_for_each_entry_safe
尋訪 struct list_head 環狀佇列計次

int q_size(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return 0;

    int size = 0;
    struct list_head *node = NULL;

    list_for_each (node, head) {
        size++;
    }
    return size;
}

q_delete_mid

第ㄧ版

直接用 q_size(head) 取得佇列長度
除以2就能求出長度一半，可作為計算要移動節點幾次才到達 mid_head
到達 mid_head 後，用 list_entry() 取得節點內容刪除

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (head == NULL || list_empty(head))
        return false;
    int mid_length = q_size(head) / 2;
    struct list_head *mid_head = head->next;
    while (mid_length > 0) {
        mid_head = mid_head->next;
        mid_length--;
    }

    element_t *ele_node = list_entry(mid_head, element_t, list);
    list_del(mid_head);
    free(ele_node->value);
    free(ele_node);
    return true;
}

第二版

參考金刀的算法小册子 0876-链表的中间结点改成快慢兩種指標做 Floyd’s Cycle detection

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (head == NULL || list_empty(head))
        return false;
    
    struct list_head *fast = head->next;
    struct list_head *slow = head->next;
    while (fast!=head && fast->next !=head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    element_t *ele_node = list_entry(slow, element_t, list);
    list_del(slow);
    free(ele_node->value);
    free(ele_node);
    return true;
}

q_delete_dup

參考 SmallHanley 同學的方法

檢查 head 是否為 NULL，是則回傳 false。
用一個 bool 值 last_same_node 判斷相鄰重複的節點，是否已經刪除到最後一個。
呼叫 list_for_each_safe (node, tmp, head) 走訪每個節點
走訪節點時，此node內是儲存某 element_t 節點的記憶體位址，得用 list_entry(node, element_t, list) 和 list_entry(node, element_t, list) 才能解析出 element_t 節點內的 value 成員
判斷此 element_t 節點和下一個 element_t 節點的 value 是否相同，是則將 last_same_node 設為 true，然後從串列中移除此節點並釋放相關空間。
若 value 不同，而 last_same_node 依然是 true，代表此節點是相鄰重複的節點中的最後一個，將 last_same_node 設回 false 並釋放相關空間。例如 link-list 1==>1==>1==>2==>3 當刪除到剩 1==>2==>3 時，此 1 節點就是相鄰重複節點中的最後一個

list_entry 介紹内核双链表遍历：带 safe 和不带 safe 的区别

#define list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)


#define list_for_each_safe(pos, n, head) \
        for (pos = (head)->next, n = pos->next; pos != (head); \
                pos = n, n = pos->next)
从两个接口的定义差别只看出，list_for_each_safe() 的定义多了一个参数 n，这个参数 n 用于缓存下一个节点，其余并没有什么逻辑上的差异。

所以寫 list_for_each_safe (node, tmp, head) 相當於用 node 節點跑 for 迴圈

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (head == NULL || list_empty(head))
        return false;
    struct list_head *node, *tmp;
    bool last_same_node = false;
    list_for_each_safe (node, tmp, head) {
        element_t *curr_element_t = list_entry(node, element_t, list);
        element_t *next_element_t = list_entry(node->next, element_t, list);
        if (node->next != head &&
            strcmp(curr_element_t->value, next_element_t->value) == 0) {
            last_same_node = true;
            list_del(node);
            free(curr_element_t->value);
            free(curr_element_t);
        } else if (last_same_node == true) {
            last_same_node = false;
            list_del(node);
            free(curr_element_t->value);
            free(curr_element_t);
        }
    }
    return true;
}

q_swap

在官方 linux/list.h 中，發現有 list_swap() 可調用

/**
 * list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
 * @entry1: the location to place entry2
 * @entry2: the location to place entry1
 */
static inline void list_swap(struct list_head *entry1,
			     struct list_head *entry2)
{
	struct list_head *pos = entry2->prev;

	list_del(entry2);
	list_replace(entry1, entry2);
	if (pos == entry1)
		pos = entry2;
	list_add(entry1, pos);
}

調用 list_swap() 編譯時出現

$ make
  CC    queue.o
queue.c: In function ‘q_swap’:
queue.c:267:9: error: implicit declaration of function ‘list_swap’ [-Werror=implicit-function-declaration]
  267 |         list_swap(node,node->next);
      |         ^~~~~~~~~
cc1: all warnings being treated as errors
make: *** [Makefile:50：queue.o] 錯誤 1

發現我們 lab0 專案內的 list.h 中沒有加入官方 linux/list.h 的 list_swap() 程式碼

於是我自己將官方 list_swap() 程式碼加在 lab0 專案內的 queue.c 中再次編譯

$ make
  CC    qtest.o
In file included from qtest.c:16:
list.h: In function ‘list_swap’:
list.h:348:2: error: implicit declaration of function ‘list_replace’; did you mean ‘list_splice’? [-Werror=implicit-function-declaration]
  348 |  list_replace(entry1, entry2);
      |  ^~~~~~~~~~~~
      |  list_splice
cc1: all warnings being treated as errors
make: *** [Makefile:50：qtest.o] 錯誤 1

queue.c 中還要再補上官方 linux/list.h list_replace()

/**
 * list_replace - replace old entry by new one
 * @old : the element to be replaced
 * @new : the new element to insert
 *
 * If @old was empty, it will be overwritten.
 */
static inline void list_replace(struct list_head *old,
				struct list_head *new)
{
	new->next = old->next;
	new->next->prev = new;
	new->prev = old->prev;
	new->prev->next = new;
}

編譯成功

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if ( head==NULL|| list_empty(head))
        return;

    struct list_head *node = head->next, *tmp_node;
    while (node != head && node->next != head) {
        tmp_node = node->next->next;//相鄰兩節點交換前，先備份第3個節點位址到 tmp_node 變數中
        list_swap(node, node->next);//相鄰兩節點交換
        node = tmp_node;//載入新的節點
    }
}

q_reverse

將 prev 與 next 兩個指標的內容交換(可藉由 tmp_node 暫存)

struct list_head 為環狀佇列，當節點走訪一圈後就會回到 head 位址，利用此特點判斷 while(node!=head) 是否走訪一圈回到head

圖片來源：你所不知道的 C 語言: linked list 和非連續記憶體

先做 next_node=node->next ，備份好下個節點
每個節點逐一將 prev 與 next 兩個指標內儲存的地址交換(藉由 tmp_node 變數，暫存節點地址)
離開前，記得 head 節點的 prev 與 next 也要交換

void q_reverse(struct list_head *head) {
    if ( head==NULL || list_empty(head)) {
        return;
    } 
    struct list_head *node=head->next,*next_node,*tmp_node;
    while(node!=head)//判斷是否走訪一圈回到 head
    {
	/* prev 與 next 交換前，先備份好下個節點*/	
       next_node=node->next;
		
       /*將 prev 與 next 兩個指標內儲存的地址交換*/	
       tmp_node=node->next;
       node->next=node->prev;
       node->prev = tmp_node; 
		
	/* 更新下一個節點*/
       node=next_node;
    } 
    /*離開前 記得 head 節點的 prev 與 next 也要交換*/
    tmp_node = head->next;
    head->next = head->prev;
    head->prev = tmp_node;      
}

q_sort（遞迴版）

參閱

你所不知道的 C 語言: linked list 和非連續記憶體 Merge Sort 的實作遞迴作法
freshLiver 同學
kevinshieh0225 同學

void q_sort(struct list_head *head)
{
    if (head == NULL || list_empty(head)) {
        return;
    }
    head->prev->next = NULL;
    head->next = mergesort_list(head->next);
    struct list_head *ptr = head;
    while (ptr->next != NULL) {
        ptr->next->prev = ptr;
        ptr = ptr->next;
    }
    ptr->next = head;
    head->prev = ptr;
}

mergesort_list() 的詳細實做如下

struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL;
    struct list_head **ptr = &head;
    for (; L1 && L2; ptr = &(*ptr)->next) {
        element_t *L1_element_t = list_entry(L1, element_t, list);
        element_t *L2_element_t = list_entry(L2, element_t, list);
        if (strcmp(L1_element_t->value, L2_element_t->value) <= 0) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }
    }
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

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

    struct list_head *slow = head;
    for (struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next)
        slow = slow->next;
    struct list_head *mid = slow->next;
    slow->next = NULL;

    struct list_head *left = mergesort_list(head), *right = mergesort_list(mid);
    return mergeTwoLists(left, right);
}