# 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)

---

### 解釋以下巨集的原理

#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` 這樣的設計有何意義？

#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" 在執行時期的影響為何？

#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 的資料結構後，修改為以下的樣子：

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` 。

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()` 處理繁瑣的「連接」：

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` ，用第二個參數紀錄當前的下一個節點。

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;
}

## 實驗環境

$ 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