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 的數值並非所求，檢查下一個節點。

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

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

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

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

解釋測試程式碼運作原理

主要測試函式為 test_list ，主要測試三個項目

1. 頭部插入
2. 尾部插入
3. 尾部插入（無數值檢查）

每項目由

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

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

實作 buttom-up mergesort

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

詳細實作

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 左右子樹，遞迴修剪欲替換的節點，待欲替換的節點整理完成，執行替換。

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

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

第三種：存在左與右子代

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

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

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

嘗試補完程式碼

詳細程式碼

測試程式碼移除的三種情況。實作找到指向 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) 實作非遞迴 (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 =