Try   HackMD

2024q1 Homework2 (quiz1+2)

contributed by < fatcatorange >

第一周測驗題:

測驗一

在以下程式嗎中,應是要取得串列的尾端指標,因此此處透過 while 迴圈逐個向後,直到串列尾端,故 AAAA 應為 (*left)->next

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &(AAAA);
    return *left;
}

同樣的,在BBBB 中,要求的是整個佇列的長度,因此同樣為 (*left)->next

接下來分析 quick_sort 的函式:

首先,初始時 begin[0] 為串列開頭,end[0] 則為串列尾端。
在每一輪開始時,將 pivot 設定 begin[i],並由 pivot 的下一元素開始執行:

node_t *L = begin[i], *R = end[i];
if (L != R) {
    node_t *pivot = L;
    value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

接下來,程式開始由pivot的下個元素開始,逐一比對當前節點的 value 值是否比 pivot 大,若是則加入 right(將該節點設為 right 的頭,並連接原本的 right head),否則加入 left 。

因此,此處 CCCC 應為 p->next。

之後就是將 left 和 right 加入陣列中,此處 begin[i] 為left,而 end[i] 會是這個部份的尾端,因此應為 list_tail(left),而 begin[i+1]、end[i+1] 放入的是pivot, begin[i+2] 放入 right,尾端則同樣放入 list_tail(right)。

begin[i] = left;
end[i] = list_tail(left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(right);

到這裡,已經將原本的 list 切成三部份:
begin[i] ~ end[i]:比 pivot 小的部份
begin[i+1] ~ end[i+1]:pivot 自己一個點
begin[i+2] ~ end[i+2]:比 pivot 大的部份

到下一輪時,會由 begin[i+2] 和 end[i+2] 開始一樣步驟,假設此時
begin[i+2] != end[i+2]: 重做剛才的步驟,再切成三等份
否則的話,代表這部份只剩下一個節點或零個節點:
若為一個節點,將該節點加入結果
然後將 i ,代表這個部份做完了

由於每次切割後都是 i+=2,也就是針對比 pivot 大的部份進行動作,因此最早被加進 result 的必定是最大的,而下個被加入的是第二大的,又因為每次插入都是插在頭節點前面,因此最後結果就會是一由小至大排序好的串列。

測驗二

測試程式碼:

create_sample: 創建一個鍊結串列,內容隨機。
copy_list: 創見一個 from 為開頭的串列的複製,並放入 space 陣列中

此處 space 是一個陣列,內容是一堆 element_t ,因此 space 指標才能直接進行 ++ 操作

compare: 回傳兩節點內值的大小差距,並把 priv 指標內的值 +1。
check_list: 透過 list_for_each_entry_safe 巨集檢查所有節點是否有按照順序排列,因為此巨集會有一個 safe 指標會在每一輪先更新成 entry 的 next ,因此透過 safe 可以直接當成是 entry 的下一個節點。

此函式會檢查 3 項事項:

  1. 是否按照順序排列,可透過檢查 entry 和 safe 節點的值得知
  2. 是否為 stable (假如原本有兩個 1,以 1 和 1代表,若原本順序事先 1 才是 1,排序後不能變成先 1 才 1),可以透過檢查 seq 得知,若後面的點 seq 比前面的節點的 seq 還大,代表並不是 stable。

目前沒有找到 seq 第一次是在哪裡定義,其含意應是元素原始的出現順序

  1. 節點數是否和原先串列的節點數相同。

接下來為 timsort 的程式碼部份:

首先,創建一個 head 指標,並且在一開始將 tail 指向 head 的位址,因此 AAAA 應為:

&head

接下來,此處會透過指標的指標操作,先比較 a, b 兩節點的值,若 a 較小或相等,代表目前應該插入的是 a ,因此將執行 *tail = a,可參考下圖(省略部份未用到的節點內容),假設初始有a, b 指標和 tail 指向 head 的位址:







QueueRelationships



alist_1

list_node_a1

next: list_head*

val:int = 1



alist_2

list_node_a2

next: list_head*

val:int = 3



alist_1->alist_2





alist_3

list_node_a3

next: list_head*

val:int = 5



alist_2->alist_3





a

a



a->alist_1





blist_1

list_node_b1

next: list_head*

val:int = 2



blist_2

list_node_b2

next: list_head*

val:int = 4



blist_1->blist_2





blist_3

list_node_b3

next: list_head*

val:int = 6



blist_2->blist_3





b

b



b->blist_1





tail

tail



head

head



tail->head





當 a->val 比 b->val 小時,先將 tail 指向的指標改為指向 a,在第一次時就是 head,因此變為:







QueueRelationships



alist_1

list_node_a1

next: list_head*

val:int = 1



alist_2

list_node_a2

next: list_head*

val:int = 3



alist_1->alist_2





alist_3

list_node_a3

next: list_head*

val:int = 5



alist_2->alist_3





a

a



a->alist_1





blist_1

list_node_b1

next: list_head*

val:int = 2



blist_2

list_node_b2

next: list_head*

val:int = 4



blist_1->blist_2





blist_3

list_node_b3

next: list_head*

val:int = 6



blist_2->blist_3





b

b



b->blist_1





tail

tail



head

head



tail->head





head->alist_1





接下來,改將 tail 指向 a->next 的指標,並將 a 改為 a->next,也就是改為:







QueueRelationships



alist_1

list_head_a1

next: list_head*

val:int = 1



alist_2

list_head_a2

next: list_head*

val:int = 3



alist_1->alist_2





alist_3

list_head_a3

next: list_head*

val:int = 5



a

a



a->alist_2





blist_1

list_head_b1

next: list_head*

val:int = 2



blist_2

list_head_b2

next: list_head*

val:int = 4



blist_1->blist_2





blist_3

list_head_b3

next: list_head*

val:int = 6



blist_2->blist_3





b

b



b->blist_1





tail

tail



tail->alist_1:next


指向 a1->next 的位址



此處的 tail 並非指向 list_head_a1 ,而是 list_head_a1 的 next 指標的位址,這樣等一下要進行插入時,可以直接修改 next 指標指向的位址。

下一輪因為 b 指向的 b1 的值比 a 指向的 a2 的值小,因此是要插入 b1 的節點,這時可以透過修改 tail 指向的指標(也就是 a1 的 next)來達成,也就是變為:







QueueRelationships



alist_1

list_head_a1

next: list_head*

val:int = 1



blist_1

list_head_b1

next: list_head*

val:int = 2



alist_1->blist_1





alist_2

list_head_a2

next: list_head*

val:int = 3



alist_3

list_head_a3

next: list_head*

val:int = 5



alist_2->alist_3





a

a



a->alist_2





blist_2

list_head_b2

next: list_head*

val:int = 4



blist_1->blist_2





blist_3

list_head_b3

next: list_head*

val:int = 6



blist_2->blist_3





b

b



b->blist_1





tail

tail



tail->alist_1





然後和前面一樣,tail 改為指向 b->next 指標的位址,並把 b 改為 b->next , 因此會變成:







QueueRelationships



alist_1

list_head_a1

next: list_head*
 val:int = 1



blist_1

list_head_b1

next: list_head*

val:int = 2



alist_1->blist_1





alist_2

list_head_a2

next: list_head*
 val:int = 3



alist_3

list_head_a3

next: list_head*
 val:int = 5



alist_2->alist_3





a

a



a->alist_2





blist_2

list_head_b2

next: list_head*

val:int = 4



blist_3

list_head_b3

next: list_head*

val:int = 6



blist_2->blist_3





b

b



b->blist_2





tail

tail



tail->blist_1:next


指向 b1->next的指標



依照這個步驟持續下去,最後就可以完成 merge

此處最值得注意的就是 merge 是透過指標的指標直接修改了目前 tail 節點的 next 指標指向的位址,因此就不需要額外配置空間。

因此, BBBB 應為 &(a->next), CCCC 則為 &(b->next)

接下來, build_prev_link 將 list 串列接上 tail,因此程式開始時先將 tail->next = list

接下來,將list->prev 接上 tail,並且將 list 和 tail 往前,直到 list 為 NULL。

最後必須結束時 list 為 NULL,而 tail 會是最後一個節點,將 tail->next 接到 head,並將 head->prev 接到 tail 形成環狀鏈結串列。

DDDD 為 tail->next
EEEE 為 head->prev

list->prev = tail?

merge_final:將 a, b 兩串列 merge,每輪將較小的節點連接至要回傳的串列,如果 a 的節點先用盡,會用 build_prev_link 來連接剩下的 b 串列的節點,否則將 b 指標改為 a 後再做 build_prev_link

例如此情況 a 的節點已經用盡:







QueueRelationships



alist_1

list_head_a1

next: list_head*
 val:int = 1



head

head



head->alist_1





tail

tail



tail->alist_1





a

a



NULL

NULL



a->NULL





blist_1

list_head_b1

next: list_head*
 val:int = 2



blist_2

list_head_b2

next: list_head*
 val:int = 4



blist_1->blist_2





blist_3

list_head_b3

next: list_head*
 val:int = 6



blist_2->blist_3





b

b



b->blist_1





則會將 b 串列和 head, tail 進行 build_prev_link

而如果是 b 串列先耗盡:







QueueRelationships



alist_1

list_head_a1

next: list_head*
 val:int = 1



blist_1

list_head_b1

next: list_head*
 val:int = 2



alist_1->blist_1





alist_2

list_head_a1

next: list_head*
 val:int = 7



alist_3

list_head_a1

next: list_head*
 val:int = 9



alist_2->alist_3





head

head



head->alist_1





tail

tail



tail->alist_1





a

a



a->alist_2





blist_2

list_head_b2

next: list_head*
 val:int = 4



blist_1->blist_2





blist_3

list_head_b3

next: list_head*
 val:int = 6



blist_2->blist_3





b

b



b->alist_2





由於 b 也已經改成指向串列 a ,因此可以同樣透過
build_prev_link(head, tail, b);來完成串接後面的節點。

find_run

在此函式中目標是要找出一組 run ,而其回傳值是一個 struct,內容包含該 run 的開頭和結尾。

例如,假設有以下節點,初始狀態為(藍色代表指標):







structs



prev

prev



NULL

NULL



prev->NULL





list

list



struct1

prev

data:6

next



list->struct1





head

head



head->struct1





next

next



struct2

prev

data:4

next



next->struct2





struct1:next->struct2





struct2:prev->struct1





struct3

prev

data:5

next



struct2:next->struct3





struct3:prev->struct2





struct4

prev

data:7

next



struct3:next->struct4





struct4:prev->struct3





接下來就會檢查 list->data 和 next->data,這裡的狀況是 list 的值較大,因此會執行:

len++;
list->next = prev;
prev = list;
list = next;
next = list->next;
head = list;

執行上述步驟後,會變為以下狀況:







structs



prev

prev



struct1

prev

data:6

next



prev->struct1





list

list



struct2

prev

data:4

next



list->struct2





head

head



head->struct1





next

next



struct3

prev

data:5

next



next->struct3





NULL

NULL



struct1:next->NULL





struct2:prev->struct1





struct2:next->struct3





struct3:prev->struct2





struct4

prev

data:7

next



struct3:next->struct4





struct4:prev->struct3





接下來會檢查 list->data 是否仍大於 list->data 若是則繼續重複執行,否則跳離迴圈
這裡的範例已經不符合,因此離開迴圈,而離開後會在將 prev->next 設為 list,因此結果為:







structs



prev

prev



struct1

prev

data:6

next



prev->struct1





list

list



struct2

prev

data:4

next



list->struct2





head

head



head->struct1





next

next



struct3

prev

data:5

next



next->struct3





NULL

NULL



struct1:next->NULL





struct2:prev->struct1





struct2:next->struct1





struct3:prev->struct2





struct4

prev

data:7

next



struct3:next->struct4





struct4:prev->struct3





若單純只看 next 指標,程式已經成功找出了一組 run:







structs



struct1

prev

data:6

next



NULL

NULL



struct1:next->NULL





struct2

prev

data:4

next



struct2:next->struct1





而未設定好的 prev 指標則可在後續 merge 時透過build_prev_link設定,可以發現這麼做之後還會把 new 的節點反轉過來。

考慮另一情況,就是一開始 list->data <= next->data 時:







structs



prev

prev



NULL

NULL



prev->NULL





list

list



struct1

prev

data:1

next



list->struct1





head

head



head->struct1





next

next



struct2

prev

data:2

next



next->struct2





struct1:next->struct2





struct2:prev->struct1





struct3

prev

data:5

next



struct2:next->struct3





struct3:prev->struct2





struct4

prev

data:7

next



struct3:next->struct4





struct4:prev->struct3





此時,程式執行以下程式碼一輪後會是:

do {
    len++;
    list = next;
    next = list->next;
} while (next && cmp(priv, list, next) <= 0);
list->next = NULL;






structs



prev

prev



NULL

NULL



prev->NULL





list

list



struct2

prev

data:2

next



list->struct2





head

head



struct1

prev

data:1

next



head->struct1





next

next



struct3

prev

data:5

next



next->struct3





struct1:next->struct2





struct2:prev->struct1





struct2:next->struct3





struct3:prev->struct2





struct4

prev

data:7

next



struct3:next->struct4





struct4:prev->struct3





實際上,就是不需要做特別的事,因為原本就是按照順序的了,因此串列最後的狀況就會是







structs



prev

prev



NULL

NULL



prev->NULL





list

list



struct4

prev

data:7

next



list->struct4





head

head



struct1

prev

data:1

next



head->struct1





next

next



next->NULL





struct2

prev

data:2

next



struct1:next->struct2





struct2:prev->struct1





struct3

prev

data:5

next



struct2:next->struct3





struct3:prev->struct2





struct3:next->struct4





struct4:prev->struct3





不管是何種情況,最後要把 head 的 prev 改為 NULL 來切斷與前面的連接,並在最前面接上一個開頭head->next->prev = (struct list_head *) len;,最後將 head, next 回傳即可。

timsort

有了前面那些函式,可以開始分析 timsort,首先,函式透過迴圈不斷找出 run ,當 run 數量達成一定條件(還在看)時會先進行合併。

    do {
        /* Find next run */
        struct pair result = find_run(priv, list, cmp);
        result.head->prev = tp;
        tp = result.head;
        list = result.next;
        stk_size++;
        tp = merge_collapse(priv, cmp, tp);
    } while (list);

接下來,透過 merge_force_collapse 合併所有 run。

最後,因為剛才接上的可能有些是在 find_run 中的狀況一,其 prev 節點未設定好,透過 build_prev_link 調整好。

後面的一些程式碼目前只能看懂大致架構..

第二週測驗

測驗一

list_add_head:

首先,此串列的結構應如下:







structs



head

h

first



struct1

pprev

data:6

next



head:first->struct1





struct1:prev->head:first





struct2

pprev

data:4

next



struct1:next->struct2





struct2:prev->struct1:next





struct3

pprev

data:5

next



struct2:next->struct3





struct3:prev->struct2:next





struct4

pprev

data:7

next



n

n



n->struct4





假設要把 n 指向的節點插入此串列的開頭,可以透過修改目前第一個節點的 pprev 指標,因為這個指標指向的是 h 的 first 指標,透過指標的指標可以直接修改,也就是改為指向 n 指向的節點的 next 指標的位址







structs



head

h

first



struct1

pprev

data:6

next



head:first->struct1





struct2

pprev

data:4

next



struct1:next->struct2





struct4

pprev

data:7

next



struct1:prev->struct4:next





struct2:prev->struct1:next





struct3

pprev

data:5

next



struct2:next->struct3





struct3:prev->struct2:next





n

n



n->struct4





接下來必須讓 n 指向的節點的 next 指標指向原本的第一個節點,並將 n 指向的節點的 pprev 指標指向為 h->first 的位址,並把 h->first 改為指向 n 指向的節點,也就是:







structs



head

h

first



struct4

pprev

data:7

next



head:first->struct4





struct1

pprev

data:6

next



struct2

pprev

data:4

next



struct1:next->struct2





struct1:prev->struct4:next





struct2:prev->struct1:next





struct3

pprev

data:5

next



struct2:next->struct3





struct3:prev->struct2:next





struct4:prev->head:first





struct4:next->struct1





n

n



n->struct4





這樣就完成了插入頭的行為,因此 AAAA應為 h->first。

find:

首先,函式會先針對整個串列進行遍歷,根據 hlist_for_each 巨集, BBBB 的內容應為此串列的 head,因此應為 heads
傳入的 heads 應為一個包含多個 head 節點的陣列,因此 BBBB 應為 &(heads[hash]),代表到那個 bucket 去找是否存在資料。

在每一輪,函式創建一個 order_node pointer,由此處可知 CCCC 應為 list_entry。

此處是在檢查是否在指定的串列中找到該數,若有則回傳 index,否則回傳 1。

node_add:

此函式用於將值插入某個 bucket,首先先分配一塊節點空間,接下來根據其值算出應該插在哪一個 bucket 後即可透過 node_add_head 插入,概念和前個函式相似, DDDD 應為 &(heads[hash])

測驗二

hlist_del:

在此函式中要刪除特定的節點,因此透過修改 pprev 這個指標指向的位置來達成,具體如下,假設要刪除紅色節點:







structs



head

h

first



struct4

pprev

data:7

next



head:first->struct4





struct1

pprev

data:6

next



struct2

pprev

data:4

next



struct1:next->struct2





struct1:prev->struct4:next





struct2:prev->struct1:next





struct3

pprev

data:5

next



struct2:next->struct3





struct3:prev->struct2:next





struct4:prev->head:first





struct4:next->struct1





n

n



n->struct2





透過以下操作,串列變成:

    struct hlist_node *next = n->next, **pprev = n->pprev;
    *pprev = next;






structs



head

h

first



struct4

pprev

data:7

next



head:first->struct4





struct1

pprev

data:6

next



struct3

pprev

data:5

next



struct1:next->struct3





struct1:prev->struct4:next





struct2

pprev

data:4

next



struct2:next->struct3





struct3:prev->struct2:next





struct4:prev->head:first





struct4:next->struct1





next

next



next->struct3





n

n



n->struct2





pprev

pprev



pprev->struct3:prev





接下來只要透過再修改 next 指標的 pprev 的指標改為指向 pprev,就可以完成移除該節點的操作:







structs



head

h

first



struct4

pprev

data:7

next



head:first->struct4





struct1

pprev

data:6

next



struct3

pprev

data:5

next



struct1:next->struct3





struct1:prev->struct4:next





struct2

pprev

data:4

next



struct2:next->struct3





struct3:prev->struct1:next





struct4:prev->head:first





struct4:next->struct1





next

next



next->struct3





因此, EEEE 應填入 next->pprev。

LRUCacheFree:

此處在把 cache 內的節點釋放,因為其透過 list_for_each_safe 巨集,且 pos, n 為 list_head 型態的指標,因此 FFFF 的 member_name 應為 link。

而在刪除節點時,是要傳入該節點的 link 部份的指標,實際上就是 pos 指標,因此 GGGG 應為 pos。

LRUCacheGet:

此處在抓取 cache 內某個節點並將其移動至最前面,因此 HHHH 部份應為 node,因為目前是在遍歷 hlist 而不是普通的 list 。

接下來就可以透過 list_move 來把 pos 指向的節點移動到前面

void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, node);
        list_del(pos);
        free(cache);
    }
    free(obj);
}

部份待補

測驗三

巨集__const_hweight8(w)

#define __const_hweight8(w)                                              \
    ((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
                     (!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
                     (!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
                     (!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))

這個巨集主要在計算共有多少個 bit 被設定成 1,首先假如有一個值 200,那麼他的二進位表示法為:

11001000

假設我們對這個數字進行

(!!((w) & (1ULL << 0)))

相當於不進行左移,而其結果就是 200 & 1 的結果,那其實就是看:

11001000
00000001
--------
00000000

也就是看最後一位元是否為 1 ,此處是否,因此回傳 0 。
至於!!的用意,以另一個例子來看,如 (!!((w) & (1ULL << 3)))

11001000
00001000
--------
00001000

這時會回傳結果 8 ,但不能直接把 8 加上去,因此首先透過 ! 符號,當結果 > 0 時就會變為 0 ,否則變為 1。

因此, !! 符號的用意為:

!!8->!0->1

也就是當結果 > 0 時變 1 ,否則不變。

因此,做 8 次就是取前8位元不為0的 bit 數。

__const_hweight16 實際上就是做兩次,但第一次做前 8 位元,第二次做後 8 位元。

後面也都相同,例如 __const_hweight32 就做兩次 __const_hweight16
__const_hweight64(w) 就做兩次 __const_hweight32

__ffs 主要功能就是找到第一個不為 1 的在第幾位,因為概念類似,此處假設只有 8-bit

if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }

假如對 10010000 做這個操作:

num = 0
10010000
11111111
--------
10010000

此處不為 0 ,因此繼續往下:

if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
num = 0
10010000
00001111
--------
00000000

此處為答案為 0 ,因此執行 if 內的行為後繼續往下:

if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }

num = 4
00001001
00000011
--------
00000001

此處不為 0 ,因此繼續往下:

 if ((word & 0x1) == 0)
        num += 1;

num = 4
00001001
00000001
--------
00000001

仍不為 0 ,中止條件,因此答案為 4

由上述規律,可判斷 AAAA 為 0xffffffff

__clear_bit

這個函式在清掉 index nr 的 bit, 首先 BIT_MASK(nr) 巨集將返回一個值,其 bit 除了 nr 外皆為 0,例如:

    BIT_MASK(5)
  ->000...00100000

因此,透過 *p &= ~mask 即可完成 clear_bit,例如:

nr = 5
*addr = 11110111

其mask:

00100000

而 *addr & ~mask 即為:

11010111

因此, BBBB 應為 ~mask。

fns

這個函式是尋找第 n 個 set bit,概念其實比較簡單,例如假如要找第 2 個:

11010011

先透過 ffs 找到第一個,之後把這個 bit 用 clear_bit 清掉

11010010

之後再找一次 ffs 就是答案,假如要找第 n 個,就是做 n-1 次 ffs和 clear_bit 後,再做一次 ffs 的結果就是答案。