2025q1 Homework2 (quiz1+2)

contributed by <Nsly0204>

第一周測驗題

測驗 1

解釋程式碼運作原理

先分析以下程式碼，可以發現 list_item 是一個類似 linux 核心風格的鍊結串列實作，list_item 類似於 list_head ，而list_t 類似於 *head。

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

typedef struct {
    struct list_item *head;
} list_t;

有了以上分析再結合指標的指標的概念，將 p 作為指向 (*node)->next 的指標，而 (*p) 指向 node ，由此可知當*p != before 時持續往下走訪，直到停止條件 (*p)->next == before 時，把 node 替換成 item 即為所求。

// 在指定節點之前插入新節點
static void list_insert_before(list_t *list, list_item_t *before, list_item_t *item)
{
    list_item_t **p;
    for (p = &list->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
    (*p)->next = before;
}

在執行以下程式時出現 segmentation fault:

    int main() {
    list_t l;
    list_item_t *it1, *it2;
    list_item_t it3;

    list_item_t *ptr1;
    it1->value = 1;
    it2->value = 2;
    it1->next = it2;
    it2->next = NULL; 
    l.head = it1;
    ptr1 = it2;
    printf("l.head->value = %d \n", l.head->value);
}

利用 gdb 偵錯之後發現在第7行時發現錯誤

Program received signal SIGSEGV, Segmentation fault.
0x0000555555555159 in main () at dbl_ptr_test.c:21
21 it1->value = 1;

查閱 c11 規格書

§ 6.2.4 Storage durations of objects
A non-lvalue expression with structure or union type, where the structure or union
contains a member with array type (including, recursively, members of all contained
structures and unions) refers to an object with automatic storage duration and temporary
lifetime.36) Its lifetime begins when the expression is evaluated and its initial value is the
value of the expression. Its lifetime ends when the evaluation of the containing full
expression or full declarator ends. Any attempt to modify an object with temporary
lifetime results in undefined behavior.

思考後發現來目前所有指標變數 it1，it2 等都是只有 temporary lifetime 的指標，尚未被配置記憶體位置，觸發上述規格書末段的 undefined behavior ，須補上顯示記憶體配置即可正常執行。

it1 = (list_item_t *)malloc(sizeof(list_item_t));
it2 = (list_item_t *)malloc(sizeof(list_item_t));

在原本的quiz1中不用這樣寫的原因是 static list_t l; 為 file scope variable ，代表在編譯時在 .data 的部份就有靜態配置記憶體，故沒有發生 undefined behavier。

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

測驗 2

快速複習BST(Binary Search Tree)

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

本次測驗嘗試用樹狀結構模擬記憶體管理，二元搜索樹(以下簡稱BST)的節點代表可用空間，函式 remove_free_tree 代表目前需要一個 target->size 大小的記憶體區塊，對應操作從 BST 中找到一個大於等於要求 (target) 的記憶體空間進行分配，被分配的空間會從管理閒置空間的 BST 中被刪除。

BST 的刪除通常會被分成三種情況：

1. 刪除的節點是 leaf (沒有child)
   • 直接刪除節點即可
2. 刪除的節點只有一個 child
   • 用唯一的子節點代替被刪除的節點
3. 刪除的節點有兩個 child
   • 繼承者為待刪除的節點的左子節點，直接取代。
   • 繼承者在左子樹更深曾的地方，遞迴呼叫函式把繼任者從子樹刪除，直到

3 的情況因為需要把左右子數接回，我們需要找到 inorder predecessor 也就是左子樹中最右邊的點(小於root中最大的節點)取代被移除的節點所以我們進一步討論子節點取代被刪除節點的可能。

find_free_tree
考慮到如果目的是管理樹狀結構的記憶體區塊，樹狀結構本身會很深，外加 void remove_free_tree(block_t **root, block_t *target) 在每次遞迴都會呼叫此函式，若使用常規的遞迴寫法可能會有 stack overflow 發生，故這裡使用迭代實現。

block_t **find_free_tree(block_t **root, block_t *target)
{
    // find the minimum node >= target
    if (!(*root) || !root)
        return NULL;
    
    block_t **curr = root;
    while ((*curr))
    {
        if ((*curr)->size == target->size)
            break;
        if ((*curr)->l && (*curr)->l->size >= target->size)
            curr = &(*curr)->l;
        else 
            break;
    }
    return curr;
}

測試
這裡參考 rota1001 補上 insert_tree 和主函式，以亂序插入10個節點測試程式運作。

void insert_tree(block_t **root, size_t size)
{
    if (!(*root)) {
        *root = malloc(sizeof(block_t));
        if(!(*root))
            return;
        (*root)->size = size;
        (*root)->l = (*root)->r = NULL;
        return;
    }
    if ((*root)->size < size)
        insert_tree(&(*root)->r, size);
    else if ((*root)->size > size)
        insert_tree(&(*root)->l, size);
    else {
        printf("Invalid input size");
        free(*root);
    }
}

int main ()
{
    block_t *root = NULL;
    for (int i = 0; i < 10; i++) {
        insert_tree(&root, (i * 3) % 10);
    }
    print_tree(root);
    puts("");

    block_t temp;
    for (int i = 0; i < 10; i++)
    {
        temp.size = i;
        remove_free_tree(&root,&temp);
        print_tree(root);
        puts("");
    }
}

輸出如預期運作：

0 1 2 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9 
2 3 4 5 6 7 8 9 
3 4 5 6 7 8 9 
4 5 6 7 8 9 
5 6 7 8 9 
6 7 8 9 
7 8 9 
8 9 
9 

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

測驗 3

解釋上述程式碼運作原理

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

第二周測驗題

測驗 1

測驗 2

測驗 3

筆記

你所不知道的C語言：指標篇

// Answer
struct tag (*var[])()

cdecl> declare array of pointer to function returning struct tag

我們必須先了解以下兩者的差別：

// an array of pointer: *var[]
pointer_type *array_name [array_size];
pointer_type* array_name[array_size];

// a pointer to array
pointer_type (*array_name)[array_size];

• an array of pointer： 從宣告的形式 pointer_type * 就能看出是指標，而後面的 [array_size] 則代表有 array_size 這麼多個指標。
• a pointer to array： 先考慮 pointer_type array_name[array_size] 的基本陣列宣告後比較可以知道。這裡將 array_name 轉型成為指標，意思是說 array_name 從原本的陣列變成一個指向陣列的指標。
  在了解 array of pointer 之後，參考 Function pointers in C ，我們可以發現這其實是與 pointer to array 一樣的轉型方式，將 functionPtr 轉形成指標的形式。

// a int type pointer to the function
int sum = (*functionPtr)(2, 3); // sum == 5

接下來參考論壇討論 Declare a C/C++ function returning pointer to array of integer pointers 根據裡面提供的程式並在 godbolt 驗證。

// argument int *
function(int *)
// a function with argument int *, returning pointer to   (*function(int *)) 
// a function with argument int *, returning pointer to array of 4
(*function(int *))[4]
// a function with argument int *, returning pointer to array of 4 integer pointers
int *(*function(int *))[4];

有了以上的知識我們觀察解答然後逐一拆解

*var[] // "var" is an array of pointer
(*var[])() // "var" is an array of pointer to function w/o parameter
struct tag (*var[])() // array of pointer to function returning struct tag