# 2018q3 Homework3(list)
contributed by < `type59ty` >
###### tags: `sysprog2018`, `hw3`, `list`
---
## Linux 風格的 linked list
- [x] 閱讀 [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf) 共筆和觀看解說錄影。
- [ ] 自我檢查事項:
#### Q1: 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
- 參考：[直播錄影 1:31:30](https://youtu.be/0B0GNPv02zg?t=5490)
基於 ADT (Abstrate data type) 、資料封裝的概念，因為 linked list 的實做很多變 ( singly, doubly, circular linked list ) ，使用 macro 可以讓使用者不必去理解他的資料型態、實做方式，只要知道怎麼用他的 api 就好
- [macro vs function](https://stackoverflow.com/questions/9104568/macro-vs-function-in-c)
| features | Macro | Function |
| -------- | -------- | -------- |
| 何時被編譯 | Preprocess 階段 | Compile 階段 |
| 型態確認 | not done | done |
| 程式碼長度 | 增加 | 不變 |
| 執行速度 | 較快 | 較慢 |
| 編譯錯誤 | not check | check |
| 適用於 | 多次出現且長度短的程式 | 多次出現且長度長的程式 |
- 相關資料
- [Linux Device Drivers 3/e, ch11.5](https://static.lwn.net/images/pdf/LDD3/ch11.pdf)
- [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)
#### Q2: Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
- Job scheduling
Process 的排程是用 priority queue 來實做，而 priority queue 又可以用 linked list 來作
- [merge sort](https://github.com/Lukechin/mergesort_doubly_linked_list/blob/master/mergesort.c)
```c
void mergeSort(List** head_ref)
{
if(!head_ref || !(*head_ref)->next)
return;
List *left, *right;
split(*head_ref, &left, &right);
mergeSort(&left);
mergeSort(&right);
*head_ref = merge(left, right);
}
```
-
#### Q3: GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
- [Using the GNU Compiler Collection (GCC): Typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html)
typeof 的作用是用來參考( refer to )一個 expression 的資料型態，他的參數可以有兩種： expression 或 type
e.g
```c
// with an expression
typeof (x[0](1))
// with a type
typeof (int *)
```
#### Q4: 解釋以下巨集的原理
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
- container_of() - Calculate address of object that contains address ptTW
r
#### Q5: 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
- list_replace
replace old entry by new one
```c
/**
* list_replace - replace old entry by new one
* @old : the element to be replaced
* @new : the new element to insert
*
* If @old was empty, it will be overwritten.
*/
static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
```
- list_move
delete from one list and add as another's head
```c
/**
* list_move - delete from one list and add as another's head
* @list: the entry to move
* @head: the head that will precede our entry
*/
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del_entry(list);
list_add(list, head);
}
```
- list_splice
這個 function 可以將兩個 linked list 合併成一個，可以用來實做 **merge sort**
```c
/**
* list_splice - join two lists, this is designed for stacks
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice(const struct list_head *list,
struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head, head->next);
}
```
#### Q6: `LIST_POISONING` 這樣的設計有何意義？
#### Q7: linked list 採用環狀是基於哪些考量？
- 設計上較單純
#### Q8: `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
- 參考： [直播錄影1:23:00](https://youtu.be/0B0GNPv02zg?t=4980)
- safe: 針對特定情況，可以符合預期的運作
- 沒有 safe 的版本，在執行刪除時，有可能將 head 節點也刪除了，因此 safe 版本加入了其他考量
```c=
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
```
"safe" 在執行時期會比沒有 safe 的版本多走一次，因為它多了一個變數 n ，使的它會比沒有 safe 的版本多考慮一個節點，避免找不到 head
#### Q9: for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
- 這個作法讓走訪 linked list 這個動作可以抽象化表示，將實做的部份隱藏起來
#### Q10: 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
* 提示: 對照看 Doxygen
#### Q11: `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
#### Q12: `tests/` 目錄的 unit test 可如何持續精進和改善呢？
## 修改 lab0 程式碼
- 先將原本的 lab0-c 專案 設為 branch
```c
foest@forest-ubuntu:~/lab0-c$ git checkout -b branch1
foest@forest-ubuntu:~/lab0-c$ git push lab_pc branch1
Username for 'https://github.com': type59ty
Password for 'https://type59ty@github.com':
Total 0 (delta 0), reused 0 (delta 0)
remote:
remote: Create a pull request for 'branch1' on GitHub by visiting:
remote: https://github.com/type59ty/lab0-c/pull/new/branch1
remote:
To https://github.com/type59ty/lab0-c
* [new branch] branch1 -> branch1
```
- clone [linux-list](https://github.com/type59ty/linux-list)
- 為了實作 doubly linked list，首先需要在 node 結構中多加一條往回指的 link ， prev
### queue.h
```c
typedef struct ELE {
/* Pointer to array holding string.
This array needs to be explicitly allocated and freed */
char *value;
struct ELE *next;
struct ELE *prev;
} list_ele_t;
```
### queue.c
- q_insert_head, q_insert_tail
新增一個節點 newh 之後要指定他的 prev 該指向哪裡，考慮兩種情況：
1. q->size == 0
```c
q->tail = newh;
newh->next = NULL;
newh->prev = NULL;
```
2. q->size != 0
```c
newh->prev = NULL;
newh->next = q->head;
q->head->prev = newh;
```
- q_reverse
由於多了一個 prev link，所以在作 reverse 功能時可以用兩個額外的 pointer 就完成，比原本的版本少用一個 pointer
```c
//doubly linked list version q_reverse
void q_reverse(queue_t *q)
{
if ((q == NULL) || (q->size <= 1))
return;
list_ele_t *current;
list_ele_t *temp;
current = q->head;
q->tail = q->head;
while(current != NULL){
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
temp = temp->prev;
temp->prev = NULL;
q->head = temp;
}
```
- 可正常編譯
```c
forest@pop-os:~/lab0-c$ make
gcc -O0 -g -Wall -Werror -c queue.c
gcc -O0 -g -Wall -Werror -o qtest qtest.c report.c console.c harness.c queue.o
```
### qtest
```c
forest@pop-os:~/lab0-c$ ./qtest
cmd>new
cmd>new
q = []
cmd>ih 1
cmd>ih 1
q = [1]
cmd>it 2
cmd>it 2
q = [1 2]
cmd>it 3
cmd>it 3
q = [1 2 3]
cmd>rh
cmd>rh
Removed 1 from queue
q = [2 3]
cmd>reverse
cmd>reverse
q = [3 2]
cmd>reverse
cmd>reverse
q = [2 3]
cmd>free
cmd>free
q = NULL
```
Sign in with Wallet
Connect another wallet