2024q1 Homework2 (quiz1+2)

contributed by <Shiang1212>

第一週測驗題

測驗 `1`

先輩知識

結構體與函式介紹：

typedef struct __node {
    struct __node *left, *right; // Doubly linked list
    struct __node *next;
    long value;
} node_t;

void list_add(node_t **list, node_t *node_t)
將 node_t 加入至 list 的前端。
node_t *list_tail(node_t \*\*left)
回傳一個指向 left 最末節點的指標。
int list_length(node_t \*\*left)
回傳輸入串列的長度。
node_t *list_construct(node_t *list, int n)
建立一個 value 為 n 的節點，並將其 next 指向 list。
void list_free(node_t \*\*list)
走訪每個節點，並將釋放其記憶體，直到 list 內沒有結點。
void shuffle(int *array, size_t n)
隨機交換 array 裡的值，完成亂序。

其中，shuffle 的程式碼如下：












void shuffle(int *array, size_t n)
{
    if (n <= 0)
        return;

    for (size_t i = 0; i < n - 1; i++) {
        size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
        int t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

第 6、7 行可見，宣告一個 size_t i 走訪每個元素，並用第 i 個元素跟第 i ~ n 個元素交換，完成亂序操作。

介紹完基本操作，接下來介紹 main 函式在做什麼：

int main(int argc, char **argv)
{
    node_t *list = NULL;

    size_t count = 100000;

    int *test_arr = malloc(sizeof(int) * count);

    for (int i = 0; i < count; ++i)
        test_arr[i] = i;
    shuffle(test_arr, count);

    while (count--)
        list = list_construct(list, test_arr[count]);

    quick_sort(&list);
    assert(list_is_ordered(list));

    list_free(&list);

    free(test_arr);

    return;
}

建立一個陣列 test_arr，大小為 100000，內容為 0, 1, 2, …, 100000， shuffle 對其進行亂序操作後，用 list_construct 建立一個亂序內容的鏈結串列，最後使用 quick_sort，對該鏈結串列進行排序。

如何實作 quick_sort

此處為用於排序鏈結串列的非遞迴 (non-recursive; iterative) 快速排序法 (QuickSort)，以下為程式碼：

void quick_sort(node_t **list) 
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
    
            while (p) {
                node_t *n = p;
                p = p->next;
                list_add(n->value > value ? &right : &left, n);
            }

            begin[i] = left;
            end[i] = &list_tail(left);
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = &list_tail(right);

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

挑選第一個節點作為 pivot，並將 list 的首尾節點分別指派給 begin[0] 和 end[0]。

(此圖修改自 vestata)

(此圖修改於 YangYeh-PD)

走訪每個節點，將小於 pivot 的節點存進 left，大於 pivot 的節點存進 right。
begin[i] 存放 left，begin[i + 1] 存放 pivot，begin[i + 2] 存放 right。end[i] ~ end[i + 2] 存放 begin[i] ~ begin[i + 2] 的末端節點。

從 begin[i + 2] 開始，也就是 begin[] 最末端的串列，繼續找 pivot 切割成 left 和 right。

當 begin[i] == end[i] 時，代表串列已經無法再切割，就可以把該節點加入 result，當作排序完成的節點。

問題

why max_level = 2 * n

測驗 `2`

待完成

第二週測驗題

測驗 `1`

用 preoreder 和 inorder 的排序，要求回傳重建的二元樹。

Hash Table

使用雙向鏈結串列處理 Hash Table 發生碰撞 (collision) 的情況。

struct hlist_head {
    struct hlist_node *first;
}

struct hlist_node { 
    struct hlist_node *next, **pprev;
}

參考 Linux 核心的 hash table 實作

next 指向相鄰的節點本身，而 pprev 指向指著自身節點的指標。

hlist_add_head

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = h->first;
    n->pprev = &h->first;
    h->first = n;
}

這個函式執行 hash table 中，將 n 插入雙向鏈結串列。將 hlist_node n 插入於 hlist_head h 的前端。

TreeNode、order_node

struct TreeNode {
    int val;
    struct TreeNode *left, *right;
}

struct order_node {
    struct hlist_node node;
    int val;
    int idx;
}

建樹以及相關操作

find

static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, &heads[hash]) {
        struct order_node *on = list_entry(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

用傳入的 num 值尋找 hash table 中的位置索引。宣告 hash 得知該節點放於 hash table 中的哪個槽，用 hlist_for_each 走訪每個節點，尋找節點並回傳索引。

static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)
{
    if (in_low > in_high || pre_low > pre_high)
        return NULL;

    struct TreeNode *tn = malloc(sizeof(*tn));
    tn->val = preorder[pre_low];
    int idx = find(preorder[pre_low], size, in_heads);
    tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
    tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
    return tn;
}

待完成

node_add

static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, &head[hash]);
}

這裡執行的是建立一個 node 並將其存放至 hash table。建立一個新節點，宣告 hash 決定該節點要存放於 hash table 的哪個槽裡，最後使用 hlist_add_head 將該節點加入 hash table

測驗 `2`

待完成

測驗 `3`

實作 find_nth_bit 可在指定的記憶體空間找出第 N 個設定的位元。

__ffs

find first bit set in a word

static inline unsigned long __ffs(unsigned long word)
{
    int num = 0;
#if BITS_PER_LONG == 64
    if ((word & 0xffffffff) == 0) {
        num += 32;
        word >>= 32;
    }
#endif
    if ((word & 0xffff) == 0) {
        num += 16;
        word >>= 16;
    }
    if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }
    if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
    if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }
    if ((word & 0x1) == 0)
        num += 1;
    return num;
}

依循 binary search 的概念，用 mask 做 bit-wise and 找出首個 bit 為 1 的位置 (由右至左)，有了這個函式就可以往下繼續做 fns。

fns

find N'th bit set in a word

static inline unsigned long fns(unsigned long word, unsigned int n)
{
    while (word) {
        unsigned int bit = __ffs(word);
        if (n-- == 0)
            return bit;
        __clear_bit(bit, &word);
    }

    return BITS_PER_LONG;
}

使用 __fns 從 LSB 找出首個 bit 為 1 的位置，並判斷是否為該 word 中第 n 個 1 (由右至左)，若不是的話就把該 bit 清除掉，用 __fns繼續找下一個 bit 為 1 的位置。

__clear_bit

clear certain bit







static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
    unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);

    *p &= ~mask;
}

功能：將 addr 的第 nr 個 bit 改成 0。

清除第 4 個 bit

p         = 0111 1011
mask      = 0000 1000
~mask     = 1111 0111
p & ~mask = 0111 0011

其中的 BIT_MASK(nr) 和 BIT_WORD(nr) 巨集程式碼如下：

#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))

1UL 代表無號長整數 1，也就是

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001

1UL << ((nr) % BITS_PER_LONG) 將 1UL 向左位移 (nr) % BITS_PER_LONG 個 bit。

例如：BIT_MASK(5) 的結果

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010 0000

#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)

計算 word 的 offset。

不知道第 4 行為什麼要加 BIT_WORD(nr)，如果想要清除大於 64 的 bit，那不就代表要清除到該 word 以外的 bit 嗎？為什麼要允許這樣的行為？

small_const_nbits(size)

判定 size 是否為正常的常數且長度大於 0、小於 BIT_PER_LONG (64)。

#define small_const_nbits(nbits) \
    (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)

GENMASK(h, l)

產生一個第 l+1 到 h+1 個 bit 皆為 1，其餘為 0 的遮罩。

#define GENMASK(h, l) \
    (((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))

用一個例子快速了解 GENMASK 在幹嘛：

BIT_PER_LONG = 8

GENMASK(5, 2):

left  : 1111 1111 - (0000 0001 << 2) + 1
       =1111 1111 - 0000 0100 + 1
       =1111 1100
     
right : 1111 1111 >> (8 - 1 - 5)
       =0011 1111

left & right : 0011 1100

FIND_NTH_BIT(FETCH, size, num)

用來在指定的 bitmap 中，找尋第 n 個 set bit的 index。

#define FIND_NTH_BIT(FETCH, size, num)                     
    ({                                                          
        unsigned long sz = (size), nr = (num), idx, w, tmp;     
                                                                
        for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { 
            if (idx * BITS_PER_LONG + nr >= sz)
                goto out;

            tmp = (FETCH);
            w = hweight_long(tmp);
            if (w > nr)
                goto found;
                                                           
            nr -= w;                                       
        }                                                   
                                                           
        if (sz % BITS_PER_LONG)                         
            tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);     
    found:                                                 
        sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);   
    out:                                                   
        sz;                                                 
    })

`find_nth_bit`

find N'th set bit in a memory region















static inline unsigned long find_nth_bit(const unsigned long *addr,
                                           unsigned long size,
                                           unsigned long n)
{
    if (n >= size)
        return size;

    if (small_const_nbits(size)) {
        unsigned long val = *addr & GENMASK(size - 1, 0);

        return val ? fns(val, n) : size;
    }

    return FIND_NTH_BIT(addr[idx], size, n);
}

輸入參數：

addr：欲搜尋的起始記憶體位置
size：最大搜尋範圍 (bit)
n：欲查找的設定位元個數 (set bit)

接下來讓我們逐行檢視：

第 3~4 行：若欲查找的設定位元數超出最大搜尋範圍，則判定為尋找失敗，回傳 size。

第 8~15 行：透過 small_const_nbits(size) 檢查 size 是否為正常的常數且長度大於 0、小於 BIT_PER_LONG (64)。

若成立，代表要尋找的 index 就落在該字節內。
- 用 GENMASK() 設定一個遮罩，找出要處理的範圍。然後將遮罩後的值傳進 fns() 來找第 n 個被設置的位元的索引位置。
若不成立，則代表要尋找的 index 就不在該字節內。
- 呼叫 FIND_NTH_BIT()，來處理跨字節邊界的情況。

待完成

第一週測驗題

測驗 1

先輩知識

如何實作 quick_sort

測驗 2

第二週測驗題

測驗 1

Hash Table

TreeNode、order_node

建樹以及相關操作

測驗 2

測驗 3

find_nth_bit

Read more

資訊科技產業專案設計課程作業 4

Linux 期末專題

2024q1 Homework5 (assessment)

2024q1 Homework4 (quiz3+4)

測驗 `1`

測驗 `2`

測驗 `1`

測驗 `2`

測驗 `3`

`find_nth_bit`