# 2025q1 Homework2 (quiz1+2)
contributed by < JeffBla >

## Q1 間接指標、鏈結串列與記憶體配置
### 測驗 1

### 解釋程式碼運作的原理

/**
 * Inserts a new item into the list before a specified item.
 *
 * This function traverses the list to locate the position immediately before
 * the item pointed to by @before and inserts @item in that position.
 * The time complexity is O(n), where n is the number of steps needed to
 * reach @before from the head of the list.
 *
 * Parameters:
 * @l      : Pointer to the list.
 * @before : Pointer to the item before which the new item should be inserted.
 *           - If @before is the head of the list, the new item is inserted
 *             at the front.
 *           - If @before is NULL, the new item is appended to the end of
 *             the list.
 *           - In all other cases, behavior is undefined if @before does not
 *             belong to @l.
 * @item   : The new list item to be inserted.
 */
static inline void list_insert_before(list_t *l,
                                     list_item_t *before,
                                     list_item_t *item){
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC)
        ;
    *p = item;
    DDDD = before;
}

AAAA = &l->head
BBBB = before
CCCC = &(*p)->next
DDDD = item->next

此函式是將節點 `item` 插入到 `before` 之前，在插入之前，需要知道指向 `before` 的節點，以修改節點順序，因此 for 的流程：
1. 初始化： 鏈結串列開頭。
2. 條件判斷： 當 pointer to pointer 所指向的 `next` 或 `head` 指向 `before` 則代表所操控的指標為 `before` 的前一個節點的 `next` ，即我們希望插入的位置，當到達此情況，則停止迴圈。
3. 移動至下一個：當離開迴圈條件不滿足，代表此 pointer to pointer 的數值並非所求，檢查下一個節點。

最後，因為找到目標指標所以將此指標指向欲新增的節點，並維護後續節點。其函式流程圖如下：
假設一開始的鏈結串列如下

digraph {
    rankdir=LR;
    node [shape=record];
    
    list -> head [tailport=s, headport=n];
    head -> node1;
    node1 -> node2;
    node2 -> node3;
}

初始化，將 pointer to pointer 指向 `&list->head` ，利用 pointer to pointer 控制指標以去除特例。

digraph {
    rankdir=LR;
    node [shape=record];
    
    edge_p [shape=point, width=0, height=0, label=""];
        
    list -> edge_p [dir=none];
    edge_p -> head;
    head -> before;
    before -> node2;
    node2 -> node3;
    
    p -> edge_p;
}

digraph {
    rankdir=LR;
    node [shape=record];
    
    edge_p [shape=point, width=0, height=0, label=""];
        
    list -> head;
    head -> edge_p [dir=none];
    edge_p -> before
    before -> node2;
    node2 -> node3;
    
    p -> edge_p;
}

當找到目標，則另用 pointer to pointer 控制 `next` 或 `head` 指標，插入新節點。

digraph {
    rankdir=LR;
    node [shape=record];
    
    edge_p [shape=point, width=0, height=0, label=""];
        
    list -> head;
    head -> edge_p [dir=none];
    edge_p -> before [color=red, style=dashed, label="old", fontcolor=red];
    before -> node2;
    node2 -> node3;
    
    p -> edge_p;
    
    // New connection (being added)
    edge_p -> new_node [color=green, style=bold, label="new", fontcolor=green];
    // Add a note
    note [shape=note, label="Changing pointer\nfrom before to new_node", color=blue];
    note -> edge_p [style=dotted, arrowhead=none, color=blue];
}

最後將新節點指向 `before` 完整插入。

digraph {
    rankdir=LR;
    node [shape=record];
    
    edge_p [shape=point, width=0, height=0, label=""];
        
    list -> head;
    head -> edge_p [dir=none];
    
    before -> node2;
    node2 -> node3;
    
    p -> edge_p;
    edge_p -> new_node;
    new_node->before;
}

### 解釋測試程式碼運作原理

主要測試函式為 `test_list` ，主要測試三個項目
1. 頭部插入
2. 尾部插入
3. 尾部插入（無數值檢查）

每項目由
1. 重設鏈結串列與待插入數值
2. 確認鏈結串列長度為零
3. 插入 `N` 項
4. 確認插入後鏈結串列長度為 `N`
5. 檢查插入數值是否符合預期

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

#### 實作 buttom-up mergesort

想法：使用 list_insert_before 進行將鏈結串列 2 依據遞增插入到 鏈結串列 1 的合併演算法。

[詳細實作](https://gist.github.com/JeffBla/921deb6a18373320151af0904541215e)

list_item_t *merge(list_item_t *left, list_item_t *right) {
  list_t result = {NULL};
  list_item_t *next;

  // Merge the two lists
  while (left && right) {
    if (left->value <= right->value) {
      next = left->next;
      list_insert_before(&result, NULL, left); // Insert at end
      left = next;
    } else {
      next = right->next;
      list_insert_before(&result, NULL, right); // Insert at end
      right = next;
    }
  }

  // Handle remaining elements
  while (left != NULL) {
    next = left->next;
    list_insert_before(&result, NULL, left);
    left = next;
  }

  while (right != NULL) {
    next = right->next;
    list_insert_before(&result, NULL, right);
    right = next;
  }

  return result.head;
}

void merge_sort(list_t *l) {
  if (!l || !l->head || !l->head->next)
    return;
  int len = 0;
  for (list_item_t *curr = l->head; curr; curr = curr->next)
    len++;

  for (int size = 1; size < len; size *= 2) {
    list_item_t dummy;
    dummy.next = NULL;
    list_item_t *tail = &dummy;
    list_item_t *curr = l->head, *left, *right;
    while (curr) {
      left = curr;
      right = split(left, size);
      curr = split(right, size);

      tail->next = merge(left, right);
      while (tail->next) {
        tail = tail->next;
      }
    }
    l->head = dummy.next;
  }
}

### 測驗 2

EEEE = (*pred_ptr)->r
FFFF = &(*pred_ptr)->r

### 解釋程式碼運作的原理

1. `find_free_tree` 從 `root` 找到 `target` 並回傳指向 `target` 的指標的指標，也就是指標的指標指向 `l` 或 `r` 。
2. `find_predecessor_free_tree` 找到能夠替換的 `target` 的節點。

此函式刪除二元搜尋樹中的特定節點。首先找到指向 `target` 的指標的指標。判斷欲刪除節點之子嗣的存在與否，如果沒有則直接刪除，若存在其一且唯一，則將後代上提，替換目標節點。若左右兩邊都存在節點且將替換的節點為 `target` 的兒子，則直接替換，因為其替換的演算法為找尋左子樹中最大值，如果將替換節點為其後代，則代表欲替換節點左子樹不須處理且能夠直接承接 `target` 之右子樹。若左右兩邊都存在節點但將替換節點不為 `target` 的兒子，則紀錄 `target` 左右子樹，遞迴修剪欲替換的節點，待欲替換的節點整理完成，執行替換。

第一種：欲刪除節點沒有子嗣

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
        
    root:l -> node2;
    root:r -> node3;
    
    node2:l -> node4;
    node2:r -> node5;
}

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
    node5 [label="<l> left|<s> target|<r> right"];
    node_ptr [label="node_ptr"];
    edge_p [shape=point, width=0, height=0, label=""];
    null [label="NULL"];
        
    root:l -> node2;
    root:r -> node3;
    
    node2:l -> node4;
    node2:r -> edge_p [dir=none];
    edge_p -> node5 [color=red, style=dashed, label="old", fontcolor=red];
    
    node_ptr ->edge_p;
    
    
    // New connection (being added)
    edge_p -> null [color=green, style=bold, label="new", fontcolor=green];
}

第二種：存在左或右子代其一

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
        
    root:l -> node2;
    root:r -> node3;
    
    node2:l -> node4;
    
    node4:l -> node8;
    node4:r -> node9;
}

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
    node2 [label="<l> left|<s> target|<r> right"];
    node_ptr [label="node_ptr"];
    edge_p [shape=point, width=0, height=0, label=""];
        
    root:l -> edge_p [dir=none];
    edge_p -> node2;
    root:r -> node3;
    
    node2:l -> node4;
    
    node4:l -> node8;
    node4:r -> node9;

    node_ptr -> edge_p;
}

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
    node2 [label="<l> left|<s> target|<r> right"];
    edge_p [shape=point, width=0, height=0, label=""];
    node_ptr [label="node_ptr"];
        
    root:l -> edge_p [dir=none];
    edge_p -> node2 [color=red, style=dashed, label="old", fontcolor=red];
    root:r -> node3;
    
    node2:l -> node4;
    
    node4:l -> node8;
    node4:r -> node9;

    node_ptr -> edge_p;
    
    // New connection (being added)
    edge_p -> node4 [color=green, style=bold, label="new", fontcolor=green];
}

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
    node2 [label="<l> left|<s> target|<r> right"];
        
    root:l -> node4;
    root:r -> node3;
    
    node4:l -> node8;
    node4:r -> node9;
}

第三種：存在左與右子代

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
        
    root:l -> node2;
    root:r -> node3;
    
    node2:l -> node4;
    node2:r -> node5;
    
    node4:l -> node8;
    node4:r -> node9;

    node9:l -> node18;
}

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
    node2 [label="<l> left|<s> target|<r> right"];
    edge_p [shape=point, width=0, height=0, label=""];
    edge_pred [shape=point, width=0, height=0, label=""];
    node_ptr [label="node_ptr"];
    pred_ptr [label="pred_ptr"];
        
    root:l -> edge_p [dir=none];
    edge_p -> node2;
    root:r -> node3;
    
    node2:l -> edge_pred;
    edge_pred -> node4;
    node2:r -> node5;
    
    node4:l -> node8;
    node4:r -> node9;

    node9:l -> node18;

    node_ptr -> edge_p;
    pred_ptr -> edge_pred;
}

紀錄欲移除節點的左右子樹，以利後續維護。

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
    node2 [label="<l> left|<s> target|<r> right"];
    edge_p [shape=point, width=0, height=0, label=""];
    edge_pred [shape=point, width=0, height=0, label=""];
    node_ptr [label="node_ptr"];
    pred_ptr [label="pred_ptr"];
    pred_node [label="pred_node"];
    node9 [label="<l> left|<s> node9|<r> right"];
    node18 [label="<l> left|<s> node18|<r> right"];
        
    root:l -> edge_p [dir=none];
    edge_p -> node2;
    root:r -> node3;
    
    node2:l -> node4 [color=red label="recorded"];
    node2:r -> node5 [color=red label="recorded"];
    
    node4:l -> node8;
    node4:r -> edge_pred [dir=none];
    edge_pred -> node9;

    node9:l -> node18;

    node_ptr -> edge_p;
    pred_ptr -> edge_pred;
    
    pred_node -> node9;
}

`pred_ptr` 找到將替換節點後，利用遞迴，將欲替換節點當作欲移除節點，確保替換後，二元搜索樹結構仍正確。因為替換節點需要做移除並插入的動作，所以利用遞迴將此種操作傳遞到子代，一直到末端。下面是進入迴圈，處理子代的操作：

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
    node2 [label="<l> left|<s> target|<r> right"];
    edge_p [shape=point, width=0, height=0, label=""];
    edge_pred [shape=point, width=0, height=0, label=""];
    node_ptr [label="node_ptr"];
    pred_ptr [label="pred_ptr"];
    pred_node [label="pred_node"];
    node9 [label="<l> left|<s> node9|<r> right"];
    node18 [label="<l> left|<s> node18|<r> right"];
        
    root:l -> edge_p [dir=none];
    edge_p -> node2;
    root:r -> node3;
    
    node2:l -> node4 [color=red label="recorded"];
    node2:r -> node5 [color=red label="recorded"];
    
    node4:l -> node8;
    node4:r -> edge_pred [dir=none];
    edge_pred -> node9 [color=red, style=dashed, label="old", fontcolor=red];

    node9:l -> node18;

    node_ptr -> edge_p;
    pred_ptr -> edge_pred;
    pred_node -> node9;
    
    // New connection (being added)
    edge_pred -> node18 [color=green, style=bold, label="new", fontcolor=green];
}

當子代處理完成，回到 `target` 的處理。

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
    node2 [label="<l> left|<s> target|<r> right"];
    edge_p [shape=point, width=0, height=0, label=""];
    node_ptr [label="node_ptr"];
    pred_node [label="pred_node"];
    node9 [label="<l> left|<s> node9|<r> right"];
    node18 [label="<l> left|<s> node18|<r> right"];
        
    root:l -> edge_p [dir=none];
    edge_p -> node2;
    root:r -> node3;
    
    node2:l -> node4 [color=red label="recorded"];
    node2:r -> node5 [color=red label="recorded"];
    
    node4:l -> node8;
    node4:r -> node18;

    node_ptr -> edge_p;
    pred_node -> node9;
}

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
    node2 [label="<l> left|<s> target|<r> right"];
    edge_p [shape=point, width=0, height=0, label=""];
    node_ptr [label="node_ptr"];
    pred_node [label="pred_node"];
    node9 [label="<l> left|<s> node9|<r> right"];
    node18 [label="<l> left|<s> node18|<r> right"];
        
    root:l -> edge_p [dir=none];
    edge_p -> node2 [color=red, style=dashed, label="old", fontcolor=red];
    root:r -> node3;
    
    node2:l -> node4 [color=red label="recorded"];
    node2:r -> node5 [color=red label="recorded"];
    
    node4:l -> node8;
    node4:r -> node18;

    node_ptr -> edge_p;
    pred_node -> node9;
    
    // New connection (being added)
    edge_p -> node9 [color=green, style=bold, label="new", fontcolor=green];
}

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
    node2 [label="<l> left|<s> target|<r> right"];
    node9 [label="<l> left|<s> node9|<r> right"];
    node18 [label="<l> left|<s> node18|<r> right"];
        
    root:l -> node9;
    root:r -> node3;
    
    node2:l -> node4;
    node2:r -> node5;
    
    node4:l -> node8;
    node4:r -> node18;

    node9:l -> node4 [color=red];
    node9:r -> node5 [color=red];
}

digraph {
    rankdir=TD;
    node [shape=record];
    node [label="<l> left|<s> node|<r> right"];
    
    root [label="<l> left|<s> root|<r> right"];
    node2 [label="<l> left|<s> target|<r> right"];
    node9 [label="<l> left|<s> node9|<r> right"];
    node18 [label="<l> left|<s> node18|<r> right"];
        
    root:l -> node9;
    root:r -> node3;
    
    node4:l -> node8;
    node4:r -> node18;

    node9:l -> node4;
    node9:r -> node5;
}

### 嘗試補完程式碼

[詳細程式碼](https://gist.github.com/JeffBla/353b44dd7bf834b76a21309b1472fcf8)

測試程式碼移除的三種情況。實作找到指向 `target` 的指標、初始化並插入建二元搜索樹。

block_t **find_free_tree(block_t **root, block_t *target) {
  if (!*root) {
    return root;
  }
  while ((*root)->size != target->size) {
    if ((*root)->size < target->size) {
      root = &(*root)->r;
    } else {
      root = &(*root)->l;
    }
  }

  return root;
}

void insert_free_tree(block_t **root, size_t sz) {
  if (!*root)
    return;

  while (*root) {
    if ((*root)->size < sz) {
      root = &(*root)->r;
    } else {
      root = &(*root)->l;
    }
  }
  *root = malloc(sizeof(block_t));
  (*root)->l = NULL;
  (*root)->r = NULL;
  (*root)->size = sz;
}

static void tree_reset(void) {
  root.l = NULL;
  root.r = NULL;

  for (size_t i = 0; i < N; i++) {
    temp[i] = i + 1;
  }

  size_t index = 0;

  fill_balanced(0, N - 1, &index);
}

以 N 為 1000 節點測試，建造 complete BST ，並依序刪除
1. First quarter: N / 4
2. Middle: N / 2
3. Third quarter: 3 * N / 4
4. First item: 0
5. Last item: N -

之後測試隨機刪除直到節點全被移除。

### 效能評比

### 測驗 3

### 解釋程式碼運作原理

GGGG = head->prev=prev
HHHH = list_entry(pivot,node_t,list)->value
IIII = list_entry(n,node_t,list)->value
JJJJ = pivot
KKKK = right

此程式碼和運用 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼原理相同。

利用 `begein` 與 `end` (在此實作利用 list_tail 取代) 代替分割所需要的遞迴空間及紀錄數值。採用和 list_sort.h 類似風格實作，首先，將環狀改成非環狀並在後續復原 `prev` 指標，復原環狀與雙向指標的特性。利用 `L` 代表串列最左， `R` 代表串列最右進行範圍內的運算，其中 `pivot` 為最左邊的節點，並將此節點獨立，利用 `p` 指標遍歷`L` 到 `R` 中的節點，將大於 `pivot` 內數值的節點歸到 `right` 其他歸到 `left` 。 最後將 `right` 、 `pivot` 、 `left` 開頭記錄到 `begin` ，其中 `right` 所記錄的位置最後面， 其次是 `pivot` 和 `left` ，由於 `begin` 採用堆疊的概念，在排序時，也是 `right` 完成後才是 `pivot` 與 `left` 。 當排序完成， `L` 與 `R` 指向相同節點，將此節點記錄到 `result` ，並使用 `begin` 執行前面一項鏈結串列排序。

## Q2 鏈結串列、雜湊表，及位元操作

### 測驗 1

AAAA = list_first_entry
BBBB = list_del
CCCC = list_move_tail
DDDD = list_add
EEEE = list_splice
FFFF = list_splice_tail

### 解釋上方程式碼運作原理

### 改進 random_shuffle_array

利用 ASLR 實作隨機，在 `unbiased_random` 中乘法可有效地將隨機分佈擴展到目標範圍，透過採用高位而不是使用模數，避免偏差。

#include <stdlib.h>
#include <time.h>
#include <stdint.h>

static uint16_t get_unsigned16(void) {
    // Get addresses of different functions that will be randomized by ASLR
    void* func_ptr1 = (void*)&malloc;
    void* func_ptr2 = (void*)&free;
    
    // Create some stack variables to get their addresses
    int stack_var1;
    int stack_var2;
    
    // Mix function and stack addresses together
    uintptr_t addr_mix = (uintptr_t)func_ptr1 ^ 
                         (uintptr_t)func_ptr2 ^ 
                         (uintptr_t)&stack_var1 ^ 
                         (uintptr_t)&stack_var2;
    
    // Mix in some dynamic memory address
    void* heap_ptr = malloc(sizeof(int));
    addr_mix ^= (uintptr_t)heap_ptr;
    free(heap_ptr);
    
    // Add time component for additional entropy
    addr_mix ^= (uintptr_t)time(NULL);
    
    // Extract 16 bits with better mixing
    uint16_t random_value = (uint16_t)((addr_mix >> 4) ^ (addr_mix >> 8) ^ addr_mix);
    
    return random_value;
}

static uint16_t unbiased_random(uint16_t max_exclusive) {
    // For small ranges relative to UINT16_MAX, this approximation works well
    uint32_t random = get_unsigned16();
    uint32_t scaled = (random * (uint32_t)max_exclusive) >> 16;
    return (uint16_t)scaled;
}

static inline void random_shuffle_array(uint16_t *operations, uint16_t len) {
    for (uint16_t i = 0; i < len; i++) {
        // Will generate a number between 0 and i inclusive
        uint16_t j = unbiased_random(i + 1);
        uint16_t temp = operations[i];
        operations[i] = operations[j];
        operations[j] = temp;
    }
}

### 若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting

`list_for_each_entry_safe` 是由前到後遍歷， `list_move_tail` 將每次遍歷的數值加入到特定鏈結串列的末端，形成類似佇列的排列，先插入的節點會在前面，而後插入的在後面，確保了 stable 的性質。若換成 `list_move` 將每次遍歷的數值加入到特定鏈結串列的前端，則形成如堆疊的排列，先插入的節點在後面，後插入的在前面。

### 測驗 2

GGGG = 14
HHHH = 2
IIII = 0
JJJJ = 3
KKKK = 2
LLLL = 1
MMMM = ~1
NNNN =
PPPP =