# 2025q1 Homework2 (quiz1+2)
contributed by < willy-liu >

## 2025q1 第 1 週測驗題

### 測驗 `1`

根據定義

#include <stddef.h>
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;


要實作`list_insert_before`，就要先遍歷鏈結串列，找到before。最簡單的做法其實只需要`*p`就好，實作如下

{
    list_item_t *p;

    if (l->head == before) {
        item->next = l->head;
        l->head = item;
        return;
    }

    for (p = l->head; p && p->next != before; p = p->next);
    if (p) {
        item->next = p->next;
        p->next = item;
    }
}

首先找到要插入的位置，然後將`item->next`設定為`p->next`，最後讓`p->next`等於item就好。
然而，這樣的實作方式在邊界條件就會有例外，`before`如果在`head`就需要將`l->head`取代成`item`。這樣的例外就是一個不好的code smell，特別是在雙向鏈結串列，或是其他結構，如果邊界情況有好幾個時，不但會影響程式碼的閱讀，還會影響效能。

使用了`**p`就可以完美解決這樣的邊界情況，將遍歷的對象從節點本身，改為在`next`指標的**位址**上做移動，`head`的型態也與`next`相同，所以對p取址一次`*p`就可以變更`l->head`或是`list_item->next`，邊界情況要做的事與一般情況的邏輯就會一致。

{
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next);
    item->next = *p;
    *p = item;
}

:::spoiler 延伸-撰寫合併排序操作
要實作合併排序，需要


:::

### 測驗 `2`

### 測驗 `3`

## 2025q2 第 2 週測驗題

### 測驗 `1`

### 測驗 `2`

### 測驗 `3`

`AAAA`：`map->bits`
`BBBB`：`map->bits`
`CCCC`：`first->next`
`DDDD`：`n->pprev`
`EEEE`：`n->pprev`

Linux kernel風格的hash table架構如下
這邊注意到pprev是「指標的指標」，才可以避免發生移除節點時的例外，因為開頭的行為會與其他節點有不一致的行為

digraph G {
    rankdir = LR;
    splines = false;
    node[shape = "record"]

    list_head[label = "<m>list_head | <n>first"]
    node_1[label = "<m>dll_node_1 | {<p>prev | <n>next}", group = list];
    node_2[label = "<m>dll_node_2 | {<p>prev | <n>next}", group = list];
    node_3[label = "<m>dll_node_3 | {<p>prev | <n>next}", group = list];
    
    NULL_1, NULL_2[shape = plaintext, label = "NULL", group = list]

    {rank = "min" list_head NULL_1}
    
    list_head -> node_1:m;
    node_1:p -> NULL_1
    
    node_1:n -> node_2:m;
    node_2:p -> node_1:m;
    
    node_2:n -> node_3:m;
    node_3:p -> node_2:m;
    node_3:n -> NULL_2;
}

#### 結構體解釋

typedef struct {
    int bits;
    struct hlist_head *ht;
} map_t;

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};