contributed by < fatcatorange
>
在以下程式嗎中,應是要取得串列的尾端指標,因此此處透過 while 迴圈逐個向後,直到串列尾端,故 AAAA
應為 (*left)->next
同樣的,在BBBB
中,要求的是整個佇列的長度,因此同樣為 (*left)->next
接下來分析 quick_sort 的函式:
首先,初始時 begin[0] 為串列開頭,end[0] 則為串列尾端。
在每一輪開始時,將 pivot 設定 begin[i],並由 pivot 的下一元素開始執行:
接下來,程式開始由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)。
到這裡,已經將原本的 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 項事項:
目前沒有找到 seq 第一次是在哪裡定義,其含意應是元素原始的出現順序
接下來為 timsort 的程式碼部份:
首先,創建一個 head 指標,並且在一開始將 tail 指向 head 的位址,因此 AAAA 應為:
接下來,此處會透過指標的指標操作,先比較 a, b 兩節點的值,若 a 較小或相等,代表目前應該插入的是 a ,因此將執行 *tail = a
,可參考下圖(省略部份未用到的節點內容),假設初始有a, b 指標和 tail 指向 head 的位址:
當 a->val 比 b->val 小時,先將 tail 指向的指標改為指向 a,在第一次時就是 head,因此變為:
接下來,改將 tail 指向 a->next 的指標,並將 a 改為 a->next,也就是改為:
此處的 tail 並非指向 list_head_a1 ,而是 list_head_a1 的 next 指標的位址,這樣等一下要進行插入時,可以直接修改 next 指標指向的位址。
下一輪因為 b 指向的 b1 的值比 a 指向的 a2 的值小,因此是要插入 b1 的節點,這時可以透過修改 tail 指向的指標(也就是 a1 的 next)來達成,也就是變為:
然後和前面一樣,tail 改為指向 b->next 指標的位址,並把 b 改為 b->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 的節點已經用盡:
則會將 b 串列和 head, tail 進行 build_prev_link
而如果是 b 串列先耗盡:
由於 b 也已經改成指向串列 a ,因此可以同樣透過
build_prev_link(head, tail, b);
來完成串接後面的節點。
在此函式中目標是要找出一組 run ,而其回傳值是一個 struct,內容包含該 run 的開頭和結尾。
例如,假設有以下節點,初始狀態為(藍色代表指標):
接下來就會檢查 list->data 和 next->data,這裡的狀況是 list 的值較大,因此會執行:
執行上述步驟後,會變為以下狀況:
接下來會檢查 list->data 是否仍大於 list->data 若是則繼續重複執行,否則跳離迴圈
這裡的範例已經不符合,因此離開迴圈,而離開後會在將 prev->next 設為 list,因此結果為:
若單純只看 next 指標,程式已經成功找出了一組 run:
而未設定好的 prev 指標則可在後續 merge 時透過build_prev_link
設定,可以發現這麼做之後還會把 new 的節點反轉過來。
考慮另一情況,就是一開始 list->data <= next->data 時:
此時,程式執行以下程式碼一輪後會是:
實際上,就是不需要做特別的事,因為原本就是按照順序的了,因此串列最後的狀況就會是
不管是何種情況,最後要把 head 的 prev 改為 NULL 來切斷與前面的連接,並在最前面接上一個開頭head->next->prev = (struct list_head *) len;
,最後將 head, next 回傳即可。
有了前面那些函式,可以開始分析 timsort,首先,函式透過迴圈不斷找出 run ,當 run 數量達成一定條件(還在看…)時會先進行合併。
接下來,透過 merge_force_collapse
合併所有 run。
最後,因為剛才接上的可能有些是在 find_run 中的狀況一,其 prev 節點未設定好,透過 build_prev_link 調整好。
後面的一些程式碼目前只能看懂大致架構..
首先,此串列的結構應如下:
假設要把 n 指向的節點插入此串列的開頭,可以透過修改目前第一個節點的 pprev 指標,因為這個指標指向的是 h 的 first 指標,透過指標的指標可以直接修改,也就是改為指向 n 指向的節點的 next 指標的位址
接下來必須讓 n 指向的節點的 next 指標指向原本的第一個節點,並將 n 指向的節點的 pprev 指標指向為 h->first 的位址,並把 h->first 改為指向 n 指向的節點,也就是:
這樣就完成了插入頭的行為,因此 AAAA
應為 h->first。
首先,函式會先針對整個串列進行遍歷,根據 hlist_for_each
巨集, BBBB 的內容應為此串列的 head,因此應為 heads
傳入的 heads 應為一個包含多個 head 節點的陣列,因此 BBBB 應為 &(heads[hash]),代表到那個 bucket 去找是否存在資料。
在每一輪,函式創建一個 order_node pointer,由此處可知 CCCC 應為 list_entry。
此處是在檢查是否在指定的串列中找到該數,若有則回傳 index,否則回傳 1。
此函式用於將值插入某個 bucket,首先先分配一塊節點空間,接下來根據其值算出應該插在哪一個 bucket 後即可透過 node_add_head 插入,概念和前個函式相似, DDDD 應為 &(heads[hash])
在此函式中要刪除特定的節點,因此透過修改 pprev 這個指標指向的位置來達成,具體如下,假設要刪除紅色節點:
透過以下操作,串列變成:
接下來只要透過再修改 next 指標的 pprev 的指標改為指向 pprev,就可以完成移除該節點的操作:
因此, EEEE 應填入 next->pprev。
此處在把 cache 內的節點釋放,因為其透過 list_for_each_safe 巨集,且 pos, n 為 list_head 型態的指標,因此 FFFF 的 member_name 應為 link。
而在刪除節點時,是要傳入該節點的 link 部份的指標,實際上就是 pos 指標,因此 GGGG 應為 pos。
此處在抓取 cache 內某個節點並將其移動至最前面,因此 HHHH 部份應為 node,因為目前是在遍歷 hlist 而不是普通的 list 。
接下來就可以透過 list_move 來把 pos 指向的節點移動到前面
部份待補
巨集__const_hweight8(w)
:
這個巨集主要在計算共有多少個 bit 被設定成 1,首先假如有一個值 200,那麼他的二進位表示法為:
假設我們對這個數字進行
相當於不進行左移,而其結果就是 200 & 1 的結果,那其實就是看:
也就是看最後一位元是否為 1 ,此處是否,因此回傳 0 。
至於!!
的用意,以另一個例子來看,如 (!!((w) & (1ULL << 3)))
這時會回傳結果 8 ,但不能直接把 8 加上去,因此首先透過 ! 符號,當結果 > 0 時就會變為 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
假如對 10010000 做這個操作:
此處不為 0 ,因此繼續往下:
此處為答案為 0 ,因此執行 if 內的行為後繼續往下:
此處不為 0 ,因此繼續往下:
仍不為 0 ,中止條件,因此答案為 4
由上述規律,可判斷 AAAA 為 0xffffffff
這個函式在清掉 index nr 的 bit, 首先 BIT_MASK(nr) 巨集將返回一個值,其 bit 除了 nr 外皆為 0,例如:
因此,透過 *p &= ~mask 即可完成 clear_bit,例如:
其mask:
而 *addr & ~mask 即為:
因此, BBBB 應為 ~mask。
這個函式是尋找第 n 個 set bit,概念其實比較簡單,例如假如要找第 2 個:
先透過 ffs 找到第一個,之後把這個 bit 用 clear_bit 清掉
之後再找一次 ffs 就是答案,假如要找第 n 個,就是做 n-1 次 ffs和 clear_bit 後,再做一次 ffs 的結果就是答案。