2021q1 Homework2 (quiz2)

contributed by < Chialiang86 >

Todo

重寫測驗

測驗 1

此題目的內容首先仿效 Linux 核心 include/linux/list.h 的精簡實作，設計了一套可以方便使用環狀 doubly-linked list 的介面；此外，從此作為基礎延伸出 merge sort 的實做。
由以下的程式碼不難看出， merge sort 的充分使用了 divide-and-conquer 的特性。
Divide : 使用 list_cut_position 搭配 get_middle 函數藉由找出 list 中間點來將 list 切成左右兩部份，而從 list_cut_position 的參數 (parameter) 可看出 node 為 list_head 型態，而 get_middle 的回傳值型態為 list_ele_t * ，因此 MMM 代換為 &get_middle(&q->list)->list 。
Conquer : 藉由遞迴呼叫 list_merge_sort 來分別將剛剛切出的左右兩 list 進行排序。
Combine : 把左右兩邊排序完的 list 進行合併，成為更長的一個排序好的 list 。















void list_merge_sort(queue_t *q)
{
    if (list_is_singular(&q->list))
        return;

    queue_t left;
    struct list_head sorted;
    INIT_LIST_HEAD(&left.list);
    list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list /*MMM*/);
    list_merge_sort(&left);
    list_merge_sort(q);
    list_merge(&left.list, &q->list, &sorted);
    INIT_LIST_HEAD(&q->list);
    list_splice_tail(&sorted, &q->list);
}

探討 `list_cut_position` 函數

























static inline void list_cut_position(struct list_head *head_to,
                                     struct list_head *head_from,
                                     struct list_head *node)
{
    /* 1 */
    struct list_head *head_from_first = head_from->next;

    if (list_empty(head_from))
        return;

    if (head_from == node) {
        INIT_LIST_HEAD(head_to);
        return;
    }

    /* 2 */
    head_from->next = node->next;
    head_from->next->prev = head_from;

    /* 3 */
    head_to->prev = node;
    node->next = head_to;
    head_to->next = head_from_first;
    head_to->next->prev = head_to;
}

以下圖示說明實做細節，程式碼中的註解對應了圖示順序。

1. 先將 head_from_first 指派為 head_from->next ，而 node 為 head_from 此環狀 list 依據 get_middle 算出的中間點。

2. 將 head_from->next 指派為 node->next ；再把 head_from->next->prev 指派為 head_from 。

3. head_to->prev 指派為 node,node->next 指派為 head_to, 再把 head_to->next 指派為 head_from_first,head_to->next->prev 指派為 head_to 。

此動作順利將環狀 list 分為兩個小環狀 list。

探討 `get_middle` 函數

此函數主要的目的在於找到實做 merge sort 的 list 之中間點。
其中 list_for_each 為一個 function-liked macro ，主要是簡化走訪整個 list 的過程。


#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

考慮 low 和 fast 兩變數，可看見 slow 每次執行完一輪會變為 slow->next ；但 fast 會變成 fast->next->next ，由其變數命名可知一個移動的較慢，另一個較快，主要目的是利用當 fast 到達起始點時， slow 到達 list 的中間位置，並將中間位置的指標藉由 list_entry 找出並回傳。










static list_ele_t *get_middle(struct list_head *list)
{
    struct list_head *fast = list->next, *slow;
    list_for_each (slow, list) {
        if (fast->next == list /*COND1*/ || fast->next->next == list /*COND2*/)
            break;
        fast = fast->next->next;
    }
    return list_entry(slow /*TTT*/, list_ele_t, list);
}


#define list_entry(node, type, member) container_of(node, type, member)

其中 list_entry 是由 container_of 這個 macro 來實現

考慮 `container_of` 的定義：







#ifndef container_of
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
#endif

首先探討 container_of 中的 __extension__
- typeof 關鍵字為 GNU C extension，並非 c 原始的標準。
- 而 __typeof__ 為 alternate keyword ，根據 gcc.gnu.org 中對 alternate keyword 的解釋 :
-ansi and the various -std options disable certain keywords. This causes trouble when you want to use GNU C extensions, or a general-purpose header file that should be usable by all programs, including ISO C programs. The keywords asm, typeof and inline are not available in programs compiled with -ansi or -std
- 在 gcc 引數 (argument) 指定 -ansi 或 -std 時，某些關鍵字如 typeof , asm, inline 是無法編譯的，解決辦法是在關鍵字頭尾加上 __ (用 __typeof__ 代替 typeof) ，即 alternate keyword
- 然而 gcc 某些 option 如 -pedantic 會造成使用 GNU C extensions 產生 warning 的狀況，可以在 __typeof__ 之前加上 __extension__ 來避免。
- 可見主要功能為傳回 struct 中成員所在記憶體空間的起始位址（即 struct 的起始位址）
以 container_of(slow, list_ele_t, list) 當作範例

typedef struct __element {
    char *value;
    struct __element *next;
    struct list_head list;
} list_ele_t;

slow 為 list_head 型態的指標， list 為 list_ele_t 其中一個成員的名稱（可以想成 slow 即為 list_ele_t 中 list 成員的實體），結果回傳 slow 所在的 list_ele_t 記憶體起始位置。

改寫程式碼

經過觀察可以發現， struct list_head 已經具有完整 circular doubly-linked list 的結構，只要加上一個存放字串 (value) 的欄位即可時做出 list merge sort 。
以下的 list_ele_t 擴充了原有的 struct list_head 結構，主要是加上了可以存字串的 value 欄位
實作上我們直接省略 queue_t 這個結構（因為 list_ele_t 已經足夠去實做 list sort ），並且把 list_ele_t 中的 struct list_head list 放到第一個欄位，這樣有一個非常大的好處是，如果要進行走訪 list 的動作，只要直接把 list_ele_t * 強制轉型成 struct list_head * 即可，因為兩個指標指向的是同一塊記憶體位址，不需要用 contain_of 這個 macro 來計算 list 成員的相對記憶體位置，不但精簡了程式碼提高了可讀性，也省去了計算相對位置所使用的時間。




typedef struct __element {
    struct list_head list;
    char *value;
} list_ele_t;

q 的型態改變成 struct list_head *，其實整個 q 的 list 只有 q 自己是真正屬於 struct list_head * ，其他的節點是有 value 成員的 list_ele_t *，因此 q 本身可以算是一個 dummy node ，只有指向 list 功能。


 struct list_head *q = q_new();

關鍵的 q_insert_head 函數，以下程式碼第 17 行可以看到，lsit_ele_t * 型態的新節點 newh 被強制轉形成 struct list_head * 加到 q->next 中，雖然兩者型態不同，但因為指向的是同一塊記憶體空間，因此省去許多計算相對位置，或額外設計 struct 來操作記憶體空間的成本。




















bool q_insert_head(struct list_head *q, char *s)
{
    // modify
    if (!q) return false;

    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    char *new_value = strdup(s);
    if (!new_value) {
        free(newh);
        return false;
    }

    newh->value = new_value;
    list_add_tail((struct list_head *)newh, q->next);

    return true;
}

q_free 函數更改如下，傳進去的 type 雖然為 struct list_head * ，但走訪整條 list 要先轉型成 list_ele_t * 才能正確釋放記憶體。













static void q_free(struct list_head *q)
{
    // modify
    if (!q) return;

    struct list_head *current = q->next;
    while (current != q) {
        struct list_head *tmp = current;
        current = current->next;
        free(((list_ele_t*)tmp)->value);
        free(tmp);
    }
}

sort 的函數更改










































static struct list_head *get_middle(struct list_head *list)
{
    struct list_head *fast = list, *slow;
    list_for_each (slow, list) {
        if (fast->next != list || fast->next->next != list)
            break;
        fast = fast->next->next;
    }
    return slow;
}

static void list_merge(struct list_head *lhs,
                       struct list_head *rhs,
                       struct list_head *head)
{
    INIT_LIST_HEAD(head);

    while (!list_empty(lhs) && !list_empty(rhs)) {
        char *lv = ((list_ele_t *)lhs->next)->value;
        char *rv = ((list_ele_t *)rhs->next)->value;
        struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
        list_del(tmp);
        list_add_tail(tmp, head);
    }
    list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}

void list_merge_sort(struct list_head *q)
{
    if (list_is_singular(q))
        return;

    struct list_head left;
    struct list_head sorted;
    INIT_LIST_HEAD(&left);
    list_cut_position(&left, q, get_middle(q));
    list_merge_sort(&left);
    list_merge_sort(q);
    list_merge(&left, q, &sorted);
    INIT_LIST_HEAD(q);
    list_splice_tail(&sorted, q);
}

另外撰寫 print 函數來印出完整的 list






void print(struct list_head *head)
{
    struct list_head* tmp;
    list_for_each (tmp, head)
        printf(" %s", ((list_ele_t*)tmp)->value);
}

main 修改






















int main(void)
{
    FILE *fp = fopen("cities.txt", "r");
    if (!fp) {
        perror("failed to open cities.txt");
        exit(EXIT_FAILURE);
    }

    struct list_head *q = q_new();
    char buf[256];
    while (fgets(buf, 256, fp))
        q_insert_head(q, buf);
    fclose(fp);

    print(q);
    list_merge_sort(q);
    assert(validate(q));
    print(q);
    q_free(q);

    return 0;
}

執行 gcc -o q1 q1.c 結果 (input 為 cities.txt)

 ..............
 Burnopfield, United Kingdom
 Novonikolayevka, Ukraine
 Yertsevo, Russia
 Apango, Guerrero, Mexico
 Weggis, Switzerland
 Bammatyurt, Russia
 Buray, Philippines
 Uggiate-Trevano, Italy
 Saint-Pantaléon-de-Larche, France
 ..............
 Yāşīd, Palestinian Territory
 Zaamslag, Netherlands
 Zabeltitz, Germany
 Zaberfeld, Germany
 Zabierzów Bocheński, Poland
 Zabok, Croatia
 Zabolotovka, Russia
 Zaborze, Poland
 Zabrušany, Czech Republic
 Zabrzeg, Poland
 Zabór, Poland
 Zabłocie, Poland
 Zabłudów, Poland
 Zachenberg, Germany
 Zacualpan, México, Mexico
 Zadelsdorf, Germany
 ..............

測驗 2

函式 func 接受一個 16 位元無號整數 N，並回傳小於或等於 N 的 power-of-2 (漢字可寫作為 2 的冪)
實作程式碼如下









uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> X;
    N |= N >> Y;
    N |= N >> Z;

    return (N + 1) >> 1;
}

思考函數的意義

例如 N 為 30(0b11110) 或 20(0b10100)，為求小於等於 N 之二的冪，答案皆為 16(0b10000) ，觀察發現其實函數的輸出只跟 N 的二進制之 MSB(most signicant bit) 有關，輸入的值二進制最左邊的 1 才是關鍵。
思路：關注二進制最左邊的 1，其他的 1 視為 don't care
- 設輸入 N 為 : 0b0010001110001101
- N |= N >> 1: 0b0011001111001111
- N |= N >> 2: 0b0011111111111111
- N |= N >> 4: 0b0011111111001111
- N |= N >> 8: 0b0011111111111111
- (N + 1) : 0b01000000000000000
- (N + 1) >> 1 : 0b00100000000000000
可見函數是利用 2 進制的 MSB 來進行 Bitwise 操作，忽略 MSB 以下的值，藉由關鍵的 MSB 並善用 >> 和 | 運算子來將 MSB 以後的值都變成 1 ，再 +1 進位到產生"大於 N 之最大的二的冪"並右移一位來得到答案。
換句話說，若最後不進行右移的動作，函數即便成了回傳大於 N 之最小的二的冪。

測驗 3

題目所實做的為一個逐 bit 複製 data 給目標的函式，因為牽涉到 bitwise 的操作，因此要熟練 c 語言對於 bitwise 操作如 |,&,>>,<<,bitmask 或數字的二進制表示法等，並了解函數操作其中的意義。
以下程式碼擷取自題目的 bitcpy 函數：



























    while (count > 0) {
        uint8_t data = *source++;
        size_t bitsize = (count > 8) ? 8 : count;
        if (read_lhs > 0) {
            data <<= read_lhs /*RRR*/;
            if (bitsize > read_rhs)
                data |= (*source >> read_rhs);
        }

        if (bitsize < 8)
            data &= read_mask[bitsize];

        uint8_t original = *dest;
        uint8_t mask = read_mask[write_lhs];
        if (bitsize > write_rhs) {
            /* Cross multiple bytes */
            *dest++ = (original & mask) | (data >> write_lhs);
            original = *dest & write_mask[bitsize - write_rhs];
            *dest = original | (data << write_rhs);
        } else {
            // Since write_lhs + bitsize is never >= 8, no out-of-bound access.
            mask |= write_mask[write_lhs + bitsize] /*DDD*/;
            *dest++ = (original & mask) | (data >> write_lhs);
        }

        count -= bitsize;
    }

由程式碼可觀察出 count 為總共要複製的 bit 數，而 bitsize 為 while 迴圈進行一輪所複製的 bit 數 (bitsize <= 8)，而 data 為一個從 _src 複製的 buffer ，經過偏移量的處理，要把正確的資料複製給 dest，大小為一個 byte。
read_lhs(write_lhs) 和 read_rhs(write_rhs) 主要是操作從一個 byte 的角度處理 bit-offset 的變數，因為記憶體是以 byte 當作單位，因此 bit level 需要充分善用 c 中 bitwise 的特性，也是 bitcpy 最關鍵的變數之一。

read_lhs 為 byte 中的左偏移量； read_rhs 為右偏移量，兩者相加為 8 (1 byte 為 8 bits)。

假設 source 指標所指的 byte 的值為 00101110, read_lhs=3 , read_rhs=5
```
data=source++; /* (*source) = 0b00101110 */
```
上述程式碼執行之後的狀況

偏移量 read_lhs, read_rhs 對 data 的表示：

先觀察第 4~8 行 if 的敘述，若 read_lhs > 0 ，則必須從 byte 由左往右數第 read_lhs + 1 個 bit 開始讀取，相當於是先把 data 左移 read_lhs 個 bit。

因為 read_rhs 代表 byte 中右邊的 bit 數，因此若 bitsize > read_rhs，則此回合會跨 byte 讀取資料至 data，因此要借用剛剛 source++ 後的位址，進行 data |= (*source >> read_rhs)

最後再依據 bitsize 和 read_mask 來將要複製的 bit 進行 & 運算

假設 bitsize = 7

data 結果變為 01110100

類似的原理，觀察 13 到 24 行

uint8_t original = *dest;
uint8_t mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
   /* Cross multiple bytes */
   *dest++ = (original & mask) | (data >> write_lhs);
   original = *dest & write_mask[bitsize - write_rhs];
   *dest = original | (data << write_rhs);
} else {
   // Since write_lhs + bitsize is never >= 8, no out-of-bound access.
   mask |= write_mask[write_lhs + bitsize] /*DDD*/;
   *dest++ = (original & mask) | (data >> write_lhs);
}

以下假設 write_lhs=5, write_rhs=3, bitsize=7, data=01101100

if 區塊的程式碼主要適用於要跨兩個 byte 把資料寫入 dest 中

其中(original & mask) | (data >> write_lhs) 這段程式碼是將 data 中的資料寫入 dest (此時指向左半邊的 byte)，例如 mask = 0b11111000 ， original & mask 相當於先將 original 所指向的 byte 的右邊 3 個 bits 做清空的動作，因為會跨 byte 寫入，因此清空的 3 個 bit 之後會被寫入的資料取代。

而 original = *dest & write_mask[bitsize - write_rhs] 為先將 dest (此時指向右半邊的 byte) 左邊進行清空的動作。例如 write_rhs=3; bitsize=7 代表 dest 左邊兩個 bit 會被寫入（因為左邊 byte 中右邊 3 個 bits 被寫入， 7 - 3 = 4 剩下 4 bit 給右邊 byte）。

*dest = original | (data << write_rhs) 這行是將 data 複製到 dest 中，由於 data 的左邊 write_lhs 個 bit 已複製完成，故現在把剩下的 bit 資料複製給 dest 。

結果如下

else 區塊成處理是處理未跨 byte 資料寫入至 dest
- mask |= write_mask[write_lhs + bitsize] 的目的為將 dest 左邊及右邊不需要被寫入的 bit 保留，如 wrtie_lhs = 5,mask 原先為 0b11111000, bitsize = 2, 操作後 mask ＝ 0b11111001，這個 mask 在下一行和 original 做 & 運算，代表 original 只有第 6, 7 兩個會被寫入的 bit 位置被 mask 清空，而把清空過的 original 和 (data >> write_lhs) （即右移 write_lhs 個 bit 的資料）進行 | 運算，成功把資料複製進 dest 中。

2021q1 Homework2 (quiz2)

Todo

重寫測驗

測驗 1

探討 list_cut_position 函數

探討 get_middle 函數

考慮 container_of 的定義：

改寫程式碼

測驗 2

思考函數的意義

測驗 3

測驗 4

Read more

Parallel Programming HW6

Parallel Programming HW5

Parallel Programming HW4

Parallel Programming HW2

探討 `list_cut_position` 函數

探討 `get_middle` 函數

考慮 `container_of` 的定義：