# 2024q1 Homework1 (lab0) contributed by < [zack-404](https://github.com/zack-404/lab0-c) > ## 開發環境 ```shell ❯ gcc --version gcc (Debian 10.2.1-6) 10.2.1 20210110 Copyright (C) 2020 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. ❯ cppcheck --version Cppcheck 2.3 ❯ lscpu Architecture: aarch64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 1 Core(s) per socket: 4 Socket(s): 1 Vendor ID: ARM Model: 3 Model name: Cortex-A72 Stepping: r0p3 CPU max MHz: 1800.0000 CPU min MHz: 600.0000 BogoMIPS: 108.00 L1d cache: 128 KiB L1i cache: 192 KiB L2 cache: 1 MiB ``` 以樹莓派藉由遠端控制進行此項作業唯一一個問題就是無法直接以提交所寫的程式碼至 Github ，目前尚未有 raspian 版本的 git-credential-manager 。目前以使用樹莓派進行測試，再藉由 Macbook Air 進行提交的動作。 :::danger 工欲善其事，必先... ::: ## 背景知識 ### 佇列（唸作：ㄓㄨˋ） 佇列為一種先進先出的資料結構，此次實作注重其與鏈結串列的關係。 ### `inline` 對函式效能的影響 在參閱 [25077757](https://github.com/25077667) 與 [nosba0957](https://github.com/nosba0957) 的程式碼時，發現 [25077757](https://github.com/25077667) 在諸多函式加入了 `static` 與 `inline` 兩個關鍵字。 #### `static` 關鍵字在 C 語言 > If the declaration of a file scope identifier for an object or a function contains the storageclass specifier static, the identifier has internal linkage.(22) (C99 6.2.2) > (22) A function declaration can contain the storage-class specifier static only if it is at file scope; see 6.7.1. (C99 6.2.2) > In addition to optional type qualifiers and the keyword `static`, the [ and ] may delimit an expression or `*`. If they delimit an expression (which specifies the size of an array), the expression shall have an integer type. If the expression is a constant expression, it shall have a value greater than zero. The element type shall not be an incomplete or function type. The optional type qualifiers and the keyword `static` shall appear only in a declaration of a function parameter with an array type, and then only in the outermost array type derivation (C99 6.7.5.2) :::danger 查閱 C 語言規格書，不要把自己的專業前途交給你沒有注入資本的大語言模型。 ::: <s> [工程師應知道的0x10個問題(6): Static的用法 MuLong PuYang](https://medium.com/@racktar7743/%E5%B7%A5%E7%A8%8B%E5%B8%AB%E6%87%89%E7%9F%A5%E9%81%93%E7%9A%840x10%E5%80%8B%E5%95%8F%E9%A1%8C-6-static%E7%9A%84%E7%94%A8%E6%B3%95-d391dacb28a3) </s> :::danger 優先閱讀權威材料！ ::: #### `inline` > A function declared with an inline function specifier is an inline function. The function specifier may appear more than once; the behavior is the same as if it appeared only once. Making a function an inline function suggests that calls to the function be as fast as possible.(118) The extent to which such suggestions are effective is implementation-defined.(119) (C99 6.7.4.5) > Any function with internal linkage can be an inline function. For a function with external linkage, the following restrictions apply: If a function is declared with an inline function specifier, then it shall also be defined in the same translation unit. If all of the file scope declarations for a function in a translation unit include the inline function specifier without extern, then the definition in that translation unit is an inline definition. An inline definition does not provide an external definition for the function, and does not forbid an external definition in another translation unit. An inline definition provides an alternative to an external definition, which a translator may use to implement any call to the function in the same translation unit. It is unspecified whether a call to the function uses the inline definition or the external definition.120) (C99 6.7.4.5) ### 了解 `elememt_t` 與 `queue_contest_t` ```c /** * struct list_head - Head and node of a doubly-linked list * @prev: pointer to the previous node in the list * @next: pointer to the next node in the list * * The simple doubly-linked list consists of a head and nodes attached to * this head. Both node and head share the same struct type. The list_* * functions and macros can be used to access and modify this data structure. * * The @prev pointer of the list head points to the last list node of the * list and @next points to the first list node of the list. For an empty list, * both member variables point to the head. * * The list nodes are usually embedded in a container structure which holds the * actual data. Such container structure is called entry. The helper list_entry * can be used to calculate the structure address from the address of the node. */ struct list_head { struct list_head *prev; struct list_head *next; }; ``` 由上述程式碼與註解可知， `list_head` 提供一個雙向鏈結串列的單元結構。 ```c /** * element_t - Linked list element * @value: pointer to array holding string * @list: node of a doubly-linked list * * @value needs to be explicitly allocated and freed */ typedef struct { char *value; struct list_head list; } element_t; ``` ```c /** * queue_contex_t - The context managing a chain of queues * @q: pointer to the head of the queue * @chain: used by chaining the heads of queues * @size: the length of this queue * @id: the unique identification number */ typedef struct { struct list_head *q; struct list_head chain; int size; int id; } queue_contex_t; ``` `element_t` 中的 `*value` 則是在記錄該結點的值，而 `list` 則是記錄串列中相鄰的兩個節點。 而`queue_context_t` 與 `element_t` 不同的地方在於它可以記錄的不單單是一個節點，而可以是串列中的一個子串列。 `size` 與 `id` 則分別紀錄此子串列的大小與 `id`。 ## 針對佇列的操作 ### `q_new` ### `q_free` 此函式目標為清除佇列上所有的節點。 ```c * list_for_each_safe - Iterate over list nodes and allow deletions * @node: list_head pointer used as iterator * @safe: list_head pointer used to store info for next entry in list * @head: pointer to the head of the list * * The current node (iterator) is allowed to be removed from the list. Any * other modifications to the the list will cause undefined behavior. */ #define list_for_each_safe(node, safe, head) \ for (node = (head)->next, safe = node->next; node != (head); \ node = safe, safe = node->next) ``` 以上為 `list.h` 所提供的 API ，用途為持續進行 `node->next` 直到 `node` 與 `(head)` 相同。若 `node` 與 `(head)` 相同，則代表 `head` 與 `tail` 相同，意即為空的佇列。 ```c /* Free all storage used by queue */ void q_free(struct list_head *head) { if (!head) return; struct list_head *entry = NULL, *safe = NULL; list_for_each_safe (entry, safe, head) q_release_element(container_of(entry, element_t, list)); free(head); } ``` 首先，要先確認 `head` 是否為空指標。若為空指標，則此佇列以為空佇列，不用繼續執行後續程式。若非空指標，則藉由 `list.h` 提供的 `list_for_each_safe` 與 `queue.h` 提供的 `q_release_element` 走訪與刪除節點，最後就可以完成清空佇列的動作。 ### `q_insert_head` 與 `q_insert_tail` `q_insert_head` 目標為在佇列的前端插入一個節點並回傳布林值確認是否成功插入，而 `q_insert_tail` 則目標插入節點於最末端。不過兩者的實作皆須注意是否為 `head` 與`tail` 。此外，此兩項實作亦可與通用的 `q_insert` 結合，進而精簡程式碼。以下實作將注重於實作通用的 `q_insert` 。 ```c static inline bool q_insert(struct list_head *head, char *s) { if (!head || !s) return false; element_t *new_element = malloc(sizeof(element_t)); if (!new_element) return false; new_element->value = strdup(s); if (!(new_element->value)) { free(new_element); return false; } list_add(&new_element->list, head); return true; } ``` ### `q_remove_head` 與 `q_remove_tail` ```c /** * container_of() - Calculate address of structure that contains address ptr * @ptr: pointer to member variable * @type: type of the structure containing ptr * @member: name of the member variable in struct @type * * Return: @type pointer of structure containing ptr */ #ifndef container_of #ifdef __LIST_HAVE_TYPEOF #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) #else #define container_of(ptr, type, member) \ ((type *) ((char *) (ptr) -offsetof(type, member))) #endif #endif ``` `container_of` 巨集用於計算共有幾個結構的指標有包含指標 `ptr`。 `strncpy` 函式用於複製字串，特別之處在於能夠使用空值字元 `'\0'` 填補省略空缺，其取決於字串長度。 要刪除整個佇列的 `head` 或 `tail` ，此行為即為刪除此佇列開頭的 ### `q_size` 此函式的目的在於回傳目前佇列的長度。 ```c /** * list_for_each - Iterate over list nodes * @node: list_head pointer used as iterator * @head: pointer to the head of the list * * The nodes and the head of the list must be kept unmodified while * iterating through it. Any modifications to the the list will cause undefined * behavior. */ #define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next) ``` 上述 `list.h` 所提供的 `list_for_each` API 使用與 `list_for_each_safe` 相同的技巧走訪佇列中的每個節點，直到 `head` 與 `tail` 相同，即走訪完成。 > 註：在 linux 中，鏈結串列為雙向且環狀 ```c /* Return number of elements in queue */ int q_size(struct list_head *head) { if (!head || list_empty(head)) return 0; size_t len = 0; struct list_head *iter; list_for_each (iter, head) len++; return len; } ``` 實作以 `list_for_each` API 為基底，以 `len` 紀錄共走訪了幾步。 ### `q_delete_mid` `q_delete_dup` 首先， `del` 與 `remove` 最大的差別在於被刪除的節點是否會繼續存在於記憶體。在串列中 `del` 就是將該節點與前後節點斷開，但該節點仍存在於記憶體；而`remove` 則是將該節點於記憶體中抹除，釋放記憶體空間。 ### `list_splice` > join or connect (a rope or ropes) by interweaving the strands at the ends. ```c /** * list_splice() - Add list nodes from a list to beginning of another list * @list: pointer to the head of the list with the node entries * @head: pointer to the head of the list * * All nodes from @list are added to the beginning of the list of @head. * It is similar to list_add but for multiple nodes. The @list head is not * modified and has to be initialized to be used as a valid list head/node * again. */ static inline void list_splice(struct list_head *list, struct list_head *head) { struct list_head *head_first = head->next; struct list_head *list_first = list->next; struct list_head *list_last = list->prev; if (list_empty(list)) return; head->next = list_first; list_first->prev = head; list_last->next = head_first; head_first->prev = list_last; } ``` ### `swap` :::danger 1. 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利) 2. 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。 3. 改進你的漢語描述 ::: 鏈結串列是一個環狀的結構，所以只要拆開其中一個，並把他的 `next` 與 `prev` 接上 `first` 與 `last` ；因其是雙向的，所以最後還要再用一次。 `delete` 會用到。 ### `q_reverse` `reverse` 最直觀的觀點就是走訪每個節點，並把節點中的 `prev` 與 `next` 對調，不過實作中必須注意是否能夠走訪每個節點。 ```c /** * list_move() - Move a list node to the beginning of the list * @node: pointer to the node * @head: pointer to the head of the list * * The @node is removed from its old position/node and add to the beginning of * @head */ static inline void list_move(struct list_head *node, struct list_head *head) { list_del(node); list_add(node, head); } ``` ```c /* Reverse elements in queue */ void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *cur = NULL, *safe = NULL; list_for_each_safe (cur, safe, head) list_move(cur, head); // Move to the beginning } ``` 實作中，藉由 `list_move` 的 API 完成更新節點的步驟；而 `list_add` API 則包含了交換 `prev` 與 `next` 的步驟。 ### `q_reverseK` 此項函式與 `q_reverse` 不同的地方在於 `q_reverseK` 轉置的不是一個節點，而是連續 K 個節點。 ```c /* Reverse the nodes of the list k at a time */ void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (!head || list_empty(head)) return; size_t count = 0; struct list_head *safe, *end, *start = head; list_for_each_safe (end, safe, head) { count++; if(count == k){ LIST_HEAD(tmp); list_cut_position(&tmp, start, end); q_reverse(&tmp); list_splice_init(&tmp, start); start = safe->prev; count = 0; } } } ``` ### delete() ### mergeSort() poat 才有順序 :::danger ? ::: [並行與平行](https://medium.com/mr-efacani-teatime/concurrency%E8%88%87parallelism%E7%9A%84%E4%B8%8D%E5%90%8C%E4%B9%8B%E8%99%95-1b212a020e30) $\to$ 參見[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)