owned this note
owned this note
Published
Linked with GitHub
# 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
```
Sign in with Wallet
