contributed by < zeddyuu >
queue.[ch]
程式釋放佇列所佔用的所有記憶體,這邊剛開始是使用 list_for_each
,但沒有考慮到刪除當前節點後,下個節點的位置就找不到了,需要一個額外暫存下個節點的指標,故改用 list_for_each_safe
完成。
宣告一個新的 element
接著處理它的 value
成員,考慮到空字元,先分配此字串長度 + 1 的記憶體空間,再利用 memcpy
將參數 s 的內容複製到此空間, value
指向此空間,最後用 list_add
將 element
加入到佇列的開頭。
在分配記憶體空間給 s_new 時,須注意若分配失敗要將已分配給 element 的記憶體空間釋放掉,否則會引起 memory leak 的問題。
做法和 q_insert_head
相同,差別在於使用 list_add_tail
。
先確認head是否為NULL
以及empty
,使用 list_first_entry
得到佇列第一個 element ,隨後確認參數 sp 以及 bufsize 是否合理 , 再用 strncpy
複製欲刪除 element 的 value 成員到 sp 中,記得加上空字元,最後用 list_del
刪除元素。
做法和 q_remove_head
相同,差別在於使用 list_last_entry
。
先確認 head 是否為NULL
以及empty
,使用 list_for_each
走訪佇列並計算 node 總數。
還沒想到有沒有較快解法,目前只想到最直觀的解法是走訪過一次計算 node 總數,接著再走訪一次到中間 node 做指標操作(直接 list_del
就好),時間複雜度是 。
要注意刪除 node 的操作要配合 list_for_each_entry_safe
。
看了 你所不知道的 C 語言: linked list 和非連續記憶體 中所提到的快慢指標的方法,利用兩個步數不同的指標 slow 和 fast,當 fast 走完整個 list,slow 的位置剛好指到中間的節點,再釋放 slow 指標所指到的記憶體位置即可完成更精簡的 q_delete_mid
操作。
使用 list_for_each_entry_safe
每次迭代會紀錄下個節點,並且比較當前和下個節點的字串,利用一個 flag 去紀錄是否重複來決定下次迴圈是否要刪除節點,
將 while
敘述改為 for
迴圈,撰寫更精簡的程式碼。
使用 for
敘述取代 while
,改成更 精簡的程式碼。
從 head 後第一個 node 開始走訪每一個節點,使用 list_move
將當前 node 移到下個 node 後一位,此操作等同於交換兩個 node,再將當前指標移到下一個 node,重複此操作直到迴圈結束即完成 q_swap。
以 list_mov
將 Node1 移到 Node2 後。
移動指標 c 至下個節點,重複一樣的操作直到迴圈結束。
逐一走訪每個節點,並依序搬移到 head 即可。
每 k 個節點做一次 list_cut_position
切出一個欲進行 reverse 操作的 list,用先前實作好的 q_reverse 反轉再接回原來的串列。
先將最後節點的 next 設為 NULL 斷開和 head 間的連結 ,使用 mergesort 函式用快慢指標找出中間節點,分出左右兩段 list,一樣將左段最後節點的 next 設為 NULL 切斷鏈結以利後續 merge_two_list 的迴圈結束條件判斷(右段不用,因為最後一定是接到 NULL),遞迴處理直到佇列中剩下一個節點,接著使用 merge_two_list 開始比較大小並合併兩個 list,最後回傳合併完成的佇列。
回到 q_sort 後會將原先 head 和合併完成的佇列連接起來,完成排序。
寫法上應該可以更有品味,且尚未完整研讀 list_sort.c,之後改進並嘗試引入 list_sort.c。
反向走訪佇列,若下個節點的 value 小於當前節點的 value,刪除下個節點。
先前有先玩過 qtest,功能可以建立多個不同的佇列,沒有仔細去看實作內容,到要實作 q_merge 才覺得傳進來的參數 head 跟之前其他函式的 head 好像不同,原來 queue 之間也是有用另外一個 linked list 串起來的,所以拿到的參數是 queue 之間串列的 head,以此來走訪每個 queue。
這裡就感受到 container_of
的強大,可以利用已知成員的記憶體位置去得到結構體的記憶體位置以存取成員,之後使用 list_splice_init
將每個佇列合併。
參考 komark06 的作法,將每個佇列都合併為一個佇列再利用實作的好的 q_sort 進行排序,確認是否只有一個節點可以改用 list_is_singular
。
目前分數 95 / 100
時間複雜度有問題,看了課程討論區留言應該要改良 dudect。
testcommand.sh
用以開啟 simulation 模式
視覺化的結果圖
給額外參數 max-snapshot 為 1000,可以看到更詳細的 heap memory 變化
第一行就看不懂,查了才發現這是一種函式屬性 (function attribute) 的用法,用來指定函式2、3、4的參數位置不可為NULL,注意是用於指標參數,避免空指標錯誤。
此為合併兩個 list 的函式,這裡的關鍵是指標的指標變數 tail,存的是指標變數的記憶體位置,指標變數存的又是 list_head 這個結構體的記憶體位置,每一次迭代都會將 tail 指向 next 變數的記憶體位置,故使用取值運算子 *
可以更改此指標變數 next 存的 list_head 記憶體位置,以此更改下個節點為比較值小的節點,最後回傳 head。
先來看註解部分
一般合併的方法會將同一層相同大小的串列合併之後才合併更大的串列,此為 level order merge,在每一層都會讀取所有子串列。
但當欲排序的串列超過 L1 cache 的大小,在上層合併好的串列會從 cache 內搬出讓出空間給下個需要排序的序列,而到下一層,上層剛合併好的串列又要搬進 cahce,造成資料不斷重複進出 cache,多次發生 cache miss ,引發 thrashing,此時 CPU 每次都要去 memory 存取資料,速度變慢,cache 的存在就形同虛設。
因此此演算法的想法是以 depth-first order 去完成合併,這樣會有好的 cache locality,但 depth-first order 的方式可能會有不平衡的合併情況發生。
一般的 bottom-up mergesort 會在出現兩個大小為 的 list 時就進行比較合併,所以想法是不馬上進行合併,而是等有第三個大小為 的 list 出現才會進行比較合併,讓最差的合併情況會是以 2:1 的比例進行,只要這三個 list 可以被放進 cache,可以降低比較次數並且有效利用 cache locality,而這個比例會透過 count 變數來實作。
list_sort 的實作方式是使用一個 count 變數來記錄當前處理的節點數量,用二進位來看這個 count 變數,在 時不用進行合併,以表格說明。
參考 DokiDokiPB 的表格
Decimal of count | Binary of count | Merge | Range | Size |
---|---|---|---|---|
0 | 00000 | X | X | X |
1 | 00001 | X | X | X |
2 | 00010 | O | [0,1] | 2 |
3 | 00011 | X | X | X |
4 | 00100 | O | [2,3] | 2 |
5 | 00101 | O | [0,3] | 4 |
6 | 00110 | O | [4,5] | 2 |
7 | 00111 | X | X | X |
8 | 01000 | O | [6,7] | 2 |
9 | 01001 | O | [4,7] | 4 |
10 | 01010 | O | [8,9] | 2 |
11 | 01011 | O | [0,7] | 8 |
12 | 01100 | O | [10,11] | 2 |
13 | 01101 | O | [8,11] | 4 |
14 | 01110 | O | [12,13] | 2 |
15 | 01111 | X | X | X |
16 | 10000 | O | [14,15] | 2 |
接著來看 list_sort 的實作細節。
一樣是 function attribute 的用法,限制第二、三參數不能為NULL。
一開始會先將最後節點跟 head 之間的鏈結切斷,發現我 qsort 實作方式和它有相同的地方。
一開始有個疑問是,在函式開始後會先把 pending 指向 NULL,而這邊在找從右邊數起第一個出現的0 時,應該會存取到 NULL,發生 Segmetation fault,但後來發現 count 一開始是 0,跟 1 做完 AND 不會進入迴圈執行。
tail 這個指標在每次 do-while 敘述都會指向現在 pending 的記憶體位置。
第 6 行的 for 迴圈負責找出從右邊數起第一個出現的 bit 0,並且調整 tail 往前找出要合併的 sorted list,這裡的原理是利用 prev 成員連接每個不同的 sorted list,在這邊找到要合併的 list 位置後,就可以利用下個 if 敘述去做合併。
接著在第 9 行發現一個從來沒看過的東西–-likely,參考 Linux Kernel慢慢學 likely and unlikely macro 才發現是一種編譯器最佳化的方法,把分支的預測資訊告訴編譯器,以便對程式碼改變分支順序進行優化,之前念計組好像有類似的觀念叫做 Delay slot,也是預測分支常不常發生來進行組語程式碼的搬移。
這邊的 if 是用來判斷是否要進行 list 的合併,可以發現只有當 count 為 時不會進入判斷式中進行合併,舉例來說像是 為 0…0111,做完 for 迴圈後 bits 為 0,就不會進入 if 敘述中進行合併。
最後 19 行會將 list 還有 pending 的指標往後推移,也就是把下一個元素放入 pending。
把 list_sort.c
的函式放到 queue.c,之後把一些不會使用到的參數 priv 以及 cmp 拿掉,在函式內的 cmp 只要用 strcmp
取代即可。
定義 likely(x) 以及 unlikely(x)
接著在 qtest.c
當中新增指令
實作 do_lsort 函式,大部份內容和 do_sort 一樣,只是差在會去呼叫定義在 queue.c 的 list_sort
TODO: 效能評測比較還在想如何做
新增 shuffle 命令到 qtest.c
藉由 Fisher–Yates shuffle 演算法實作 shuffle 功能,使用 mod 可以隨機找到要往後找的步數,故要和當前節點交換的節點(步數會落於範圍 ,故節點會落於範圍 ,為當前節點,為最後節點)。
因為是 linked list,不能隨機存取,只能逐一尋訪每個節點找到此節點,時間複雜度是 ,演算法中的 swap 部份其實可以用 list_swap
去取代那些指標操作,但老師給的 list.h
裡面似乎把這個功能給拔了,應該是要我們用基本指標操作去實現 swap。