# linux2023:tintinjian12999 contributed by < [tintinjian12999](https://github.com/tintinjian12999) > ## 測驗 𝛼 - 1 ### 結構體 #### st_node ``` c struct st_node { short hint; struct st_node *parent; struct st_node *left, *right; }; ``` parent 為指向親代節點的指標，left, right 分別為指向左子樹與右子樹的指標，hint 為用來決定是否需要平衡的參數。 ![](https://hackmd.io/_uploads/BJ_ITQ-hh.png) #### st_root ```c struct st_root { struct st_node *root; }; ``` root 為指向整棵樹的根節點的指標。 ![](https://hackmd.io/_uploads/Byr9AmWh3.png) ### 型別 ```c enum st_dir { LEFT, RIGHT }; ``` 用來讓程式變得更有可讀性，而非用布林或數字決定是左或右。 ### 巨集 ```c #define st_root(r) (r->root) #define st_left(n) (n->left) #define st_right(n) (n->right) #define st_rparent(n) (st_right(n)->parent) #define st_lparent(n) (st_left(n)->parent) #define st_parent(n) (n->parent) ``` st_root : 取出根節點的指標 st_left : 取出左子節點的指標 st_right : 取出右子節點的指標 st_rparent : 取出右子節點之親代節點的指標 st_lparent : 取出左子節點之親代節點的指標 st_parent : 取出當前節點之親代節點的指標 ### 函式 #### st_first ```c struct st_node *st_first(struct st_node *n) { if (!st_left(n)) return n; return st_first(st_left(n)); } ``` 找出整棵樹的最小節點 ![](https://hackmd.io/_uploads/BJKSBBb22.png) #### st_last ```c struct st_node *st_last(struct st_node *n) { if (!st_right(n)) return n; return st_last(st_right(n)); } ``` 找出整棵樹最大的節點 (這裡節點 14 的右子樹為 NULL) ![](https://hackmd.io/_uploads/SkdV6D7n3.png) #### st_rotate_left ```c static inline void st_rotate_left(struct st_node *n) { struct st_node *l = st_left(n), *p = st_parent(n); st_parent(l) = st_parent(n); st_left(n) = st_right(l); st_parent(n) = l; st_right(l) = n; if (p && st_left(p) == n) st_left(p) = l; else if (p) st_right(p) = l; if (st_left(n)) st_lparent(n) = n; } ``` 對當前節點作左旋 #### st_rotate_right ```c static inline void st_rotate_right(struct st_node *n) { struct st_node *r = st_right(n), *p = st_parent(n); st_parent(r) = st_parent(n); st_right(n) = st_left(r); st_parent(n) = r; st_left(r) = n; if (p && st_left(p) == n) st_left(p) = r; else if (p) st_right(p) = r; if (st_right(n)) st_rparent(n) = n; } ``` 對當前節點做右旋 #### st_balance ```c static inline int st_balance(struct st_node *n) { int l = 0, r = 0; if (st_left(n)) l = st_left(n)->hint + 1; if (st_right(n)) r = st_right(n)->hint + 1; return l - r; } ``` 計算當前節點的 balance factor #### st_max_hint ```c static inline int st_max_hint(struct st_node *n) { int l = 0, r = 0; if (st_left(n)) l = st_left(n)->hint + 1; if (st_right(n)) r = st_right(n)->hint + 1; return l > r ? l : r; } ``` 回傳左節點與右節點中 hint 較高的一方(相當於 AVL tree 中的樹高) ### st_update ```c static inline void st_update(struct st_node **root, struct st_node *n) { if (!n) return; int b = st_balance(n); int prev_hint = n->hint; struct st_node *p = st_parent(n); if (b < -1) { /* leaning to the right */ if (n == *root) *root = st_right(n); st_rotate_right(n); } else if (b > 1) { /* leaning to the left */ if (n == *root) *root = st_left(n); st_rotate_left(n); } n->hint = st_max_hint(n); if (n->hint == 0 || n->hint != prev_hint) st_update(root, p); } ``` 對當前節點做 balancing #### st_insert ```c void st_insert(struct st_node **root, struct st_node *p, struct st_node *n, enum st_dir d) { if (d == LEFT) st_left(p) = n; else st_right(p) = n; st_parent(n) = p; st_update(root, n); } ``` 根據 st_dir 的值將新的節點插入當前節點的左節點或右節點並做 balancing #### st_replace_right #### st_replace_left #### st_remove ```c void st_remove(struct st_node **root, struct st_node *del) { if (st_right(del)) { struct st_node *least = st_first(st_right(del)); if (del == *root) *root = least; st_replace_right(del, least); //AAAA st_update(root, st_right(least)); //BBBB return; } if (st_left(del)) { struct st_node *most = st_last(st_left(del)); if (del == *root) *root = most; st_replace_left(del, most); //CCCC st_update(root, st_left(most)); //DDDD return; } if (del == *root) { *root = 0; return; } /* empty node */ struct st_node *parent = st_parent(del); if (st_left(parent) == del) st_left(parent) = 0; else st_right(parent) = 0; st_update(root, parent); //EEEE } ``` 當要移除的節點有右子樹時，要將該節點替換為右子樹的最小節點 (為確保替換後該節點右子樹裡的值都比該節點大)，且因為已經更動過右子樹內的節點，因此需要對其作 update ，如果沒有右子樹的話則替換為左子樹裡的最大節點，並對左子樹做 update ，如果要被移除的節點沒有任何的子節點的話， 則可以將其直接移除並對該節點的親代節點做 update。 #### __treeint_dump ```c /* ascending order */ static void __treeint_dump(struct st_node *n, int depth) { if (!n) return; __treeint_dump(st_left(n), depth + 1); //FFFF struct treeint *v = treeint_entry(n); printf("%d\n", v->value); __treeint_dump(st_right(n), depth + 1); //GGGG } ``` 走訪並印出左子樹與右子樹的值 ## 測驗 𝛽 - 1 考慮給定的範例 ``` align_up(120, 4) = 120 align_up(121, 4) = 124 align_up(122, 4) = 124 align_up(123, 4) = 124 ``` 從以上不難觀察到其實 align_up 所做的是將 sz 除以 alignment 的商取上高斯並再乘以 alignment，也就是 $$ \lceil\frac{sz}{alignment}\rceil * alignment $$ 上高斯的部分可以透過 $$ceilVal = (a + b - 1) / b$$獲得，因此整個式子可以寫成 $$ (\frac{sz + (alignment - 1)}{alignment}) * alignment$$ 因為這裡的 alignment 為 2 的冪且 mask = alignment - 1，我們可以進一步改寫為 $$(sz + mask) >> \log2(alignment)) << \log2(alignment)$$ 透過觀察$$>> \log2(alignment)) << \log2(alignment)$$ 的操作 (以 123, alignment = 4 為例) $$ (123 + 3) = 1111110_2 \\ 1111110 >> 2 = 11111\\ 11111 << 2 = 1111100 $$ 可以看到作用為消除最後的 ```log2(alignment)``` 個 bit ，而此操作可以改寫為 ```(sz + mask) & alignment -> (sz + mask) & ~mask``` ```c #include <stdint.h> static inline uintptr_t align_up(uintptr_t sz, size_t alignment) { uintptr_t mask = alignment - 1; if ((alignment & mask) == 0) { /* power of two? */ return (sz + mask) & ~mask; //MMMM } return (((sz + mask) / alignment) * alignment); //如果 alignment 不是 2 的冪則不能化簡 } ``` ## 測驗 𝛾 - 1 參考 [並行程式設計: POSIX Thread](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fposix-threads) 裡有關 condition variables 的用法，此處的 HHHH 應為 ```c pthread_cond_wait(&qs->cond_st) ``` JJJJ 為 ```c pthread_cond_signal(&qs->cond_st, &qs->mtx_st) ``` :::warning 為何？ :notes: jserv :::