2023q1 Homework3 (quiz3)

tags: linux2023

contributed by <Paintako>

測驗 1

考慮以下結構體, "利用 ABI 特性來「標示不用的節點」手段"

typedef struct __node {
    uintptr_t color;
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t __attribute__((aligned(sizeof(long))));

首先看到 __attribute__((aligned(sizeof(long)))), 透過 __attribute__((aligned(sizeof(long)))) 讓編譯器知道 struct rb_node 會對齊 sizeof(long)
指的是, struct __node 的起始位址會是 8 Byte 倍數的位置
反過來說, 如果某個位址對齊了 8 byte (1000), 會有3個 bit 是永遠用不到的.

以下實驗證明了使用 __attribute__((aligned(sizeof(long)))) 的結構體的地址永遠對齊 8 Bytes:

#include <stdio.h>

typedef struct __node1{
    int value;
    char c;
} node1_t __attribute__((aligned(sizeof(long))));

int main() {

    node1_t *ptr = malloc(sizeof(node1_t));
    printf("%p\n",ptr);

    node1_t *ptr1 = malloc(sizeof(node1_t));
    printf("%p\n",ptr1);

    node1_t *ptr2 = malloc(sizeof(node1_t));
    printf("%p\n",ptr2);

 
    return 0;
}

Node1 address: 0x7ffcbb1b7040
Node2 address: 0x7ffcbb1b7018
Node3 address: 0x7ffcbb1b7020

那 uintptr_t color 這段 color 到底代表的是？
只知道是一個指標，具體這個指標指的東西是指？

看到後續程式碼：

#define rb_parent(r) ((node_t *) (AAAA))
#define rb_color(r) ((color_t) (r)->color & 1)

可得知, 父點和顏色都存儲在 node_t 中，猜測父點和顏色都存在　color中

結合前面已知條件, node_t的記憶體位址皆對齊於8, 所以不論 color 指向的記憶體位址為何, 把後 3 bit 給清除掉, 那此地址就符合 node_t 的規範.

再結合記憶體對齊的規範, 如果此記憶體對齊 8 Byte, 那後 3 bit 皆不用不到, 那此 3 bit 可以用來表示此點是黑還是紅

結合以上兩者操作, 基本可以判定 color 指的就是：

  1. 父點指標
  2. 自己的顏色

故程式碼如下：

#define rb_parent(r) ((node_t *) (r)->color & ~7) // AAAA
#define rb_color(r) ((color_t) (r)->color & 1)

要設定一個 node_t 的顏色為黑色的話, 根據 typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t; 得知, 黑色＝1, 紅色=0

#define rb_set_red(r) 
    do {             
        r->color &= 0; // BBBB
    } while (0)
#define rb_set_black(r) 
    do {               
        r->color ｜= 1; // CCCC
    } while (0)

ABI:

  • 二進制介面（Application Binary Interface），也就是程序二進制接口或應用程式介面。ABI 定義了在這個架構下不同程式和函數之間的二進制接口規範，例如函數的呼叫約定、參數傳遞方式、資料對齊方式等等。

while(0):

  • while (0) 是一個空循環，其主要作用是在 Marco 定義中使用，以便在調用 Marco 時可以避免出現語法錯誤。

Ref: ChatGpt

關於插入紅黑樹, 非常直覺的, 比現在這個節點的值小就往左子樹找, 反之往右子樹找
如果往下走的過程中當前節點是 NULL, 等於找到要插入的位置

所以以下程式碼：

if (res < 0) {
    if (!cur->left) {
        cur->left = node;
        rb_set_parent(node, cur);
        cmap_fix_colors(obj, node);
        break;
    }
    cur = curr->left; // DDDD
    } else {
        if (!cur->right) {
            cur->right = node;
            rb_set_parent(node, cur);
            cmap_fix_colors(obj, node);
            break;
        }
        cur = curr->right; // EEEE
    }

以下程式碼, 會把一個 list 的 node_t 給傳入, 然後建立一個新的 map 給這個 list, 一個個的插入 node_t
插入後相當於建好一棵紅黑樹, 再從這棵樹中依照 cmap_next 中取得下一個點, 放入 list 中, 這樣子把整個 cmap iterate 完後, 等同於排序好整個 list.

void tree_sort(node_t **list)
{
    node_t **record = list;
    cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
    while (*list) {
        cmap_insert(map, *list, NULL);
        list = &(*list)->next; // FFFF
    }
    node_t *node = cmap_first(map), *first = node;
    for (; node; node = cmap_next(node)) {
        *list = node;
        list = &(*list)->next // GGGG
    }
    *list = NULL; // HHHH
    *record = first;
    free(map);
}

測驗 2

考慮以下程式碼：

#define AVL_NODE_ALIGNED __attribute__((aligned(sizeof(unsigned long))))
    
struct avl_node {
    unsigned long parent_balance;
    struct avl_node *left, *right;
} AVL_NODE_ALIGNED;

可得知, 這裡的對齊手法跟紅黑樹的對齊手法一致, 讓地址皆對齊於 8 byte

static inline struct avl_node *avl_parent(struct avl_node *node)
{
    return (struct avl_node *) ((node->parent_balance)& ~7); // IIII
}

AVL tree 對於樹高有嚴格要求, 這裡使用一個 enum 來紀錄左右子樹高度差
enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };

當：

  1. 左右子樹一樣高： node_balance = 0
  2. 左樹比又右樹高： node_balance = 1
  3. 左樹比又右樹高： node_balance = 2
    可用 2 個 bit 表示這棵樹的平衡狀態

故當要讀取此樹的高度差時, 只需要讀取最後兩個 bit 就可以了

static inline enum avl_node_balance avl_balance(const struct avl_node *node)
{
    return (enum avl_node_balance)((node->parent_balance) & 3); // JJJJ
}

static void avl_set_parent:
此函式的用意在於給定父點的指標, 並且設定 current node 的 parent_balance, 已知 parent_balance 含：

  1. 父點指標
  2. 自身平衡狀態 （0,1,2)

參考以下兩位同學的作法

  • avl_balance(node) Ref
  • node->parent_balance & 3 Ref

看到原本程式碼中的註解：

 * struct avl_node - node of an avl tree
 * @parent: pointer to the parent node in the tree
 * @balance: balance of the node
 * @parent_balance: combination of @parent and @balance (lowest two bits)
 * @left: pointer to the left child in the tree
 * @right: pointer to the right child in the tree

一開始有點疑惑, 但後來才想到這個函式的用意是設定新的父點, 那原本 node 內的後 3 bit 代表的是原本的平衡狀態, 故結合新的 parent pointer 以及原本的平衡狀態就可以更新 parent_balance 了

前面的問題釐清後, 要解答 static void avl_set_balance 就簡單很多, 只要把 parent_balance 後 3 bit 設定成0 剩餘的就是地址了, 再結合 balance 就可以把 parent_balance 給設定好.

static void avl_set_balance(struct avl_node *node,
                            enum avl_node_balance balance)
{
    node->parent_balance = (node->parent_balance) & ~7 | balance;
}

接著, 看到 void avl_insert_balance(struct avl_node *node, struct avl_root *root)

他的描述是： 沿著樹往"上"走, 然後沿路 rebalance, 如果路上會遇到：
RL/RR/LR/LL 這四種情況就會進行調整.

在 static inline void avl_insert 中會呼叫到此函式
插入前, 先呼叫 avl_link_node 函式, 作用是將給定的 parent 連結到此點上面, 連結後相當於這棵樹多了一個 leaf, 再從這個葉子往上走到 root為止, 期間如果有遇到不平衡狀態就調整.

當插入後, 先判斷插入的點是左是右（因為要區分父點平衡狀態）, 然後檢查父點的平衡狀態

  • 當前節點是右邊的話, 則父點有三種情況
    • 平衡
      • 這樣就無須調整, 只須把父點的平衡設成右子樹比較高, 繼續往上檢查
    • 左子樹比右子樹還高
      • 原本父點是左子樹比較高, 但是右邊插入一個點後, 父點變平衡
    • 右子樹比左子樹還高
      • 這種情況下, 是不可能發生在 leaf 的, 考慮已經往上爬了一點距離的情況
      • 如果 node 平衡狀況是：
        • 平衡
        • 右子樹比較高
          • 程式碼中並未定義這種情形, 原因是因為上面平衡的情況下就會先進行旋轉, 來避免LL/RR 的情況
        • 左子樹比較高
          • 進行 RL 調整 avl_rotate_rightleft(node, parent, root)

釐清了以上觀念, 考慮插入節點是左子的情況：

  • 當前節點是左邊的話, 則父點有三種情況

    • 平衡

      • 原本父點平衡, 插入左子後, 父點平衡變左子比右子高

    • 左子樹比右子樹還高

      • 同上面的結論, 這種情況不可能發生在 leaf 的, 考慮已經往上爬了一點距離的情況
      • 如果 node 平衡狀況是：
        • 平衡
          • 為了避免出現 RR 的情況, 會提前進行旋轉
        • 左子樹比較高
          • 程式碼中並未定義這種情形, 原因是因為上面平衡的情況下就會先進行旋轉, 來避免LL/RR 的情況
        • 右子樹比較高
          • LR 調整

    • 右子樹比左子樹還高

      • 這種情況下, 因為原本右子比左子還高, 插入左子後, 讓父點剛好變平衡

程式碼：

void avl_insert_balance(struct avl_node *node, struct avl_root *root)
{
    struct avl_node *parent;

    /* go tree upwards and fix the nodes on the way */
    while ((parent = avl_parent(node))) {
        if (avl_is_right_child(node)) {
            switch (avl_balance(parent)) {
            default:
            case AVL_RIGHT:
                /* compensate double right balance by rotation
                 * and stop afterwards
                 */
                switch (avl_balance(node)) {
                default:
                case AVL_RIGHT:
                case AVL_NEUTRAL:
                    avl_rotate_left(node, parent, root);
                    break;
                case AVL_LEFT:
                    avl_rotate_rightleft(node, parent, root);
                    break;
                }

                parent = NULL;
                break;
            case AVL_NEUTRAL:
                /* mark balance as right and continue upwards */
                avl_set_balance(parent, AVL_RIGHT);
                break;
            case AVL_LEFT:
                /* new right child + left leaning == balanced
                 * nothing to propagate upwards after that
                 */
                avl_set_balance(parent, AVL_NEUTRAL);
                parent = NULL;
                break;
            }
        } else {
            switch (avl_balance(parent)) {
            default:
            case AVL_RIGHT:
                /* new left child + right leaning == balanced
                 * nothing to propagate upwards after that
                 */
                avl_set_balance(parent, AVL_NEUTRAL);
                parent = NULL;
                break;
            case AVL_NEUTRAL:
                /* mark balance as left and continue upwards */
                avl_set_balance(parent, AVL_LEFT);
                break;
            case AVL_LEFT:
                /* compensate double left balance by rotation
                 * and stop afterwards
                 */
                switch (avl_balance(node)) {
                default:
                case AVL_LEFT:
                case AVL_NEUTRAL:
                    avl_rotate_right(node, parent, root); // MMMM
                    break;
                case AVL_RIGHT:
                    avl_rotate_leftright(node, parent, root); // NNNN
                    break;
                }

                parent = NULL;
                break;
            }
        }

        if (!parent)
            break;

        node = parent;
    }
}
Select a repo