2018q3 Homework3 (list)

# 2018q3 Homework3 (list) contributed by < `kevin110604` > ###### tags: `2018q3` ## Linux 風格的 linked list: 自我檢查事項 [linux/include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) [sysprog21/linux-list/include/list.h](https://github.com/sysprog21/linux-list) ### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？ Two advantages 1. Macros may be silightly faster A function call usually requires some overhead during program execution --- **context information** must be saved, **arguments copied**, and so forth. A macro invocation, on the other hand, requires no run-time overhead. ps: However, inline function can avoid this overhead. 2. Macros are "generic" Macro parameters have no particular type. As a result, a macro can accept arguments of any type, providing that the resulting program --- after preprocessing --- is valid. Also have some disadvantage 1. The compiled code will often be larger 2. Arguments aren't type-checked 3. It's not possible to have a pointer to a macro 4. A macro may evaluate its arguments more than once 所以我想最主要還是考慮到 function call 會有的成本而使用 macro 。 #### 參考資料 * K.N.King (2008). *C Programming: A Modern Approach.* (2/e) --- ### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量 #### 參考資料 --- ### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？ `typeof` 可以用來取得一個 variable 的 type 。當我們在程式當中使用 macro 時， macro 可能接受到各種不同 type 的 variable 。如果我們沒有對不同的 type 做轉換可能會發生錯誤，這時就可以用 `typeof` 先得知該 variable 的 type 再做適當的轉換。 #### 參考資料 * [GCC typeof在kernel中的使用——C語言的“編譯時多態”](http://deltamaster.is-programmer.com/posts/37253.html) --- ### 解釋以下巨集的原理 ```Clike #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) ``` 這個巨集透過給一個指向 structure 裡的一個 member 的指標，和 structure 的 type ，計算出該 structure 的地址。原理是先宣告一個指標 `__pmember` 指向 member，然後將這個指標減去 member 在這個 structure 中的 offset ，指標自然就指向了包含該 member 的 structure 了。 #### 參考資料 * [GCC typeof在kernel中的使用——C語言的“編譯時多態”](http://deltamaster.is-programmer.com/posts/37253.html) --- ### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？ #### 參考資料 --- ### `LIST_POISONING` 這樣的設計有何意義？ ```c #ifdef LIST_POISONING node->prev = (struct list_head *) (0x00100100); node->next = (struct list_head *) (0x00200200); #endif ``` 根據 `list_del` 上面的註解，這是為了防止我們取用 invalid memory ，因為經過移除的 node 已經不屬於原本的 list 了，如果讓 node 的 next 和 prev 繼續指向 list 裡面的其他 node ，往後當我們取用這個 node 時，可能就會無故變更到不該變動的 list。 #### 參考資料 --- ### linked list 採用環狀是基於哪些考量？ Advantages of a circular linked list * Some problems are circular and a circular data structure would be more natural when used to represent it * The entire list can be traversed starting from any node (traverse means visit every node just once) * Fewer special cases when coding (all nodes have a node before and after it) #### 參考資料 * [Circular Linked List](https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/lists/circular_linked_list.html) --- ### list_for_each_safe 和 list_for_each 的差異在哪？ "safe" 在執行時期的影響為何？ ```c #define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next) #define list_for_each_safe(node, safe, head) \ for (node = (head)->next, safe = node->next; node != (head); \ node = safe, safe = node->next) ``` 兩者都是將 linked list 從給定的 `head` 開始拜訪每一個節點，一圈後回到 `head` 然後停下來。 `list_for_each` 很單純的就是只有紀錄當前的節點 `cur` ，所以任何對 list 的修改都會造成 undefined behavior 。 `list_for_each_safe` 則因為有用 `safe` 來紀錄 `cur` 的下一個節點，所以可以對 `cur` 做移除（我們還是知道下一個節點在哪）。不過任何其他的修改動作也都是 undefined behavior 。 #### 參考資料 --- ### for_each 風格的開發方式對程式開發者的影響為何？ * 提示：對照其他程式語言，如 Perl 和 Python 這種已經封裝好的語法使用起來比較方便，不需要考慮到太多指標的問題，也較不容易出錯。 #### 參考資料 --- ### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？ * 提示: 對照看 Doxygen 可利用 Doxygen 來抓取程式碼裡的註解，自動產生說明文件。 `@` 後面接的是參數的名字。 #### 參考資料 * [Doxygen 程式文件產生器與簡易筆記](https://blog.longwin.com.tw/2011/04/doxygen-document-generator-2011/) --- ### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？ `tests/` 目錄底下有非常多獨立的程式碼，每一個程式碼都是用來測試 list.h 裡頭一小部分的功能。這樣獨立分開來測試可避免其中一項功能出錯影響到另一項功能。（或許也利於這種大型程式碼的封裝？） #### 參考資料 * [rex662624 的筆記](https://hackmd.io/s/S1GRtsEiM) --- ### `tests/` 目錄的 unit test 可如何持續精進和改善呢？對測試的項目更多元化，故意測那種容易出錯的情況（如 boundary condition ）。 #### 參考資料 * [rex662624 的筆記](https://hackmd.io/s/S1GRtsEiM) --- ## Homework1: lab0 修改過程 :::info 其實我很不確定這樣的修改好不好... ::: ### queue.h Queue 的 structure 參考 list.h 的資料結構後，修改為以下的樣子： ```c typedef struct list_node { struct list_node *head; /* next */ struct list_node *tail; /* prev */ int size; } queue_t; typedef struct ELE { char *value; /* Pointer to array holding string */ queue_t list; } list_ele_t; ```` 為了不要改太多名字所以名稱幾乎沒有變，像是 `queue_t`, `list_ele_t`，甚至連 `head`, `tail` （兩個的用處對應到 list.h 裡的 `next`, `prev` ）這兩個名稱我都保留了。所以主要的修改是將 `list_ele_t` 裡的 `struct ELE *next` 換掉變成 `queue_t list` 。 `queue_t` 裡的 `head`, `tail` 都變成指向 `queue_t` 的指標。 ### qtest.c 所有提到 `q->head->value` （或是 `q->head->next` ）的地方都需要做修正，因為現在 `head` 不再是指向 `list_ele_t` 的指標了。所以我先用 `list_entry()` 取得節點的地址（事實上 `list_entry()` 裡頭就是 `container_of()` ），再用它取得 `value` 。 ```c list_ele_t *item = list_entry(q->head, list_ele_t, list); ... if (!item->value) { ... } ``` ### queue.c 在將 linked list 使用的 structure 改成 linux-style 後，這部分就容易多了。例如 `q_insert_head()` 就可以直接使用 `list_add()` 處理繁瑣的「連接」： ```c bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; if (q == NULL) return false; newh = malloc(sizeof(list_ele_t)); if (newh == NULL) return false; newh->value = malloc(strlen(s) + 1); if (newh->value == NULL) { free(newh); return false; } strcpy(newh->value, s); list_add(&newh->list, q); q->size++; return true; } ``` `q_reverse()` 在走訪節點的時候，因為會修改到當前節點的連接，所以應該要使用 `list_for_each_safe` ，用第二個參數紀錄當前的下一個節點。 ```c void q_reverse(queue_t *q) { if (q == NULL || q->size <= 1) return; queue_t *cur, *pre, *old_tail, *tmp; old_tail = q->tail; pre = q; q->tail = q->head; list_for_each_safe(cur, tmp, q) { if (cur == old_tail) break; cur->head = pre; cur->tail = old_tail; pre->tail = cur; pre = cur; old_tail->head = cur; } q->head = old_tail; old_tail->tail = q; } ``` ## 實驗環境 ```shell $ cat /etc/os-release NAME="Ubuntu" VERSION="18.04.1 LTS (Bionic Beaver)" ID=ubuntu ID_LIKE=debian PRETTY_NAME="Ubuntu 18.04.1 LTS" VERSION_ID="18.04" HOME_URL="https://www.ubuntu.com/" SUPPORT_URL="https://help.ubuntu.com/" BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/" PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy" VERSION_CODENAME=bionic UBUNTU_CODENAME=bionic $ cat /proc/version Linux version 4.15.0-34-generic (buildd@lgw01-amd64-047) (gcc version 7.3.0 (Ubuntu 7.3.0-16ubuntu3)) #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018 ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.