Try   HackMD

2025q1 Homework2 (quiz1+2)

contributed by < eleanorLYJ >

2025q1 第 1 週測驗題

測驗 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 週測驗題

測驗 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;
}