2025q1 Homework2 (quiz1+2)

contributed by < Huadesuwa >

第 1 周測驗題

測驗 `1`

解釋上方程式碼運作原理

B1csI9bqJe
首先看到 struct list_item 為節點的結構，其中有一個整數型別 value 用於儲存資料，以及一個 a pointer named next to a strcut list_item ，因此可以得知這是一個單向的鏈結串列，而 head 則會指向整個鏈結串列

typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;
typedef struct {
    struct list_item *head;
} list_t;

static inline void list_insert_before(list_t *l,
                                      list_item_t *before,
                                      list_item_t *item);

其關鍵操作 list_insert_before 函式的語意如下：
函式會逐步走訪整個鏈結串列，定位到 before 之前指向的節點，並將 item 插入該位置

時間複雜度為 \(O(n)\) ，n 是指需要幾步才能找到要插入的位置
若 before 指向鏈結串列的頭，意謂著會插入在鏈結串列最前面的位置

digraph foo {
    rankdir=LR;
    subgraph cluster_0 {
        label = "linked list"
        node [shape=record];
        head [shape=ellipse];
        a [label="{ <data> 12 | <ref>  }", width=1.2]
        b [label="{ <data> 37 | <ref>  }", width=1.2];
        c [label="{ <data> 99 | <ref>  }", width=1.2];
        NULL [shape=plaintext];
    }
    before [shape=plaintext];
    subgraph cluster_1 {
        node [shape=record];
        label = "item";
        labelloc = "t";
        item [label="{ <data> 1 | <ref>  }", width=1.2];
    }
     
    head -> a:data [arrowhead=vee, tailclip=true];
    a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    before -> head [arrowhead=vee, tailclip=true, ];
}

digraph foo {
    rankdir=LR;
    subgraph cluster_0 {
        label = "linked list"
        node [shape=record];
        head [shape=ellipse];
        item [label="{ <data> 1 | <ref>  }", width=1.2];
        a [label="{ <data> 12 | <ref>  }", width=1.2]
        b [label="{ <data> 37 | <ref>  }", width=1.2];
        c [label="{ <data> 99 | <ref>  }", width=1.2];
        NULL [shape=plaintext];
    }
    head -> item:data [arrowhead=vee, tailclip=true];
    item:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}

反之，指向 NULL ，則會插入在尾巴

digraph foo {
    rankdir=LR;
    subgraph cluster_0 {
        label = "linked list"
        node [shape=record];
        head [shape=ellipse];
        a [label="{ <data> 12 | <ref>  }", width=1.2]
        b [label="{ <data> 37 | <ref>  }", width=1.2];
        c [label="{ <data> 99 | <ref>  }", width=1.2];
        NULL [shape=plaintext];
    }
    before [shape=plaintext];
    subgraph cluster_1 {
        node [shape=record];
        label = "item";
        labelloc = "t";
        item [label="{ <data> 1 | <ref>  }", width=1.2];
    }
     
    head -> a:data [arrowhead=vee, tailclip=true];
    a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    before -> NULL [arrowhead=vee, tailclip=true, ];
}

digraph foo {
    rankdir=LR;
    node [shape=record];
    head [shape=ellipse];
    a [label="{ <data> 12 | <ref>  }", width=1.2]
    b [label="{ <data> 37 | <ref>  }", width=1.2];
    c [label="{ <data> 99 | <ref>  }", width=1.2];
    NULL [shape=plaintext];
    item [label="{ <data> 1 | <ref>  }", width=1.2];
    
    head -> a:data [arrowhead=vee, tailclip=true];
    a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> item:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    item:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}

除了之外的事件都被視為 Undefined

其測試程式 test_list 將會對 list_insert_before 進行測試，驗證函式功能是否正確:

將 before 設置為鏈結串列的頭( l.head )，測試插入 item 到前面的功能
將 before 設置為 NULL ，測試插入 item 到後面的功能
- 判斷是否有 Unexpected Value 的情況
測試完畢後，重置鏈結串列(將值由小到大重新插入)

在現有的程式碼基礎上，撰寫合併排序操作

使用間接指標 **ptr 指向鏈結串列的頭，避免配置暫時指標的記憶體空間，而迴圈的中止條件為其中一串鏈結串列被走訪完畢 ( NULL ) ，剩餘的則透過 bitops 操作串上。

因為是單向鏈結串列(傳入的鏈結串列皆為排序過的)，所以當走訪過程中指向 NULL ，則代表其中一項串列被合併完了。

list_item_t **ptr = &head->head, **node;
for (node = NULL; L1 && L2; *node = (*node)->next) {
    node = (L1->head->value < L2->head->value) ? &L1->head : &L2->head;
    *ptr = *node;
    ptr = &(*ptr)->next;
}
*ptr = (list_item_t *) ((uintptr_t) L1->head | (uintptr_t) L2->head);

測驗 `2`

解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

程式碼函式

此程式碼實作了一個二元搜尋樹 (Binary Search Tree, BST) 來管理記憶體區塊，其中每個節點 (block_t) 代表一個記憶體區塊。
以下是程式中的主要函式及其用途：
1. block_t (二元搜尋樹的節點結構)

size：記錄該記憶體區塊的大小。
l, r：指向左右子節點，形成二元搜尋樹 (BST) 結構。

2. find_free_tree (搜尋記憶體區塊)

在 BST 中搜尋大小為 target 的節點，回傳該節點的位置 (**node_ptr)。

3. find_predecessor_free_tree

在 BST 中，尋找某個節點的 in-order predecessor。
in-order predecessor 是 BST 中小於該節點的最大節點，即左子樹中最右側的節點。

4. remove_free_tree (刪除 BST 節點)

負責從 BST 中移除指定的節點，並確保樹的結構仍然維持 BST 的特性。
依據節點的子節點數量，分為三種刪除情況：
1. Case 1：刪除的節點沒有子節點
2. Case 2：刪除的節點只有一個子節點
3. Case 3：刪除的節點有兩個子節點

刪除節點的處理邏輯

Case 1：刪除的節點沒有子節點
此情況最簡單，直接刪除節點即可。

處理方式
- *node_ptr = NULL;
Case 2：刪除的節點只有一個子節點
需要讓子節點取代被刪除的節點。

處理方式
1. 判斷 target 是只有左子節點還是只有右子節點。
2. 讓 target 的唯一子節點 直接取代 target。
Case 3：刪除的節點有兩個子節點
此情況最複雜，須透過 in-order predecessor 來找到取代節點。

處理方式 :
1. 透過 find_free_tree 找到目標節點，**node_ptr 指向目標位置。
2. **pred_ptr 指向 target 左子樹的根節點。
3. 使用 find_predecessor_free_tree 找到 target 左子樹中的最大節點 (即 target 的 in-order predecessor)。
Still Case 3 (進階情境)
當 target 有兩個子節點時，會進入 Case 3 的處理邏輯，在其中有以下細節需注意：
1. while 迴圈持續向右走訪左子樹，直到找到最右側的節點 (in-order predecessor)。
2. EEEE
  - EEEE 為 (*pred_ptr)->r，確保當 pred_ptr 已無右子節點時跳出迴圈。
3. FFFF
  - FFFF 為 pred_ptr 所指向節點的右子節點的地址 &(*pred_ptr)->r，如此才能使 while 迴圈不斷向右走訪。
4. 進一步確認 in-order predecessor
  - 透過 find_predecessor_free_tree 再次搜尋，並使用 assert 檢查找到的 in-order predecessor 是否正確，若不相同則終止程式。
5. 替換 target 為 pred_ptr
  - 若 pred_ptr 剛好是 target 的左子節點，則直接替換，並保留 target 的右子樹。
  - 若 pred_ptr 位於 target 左子樹的更深處，則需要先刪除 pred_ptr，然後用它取代 target。

測試程式碼

參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現

`allocator` 結構體定義

首先，這是 allocator 的結構體定義：

typedef struct allocator {
    size_t size;
    block_t *root;
    char mem[0];  
} allocator_t;

size 是指分配給 mem 區塊的空間大小，不包括 header。
root 是二元搜尋樹的根節點。
mem 為長度為 0 的陣列，這樣可以讓它的空間取決於分配給它的大小，而不會佔用額外的空間。

`block` 結構體定義

接著是 block 的結構體定義：

typedef struct block {
    size_t size;
    size_t prev_size;
    struct block *l, *r;
    char mem[0];
} block_t;

size 用於記錄包含 header 的區塊大小，這樣可以減少運算。
1. 因為多數的使用場景是要拿來計算上一個和下一個區塊的地址
prev_size 用於記錄前一個區塊的大小，有助於計算上一個區塊的位置，並且能夠用來判斷區塊是否已被使用。
l 和 r 依然是代表二元搜尋樹的左、右子節點。
mem 和上方一樣的概念

以下是三個主要函式的說明：

/**
 * alloc_create - Create a new allocator with a
 * maximum memory size, which will be aligned up to 8 bytes.
 * @size: maximum memory size
 */
allocator_t *alloc_create(size_t size);

/**
 * print_tree - Print the tree in preorder.
 * @root: the root node
 */
void print_tree(block_t *root);

/**
 * alloc_alloc - Allocate memory with allocator and size.
 * If there is not any invalid block, it will return NULL.
 * @allocator: the allocator
 * @size: the size of memory needed
 */
void *alloc_alloc(allocator_t *allocator, size_t size);

/**
 * alloc_free - Free an allocated memory.
 * @allocator: the allocator
 * @ptr: a pointer to the memory region
 */
void alloc_free(allocator_t *allocator, void *ptr);

alloc_create
用於創建一個新的 allocator ，並指定最大可用的記憶體大小。
alloc_alloc
用來從 allocator 中分配一塊指定大小的記憶體。
alloc_free
用來釋放一塊已分配的記憶體區塊。

alloc_create 函式的實作如下：

首先，size 會被對齊至 8 位元組，然後分配空間。
並在末尾插入一個 inuse 的 block_t。
- 這樣可以確保每個區塊都能夠正確地存取下一個區塊（NEXT_BLOCK）。
整個記憶體區塊被轉換為一個 block_t，並插入到二元搜尋樹中。

alloc_alloc 函式的實作如下：

首先將 size 進行 ALIGN_UP 操作，確保對齊。
之後確保記憶體可用空間能夠至少容納兩個 header 和所需的記憶體大小 size 。
- 這樣就可以將其分割為兩個區塊。
移除原本的區塊，然後將剩餘空間重新插入二元搜尋樹。

alloc_free 函式的實作如下：

釋放指定區塊時，首先檢查這個 block 前後區塊是否正在使用中。
如果這些區塊未被使用，則將它們從樹中移除並合併，最後重新插入到樹中。

commit:

巨集定義

以下是用於區塊管理和記憶體對齊的幾個重要巨集：

#define ALIGN_UP(size) (((size) + 7) & ~0x7)

/* size filed is or'ed with PREV_INUSE when previous adjacent chunk in use */
#define prev_inuse 0x1

/* extract inuse bit of previous chunk */
#define PREV_INUSE(block) (((block_t *) (block))->prev_size & prev_inuse)

/* extract block's inuse bit */
#define INUSE(block) (((block_t *) (block))->size & prev_inuse)

#define CLEAR_USE_BIT(size) ((size) & ~(prev_inuse))

#define NEXT_BLOCK(block)            \
    ((block_t *) ((char *) (block) + \
                  CLEAR_USE_BIT(((block_t *) (block))->size)))
#define PREV_BLOCK(block)            \
    ((block_t *) ((char *) (block) - \
                  CLEAR_USE_BIT(((block_t *) (block))->prev_size)))

#define NEXT_INUSE(block) (INUSE(NEXT_BLOCK(block)))

#ifndef container_of
#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) - offsetof(type, member)))
#endif

ALIGN_UP
向上對齊到 8 位元組
PREV_INUSE
上一個區塊是否被使用中
NEXT_INUSE
下一個區塊是否被使用中
INUSE
現在區塊是否被使用中
CLEAR_USE_BIT
將大小去除 USE_BIT
NEXT_BLOCK
下一個區塊
PREV_BLOCK
前一個區塊
container_of
將 list.h 中使用的巨集引入，可以從成員得到結構體

$ ./test.elf 
malloc:		324210046
custom-alloc:	298007916

使用gnuplot繪製
statistic

測驗 `3`

解釋上述程式碼運作原理

〈Optimized QuickSort — C Implementation (Non-Recursive)〉提出非遞迴 (non-recursive; iterative) 的快速排序法。此處提到的方法是以 swap 為主體，利用 L 與 R 去紀錄需交換的數量，再用 begin[] 與 end[] 作為堆疊，用來紀錄比較的範圍。
在此使用了 Linux 風格的 List API 來建立鍊結串列，並使用 value 來紀錄數值。

typedef struct __node
{
    long value;
    struct list_head list;
} node_t;

以下為測試與輔助函式:
list_construct : 在 list 中建立新的節點。
list_free : 釋放整個鏈結串列 list 已分配的記憶體空間。
list_is_ordered : 驗證鏈結串列 list 是否為有序排列。
shuffle : 打亂陣列的排列，運作條件為 n < RAND_MAX
list_tail : 找到鏈結串列 list 的尾巴
list_length : 計算鏈結串列 list 大小(內含多少節點)
rebuild_list_link : 將單向鏈結串列轉換為雙向環狀鏈結串列

迴圈內會將單向連接轉變為雙向連接，直到走訪至鏈結串列的尾巴 ( NULL )
因此， GGGG 為 head->prev=prev ，如此才能做到首尾相連

while (node) {
    node->prev = prev;
    prev = node;
    node = node->next;
}
prev->next = head;
head->prev=prev

接著便開始進行排序的動作，

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    HEAD [label="HEAD", shape=record];
    N1 [label="{ <value> 3 }", shape=record];
    N2 [label="{ <value> 1 }", shape=record];
    N3 [label="{ <value> 4 }", shape=record];
    N4 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    HEAD -> N1;
    N1 -> N2;
    N2 -> N3;
    N3 -> N4;
    N4 -> N5;
    N5 -> NULL;
    
    N2 -> N1 ;
    N3 -> N2 ;
    N4 -> N3 ;
    N5 -> N4 ;
}

排序的過程中，先將 L 及 R 兩指標指向鏈結串列的頭及尾。

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    HEAD [label="HEAD", shape=record];
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    L [label="*L",shape=plaintext];
    R [label="*R",shape=plaintext];
    
    L -> N3;
    R -> N5;
    
    HEAD -> N3;
    N3 -> N1;
    N1 -> N4;
    N4 -> N2;
    N2 -> N5;
    N5 -> NULL;
    
    N5 -> N2 ;
    N2 -> N4 ;
    N4 -> N1 ;
    N1 -> N3 ;
}

若 L 及 R 兩者不同，則將 piviot 指向 L 所指的節點，並將 piviot 的數值存於 value。

value = list_entry(pivot, node_t, list) -> value

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    HEAD [label="HEAD", shape=record];
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    L [label="*L",shape=plaintext];
    R [label="*R",shape=plaintext];
    piviot [label="*piviot",shape=plaintext];
    value [label="value = 3",shape=plaintext];
    
    L -> N3;
    R -> N5;
    piviot -> N3
    
    HEAD -> N3;
    N3 -> N1;
    N1 -> N4;
    N4 -> N2;
    N2 -> N5;
    N5 -> NULL;
    
    N5 -> N2 ;
    N2 -> N4 ;
    N4 -> N1 ;
    N1 -> N3 ;
}

使用 p 指向 piviot 的下一個節點，並斷開 piviot (指向 NULL )。

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    L [label="*L",shape=plaintext];
    R [label="*R",shape=plaintext];
    piviot [label="*piviot",shape=plaintext];
    p [label="*p",shape=plaintext];
    value [label="value = 3",shape=plaintext];
    
    p -> N1;
    L -> N3;
    R -> N5;
    piviot -> N3
    

    N1 -> N4;
    N4 -> N2;
    N2 -> N5;
    N5 -> NULL;
    
    N5 -> N2 ;
    N2 -> N4 ;
    N4 -> N1 ;

}

使用 p 逐步走訪整個節點，將小於 value 的置於 left 中，大於 value 則置於 right 中。

int n_value = list_entry(n, node_t, list)->value;

if (n_value > value) {
    n->next = right;
    right = n;
} else {
    n->next = left;
    left = n;
}

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    L [label="*L",shape=plaintext];
    R [label="*R",shape=plaintext];
    piviot [label="*piviot",shape=plaintext];
    value [label="value = 3",shape=plaintext];
    left [label="*left",shape=plaintext];
    right [label="*right",shape=plaintext];
    
    piviot -> N3
    L -> N3;
    R -> N5;

    left  -> N2;
    right -> N5 ;
    N5 -> N4;
    
    N2 -> N1;
    
}

接著將 begin[] 指向對應的位置。

begin[i]= begin[0] = left;
begin[i + 1]= begin[1] = pivot; /* JJJJ */
begin[i + 2]= begin[2] = right; /* KKKK */
left = right = NULL;

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    i [label="i = 2",shape=plaintext];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    L [label="*L",shape=plaintext];
    R [label="*R",shape=plaintext];
    begin_i [label="begin[0]",shape=plaintext];
    begin_i1 [label="begin[1]",shape=plaintext];
    begin_i2 [label="begin[2]",shape=plaintext];
    
    begin_i1 -> N3
    L -> N3;
    R -> N5;

    begin_i  -> N2;
    begin_i2 -> N5 ;
    N5 -> N4;
    
    N2 -> N1;
    
}

在下一輪，同樣將 L 指向 begin[i] 即 begin[2] (從較大子序列開始), 而 R 則指向 begin[2] 尾端。

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    i [label="i = 2",shape=plaintext];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    L [label="*L",shape=plaintext];
    R [label="*R",shape=plaintext];
    begin_i [label="begin[0]",shape=plaintext];
    begin_i1 [label="begin[1]",shape=plaintext];
    begin_i2 [label="begin[2]",shape=plaintext];
    
    begin_i1 -> N3
    R -> N4;

    begin_i  -> N2;
    L -> N5 ;
    N5 -> N4;
    begin_i2 -> N5;
    
    N2 -> N1;
    
}

此時按照先前的步驟將 piviot 設置在 L 並將 p 指向 piviot 下一個節點

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    i [label="i = 2",shape=plaintext];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    value [label="value = 5",shape=plaintext];
    piviot [label="*piviot",shape=plaintext];
    p [label="*p",shape=plaintext];
    begin_i [label="begin[0]",shape=plaintext];
    begin_i1 [label="begin[1]",shape=plaintext];
    
    begin_i1 -> N3

    begin_i  -> N2;
    N2 -> N1;
    
    piviot -> N5;
    N5 -> N4;
    p -> N4;
}

同樣逐步走訪節點，將小於 value 的置於 left 中，大於 value 則置於 right 中，並將 begin[] 指向對應的位置。

begin[i]= begin[2] = left;
begin[i + 1]= begin[3] = pivot;
begin[i + 2]= begin[4] = right;
left = right = NULL;

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    i [label="i = 2",shape=plaintext];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    value [label="value = 5",shape=plaintext];
    piviot [label="*piviot",shape=plaintext];
    begin_i [label="begin[0]",shape=plaintext];
    left [label="*left",shape=plaintext];
    right [label="*right",shape=plaintext];
    begin_i1 [label="begin[1]",shape=plaintext];
    
    begin_i1 -> N3
    
    begin_i  -> N2;
    N2 -> N1;
    
    left -> N4
    piviot -> N5;
    right -> NULL;
}

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    i [label="i = 4",shape=plaintext];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    begin_i [label="begin[0]",shape=plaintext];
    begin_i1 [label="begin[1]",shape=plaintext];
    begin_i2 [label="begin[2]",shape=plaintext];
    begin_i3 [label="begin[3]",shape=plaintext];
    
    begin_i1 -> N3
    
    begin_i  -> N2;
    N2 -> N1;
    
    begin_i2 -> N4
    begin_i3 -> N5;
}

此時 L 將指向 begin[4] , R 指向 begin[4] 的尾端，兩者皆指向 NULL ，且 L 為 NULL 因此 i= i-1 = 3 。又 3 也同樣為單一一個節點，因此 i 會不斷扣一並在過程中逐步將元素加到 result 中。

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    i [label="i = 2",shape=plaintext];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    result [label="*result",shape=plaintext];
    begin_i [label="begin[0]",shape=plaintext];
    begin_i1 [label="begin[1]",shape=plaintext];
    begin_i2 [label="begin[2]",shape=plaintext];
    L [label="*L",shape=plaintext];
    R [label="*R",shape=plaintext];
    
    begin_i1 -> N3
    L -> N2
    R -> N1
    begin_i  -> N2;
    N2 -> N1;
    
    begin_i2 -> N4
    result -> N5;
}

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    i [label="i = 1",shape=plaintext];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    result [label="*result",shape=plaintext];
    begin_i [label="begin[0]",shape=plaintext];
    begin_i1 [label="begin[1]",shape=plaintext];
    L [label="*L",shape=plaintext];
    R [label="*R",shape=plaintext];
    
    begin_i1 -> N3
    L -> N2
    R -> N1
    begin_i  -> N2;
    N2 -> N1;
    
    result -> N4;
    N4 -> N5
}

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    i [label="i = 0",shape=plaintext];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    result [label="*result",shape=plaintext];
    begin_i [label="begin[0]",shape=plaintext];
    L [label="*L",shape=plaintext];
    R [label="*R",shape=plaintext];
    
    L -> N2
    R -> N1
    begin_i  -> N2;
    N2 -> N1;
    
    result -> N3;
    N4 -> N5;
    N3 -> N4
}

此時依照先前的方法同樣為 2 及 1 兩個節點設置 begin[] 。

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    i [label="i = 2",shape=plaintext];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    result [label="*result",shape=plaintext];
    begin_i [label="begin[0]",shape=plaintext];
    begin_i1 [label="begin[1]",shape=plaintext];
    
    begin_i  -> N1;
    begin_i1 -> N2
    
    result -> N3;
    N4 -> N5;
    N3 -> N4
}

最後使用 result 收回

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    i [label="i = 1",shape=plaintext];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    result [label="*result",shape=plaintext];
    begin_i [label="begin[0]",shape=plaintext];
    
    begin_i  -> N1;
    
    result -> N2;
    N4 -> N5;
    N3 -> N4
    N2 -> N3
}

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];
    
    i [label="i = 0",shape=plaintext];
    
    N3 [label="{ <value> 3 }", shape=record];
    N1 [label="{ <value> 1 }", shape=record];
    N4 [label="{ <value> 4 }", shape=record];
    N2 [label="{ <value> 2 }", shape=record];
    N5 [label="{ <value> 5 }", shape=record];
    
    result [label="*result",shape=plaintext];
    
    
    result -> N1;
    N4 -> N5;
    N3 -> N4
    N2 -> N3
    N1 -> N2
}

接著再使用 rebuild_list_link 設置回原本的雙向環狀鍊結串列。

digraph LinkedListSort {
    rankdir=LR;
    node [shape=record];

    // 定義節點
    N1 [label="1 ", shape=record];
    N2 [label="2 ", shape=record];
    N3 [label="3 ", shape=record];
    N4 [label="4 ", shape=record];
    N5 [label="5 ", shape=record];

    // 指向排序結果
    result [label="*result", shape=plaintext];
    result1 [label="*result", shape=plaintext];

    // 雙向連結：每個節點都指向前後節點
    result -> N1;
    N1 -> N2;
    N2 -> N3;
    N3 -> N4;
    N4 -> N5;

    N2 -> N1;
    N3 -> N2;
    N4-> N3;
    N5 -> N4;

    N5 -> result1;
}

研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作

論文起因於 Sediment Sort ——一個聲稱針對 double linked-list 最快且最有效率的排序演算法。
為驗證其效能，作者整理並比較了六種針對不同鏈結串列結構的排序演算法進行比較，分類如下：

針對 Double Linked-List：
- Sediment Sort
針對 Single Linked-List：
- Selection Sort
- Merge Sort
- Bubble Sort
- Quick Sort
  - 於排序過程中額外使用一個 equal 鏈結串列，來記錄排序時具有相同大小的元素，以維持排序的穩定性 (stable)。

作者針對上述六種排序演算法進行實驗，比較它們在不同資料量下的效能。排序資料量 \(n\) 從 \(100\) 遞增至 \(1000\)，並記錄每種演算法在對應資料量下的執行時間。

下表為各演算法在不同資料量下的執行時間比較：

\(n\)	Sediment	Bubble	Selection	Merge	Quick	Tree
100	0.22	0.12	0.10	0.08	0.07	0.05
200	0.98	0.54	0.44	0.15	0.13	0.09
300	2.20	1.22	0.76	0.23	0.22	0.19
400	4.18	2.42	1.44	0.32	0.30	0.21
500	6.38	3.74	2.18	0.42	0.42	0.30
600	10.2	6.48	4.06	0.53	0.51	0.34
700	15.38	10.10	7.60	0.63	0.57	0.43
800	21.10	14.82	9.68	0.76	0.69	0.54
900	28.34	20.20	13.62	0.88	0.79	0.60
1000	36.58	26.14	17.88	1.01	0.89	0.69

由結果可觀察到，Sediment Sort 雖然設計上是針對 Double Linked-List 的排序演算法，但在所有測試資料量下，其執行時間皆為最長，效能遠遜於其他排序演算法。

我將運用 Linux 核心風格的 List API 實作 Sediment Sort 與 Tree Sort，並進行分析與驗證。

第 2 周測驗題

測驗 `1`

延伸問題 `1`

在此使用 Linux 核心風格 List API 來開發快速排序程式碼。使用 list_head 來建立鍊結串列，並使用變數型別 uint16_t 來紀錄要被排序的數值。

struct listitem {
    uint16_t i;
    struct list_head list;
};

以下為測試與輔助函式:
cmpint : 實作 quicksort 的比較，因為傳入的參數是 void * 不能做 bitops ，因此要先做強制型別轉換 (const uint16_t *)
random_shuffle_array : 打亂 operations 裡的排列順序，於迴圈中 get_unsigned16 將決定每階段互相交換的位置
getnum :

s1、s2、s3 以 static 宣告，因此只會初始化一次
使得每獲取一次亂數就更新一次，下次獲取的亂數就不會與現在一致，作到亂數的效果。

s1=(s1*171)%30269
s2=(s2*172)%30307
s3=(s3*170)%30323

get_unsigned16 : 呼叫上述 getnum 函式兩次製造16位元的亂數
main :
對含有 256 個數字的陣列 value 進行隨機排序，並建立一個鏈結串列加入這些數字。接著對鏈結串列執行 list_quicksort 快速排序，最後比較陣列 value 和鏈結串列的值 i ，若不同會因為巨集 assert 而終止程式。

主要函式:
list_quicksort

首先，要選擇鏈結串列第一個元素作為 pivot ，由於 head 會指向整個鏈結串列，因此使用 list_first_entry ，找到指向的鏈結串列第一個元素。
之後，要從鏈結串列裡移除 pivot ，好讓 quicksort 對鏈結串列剩餘的元素進行快速排列。
以 list_for_each_entry_safe 逐步走訪整個鏈結串列，將值小於 pivot 的用 list_move_tail 移入 list_less ，反之，大於的值移入 list_greater

pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
    if (cmpint(&item->i, &pivot->i) < 0)
        list_move_tail(&item->list, &list_less);
    else
        list_move_tail(&item->list, &list_greater);
}

透過遞迴對 pivot 左右兩邊的鏈結串列進行排序，當鏈結串列排到不能在排時就返回(只有單一元素)。
最後，當整個鏈結串列都排序完畢時，就要將 pivot 、 list_less 、 list_greater 合併。

list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);

延伸問題 `2`

測驗 `2`

延伸問題 `1`

在此嘗試開發整數的開平方根運算。

首先是 clz2 函式，其作用是藉由遞迴呼叫以計算 count leading zero (clz)。每次呼叫 clz2() 函式時，代表將目前關注的位元（bits）「切成一半」，以檢查 leading zero 的數量。以下藉由一個數值（0x0001F000）來說明其步驟：

0x0001F000 = 0000 0000 0000 0001 1111 0000 0000 0000 ~2~

Step1

將此數值分為兩部分: 較高位 ( upper ) 與較低位 ( lower ) 。

Upper	Lower
0000 0000 0000 0001	1111 0000 0000 0000

Step2

此時，依據 upper 的數值判斷下一次遞迴呼叫應該處理哪一部份，以累計 leading zero 的數量。

若 upper 等於0，則下一次遞迴呼叫應檢查 lower 部分，並用計數器（counter）記錄目前已累計的 leading zero（等於 upper 位元數）。
若 upper 不等於0，則下一次遞迴呼叫應繼續檢查 upper 部分。

upper = 0000 0000 0000 0001

由於 upper 不為 0，下一次遞迴呼叫將繼續檢查 upper 部分的 leading zero。

Step3

遞迴呼叫 clz2() 函式，直到僅剩 2 位元（bits）需要檢查 leading zero，然後回傳結果。

static const int mask[] = {0, 8, 12, 14}; // GGGG
static const int magic[] = {2, 1, 0, 0}; // HHHH, IIII

mask : 決定遮罩的大小，若 upper 不等於 0，則下一次遞迴呼叫時被使用
magic : 當遞迴呼叫 clz2() 函式至僅剩 2 位元需要檢查，也就是 c = 3 時，建表判斷有多少 leading zero

unsigned clz2(uint32_t x, int c)
{
    if (!x && !c)
        return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == 3)
        return upper ? magic[upper] : 2 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

如果 upper 不等於 0，則遞迴呼叫 clz2(upper, c+1)。由於 leading zero 只會出現在 upper，因此這部分的計算與 lower 無關。

若 upper 等於 0，則需要計算當前區間 16 >> c 中的 leading zero 數量，然後再遞迴呼叫 clz2(lower, c+1) 來計算 lower 的 leading zero 數量。

延伸 clz2 函式 count leading zero 想法:
clz64 (計算 64-bit 整數的前導零數量)

`clz64` (計算 64-bit 整數的前導零數量)

對於 64-bit 無符號整數 x，我們可以根據其高 32 位與低 32 位來決定如何計算前導零數量：

若高 32 位不為 0，則直接計算 clz32(high 32 bits)。
若高 32 位為 0，則計算 clz32(low 32 bits) + 32，因為這表示高 32 位的所有位元都是 0。

int shift = (total_bits - 1 - clz64(x)) & ~1; // MMMM
y >>= 1; // NNNN
m >>= 2; // PPPP

`sqrti` (計算 64-bit 無符號整數的整數平方根)

sqrti(x) 的目標是求得 floor(sqrt(x))，即 x 的整數平方根。
其核心思想類似於二進位搜尋，從 x 的最高有效位開始逐步逼近平方根。

步驟解析

確定最高有效位 (MSB, Most Significant Bit)
透過 clz64(x) 計算出 x 的 MSB 位置，並利用：
\begin{align} \text{total_bits} - 1 - \text{clz64}(x) \end{align}
來確定 MSB 在二進位數字中的實際位置。
確保起始的位移量是偶數
由於平方根的位數變化與整數平方的位數變化相對應，因此對 MSB 進行位元操作：
\begin{align} m = (\text{MSB} - 1) \& \sim 1 \end{align}
這確保 m 是偶數，使得 m 每次遞減 2 時能夠對應二進位平方的變化。

`sqrti` 計算範例：

以 \(N^2 = 17\) 為例，求 \(\lfloor \sqrt{17} \rfloor\)。
首先，將 \(17\) 轉換為二進位表示：

\begin{align} N^2 = (17)_{10} = (10001)_2 \end{align}

最高位在 \(b_4\)，因此從 \(m=4\) 開始，逐步降低並嘗試構造平方根。

m	計算平方值	結果
4	\(P_4^2 = (2^4)^2 = 256\)	\(256 > 17\)，\(P_4 = P_5\)，\(a_4 = 0\)
3	\(P_3^2 = (2^3)^2 = 64\)	\(64 > 17\)，\(P_3 = P_4\)，\(a_3 = 0\)
2	\(P_2^2 = (2^2)^2 = 16\)	\(16 < 17\)，\(P_2 = P_3 + 2^2\)，\(a_2 = 2^2\)
1	\(P_1^2 = (2^2 + 2^1)^2 = 36\)	\(36 > 17\)，\(P_1 = P_2\)，\(a_1 = 0\)
0	\(P_0^2 = (2^2 + 2^0)^2 = 25\)	\(25 > 17\)，\(P_0 = P_1\)，\(a_0 = 0\)

最終，平方根為：

\begin{align} N = P_0 = P_1 = P_2 = 2^2 = 4 \end{align}

因此，\(17\) 的整數平方根為 \(4\)。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

2025q1 Homework2 (quiz1+2)

第 1 周測驗題

測驗 1

測驗 2

程式碼函式

刪除節點的處理邏輯

處理方式

處理方式

處理方式 :

測試程式碼

allocator 結構體定義

block 結構體定義

以下是三個主要函式的說明：

巨集定義

測驗 3

第 2 周測驗題

測驗 1

延伸問題 1

延伸問題 2

測驗 2

延伸問題 1

clz64 (計算 64-bit 整數的前導零數量)

sqrti (計算 64-bit 無符號整數的整數平方根)

步驟解析

sqrti 計算範例：

延伸問題 2

延伸問題 3

測驗 3

延伸問題 1

測驗 `1`

測驗 `2`

`allocator` 結構體定義

`block` 結構體定義

測驗 `3`

測驗 `1`

延伸問題 `1`

延伸問題 `2`

測驗 `2`

延伸問題 `1`

`clz64` (計算 64-bit 整數的前導零數量)

`sqrti` (計算 64-bit 無符號整數的整數平方根)

`sqrti` 計算範例：

延伸問題 `2`

延伸問題 `3`

測驗 `3`

延伸問題 `1`