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

## [2025q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz1)
### 測驗 1
#### 解釋程式碼原理
要完成 list_insert_before，此函式的功能為，將新的 item 插入到 list 中的特定 item 之前。

在完成函式之前，先看 list_item 的結構

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

typedef struct {
    struct list_item *head;
} list_t;

`p` 是指向 list_item_t 指標的指標，因為看到 `*p = item` 故能得知，迴圈跑完， `p` 會移到 `before` 的前一個位置的 `next`，也就是 item 插入的位置。

static list_item_t items[N];

static inline void list_insert_before(list *l, list_item_t *before, list_item_t *item)
{
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC)
        ;
    *p = item;
    DDDD = before;
}

因此由此推論，迴圈是從 list 的開頭開始跌代，接著每次先對 p 做dereference 得到該指標的下一個地址，然後發現下一個地址等於 `before`，停止迭代。

static inline void list_insert_before(list *l, list_item_t *before, list_item_t *item)
{
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*(p)->next))
        ;
    *p = item;
    item->next = before;
}

### 撰寫合併排序操作

### 測驗 2

### 測驗 3

## [2025q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz2)

### 測驗 1

### 測驗 2

開平方根

### 測驗 3
hash table

從題目敘述得知 hash table 的基礎概念
> hlist_head 只使用一個 first 指標指向 hlist_node，沒有指向串列尾節點的指標。
> hash table 主要是由一個 hlist_head 的動態陣列所構成，每個 entry 指向一個由 struct hlist_node 構成的非環狀 doubly linked list ，hash table 長度依照 bits 給定，可知大小為 2 的冪。

先看需要的雜湊表的結構。

struct hlist_node {
    struct hlist_node *next, **pprev;
};

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

`find_key()` 是要找值為 key 所在的 `struct hash_key`，若找不到就返回 NULL。

find_key 的實現細節為，先找 key 所在的 hlist，然後迭代 hlist 並逐一比較節點找是否有 key。其中為使用 `container_of` 找在 p 所在的 `struct hash_key` 的位置，比較成員 key 是否等於參數的 key。

static struct hash_key *find_key(map_t *map, int key)
{
    struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
    for (struct hlist_node *p = head->first; p; p = p->next) {
        struct hash_key *kn = container_of(p, struct hash_key, node);
        if (kn->key == key)
            return kn;
    }
    return NULL;
}

以下補充 container_of 的定義。

/* container_of() - Calculate address of object that contains address ptr
 * @ptr: pointer to member variable
 * @type: type of the structure containing ptr
 * @member: name of the member variable in struct @type
 *
 * Return: @type pointer of object containing ptr
 */
 
#define container_of(ptr, type, member)                            

map_add() 函式則負責新增一對 key 與 data 到 hash table 中。如果 key 已經存在，返回，不更新 data。如果不存在，則創建依參數而產生的 hash_key (`kn`)，並將其插入到對應的 hlist_head 中。插入操作會確保新的 node 被正確地連接到鏈結串列的頭部，並更新相關的前驅節點指標 pprev。

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    struct hlist_head *h = &map->ht[hash(key, map->bits)];
    struct hlist_node *n = &kn->node, *first = h->first;

    n->next = first;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first;
}