contributed by < hankTaro
>
延伸問題:
treesort.c
程式碼的缺失並改進treesort.c
實作手法,指出後者的改進空間並予以實作此紅黑樹節點架構將顏色與親代節點的資料存在同個空間,藉由透過 __attribute__((aligned(sizeof(long))))
對齊到 sizeof(long)
,這樣指標最低 3 個位元是沒有使用到的,便可將此位置用於儲存顏色(但是儲存顏色只需要用到 1 bit)
long 所需的位元數為 4,所以對齊後最小的三位元會固定不動
e.g.00001000
->00010000
->00011000
->00100000
->00101000
你所不知道的 C 語言:記憶體管理、對齊及硬體特性
這裡對將變數名取為 color
頗為不滿,若將其命名為 parent_color
會更容易閱讀理解,並避免混淆
並且定義巨集以便取出親代節點的位置與節點顏色
int res = obj->comparator(&node->value, &cur->value);
中的 res ,是 obj->comparator
(一個比較函數,由 cmap_new
, assign 進去的),當 &node->value
大於 &cur->value
時回傳 1,反之回傳 -1 ,相等回傳 0 ,隨後便利用 res 辨別相對大小,將此 node 放在 NIL 的位置(leaf),
cmap_new 的必要性,因為只有在 tree_sort 中呼叫過一次,內容也只是將固定傳入數值 assign 進結構中
將 struct __node
中的 struct __node *next;
用 struct list_head list;
替換
將 main
中的 list_make_node
改為使用 list_add
使用 list_for_each_entry
與 list_move_tail
省去使用 list = &(*list)->next;
,並且更改 cmap_next
與 cmap_first
資料回傳型態
IIII = node->parent_balance & ~7
JJJJ = node->parent_balance & 3
KKKK = node->parent_balance & 3
LLLL = node->parent_balance & ~7
MMMM = avl_rotate_right
NNNN = avl_rotate_leftright
AVL tree 這裡也利用 AVL_NODE_ALIGNED
做 data alignment ,將 balance 值存於 adress 的末兩位中,剛好 balance 只有三種可能,平衡、左傾或右傾,故可以使用 2 bits 空間進行保存
要注意的是,這裡左傾與右傾是指,兩邊最大高度差為 1,因為當兩邊高度差為 2 時,就會進行平衡,並且求出新的 balance ,所以這邊 Balance Factor 只會有 -1, 0, 1 的狀況
呼叫 avl_insert
的情況下,是已經找到此 node 在樹中的位置,並且 parent 已將此節點設為他的 child,故呼叫 avl_link_node
建立出一個 left
right
都是 NULL 的新節點,並且是平衡的,再將 parent 的位置存入
當 node 插入後,便開始沿著 parent 的路徑依序平衡,可以將情況分為一下幾種:
在 case 1 中只需要將 parent 設為平衡
在 case 2 中只需要依據 node 是插入在左側還是右側,將 parent 設為右傾或左傾
case 3 需要進行旋轉以平衡兩側高度,並且要同時對 node 與 parent 做判斷,可以分為 4 種類型
要注意插入新節點還沒平衡前,新節點的 parent 的 balance 尚未更新,並且新節點必定平衡,所以第一次平衡不可能會進行旋轉
新節點的 parent 只受新節點在其左還右,以改變其平衡狀態
node 為平衡或左傾時,都算做 L
LL 型:
LR 型:
RR 型:
RL 型:
而進入旋轉後,需要根據親代節點的平衡狀況去設置調整後的平衡狀況
依序分別為:
此方法對應的是 LL 型,由於此情況 node 不可能右傾,因為右傾則會成為 LR 型, 故只需要考慮 node 為平衡以及左旋的狀況,當 node 為平衡時,代表其左右側都不為 NIL(因為第一次平衡不可能會進行旋轉,故發生選轉的節點必定有子節點),所以其右側節點會成為其親節點的左側節點
node 為紅色節點
故 node 在旋轉後會右傾,而 parent 會左傾,故更新平衡狀態,隨後進行節點的移動與連結
而 RL/LR 型則是先對 node 做相對應的旋轉,使其變為 RR 或 LL 型,再用同樣的方式對 parent 旋轉,並更新平衡狀態,概念相同這裡就不多做贅述
目前Linux 核心中的 AVL tree ,逐漸被紅黑樹替代,AVL tree 相較於 RBT 的劣勢在於,當節點數量較大時,可能需要一直旋轉直到 root ,在大多數情況下,RBT 的效率會比 AVL tree 好
在考慮是否要用 RBT 取代 AVL tree 以前,必須先行了解 linux 核心的同步機制之一 RCU,以及 linux 的鎖定機制 seqlock(short for sequence lock),因為要將 AVL tree 用 RBT 取待,需要確保 RBT 支援 RCU ,否則在多執行上效率不彰
在使用 RCU 的狀況下,RBT 可使用較少的函式達成,同時使用較少的變數
延伸問題:
見 commit b145425
rbtree.h
,探究是否可用後者替換,從而爭取到貢獻程式碼到 Linux 核心的機會用 __builtin_clzl
求出左側0數量就可以求出小於 x 的
最大位元 - 左側0數量 - 1 = 右側到最大 1 之間的 0 數量 = n
延伸問題:
git log
和 grep
找出 LFSR 的應用案例lab0-c
提供類似的實作 log2_lshift16.h,解釋其原理並嘗試改進其效能此程式欲求出 並向上取整
取 的改念就是看最高有效位元的位置,因為在二進位中,位元的位置為冪運算的上標,所以只要知道 x 最左側的 1 後有幾個位元,就可以求出
在第 5 行中,將 x--
是為了將 型態的數值最大值降低一位元,確保無條件進位時的答案正確
6~15 行都是在求最高有效位的位置,最後在 return (r | shift | x >> 1) + 1;
無條件向上取整
由於 需要求出最高有效位元右側有幾個位元,便可使用 __builtin_clz
函式,求出最高有效位元左側有幾個 0
,在用最大位元數減去,便可得到其值共佔多少位元,由於要向上取整,故在運算前 x - 1
,這樣 型態算出的值會剛好是其減 1 前右側位元數,而不是 型態算出的值會是無條件進位後的位元數
另外輸入有機會為 0,故使用 assert
檢查,並達成 branchless
TODO: