Try   HackMD

2022q1 Homework1 (quiz1)

contributed by < freshLiver >

tags: linux2022

第一題 - LeetCode 1. Two Sum

Hash Table

建立雜湊表

/**
 * @brief 建立並初始化一個有 2^bits 個欄位的雜湊表
 *
 * @param bits
 * @return map_t*
 */
map_t *map_init(int bits)
{
    map_t *map = malloc(sizeof(map_t));
    if (!map)
        return NULL;

    map->bits = bits;
    map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
    if (map->ht) {
        // 成功分配空間給雜湊表,初始化所有欄位
        for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
            (map->ht)[i].first = NULL;
    } else {
        free(map);
        map = NULL;
    }
    return map;
}

節點搜尋

/**
 * @brief 從雜湊表中尋找並回傳一節點 kn,且 kn.key == @key
 *
 * 將 @key 經過雜湊函數計算後得到所屬欄位,
 * 接著依序走訪該欄位並檢查目標資料 @key 是否存在於該欄位中,
 * 若有找到則回傳包含該資料的節點,若不存在則回傳 NULL。
 *
 * @param map 目標雜湊表
 * @param key 目標節點的 key
 * @return struct hash_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;
}

資料獲取

/**
 * @brief 從雜湊表中提取 key 與 @key 相符之節點 kn 的資料 data
 *
 * @param map 目標雜湊表
 * @param key 數列 nums 中的某數 k
 * @return void*
 */
void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}

資料儲存

/**
 * @brief 建立一節點 kn 來保存 @key 以及 @data
 *
 * @param map 目標雜湊表
 * @param key 數列 nums 中的某數 k
 * @param data k 在數列 nums 中的 index
 */
void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;  // 所有節點的 key 不應重複

    // 分配空間以及將資料複製到該節點
    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;


    /**
     * @brief 將新增的節點插入到對應欄位的首位
     *
     * 首先透過雜湊函式取得目標欄位的地址 h
     * 以及該欄位的首位節點 first
     * 最後再為 h->next, n, first 重新建立連結
     *
     * - 新的節點 n 需要設定 pprev 以及 next
     *      - n->next 指向原本的首位節點 first
     *      - n->pprev 則指向欄位 h 指向首位節點的結構體地址 &h->first
     *
     * - 欄位 h 應指向新的首位節點 n
     * - 原首位節點 first 的 pprev 改指向新節點 n 的 next 的地址 &n->next
     *
     */
    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;
}

我自己的發現是 其實你仔細看 n->next = first
first->pprev = &n->next 等同於 first -> pprev = & first
n->pprev = &n
pprev 在這邊的物理意義等於指向自己位址的指標
所以下面的 if (!n->pprev) goto bail;
意思是 如果指向自己的指標為 null (即自己為空)
那麼就跳至最後面處理

上述可以在 leetcode代換程式碼發現結果不變 , 但我也不能百分百肯定是不是這樣,因為覺得這樣 pprev 變得很奇怪?

by修課同學 Haoyu

如果我的認知沒錯的話,indirect pointer 應該是用來儲存某個「指標的地址」,而這邊的 **prev 就應該是用來儲存「前一個節點的 next 指標的地址」。

但這邊的 first 是一個指向下個節點的指標,即使在 n->next = first 後,也只是這兩個指標指向相同的地址(儲存的值都是下個節點的地址),若是對 first 取址的話應該會得到 first 這個區域變數的地址,所以 &first == &n->next 應該不會成立。

若在這個認知上去思考 if (!n->pprev) 成立的情境的話,應該是代表前一個節點的 next 的地址為 NULL,或是 pprev 被手動指向 NULL,但我想不通正常操作下什麼時候會發生這個情況。

而我在 LeetCode 測試時把那行 if (...) goto ... 移除後結果也是 Accepted。

我的理解是 **pprev 變數名稱看起來的確是應該用來儲存「前一個節點的 next 指標的地址」
first 指向的是串列的首個節點 *first = h->first
n->next = first 就是把 原本串列的首個節點接在 n 這個節點的後面
if (first) 表示串列的首個節點是否存在 , 存在的話
first->pprev 指向 (指向 n->next 的位址)
而上面才剛修改過 n-> nextfirst
所以 first -> pprev 會指向 指向 first 的位址
以上為根據程式碼判斷的結論
看起來是我們對於 first 的想法不太一樣?
如果我對程式理解有誤 麻煩在幫我指出哪裡有錯誤

首先,我看不太懂你的敘述內容且 ** 造成 Markdown 格式問題,所以我對你的內文做了些調整。

再來是我實際寫了程式測試了在進行 new->next = first&first == &n->next 是否會成立:

#include <stdint.h> #include <stdio.h> #include <stdlib.h> #define print_ptr(p) \ ({ \ printf("%d:Pointer %s\n", __LINE__, #p); \ printf("\tAddress = %p\n", &p); \ printf("\t Value = %p\n\n", p); \ }) #define print_ind_ptr(p) \ ({ \ printf("%d:Indirect Pointer %s\n", __LINE__, #p); \ printf("\tAddress = %p\n", &p); \ printf("\t Value = %p\n", p); \ printf("\t Target = %p\n\n", *p); \ }) typedef struct NODE { struct NODE **pprev, *next; } hlist_node; typedef struct HEAD { hlist_node *first; } hlist_head; int main(int argc, char const *argv[]) { hlist_head *head = &(hlist_head){ .first = &(hlist_node){ .pprev = &head->first, .next = NULL, }, }; hlist_node *first = head->first; hlist_node *new = &(hlist_node){.pprev = NULL, .next = NULL}; print_ptr(head); print_ptr(head->first); print_ptr(first); print_ptr(new); new->next = first; print_ptr(first); print_ptr(new->next); if (first) { first->pprev = &new->next; print_ind_ptr(first->pprev); } head->first = new; new->pprev = &head->first; // end return 0; }

測試結果:

$ gcc indirect.c && ./a.out
41:Pointer head
        Address = 0x7ffd4e7ac880
          Value = 0x7ffd4e7ac888

42:Pointer head->first
        Address = 0x7ffd4e7ac888
          Value = 0x7ffd4e7ac8a0

43:Pointer first
        Address = 0x7ffd4e7ac890
          Value = 0x7ffd4e7ac8a0

44:Pointer new
        Address = 0x7ffd4e7ac898
          Value = 0x7ffd4e7ac8b0

47:Pointer first
        Address = 0x7ffd4e7ac890
          Value = 0x7ffd4e7ac8a0

48:Pointer new->next
        Address = 0x7ffd4e7ac8b8
          Value = 0x7ffd4e7ac8a0

51:Indirect Pointer first->pprev
        Address = 0x7ffd4e7ac8a0
          Value = 0x7ffd4e7ac8b8
         Target = 0x7ffd4e7ac8a0

可以看到在 46 行結束後,指標 first 指向的地址(變數 first 儲存的值)與 new->next 指向的地址(變數 new->next 的值)相同,但 first 的地址(&first)與 new->next 的地址(&new->next)明顯不同。

清除雜湊表

void map_deinit(map_t *map)
{
    if (!map)
        return;

    // 依序檢查雜湊表中的各個欄位
    for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
        struct hlist_head *head = &map->ht[i];

        // 依序走訪欄位中所有節點,並釋放它們佔用的資源
        for (struct hlist_node *p = head->first; p;) {
            struct hash_key *kn = container_of(p, struct hash_key, node);

            // n 保存目前節點的地址,p 則移至下一個節點
            struct hlist_node *n = p;
            p = p->next;

            if (!n->pprev) /* unhashed */
                goto bail;

            // 將當前節點 n 移出當前欄位
            struct hlist_node *next = n->next, **pprev = n->pprev;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

            // 釋放節點 n 的資料以及節點本身佔用的資源
        bail:
            free(kn->data);
            free(kn);
        }
    }
    free(map);
}

TODO : if (!n->pprev) goto bail; 用途

使用雜湊表完成 Two Sum

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    map_t *map = map_init(10);
    *returnSize = 0;


    int *ret = malloc(sizeof(int) * 2);
    if (!ret)
        goto bail;  // 無法分配空間給答案

    /**
     * @brief 利用雜湊表紀錄已看過得數值以及它們的 index
     *
     * 由於目標是要找到 num 與 k 使得 num + k == target
     * 因此檢查到數列 nums 中的數值 num 時
     * 就檢查雜湊表中是否有 key 為 k 的數值存在
     *
     *  Case 1. k 不存在
     *
     *      將 num 作為 key、index 作為 data 新增至雜湊表
     *      若之後遇到另一數 k 時就會因 num 存在而找到解
     *
     *  Case 2. k 存在
     *
     *      代表 k 有在數列 nums 中
     *      因此 k 的節點的資料 *p(代表 k 所在的 index)取出
     *      接著再將 *p 以及當前 index i 作為答案回傳
     *
     */
    for (int i = 0; i < numsSize; i++) {
        // 若雜湊表中有 key 為 k 的節點存在,則 p 不為 NULL
        int *p = map_get(map, target - nums[i]);

        // k 在雜湊表中
        if (p) {
            ret[0] = i, ret[1] = *p;
            *returnSize = 2;
            break;
        }

        // k 不在雜湊表中,將 num (nums[i]) 以及其 index i 加入雜湊表
        p = malloc(sizeof(int));
        *p = i;
        map_add(map, nums[i], p);
    }

bail:
    map_deinit(map);
    return ret;
}

Linux 核心 Hash Table 的設計和實作手法

hlist_head 以及 hlist_node

include/linux/types.h 中有定義 hlist_head 以及 hlist_node 兩個結構體:

struct hlist_head {
	struct hlist_node *first;
};

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

與 Linux Kernel Linked List API 相比:

  • 相似處
    • 結構體內都只有定義指向串列節點的指標,應該與 list_head 的設計相似,是為了能夠方便擴充。
    • 都是用雙向鏈結串列在節點間移動。
  • 不同處
    • 雜湊表多了 hlist_head 作為欄位,而每個欄位都透過 first 指向各自的鏈結串列,是透過 Chaining 的方式來處理 Collision。
    • 前述的 Chaining List 是非環狀的雙向鏈結串列,且 pprev 並不是單純指向前一個節點。(使用 indirect pointer 的設計可以參考 第二週的討論
    • 雜湊表的欄位數 (hlist_head 數量) 在宣告時就決定了(宣告成陣列的形式)。

Hash Table 相關實作

hlist_head 以及 hlist_node 相關基本操作的函式以及巨集則是定義在 include/linux/hashtable.h 以及 include/linux/list.h 中。

  • DECLARE_HASHTABLE(name, bits)
    • 宣告一個有
      2bits
      個欄位的雜湊表
  • hash_init(table)
  • hash_add_head(head, node, key)
    • 新增資料到對應的欄位中
    • 也有 add_before, add_behind 等變化。
    • 比較特別的是 hlist_add_fake 這個函式,不會新增 node 到雜湊表中,只會將 node->pprev 指向 &node->next。整個 linux 專案包含定義只出現四次,不確定實際用途但似乎與檔案系統有關
  • hash_del(node)
    • 將指定節點從它所在的 Chaining List 中移除。
    • 若要 unhash(將 pprev 以及 next 指向 NULL)這個 node,則需要使用 hlist_del_init
  • hlist_unhashed(node)
    • 檢查 node 是否已被 unhashed。
  • hlist_move_list(new_head, old_head)
    • old_head 的 Chaining List 取代 new_head 的 Chaining List,並移除 old_headfirst
  • hlist_for_each 系列巨集
    • list_for_each 系列相似,用來走訪 Chaining List,也有 entry 以及 safe 版。
    • hlist_for_each_entry_from
      • 從 Chaining List 的指定節點開始走訪剩下的節點,而不是從 head->first 開始。
    • hlist_for_each_entry_continue
      • hlist_for_each_entry_from 相似,但是從指定節點的下一個節點開始繼續走訪。

TODO

  1. RCU 是什麼
  2. GOLDEN_RATIO_PRIME

第二題 - LeetCode 82. Remove Duplicates from Sorted List II

這題的目標是將一個已排序過的 Singly-linked List 中重複的節點移除,需要注意的部份是:

  • 串列可能為空或 NULL
  • 所有重複出現的節點皆要移除,而不是只留下一個使其不重複出現

遞迴版

#include <stddef.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode *deleteDuplicates(struct ListNode *head) { if (!head) return NULL; if (COND1) { /* Remove all duplicate numbers */ while (COND2) head = head->next; return deleteDuplicates(head->next); } head->next = deleteDuplicates(head->next); return head; }

在這個程式碼中,可以發現被 if 分成了三個部份,且這三個部份的的最後皆以 return 結束,分別代表了以下三種情況:

  1. 輸入的 headNULL
  2. 當 1 不成立且 COND1 成立時
  3. 非上述兩種情況時

第一個部份是為了處理原串列為 NULL 以及遞迴呼叫到串列尾端時的遞迴終止條件。

第二個部份則是為了處理 headhead->next 兩節點資料相同的情況,所以 COND1 應該是 head->val == head->next->val,但這邊有個陷阱是 head->next->val 若是在 head->next == NULL 時會出問題,所以必須先檢查 head->next != NULL,因此正確的 COND1 應為:

head->next && head->val == head->next->val

而進入第二部份的 if 之後則是透過 while 迴圈跳過所有連續重複資料的節點,所以當目前指向的節點 head 的資料與其下一個節點 head->next 的資料相同時就要跳過目前節點,因此 COND2 應該是 head->val == head->next->val。同樣的,這邊也有個陷阱是當串列走到尾端時, head->next 會是 NULL,因此這邊也必須先檢查 head->next != NULL,所以正確的 COND2 應和 COND1 相同,皆為:

head->next && head->val == head->next->val

而在 while 迴圈結束後(即 head->next == NULL || head->val != head->next->val ),就需要再次透過遞迴呼叫 deleteDuplicates 來找到剩餘串列中部重複的節點,但由於 head 也是重複的節點,所以傳入 deleteDuplicates 的參數應為 head->next 才對。

而最後的第三部份則因為 COND1 確保了 head 的資料不與其他節點重複,所以只需要透過 deleteDuplicates 找出 head->next 要接到哪個節點,最後再回傳 head 即可。

迭代版

struct ListNode* deleteDuplicates(struct ListNode* head){ if (!head) return NULL; bool found = false; for (struct ListNode **ptr = &head; *ptr;) { // same val if ((*ptr)->next && (*ptr)->val == (*ptr)->next->val) { *ptr = (*ptr)->next; found = true; } else { // don't forget to rm last repeated node if (found) *ptr = (*ptr)->next; else ptr = &(*ptr)->next; found = false; } } return head; }

這個迭代的實作參考了你所不知道的 C 語言: linked list 和非連續記憶體中提到的有品味的移除節點的操作,使用了 ListNode 的指標的指標來避免額外判斷當前節點是否為 head

增加一個 bool 變數以簡化程式碼

struct ListNode* deleteDuplicates(struct ListNode* head){
    
    if (!head)
        return NULL;
    
    bool prev = false, found = false;
    for (struct ListNode **ptr = &head; *ptr; prev = found) {    
        
        found = (*ptr)->next && (*ptr)->val == (*ptr)->next->val;
        
        if (found || prev)
            *ptr = (*ptr)->next;
        else 
            ptr = &(*ptr)->next;
    }
    return head;
}

透過分別使用 prev 以及 found 來紀錄上一個節點以及目前節點的比較結果,這能讓原本程式碼中第 16 行的 if 與第 10 行的 if 合併。

Circular Doubly-linked List 版

與 lab0-c 中要實作的 function q_delete_dup 相似,但可以不用刪除節點資料,且儲存的資料型態為 int 而不是 char *

迭代版

主要函式
bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;

    LIST_HEAD(duplist);

    bool prev = false;
    element_t *ptr = list_entry(head->next, element_t, list), *next = ptr;

    for (bool same; next->list.next != head; ptr = next) {
        next = list_entry(ptr->list.next, element_t, list);
        same = ptr->value == next->value;
        if (same || prev)
            list_move(&ptr->list, &duplist);
        prev = same;
    }

    // don't forget last node
    if (prev)
        list_move(&ptr->list, &duplist);

    return true;
}
轉成雙向鏈結
typedef struct ListNode Node; struct ListNode *deleteDuplicates(struct ListNode *head) { if (!head) return NULL; // build doubly-linked list struct list_head doubly; INIT_LIST_HEAD(&doubly); for (Node *ptr = head; ptr; ptr = ptr->next) { element_t *e = malloc(sizeof(element_t)); e->value = ptr->val; e->list.next = NULL; list_add_tail(&e->list, &doubly); } q_delete_dup(&doubly); // back to singly Node *new = NULL, **pnew = &new; element_t *ptr; list_for_each_entry (ptr, &doubly, list) { Node *n = malloc(sizeof(Node)); n->val = ptr->value; n->next = NULL; *pnew = n; pnew = &(*pnew)->next; } return new; }

如果第 23 行的 *new 不初始化成 NULL 的話,可能在 doubly 的元素皆被移除時(例如輸入串列為 [1,1] 時)跳出以下錯誤:

Line 70: Char 15: runtime error: member access within misaligned address 0x000041b58ab3 for type 'struct ListNode', which requires 8 byte alignment [ListNode.c]
0x000041b58ab3: note: pointer points here
<memory cannot be printed>

遞迴版

主要函式
typedef struct ListNode Node;

#define assign_and_cmp(ptr, next, p_ptr_entry, p_next_entry) \
    ({                                                       \
        p_ptr_entry = list_entry(ptr, element_t, list);      \
        p_next_entry = list_entry(next, element_t, list);    \
        p_ptr_entry->value == p_next_entry->value;           \
    })

struct list_head *q_delete_dup(struct list_head *head)
{
    if (!head)
        return NULL;

    element_t *ptr, *next;
    if (head->next && assign_and_cmp(head, head->next, ptr, next)) {
        while (head->next && assign_and_cmp(head, head->next, ptr, next))
            head = head->next;
        return q_delete_dup(head->next);
    }

    head->next = q_delete_dup(head->next);
    if (head->next)
        head->next->prev = head;
    return head;
}

list_head 當作 Singly-linked List 操作,並透過定義巨集讓函式能直接沿用 Singly-linked List 的遞迴函式的結構,只需要額外宣告變數來存取 element_t 的資訊,以及要額外處理 prev 連結。

轉成雙向鏈結
struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    // build doubly-linked list
    struct list_head doubly;
    INIT_LIST_HEAD(&doubly);

    for (Node *ptr = head; ptr; ptr = ptr->next) {
        element_t *e = malloc(sizeof(element_t));
        e->value = ptr->val;
        e->list.next = NULL;

        list_add_tail(&e->list, &doubly);
    }

    // break circular
    doubly.prev->next = NULL;

    // head do not contain data, start from first node
    doubly.next = q_delete_dup(doubly.next);
    if (doubly.next)
        doubly.next->prev = &doubly;

    // make circular
    struct list_head *ptr;
    for (ptr = &doubly; ptr->next; ptr = ptr->next)
        ;
    ptr->next = &doubly;
    doubly.prev = ptr;

    // back to singly
    Node *new = NULL, **pnew = &new;

    list_for_each (ptr, &doubly) {
        element_t *entry = list_entry(ptr, element_t, list);
        Node *n = malloc(sizeof(Node));
        n->val = entry->value;
        n->next = NULL;

        *pnew = n;
        pnew = &(*pnew)->next;
    }

    return new;
}

大致上與迭代版本的相同,但差在由於這邊的遞迴版是沿用單向的遞迴的函式,因此在檢查條件時也是沿用 !head 以及 head->next ,所以這邊要先把最後一個節點的 next 指向 NULL,讓串列變成非環狀串列,並以首位節點作為開頭進行 q_delete_dup,然後在結束時還需要讓串列變回環狀。

測試函式

由於 deleteDuplicates 是有被規定的,因此不論是遞迴還是迭代版都可以用相同函式測試 deleteDuplicates

int main(int argc, char const *argv[])
{
    Node *head, **phead = &head;

    int vals[] = {1, 1};

    for (int i = 0; i < (sizeof(vals) / sizeof(vals[0])); ++i) {
        Node *n = malloc(sizeof(Node));
        n->val = vals[i];
        n->next = NULL;

        *phead = n;
        phead = &(*phead)->next;
    }

    deleteDuplicates(head);
    return 0;
}


第三題 - LeetCode 146. LRU Cache

說明

建立 LRU 快取

LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *cache;

    // 利用 GNU C Extension 建立可變大小的 LRUCache 結構體物件
    // REF : https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
    cache = malloc(sizeof(LRUCache) + capacity * sizeof(struct list_head));
    cache->capacity = capacity;
    cache->count = 0;

    // 初始化 dhead 以及雜湊表
    INIT_LIST_HEAD(&cache->dhead);
    for (int i = 0; i < capacity; ++i)
        INIT_LIST_HEAD(&cache->hheads[i]);
    return cache;
}

新增資料 (MMM3, MMM4)

/**
 * @brief 新增一資料 (key,value) 到快取中
 *
 * TRICK :
 *  新增的資料並非放到原 LRU 節點所在的欄位
 *  實際上與雜湊表概念相同
 *  是將資料放在第 HASH(key) 個欄位
 *  而實際的 Cache 存取紀錄則是由 LRUCache 的 dhead 管理
 *  透過使用雜湊表 hhead 搭配「額外的」環狀雙向鏈結串列 dhead
 *
 *  - 新增資料:
 *      - 加入(資料不存在,Cache 未滿):
 *          1. 計算 HASH(key) 並將資料加入雜湊表
 *          2. 將該節點加入到 dhead 串列
 *
 *      - 取代(資料不存在,Cache 已滿):
 *          1. 將 LRU 從 hhead 中移除
 *          2. 將 LRU 從 dhead 中移除
 *          3. 計算 HASH(key) 並將新資料加到雜湊表
 *          4. 將新資料的節點加到 dhead 串列
 *
 *      - 更新(資料存在):
 *          1. 從雜湊表中尋找該資料的節點
 *          2. 將該節點提昇至 dhead 首位(移除再加入)
 *
 *  - 取得資料:
 *      1. 從雜湊表中尋找該資料的節點
 *      2. 若有找到該資料則將該節點提昇至 dhead 首位
 *      3. 回傳節點
 *
 * @param cache LRUCache 物件的地址
 * @param key 欲新增資料的 key
 * @param value 欲新增資料的 value
 */
void lRUCachePut(LRUCache *cache, int key, int value)
{
    int hash = HASH(key, cache);
    LRUNode *node, *next;

    // MMM3, 只是 move 不需要使用到 safe
    list_for_each_entry (node, &cache->hheads[hash], hlink) {
        if (node->key == key) {
            // 更新該 key 的 value
            node->value = value;
            // 提昇至 dhead 首位
            list_move(&node->dlink, &cache->dhead);
            return;
        }
    }

    // 未滿,直接新增節點
    if (cache->count < cache->capacity) {
        node = malloc(sizeof(LRUNode));
        ++cache->count;
    }

    // 已滿,移除 dhead 中的 LRU
    else {
        // MMM4
        node = list_last_entry(&cache->dhead, LRUNode, dlink);
        list_del(&node->dlink);
        list_del(&node->hlink);
    }

    // 分別將資料加入到雜湊表以及 dhead
    node->key = key;
    node->value = value;
    list_add(&node->dlink, &cache->dhead);
    list_add(&node->hlink, &cache->hheads[hash]);
}

MMM4 的部份可能是答案錯了,能夠賦值的巨集應該是 list_entry, list_first_entry 或是 list_last_entry,而這邊因為是要獲取 LRU 所以要找的節點應該是 dhead->prev,所以答案應為 list_last_entry 才正確。

取得資料 (MMM2)

/**
 * @brief 從 LRU Cache 取得資料
 *
 * 透過 HASH(key) 計算出雜湊表的欄位索引
 * 接著到該欄位尋找目標的 key
 * 而不是走訪 dhead 中所有節點尋找 key
 *
 * @param cache
 * @param key
 * @return int
 */
int lRUCacheGet(LRUCache *cache, int key)
{
    LRUNode *node;
    // MMM2
    list_for_each_entry (node, &cache->hheads[HASH(key, cache)], hlink)
        if (node->key == key) {
            list_move(&node->dlink, &cache->dhead);
            return node->value;
        }
    return -1;
}

清除快取 (MMM1)

/**
 * @brief 清除 LRU Cache
 *
 * 雖然快取紀錄是由 dhead 管理
 * 但 LRUNode 同時包含 dlink 以及 hlink
 * 分別用來指向 dhead 及 hhead 的前後節點
 * 因此實際上 dhead 中的節點與 hhead 中的節點相同
 * 只須刪除一邊的節點即可
 *
 * @param cache
 */
void lRUCacheFree(LRUCache *cache)
{
    LRUNode *node, *next;
    // MMM 1
    list_for_each_entry_safe (node, next, &cache->dhead, dlink) {
        list_del(&node->dlink);
        free(node);
    }
    free(cache);
}

測試程式

static inline void GET_AND_SHOW(LRUCache *cache, int key)
{
    int value = lRUCacheGet(cache, key);
    printf("GET (%d,%d)\n", key, value);
}

int main(int argc, char const *argv[])
{
    LRUCache *cache = lRUCacheCreate(2);

    lRUCachePut(cache, 1, 1);
    lRUCachePut(cache, 1, 1);

    GET_AND_SHOW(cache, 1);
    lRUCachePut(cache, 3, 3);
    GET_AND_SHOW(cache, 2);
    lRUCachePut(cache, 4, 4);
    GET_AND_SHOW(cache, 1);
    GET_AND_SHOW(cache, 3);
    GET_AND_SHOW(cache, 4);

    lRUCacheFree(cache);
    return 0;
}

可改進部份

TODO

探討 Linux 核心中 LRU 相關程式碼


第四題 - LeetCode 128. Longest Consecutive Sequence

說明

尋找雜湊表中是否包含某數

/**
 * @brief 找出雜湊表中包含某個數值的節點
 *
 * 會先對 @num 取絕對值並計算出該數所屬的欄位
 * 接著在走訪該欄位、檢查是否包含此數
 *
 * @param num 目標數值
 * @param size 雜湊表大小(有幾個欄位)
 * @param heads 雜湊表
 * @return struct seq_node*
 */
static struct seq_node *find(int num, int size, struct list_head *heads)
{
    struct seq_node *node;
    int hash = num < 0 ? -num % size : num % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (node->num == num)
            return node;
    }
    return NULL;
}

尋找最長連續數列長度

int longestConsecutive(int *nums, int n_size) { // 建立並初始化雜湊表 struct list_head *heads = malloc(n_size * sizeof(*heads)); for (int i = 0; i < n_size; i++) INIT_LIST_HEAD(&heads[i]); // 將每個數字放入雜湊表 struct seq_node *node; for (int i = 0, hash; i < n_size; i++) { // 跳過重複數字 if (!find(nums[i], n_size, heads)) { // 使用 modulo 作為雜湊函數,將數字取絕對值計算後放入雜湊表 hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size; node = malloc(sizeof(*node)); node->num = nums[i]; list_add(&node->link, &heads[hash]); } } int global = 0; for (int i = 0, num; i < n_size; i++) { /** * @brief 尋找最長的連續數列 (global 代表目前找到最長的數列長度) * * Step 1. 檢查當前數字是否在雜湊表中 * * Y : 跳至 Step 2 * N : 跳至 Step 4 * * Step 2. 開始尋找包含此數(num)的連續數列 (local 代表此連續數列長度) * * 2-1 : 將此數移出雜湊表並將 local + 1 * * 2-2 : 從 num 開始向下尋找最多有幾個相鄰整數 (k>0) * * 2-2-1 : 尋找雜湊表中是否包含 num-k * Y : ++local, ++k, 將 num-k 從雜湊表中移除 * N : 結束此迴圈 * * 2-3 : 類似 2-2,但是從 num+1 往上找 * * Step 3. 如果 local 較大的話就更新 global * * Step 4. 如果尚未檢查到最後一個數字的話就回到 Step 1 * * TRICK : * 由於雜湊表不包含重複數字且在 Step 2 找連續數字時會將找到的數字移除 * 所以即使 nums 中包含連續或重複數字也只有第一次遇到時會進入第二個迴圈 * 之後遇到該群連續數列時就只需要檢查雜湊表是否包含該數而已 * 因此運作起來會像是在計算每群連續數列的長度 */ int local = 0; if (node = find(nums[i], n_size, heads)) { local++; num = node->num; list_del(&node->link); // 從 num-1 向下,因 num 已取出且每次找到應將 left 遞減,故 --left for (int left = num; (node = find(--left, n_size, heads));) { local++; list_del(&node->link); } // 從 num+1 向上,因 num 已取出且每次找到應將 right 遞增,故 ++right for (int right = num; (node = find(++right, n_size, heads));) { local++; list_del(&node->link); } global = local > global ? local : global; } } return global; }

測試程式

TODO

可改進部份

while(node) 可改用 if

第 56 列的 if 原本是 while(node),但是在第 68 列的迴圈結束條件為 node 被賦予 NULL 時,因此實際上 while 只會執行一次,可用 if 替代。

while 迴圈可改用 for 迴圈使程式碼更精簡

leftright 只會分別在各自的 while 迴圈中使用到,因此可利用 for 迴圈進行宣告,使得程式碼更加簡短並縮短 left 以及 right 的生命週期。

len 以及 length 兩變數名稱有相近含意

原先的 len 是用來表示 Step 2 中找到的連續數列的長度,而 length 則是代表目前找到的最長連續數列的長度,兩個變數名稱相近可能會造成混淆,因此將 length 以及 len 分別以 global 以及 local 進行替換。

Linux 核心風格的 hash table 重新實作

TODO