contributed by < allenliao666 >
node_t
為佇列中的節點結構,由 node_t
指標 *left 、 *right 和 *next 還有 long
value 所組成。
其中 *next 用於連接下一個 node_t
, value 為該節點的值。
以此串列為例:
在測驗一的快速排序非遞迴實作中,首先 pivot 指向串列第一個節點,並且把該節點的 value 設定為比較對象。並把 L 和 R 指標分別指向待排序串列兩側的節點。
接著依序和串列中的其他節點比較大小,將 value 小於 piovt 的節點加入 left 指向的串列,反之加入 right 指向的串列。最後使用 begin[] 和 end[] 兩個指標陣列紀錄 left 和 right 指向的兩個串列的開頭和尾端節點,其中 begin[i] 指向 left 的串列的開頭節點,end[i] 指向 left 的串列的尾端節點,begin[i + 2] 指向 right 的串列的開頭節點,end[i + 2] 指向 right 的串列的尾端節點。
接著會針對 right 串列中重複執行上述的步驟,持續分割排序串列,並把分割排序後的串列的頭尾紀錄在對應的 begin[] 和 end[] 中,直到待排序的串列只有一個節點後開始合併。
Timsort 結合合併排序及插入排序的優點。 Timsort 執行過程如下:
find_run()
尋找資料中已排序的子序列(以下稱為 run ),以避免浪費時間排序資料中已排序的部分。在尋找 run 的過程中,若遇到反向排序( value 由大到小)的部分時會將其反向排序成為 run 。pair
結構紀錄,其中 head
指向 run 的第一個節點, next
指向剩餘串列的第一個節點。tp
ˋ指標指向最新的 run ,並用 result.head
的 prev 連接上一個加入堆疊的 run 。merge_collapse
確保堆疊頂端的3個 run 符合長度規則,若不符合則合併相鄰的2個 run ,藉此維持堆疊中 run 長度的平衡。題意:給定二元樹的前序及中序表示法,藉此重建二元樹。
題意:尋找記憶體位置中的第 n 個設定位元。
因為對 bitwise 操作一竅不通,故依序理解巨集。
GENMASK(h, l)
其中((~0UL) - (1UL << (l)) + 1)
即把右邊 l - 1
個位元設為0,(~0UL >> (BITS_PER_LONG - 1 - (h)))
把左邊 h + 1
個位元設為0。其手法類似 linux 中 bitops.h 的程式碼。
其目的皆為設定 l
到 h
位元為1,其餘皆為0。
BIT_WORD(nr)
換算 nr 個位元的長度為多少個 word。
#define BITS_TO_LONGS(nr)
使用 DIV_ROUND_UP(n, d)
和 BITS_PER_TYPE(long)
兩個巨集, DIV_ROUND_UP
的目的為將 n / d 的結果向上取至整數,例如42/5=8.4 代入 DIV_ROUND_UP
就會得到9。BITS_PER_TYPE(long)
則是計算 long 的位元數。故BITS_TO_LONGS(nr)
表示至多需要多少個 long 儲存 nr 。
__const_hweight8(w)
計算8個位元中共有多少個位元被設定(即為1)。
BITMAP_LAST_WORD_MASK(nbits)
這個巨集會用在當 nbit 不整除於 BITS_PER_LONG 時(即 nbit 非64的倍數),必須把多餘的部份湊成64位元,所以使用遮罩保護右邊 nbit % BITS_PER_LONG 的值。
FIND_NTH_BIT(FETCH, size, num)
這個巨集較複雜,故先從參數開始介紹:
該巨集在 size 範圍內從 FETCH 開始尋找第 num 個設定的位元。 idx 為 word 的索引。
分為以下幾種狀況: