2022q1 Homework1 (lab0)

--- tags: linux2022 --- # 2022q1 Homework1 (lab0)  > [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)  ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 Copyright (C) 2019 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 架構： x86_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： 2041.816 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 ``` ## 開發過程先讀懂 `list.h` 裡頭的程式碼，並搭配著 [Linux kernel api](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.INIT_LIST_HEAD)看 ### new_q > Create empty queue. > Return NULL if could not allocate space. :::danger 注意作業書寫規範：中英文間用一個半形空白字元區隔 :notes: jserv ::: 首先先 malloc 一個 list_head 當作開頭，並利用 `INIT_LIST_HEAD` 來做初始化的動作。 ```c struct list_head *q_new() { struct list_head *q = malloc(sizeof(struct list_head)); if (q == NULL) return NULL; INIT_LIST_HEAD(q); return q; } ``` ### q_free > Free all storage used by queue 最後要把整個 element free 掉，利用迭代的方式去遍歷所有的 element 並 release 掉。最後把第一個 `l` 也 free 掉。 ```c void q_free(struct list_head *l) { if (!l) return; element_t *pos, *next; list_for_each_entry_safe (pos, next, l, list) q_release_element(pos); free(l); } ``` ### q_insert_head > Attempt to insert element at head of queue. > Return true if successful. > Return false if q is NULL or could not allocate space. > Argument s points to the string to be stored. > The function must explicitly allocate space and copy the string into it. 參考：[Make a copy of a char*](https://stackoverflow.com/questions/481673/make-a-copy-of-a-char) ```c bool q_insert_head(struct list_head *head, char *s) { if (!list_empty(head)) return false; element_t *new_char = malloc(sizeof(element_t)); if (new_char == NULL) return false; new_char->value = (char *) malloc(strlen(s) + 1); if (!new_char->value) { free(new_char); return false; } strncpy(new_char->value, s); *(new_char->value + strlen(s)) = '\0'; list_add(&new_char->list, head); return true; } ``` ### q_insert_tail > Attempt to insert element to the tail of queue. > Other ayytibute is as same as q_insert_head. ```c bool q_insert_tail(struct list_head *head, char *s) { if (!list_empty(head)) return false; element_t *new_char = malloc(sizeof(element_t)); if (new_char == NULL) return false; new_char->value = (char *) malloc(strlen(s) + 1); if (!new_char->value) { free(new_char); return false; } strncpy(new_char->value, s); list_add_tail(&new_char->list, head); return true; } ``` ### q_remove_head :::info **delete vs remove**: Remove and Delete are defined quite similarly, but the main difference between them is that delete means erase (i.e. rendered nonexistent or nonrecoverable), while remove denotes take away and set aside (but kept in existence). ::: > Attempt to remove element from head of queue. > Return target element. > Return NULL if queue is NULL or empty. > If sp is non-NULL and an element is removed, copy the removed string to *sp ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *remove_ele = list_first_entry (head, element_t, list); list_del_init (head->next); if(sp) { // copy to *sp from remove_ele->value. size_t len = strnlen(remove_ele->value, bufsize - 1); strncpy(sp, remove_ele->value, len); sp[len] = '\0'; } return remove_ele; } ``` * 錯誤訊息：ERROR: Probably not constant time 以上程式會在 `trace-17` 時爆出一個錯誤訊息，在參考同學們的作業後發現有些同學會先計算 `value` 的長度，後續再做 `strncpy`後提供的是字串的長度。做一改正後就解決該問題了。 :::info 但還不確定是不是這個關係，還要再確認一下。 ::: ### q_remove_tail > Attempt to remove element from tail of queue. > Other attribute is as same as q_remove_head. 跟 **q_remove_head** 不同的是： `list_last_entry` 取 list 裡頭最後一個 element `head->prev` 則是指向最後一個 ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *remove_ele = list_last_entry (head, element_t, list); list_del_init (head->prev); if(sp) { // copy to *sp from remove_ele->value. size_t len = strnlen(remove_ele->value, bufsize - 1); strncpy(sp, remove_ele->value, len); sp[len] = '\0'; } return remove_ele; } ``` ### q_delete_mid > Delete the middle node in list. > Return true if successful. > Return false if list is NULL or empty. > The middle node of a linked list of size n is the > ⌊n / 2⌋th node from the start using 0-based indexing. #### 想法利用 **Tortoise and Hare Algorithm** 的方法，先找出 middle element 之後利用 `list_entry` 的方式取到該element的位址，用 `list_del_init` 的方法將前後 element 接上，最後 `q_release_element` middle element。 ```c bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || list_empty(head)) return false; // use Tortoise and Hare Algorithm to find the middle node. struct list_head *slow = head, *fast = head; while (fast->next != head && fast->next->next != head) { fast = fast->next->next; slow = slow->next; } element_t *mid_node = list_entry(slow, element_t, list); list_del_init(slow); q_release_element(mid_node); return true; } ``` :::info 補：pointer to pointer的作法 ::: ### q_delete_dup 參考： [比較字串](https://morosedog.gitlab.io/C-20191019-C-15/) 首先利用 `list_for_each_entry_safe` 來走訪所有的element，再來利用 [strcmp](http://tw.gitbook.net/c_standard_library/c_function_strcmp.html#) 來比較 value 是否相等，若是相等的話( output 為0)則利用 `list_del_init` 以及 `q_release_element` 把 node 拿掉。 `cur_value`：紀錄當前的 value 初版： ```c= bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head || list_empty(head) || list_is_singular(head)) return false; element_t *pos, *next_pos; char *cur_value = ""; list_for_each_entry_safe (pos, next_pos, head, list) { // if different if (strcmp(cur_value, pos->value)) { cur_value = pos->value; } else { list_del_init(&pos->list); q_release_element(pos); } } return true; } ``` 但發現有一個錯誤就是這樣的話無法將重複的全部刪掉，會剩下一個，因此改寫了一下程式碼： ### q_swap <s>double pointer</s> indirect pointer版本有錯誤，待完成 :::danger 沒有 double pointer 這詞，只有 a pointer to a pointer 或 indirect pointer，請查字典以理解 double 的意義。 :notes: jserv ::: ```c void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ struct list_head **pp = &head; struct list_head *first, *second; first = (*pp)->next; second = first->next; do { // first = (*pp); // second = first->next; first->next = second->next; second->next = first; second->next->prev = first; second->prev = first->prev; first->prev = second; *pp = second; pp = &(first->next); } while ((*pp != head) && (*pp != head->next) && ((first = (*pp)) && (second = first->next))); } ``` 版本二：用 list.h 裡頭的 funtion `list_move` 來實作，每取兩個 element 進行調換。 ```c= void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ if(!head) return; struct list_head *first; for (first = head->next; (first != head) && (first->next != head); first = first->next) { list_move(first, first->next); } } ``` ### q_reverse 取一個 `node` 來做遍歷，將 ```c= void q_reverse(struct list_head *head) { if (!head) return; struct list_head *prev_node = head, *node = head->next; do { prev_node->next = prev_node->prev; prev_node->prev = node; prev_node = node; node = node->next; } while (prev_node != head); } ```  ## Reference * [Make a copy of a char*](https://stackoverflow.com/questions/481673/make-a-copy-of-a-char) * [Linux鏈結串列struct list_head 研究](https://myao0730.blogspot.com/2016/12/linux.html)