# 2018q3 Homework3 (review)
contributed by < [`jason53415`](https://github.com/jason53415) >
## 第 2 週測驗題 測驗 `3`
:::info
Linux 核心程式碼 include/linux/list.h 提到以下程式碼，為何每個 head 使用時都要先加上 () 呢？
```c
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
```
:::
* 因為這邊使用了 macro 來定義函式，會在 pre-process 時直接在程式碼之中展開，因此如果 head 是一個表示式或包含了其他優先權較低的 operator，且又沒有加上 `()` 時，就會出現程式行為不符合預期的情況。
* 以下嘗試如果 `head` 不加 `()` 會發生什麼錯誤：
```C=
#include <stdio.h>
#define list_for_each_prev(pos, head) \
for (pos = head->prev; pos != head; pos = pos->prev)
struct list_head {
struct list_head *prev;
struct list_head *next;
};
int main() {
struct list_head head, node;
struct list_head *ptr;
head.prev = &node;
head.next = &node;
node.prev = &head;
node.next = &head;
list_for_each_prev(ptr, &head)
printf("%p %p\n", ptr, &head);
}
```
* 編譯時便會產生錯誤：
```shell=
$ gcc quiz2-3.c -o quiz2-3
quiz2-3.c: In function ‘main’:
quiz2-3.c:3:20: error: invalid type argument of ‘->’ (have ‘struct list_head’)
for (pos = head->prev; pos != head; pos = pos->prev)
^
quiz2-3.c:17:5: note: in expansion of macro ‘list_for_each_prev’
list_for_each_prev(ptr, &head)
^~~~~~~~~~~~~~~~~~
```
* 加上 `()` 之後就沒有錯誤了：
```shell=
$ head quiz2-3.c -n 3
#include <stdio.h>
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
$ gcc quiz2-3.c -o quiz2-3
$ ./quiz2-3
0x7ffe70fd7ec0 0x7ffe70fd7eb0
```
:::success
延伸問題: 在 Linux 核心原始程式碼找出類似上述「走訪節點」的片段，討論其實作技巧和考量點
:::
* 以下為 kernel/sched.c 中所定義的一個函式 `__wake_up_common()`，作用是依照目前的需求來喚醒 wait queue 中的 task。
```C=
/*
* The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
* wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
* number) then we wake all the non-exclusive tasks and one exclusive task.
*
* There are circumstances in which we can try to wake a task which has already
* started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
* zero in this (rare) case, and we handle it by continuing to scan the queue.
*/
static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
int nr_exclusive, int wake_flags, void *key)
{
wait_queue_t *curr, *next;
list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
unsigned flags = curr->flags;
if (curr->func(curr, mode, wake_flags, key) &&
(flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
break;
}
}
```
* 其中第 15 行的 `list_for_each_entry_safe()` 就是定義在 list.h 中，可以用來走訪所有節點中某個 member 的函式。
```c=
/**
* list_for_each_entry_safe - iterate over list entries and allow deletes
* @entry: pointer used as iterator
* @safe: @type pointer used to store info for next entry in list
* @head: pointer to the head of the list
* @member: name of the list_head member variable in struct type of @entry
*
* The current node (iterator) is allowed to be removed from the list. Any
* other modifications to the the list will cause undefined behavior.
*
* FIXME: remove dependency of __typeof__ extension
*/
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
```
## 第 2 週測驗題 測驗 `5`
:::info
以下程式是合法 C99 程式嗎？
```C
#include <stdio.h>
int main() { return (********puts)("Hello"); }
```
請搭配 C 語言規格書解釋
繼續思考以下是否合法:
```C
#include <stdio.h>
int main() { return (**&puts)("Hello"); }
```
繼續變形:
```C
#include <stdio.h>
int main() { return (&**&puts)("Hello"); }
```
也會合法嗎？為什麼？請翻閱 C 語言規格書解說。
:::
* 實際執行結果：
```shell=
$ cat quiz2-5.c
#include <stdio.h>
int main() { return (********puts)("Hello"); }
$ gcc quiz2-5.c -o quiz2-5
$ ./quiz2-5
Hello
```
* 查閱 C99 規格書可以得到以下的解釋：
> **§6.5.2.2 Function calls**
>
> 1) The expression that denotes the called function shall have type pointer to function returning void or returning an object type other than an array type.
> **§6.3.2.1 Lvalues, arrays, and function designators**
>
> 4) A *function designator* is an expression that has function type. Except when it is the operand of the sizeof operator or the unary & operator, a function designator with type ‘‘function returning *type*’’ is converted to an expression that has type ‘‘pointer to function returning *type*’’.
* 由此可知一個為 function returning type 的 function designator 實際上在處理時會被轉為 pointer to function returning type。
* 因為 `put()` 是個 function designator，所以實際上會被轉為 pointer to function，也就是 `(*put)()`。
* 如果前面加上 `*` (dereference of) 成為 `*put()`，便會使 pointer to function returning type 變成 function returning type 的 function designator，然後又再被轉回 pointer to function，因此無論前面加多少 `*` 結果都會是一樣的。
* 如果前面加上 `&` (address of) 成為 `＆put()` 的話，則會讓直接讓原本的 function designator 變為 pointer to function returning type。
* 因此無論在 `put()` 前加上 `*` 或 `&` ，最後都還是會轉為 pointer to function returning type。
## 第 2 週測驗題 測驗 `7`
:::info
推敲以下程式碼的作用:
```C
void hex2(unsigned int x) {
do {
char c = "0123456789abcdef" [x & 0xf];
printf("char %c for %d\n", c, x);
x >>= 4;
printf("char %c for %d\n", c, x);
} while (x);
}
```
:::
* 這段程式碼主要的作用是輸出一個整數的 16 進位表示法，在第三行的 `x & 0xf` 會取出 `x` 最低的四個 bits，並且剛好對應到字串 `"0123456789abcdef"` 中相對應的 16 進位字母，例如最低的四個 bits 假如是 `1011`，也就是十進位的 `11`，就會剛好取到字串中的 `"b"`。
* 每次迴圈當中，在取出 `x` 最低的四個 bits 對應的 16 進位字母後，就會將 `x` 往右 shift 四個 bits，直到 `x` 為 `0` 後跳出迴圈。
* 比較特別的是在每次迴圈當中，`x` 被 shift 的前後都會印出結果，也許是因為這邊的寫法是從 16 進位的低位印到高位，比較容易產生混淆，所以才將 shift 的前後的值都印出，方便觀察每一次迴圈的變化。
* 測試程式與實際執行結果如下：
```C=
#include <stdio.h>
void hex2(unsigned int x) {
do {
char c = "0123456789abcdef" [x & 0xf];
printf("char %c for %d\n", c, x);
x >>= 4;
printf("char %c for %d\n", c, x);
} while (x);
}
int main() {
hex2(100);
hex2(0xabc);
return 0;
}
```
```Shell=
$ ./quiz2-7
char 4 for 100
char 4 for 6
char 6 for 6
char 6 for 0
char c for 2748
char c for 171
char b for 171
char b for 10
char a for 10
char a for 0
```
:::success
延伸問題: 在 [glibc](https://www.gnu.org/software/libc/) 原始程式碼找出類似作用和寫法的程式碼，並探討其實作技巧
:::
* 以下為 [glibc/math/atest-sincos.c](https://code.woboq.org/userspace/glibc/math/atest-sincos.c.html) 中的一個函式，其中第 9 行雖然有多做了許多運算，但目的還是將特定位置的 4 個 bits shift 到最低位，並且與 `0xf` 做 `&` 運算，來從預先定義好的字串中取得對應的 16 進位數字。
```C=
static const char hexdig[] = "0123456789abcdef";
static void print_mpn_hex (const mp_limb_t *x, unsigned size)
{
char value[size + 1];
unsigned i;
const unsigned final = (size * 4 > SZ * mpbpl) ? SZ * mpbpl / 4 : size;
memset (value, '0', size);
for (i = 0; i < final ; i++)
value[size-1-i] = hexdig[x[i * 4 / mpbpl] >> (i * 4) % mpbpl & 0xf];
value[size] = '\0';
fputs (value, stdout);
}
```
## 第 3 週測驗題 測驗 `1`
:::info
考慮以下程式碼:
```C=
#include <stdio.h>
#include <stdint.h>
struct test {
unsigned int x : 5;
unsigned int y : 5;
unsigned int z;
};
int main() {
struct test t;
printf("Offset of z in struct test is %ld\n",
(uintptr_t) &t.z - (uintptr_t) &t);
return 0;
}
```
在 GNU/Linux x86_64 環境中執行，得到以下輸出:
```
Offset of z in struct test is 4
```
倘若將第 10 和第 11 換為以下:
```C=10
printf("Address of t.x is %p", &t.x);
```
會發生什麼事？
:::
* 實際執行結果：
```shell=
$ gcc quiz3-1.c -o quiz3-1
quiz3-1.c: In function ‘main’:
quiz3-1.c:10:36: error: cannot take address of bit-field ‘x’
printf("Address of t.x is %p", &t.x);
^
```
* 查閱 C99 規格書可以得到以下的解釋：
> **§6.7.2.1 Structure and union specifiers**
>
> 8) A member of a structure or union may have any object type other than a variably modified type.^105)^ In addition, a member may be declared to consist of a specified number of bits (including a sign bit, if any). Such a member is called a **bit-field**;^106)^ its width is preceded by a colon.
> 10) An implementation may allocate any addressable storage unit large enough to hold a bitfield. If enough space remains, a bit-field that immediately follows another bit-field in a structure shall be packed into adjacent bits of the same unit. If insufficient space remains, whether a bit-field that does not fit is put into the next unit or overlaps adjacent units is implementation-defined. The order of allocation of bit-fields within a unit (high-order to low-order or low-order to high-order) is implementation-defined. The alignment of the addressable storage unit is unspecified.
>
> 106) The unary & (address-of) operator cannot be applied to a **bit-field** object; thus, there are no pointers to or arrays of **bit-field** objects.
* 因此答案為 `(e)` 編譯失敗，不能將指標指向沒有對齊 1 byte 的結構體成員。
## 第 3 週測驗題 測驗 `4`
:::info
考慮以下程式碼:
```C
#include <stdlib.h>
#include <string.h>
typedef struct rec {
char *value;
struct rec *next;
} record;
void insert_sorted(record **r, const char *value)
{
record *newrec = NULL;
while (*r && strcmp(value, (*r)->value) > 0)
r = &((F1)->next);
newrec = malloc(sizeof(record));
newrec->value = F2(value);
newrec->next = F3;
F4 = newrec;
}
```
函式 insert_sorted 的作用是在 r 所指向已依據數值排序的 linked list 中，安插給定的字串，考慮到 string literal 的生命週期，應該在新建立的節點中，複製給定的字串。
請補完上述程式碼。
:::
:::success
延伸問題: 解釋運作原理，並新增刪除和搜尋節點的程式，附上完整的測試計畫
:::
* 以下為整個 quiz3-4.h 檔的內容，包含了填補完整的 `insert_sorted()` 函式，以及另外實做的 `delete_sorted()` 可以用來刪除節點，以及 `list_sorted()` 可以印出目前 list 中的內容。
```C=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct rec {
char *value;
struct rec *next;
} record;
void insert_sorted(record **r, const char *value)
{
record *newrec = NULL;
while (*r && strcmp(value, (*r)->value) > 0)
r = &((*r)->next);
newrec = malloc(sizeof(record));
newrec->value = strdup(value);
newrec->next = *r;
*r = newrec;
}
void delete_sorted(record **r, const char *value)
{
while (*r && strcmp(value, (*r)->value) > 0)
r = &((*r)->next);
if (*r == NULL || strcmp(value, (*r)->value) != 0) {
printf("> \"%s\" not in list ", value);
return;
}
record *ptr = *r;
*r = (*r)->next;
free(ptr->value);
free(ptr);
}
void list_sorted(record **r)
{
printf("> ");
for(; *r; r = &((*r)->next))
printf("%s ", (*r)->value);
printf("\n");
}
```
* 在 `insert_sorted()` 中，`r` 是一個指標的指標，會在 while 迴圈中不斷指到每一個節點的 `next` 指標，並且去比較要插入的字串與 `next` 所指到的節點的 `value` 的大小，直到 `value` 不小於要插入的字串或是到了 list 的末端；這時便會配置一個節點的空間，並且使用 `strdup()` 配置一個字串的空間來將字串複製進去，最後則是將該節點的 `next` 指向現在 `r` 所指的指標指到的節點，並且讓 `r` 所指的指標指向新節點。
* 在 `delete_sorted()` 中，`r` 一樣會在 while 迴圈中不斷指到每一個節點的 `next` 指標，並且去比較要刪除的字串與 `next` 所指到的節點的 `value` 的大小，直到 `value` 不小於要插入的字串或是到了 list 的末端；這時如果 `value` 不等於我們要的字串或是我們已經到了 list 末端，就代表要刪除的字串不在 list 中；若是找到了我們要刪除的節點，需要先利用一個暫存的指標 `ptr` 指向我們要刪除的節點，接著讓 `r` 所指的指標指向下下一個節點，最後將 ptr 指到的節點中的 `value` 和節點的空間都釋放掉。
* 以下為完整的測試程式 quiz3-4.c：
```C=
#include "quiz3-4.h"
int main() {
record *ptr = NULL;
record **head = &ptr;
printf("Insert \"ba\" ");
insert_sorted(head, "ba");
list_sorted(head);
printf("Insert \"abc\" ");
insert_sorted(head, "abc");
list_sorted(head);
printf("Insert \"bb\" ");
insert_sorted(head, "bb");
list_sorted(head);
printf("Delete \"ba\" ");
delete_sorted(head, "ba");
list_sorted(head);
printf("Insert \"ac\" ");
insert_sorted(head, "ac");
list_sorted(head);
printf("Delete \"ba\" ");
delete_sorted(head, "ba");
list_sorted(head);
printf("Insert \"c\" ");
insert_sorted(head, "c");
list_sorted(head);
printf("Delete \"abc\" ");
delete_sorted(head, "abc");
list_sorted(head);
}
```
* 測試結果：
```shell=
$ gcc quiz3-4.c -o quiz3-4
$ ./quiz3-4
Insert "ba" > ba
Insert "abc" > abc ba
Insert "bb" > abc ba bb
Delete "ba" > abc bb
Insert "ac" > abc ac bb
Delete "ba" > "ba" not in list > abc ac bb
Insert "c" > abc ac bb c
Delete "abc" > ac bb c
```
Google Drive
Gist
Clipboard
Sign in with Wallet
