---
tags: linux2022
---

# 2022q1 Homework1 (quiz1)
contributed by < `hsuedw` >
* [作業需求](https://hackmd.io/@sysprog/B166rc3Jq)
* [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz1)
* [作業繳交區](https://hackmd.io/@sysprog/linux2022-homework1)

---

# [測驗 1](https://hackmd.io/@sysprog/linux2022-quiz1#%E6%B8%AC%E9%A9%97-1)

* [LeetCode 1. Two Sum](https://leetcode.com/problems/two-sum/)

## 作答

* AAA = `n->next = first`
* BBB = `n->pprev = &h->first`

## 延伸題目: 1. 解釋上述程式碼運作原理

為了說明方便，將程式碼還原如下所示。

#include <stddef.h>
#include <stdlib.h>

struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
typedef struct { int bits; struct hlist_head *ht; } map_t;

#define MAP_HASH_SIZE(bits) (1 << bits)

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

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

#define container_of(ptr, type, member)               \
    ({                                                \
        void *__mptr = (void *) (ptr);                \
        ((type *) (__mptr - offsetof(type, member))); \
    })

#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits) {
    /* High bits are more random, so use them. */
    return (val * GOLDEN_RATIO_32) >> (32 - bits);
}

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

void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}

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;  // AAA
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first; // BBB
}

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);
            struct hlist_node *n = p;
            p = p->next;

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

            struct hlist_node *next = n->next, **pprev = n->pprev;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

        bail:
            free(kn->data);
            free(kn);
        }
    }
    free(map);
}

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;

    for (int i = 0; i < numsSize; i++) {
        int *p = map_get(map, target - nums[i]);
        if (p) { /* found */
            ret[0] = i, ret[1] = *p;
            *returnSize = 2;
            break;
        }

        p = malloc(sizeof(int));
        *p = i;
        map_add(map, nums[i], p);
    }

bail:
    map_deinit(map);
    return ret;
}

### `map_init()` (第 10~25 行)

* `map_init()` 會為 hash table 配置記憶體空間，並對 hash table 做初始化。 `map_init()` 完成後，會產生如下圖所示的 object。
* 若配置成功 (第 18~19 行) ，則對hash table 中的每個 bucket 逐一設為 `NULL` ()。
* 若 hash table 的記憶體空間配置失敗 (第 11~13 行) ，或對 bucket 的記憶體空間配置失敗 (第 16 行與第 21~23 行)，則傳回NULL。否則傳回指向 hash table 的指標。

### `map_add()` (第 61~77 行)

* 假設目前 hash table 的狀況如下圖所示。
* 新的資料節點在第 72~76 行間被插入 hash table 中。

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

* 狀況 1: 有碰撞。
* 假設新插入 hash table 的資料節點的 `key` 經 `hash()` 計算後，所對應到的 bucket 不為 empty。也就是有發生碰撞發生。
* 在此假設新要插入的 bucket 為 `ht[1]` 所指向的非環狀雙向鏈結串列。則 `kn` 指標所指向的新節點會會成為此非環狀雙向鏈結串列的第一個節點。
* 插入新節點的過程如下圖所示。
* 狀況 2: 沒有碰撞。
* 假設新插入 hash table 的資料節點的 `key` 經 `hash()` 計算後，所對應到的 bucket 為 empty。也就是沒有發生碰撞發生。
* 在此假設新要插入的 bucket 為 `ht[2]` 所指向的非環狀雙向鏈結串列。
* 插入新節點的過程如下圖所示。

### `map_get()` 與 `find_key()` (第 45~59 行)

* `map_get()` 經由 `find_key()` 的協助，在 hash table 中尋找與 `key` 相吻合的資料節點 ( `struct hash_key` 型別的 object )。若有找到，則傳回該資料節點中表示資料的 object。否則傳回 NULL。
* 在 `find_key()` 中，經 `hash()` 計算得到 `key` 的雜湊值。也就是找到可能具有 `key` 這個資料節點的 bucket。然後，在第 47~51 行的 `for` 迴圈中，會在此 bucket (即 `ht[k]->first` 所指向的非環狀雙向鏈結串列)中搜尋具有 `key` 的資料節點。若有找到，則返回此資料節點。否則，返回NULL。

### `map_deinit()` (第 79~106 行)

* 釋放 hash table 中，所有 object 所佔用的記憶體空間。

## 延伸題目: 2. 研讀 Linux 核心原始程式碼 [include/linux/hashtable.h](https://github.com/torvalds/linux/blob/master/include/linux/hashtable.h) 及對應的文件 [How does the kernel implements Hashtables?](https://kernelnewbies.org/FAQ/Hashtables)，解釋 hash table 的設計和實作手法，並留意到 [tools/include/linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 的 `GOLDEN_RATIO_PRIME`，探討其實作考量
* 乘法運算子為二元運算子 (binary operator)，也就是有兩個運算元 (operand) 。若有一個運算元為變數，另一個為常數，那麼就可以用 bitwise left shift 與減法得到乘法的效果，而不必真的動用到硬體的乘法指令。
* 以 `x * 14` 這個 C 語言運算式為例。 因為 $14_{10} = 1110_{2}$ ，所以可以把 `x * 14` 改寫為 `(x << 3) + (x << 2) + (x << 1)` 或 `(x << 4) - (x << 1)` 。

* 再看看 linux kernel 是如何計算雜湊值的。

  #ifndef HAVE_ARCH__HASH_32
  #define __hash_32 __hash_32_generic
  #endif
  static inline u32 __hash_32_generic(u32 val)
  {
      return val * GOLDEN_RATIO_32;
  }

  static inline u32 hash_32(u32 val, unsigned int bits)
  {
      /* High bits are more random, so use them. */
      return __hash_32(val) >> (32 - bits);
  }

  #ifndef HAVE_ARCH_HASH_64
  #define hash_64 hash_64_generic
  #endif
  static __always_inline u32 hash_64_generic(u64 val, unsigned int bits)
  {
  #if BITS_PER_LONG == 64
      /* 64x64-bit multiply is efficient on all 64-bit processors */
      return val * GOLDEN_RATIO_64 >> (64 - bits);
  #else
      /* Hash 64 bits using only 32x32-bit multiply. */
      return hash_32((u32)val ^ __hash_32(val >> 32), bits);
  #endif
  }

請注意第 6 行與第 22 行。這兩行說明了在計算雜湊值的過程中，==會用到一個變數乘以一個常數的運算==。
* 根據 [[PATCH v3 05/10] Eliminate bad hash multipliers from hash_32() and hash_64()](https://lore.kernel.org/lkml/[e-mail]/)，早期的 `GOLDEN_RATIO_PRIME` 的定義如下:

  /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
  #define GOLDEN_RATIO_PRIME_32 0x9e370001UL
  /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
  #define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL

而目前的 `GOLDEN_RATIO_PRIME` 的定義如下:

   #define GOLDEN_RATIO_32 0x61C88647
   #define GOLDEN_RATIO_64 0x61C8864680B583EBull

以 `GOLDEN_RATIO_PRIME_32` 做說明。原本的定義中，bit 1 ~ bit 15 全部為 0。如果變數 `val` 的值的二進位中為 1 的 bit 集中在這個範圍內，那麼計算出來的雜湊值就會很接近，而造成碰撞發生的機會大增。原本的 `GOLDEN_RATIO_PRIME_64` 也有相同問題。
所以，目前的 `GOLDEN_RATIO_32` 與 `GOLDEN_RATIO_64` 分別定義為 `0x61C88647` 與 `0x61C8864680B583EBull` 讓 0 與 1 交錯地均勻分布。這樣一來，計算出來的雜湊值發生碰撞的機會就會下降。

---

# [測驗 2](https://hackmd.io/@sysprog/linux2022-quiz1#%E6%B8%AC%E9%A9%97-2)

## 題目

* [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/lru-cache/)

#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;
}

## 作答

COND1 = ``` head->next && head->val == head->next->val ```
COND1 = ```head->next && head->val == head->next->val```

## 延伸問題: 1. 嘗試避免遞迴，寫出同樣作用的程式碼

* 不是很簡潔。再想想。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *deleteDuplicates(struct ListNode* head)
{
    if (!head || !head->next)
        return head;
    
    struct ListNode *dummy = malloc(sizeof(struct ListNode));
    struct ListNode *prev = NULL, *node = dummy, *next = head;
    bool is_dup = false;
    
    dummy->next = head;
    dummy->val = 1000;
    
    while (node && next) {
        while (node && next && node->val == next->val) {
            struct ListNode *x = next;
            node->next = next->next;
            next = next->next;
            free(x);
            is_dup = true;
        }
        
        if (is_dup) {
            struct ListNode *x = node;
            prev->next = node->next;
            node = node->next;
            if (next)
                next = next->next;
            free(x);
            is_dup = false;
        } else {
            prev = node;
            node = node->next;
            next = next->next;           
        }

    }
    
    head = dummy->next;
    free(dummy);
    
    return head;
}

## 延伸問題: 2. 以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼

* 迭代 (iterative)

struct list_head *q_delete_dup_iter(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return head;

    struct list_head *prev = head->next, *node = head->next->next;
    bool dup_flag = false;

    while (prev != head && node != head) {
        element_t *prev_element = list_entry(prev, element_t, list);
        element_t *node_element = list_entry(node, element_t, list);

        while (node != head &&
               strcmp(prev_element->value, node_element->value) == 0) {
            dup_flag = true;
            list_del(node);
            q_release_element(node_element);
            node = prev->next;
            node_element = list_entry(node, element_t, list);
        }

        if (dup_flag) {
            dup_flag = false;
            list_del(prev);
            q_release_element(prev_element);
        }

        prev = node;
        node = node->next;
    }

    return head;
}

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;

    q_delete_dup_iter(head);

    return true;
}

* 遞迴
* 尚未完成

struct list_head *q_delete_dup_rec(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return head;

    if (!list_is_singular(head) && strcmp(list_entry(head, element_t, list)->value, list_entry(head->next, element_t, list)->value) == 0) {
        while (!list_is_singular(head) && strcmp(list_entry(head, element_t, list)->value, list_entry(head->next, element_t, list)->value) == 0) {
            struct list_head *x = head;
            head = q_delete_dup_rec(head->next);
            list_del(x);
            //free(x);
            return head;
        }
    }
    head->next = q_delete_dup_rec(head->next);
    return head;

}

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;

    q_delete_dup_rec(head);

    return true;
}

---

# 測驗 3

## 題目

* [LeetCode 146. LRU Cache](https://leetcode.com/problems/lru-cache/)

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

LRUCache *lRUCacheCreate(int capacity)
{   
    LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
    obj->count = 0;
    obj->capacity = capacity;
    INIT_LIST_HEAD(&obj->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_LIST_HEAD(&obj->hheads[i]);
    return obj;
}
    
void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    MMM1 (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}   

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM2 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM3 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }

    if (obj->count == obj->capacity) {
        lru = MMM4(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        lru = malloc(sizeof(LRUNode));
        obj->count++;
    }
    lru->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}

## 作答

* `MMM1` = `list_for_each_entry_safe`
* `MMM2` = `list_for_each_entry`
* `MMM3` = `list_for_each_entry`
* `MMM4` = `list_last_entry`

:::success
延伸問題:

- [x] 1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
- [ ] 2. 在 Linux 核心找出 LRU 相關程式碼並探討
:::

## 延伸問題: 1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作

* 資料結構(LRUCache, LRUNode)

* `LRUCache` 是描述 cache 的資料結構。
* `capacity` 為 LRU cache 能容納的節點數。
* `count` 為目前 LRU cache 內的節點數目。當 count 等於 capacity 時，表示 LRU cache 已滿。
* `LRUNode` 是描述 cache 中資料節點的資料結構。
* `key` 與 `value` 為資料節點的 key 與 value。

  typedef struct {
      int capacity, count;             
      struct list_head dhead, hheads[];
  } LRUCache;
    
  typedef struct {
      int key, value;
      struct list_head hlink, dlink;
  } LRUNode;

* `LRUCache *lRUCacheCreate(int capacity)`

  LRUCache *lRUCacheCreate(int capacity)
  {   
      LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
      obj->count = 0;
      obj->capacity = capacity;
      INIT_LIST_HEAD(&obj->dhead);
      for (int i = 0; i < capacity; i++)
          INIT_LIST_HEAD(&obj->hheads[i]);
      return obj;
  }

* `lRUCacheCreate` 會配置記憶體空間給一個型態為 `LRUCache` 的 object 並對它做初始化。 `LRUCache` 會產生如下圖所示的 object。
* `LRUCache` object 中有兩 `dhead` 與 `hhead` 兩種雙向鏈結串列。
* `dhead` 是一個以==資料節點被存取的時間序==為排列順序的雙向鏈結串列。最近被存取過的資料節點會被放在 `dhead` 所指向之雙向鏈結串列的最前端。最早被存取過的資料節點則被放在 `dhead` 所指向之雙向鏈結串列的尾端。
* `hhead` 則是一個 hash table。被插入的資料節點的 key 所對應的 hash 為 k 時，則此資料節點會被插入 `hhead[k]` 所指向的雙向鏈結串列中。
* 在 LRU cache 中的一個節點，會同時被 `dhead` 與 `hhead[k]` 所管理。


* `void lRUCachePut(LRUCache *obj, int key, int value)`

  void lRUCachePut(LRUCache *obj, int key, int value)
  {
      LRUNode *lru;
      int hash = key % obj->capacity;
      list_for_each_entry (lru, &obj->hheads[hash], hlink) {
          if (lru->key == key) {
              list_move(&lru->dlink, &obj->dhead);
              lru->value = value;
              return;
          }
      }

      if (obj->count == obj->capacity) {
          lru = list_last_entry(&obj->dhead, LRUNode, dlink);
          list_del(&lru->dlink);
          list_del(&lru->hlink);
      } else {
          lru = malloc(sizeof(LRUNode));
          obj->count++;
      }
      lru->key = key;
      list_add(&lru->dlink, &obj->dhead);
      list_add(&lru->hlink, &obj->hheads[hash]);
      lru->value = value;
  }

* 當有資料要插入 LRU cache 時，在第4行算出 `key` 的 `hash`。這裡的實作是用取餘數的方式算 hash。
* 假設 LRU cache 此時的狀況如下:
1. LRU cache 的 `capacity` 為 3。
2. 已存在的資料節點的 `key` 為 0， `value` 為 0。
3. 要插入的資料的 `key` 為 1， `value` 為 1。


* 則這筆資料會被插入 hheads[1] 所指向的雙線鏈結串列中。
* 第 18~19 行配置記憶體空間給一個型態為 `LRUNode` 的 object。並增加 LRU cache 中的節點個數 (`count`)。
* 第 22 行將新節點插入 `dhead` 所指向之雙向鏈結串列的最前端 (原本最前端的節點為 `key` = 0, `value` = 0)。
* 第 23 行將新節點插入`hhead[1]` 所指向的雙向鏈結串列的最前端 (原本為 empty)。
* 第 21 行將新節點的 `key` 更新為 1。
* 第 24 行將新節點的 `value` 更新為 1。


* 討論第二種狀況如下圖所示。再插入一個 `key` = 3, `value` = 6 的節點。


* 第 5~11 行的 `for` 迴圈會找到已存在 `hhash[0]` 所指的雙向鏈結串列中那個 `key` = 3 的節點。然後操作 `dhead` 所指向的雙向鏈結串列，將此資料節點移到此雙向鏈結串列的第一個節點，再將此節點的 `value` 更新為 6。但 `hhead[0]` 所指之雙向鏈結串列維持不動。完成狀況如下圖所示。


* 再討論第三種情況，如下圖所示。此時， LRU cache 已滿。若要再插入一個新節點 (`key` = 4, `value` = 4)。


* 則第 13 行的 `if` 條件式成立，並執行第 14~16 行。將 `dhead` 所指之雙向鏈結串列的最後一個節點 (`key` = 6, `value` = 6)自 `ddhead` 與 `hhead[0]` 雙向鏈結串列中移除(但不刪除)，並以 `lru` 指標指向此被刪除的節點。
* 接著執行第 21~24 行。
* 第此 `lru` 所指向的節點的 `key` 更新為 4。
* 將此 `lru` 所指向的節點插入 `dhead` 所指向之雙向鏈結串列的最前端。
* 然後再將此 `lru` 所指向的節點插入`hhead[1]` 所指向的雙向鏈結串列的最前端 (原本為 empty)。
* 第此 `lru` 所指向的節點的 `value` 更新為 4。
* 最後如下圖所示。

　

* 以上討論的幾種情況已涵蓋整個 `lRUCachePut()` 的主要程式碼。

* `int lRUCacheGet(LRUCache *obj, int key)`

  int lRUCacheGet(LRUCache *obj, int key)
  {
      LRUNode *lru;
      int hash = key % obj->capacity;
      list_for_each_entry (lru, &obj->hheads[hash], hlink) {
          if (lru->key == key) {
              list_move(&lru->dlink, &obj->dhead);
              return lru->value;
          }
      }
      return -1;
  }

* 假設目前 LRU cache 的狀況如下圖所示。


* 若要找的資料節點的 `key` 不為 0、3 或 6，則返回 -1。
* 若要找的資料節點的 `key` 為 6。則第 5~10 行的 `for` 迴圈會在 `hhead[0]` 所指的雙向鏈結串列中找到最後一個節點的 `key` 為 6。然後將此節點移到 `ddhead` 所指的雙向鏈結串列的第一個節點。 完成後，如下圖所示。


* `void lRUCacheFree(LRUCache *obj)`

  void lRUCacheFree(LRUCache *obj)
  {       
      LRUNode *lru, *n;
      list_for_each_entry_safe (lru, n, &obj->dhead, dlink) {
          list_del(&lru->dlink);
          free(lru);
      }
      free(obj); 
  }  

* `lRUCacheFree` 會釋放 LRU cache 所占用的記憶體空間。
* 由先前對 `lRUCachePut()` 與 `lRUCacheGet()` 的討論得知，`ddhead` 所指的雙向鏈結串列涵蓋整個 LRU cache 的所有資料節點。所以只要遍歷此雙向鏈結串，並逐一移除節點，再釋放節點記憶體空間，就可以清除所有的資料節點。這就是第 4~7 行 `for` 迴圈所做的事。
* 最後於第 8 行將 LRU cache 所占用的記憶體空間釋放掉。

## 延伸問題: 2. 在 Linux 核心找出 LRU 相關程式碼並探討

* working

---

# 測驗 4

## 題目

* [LeetCode 128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/)

  #include <stdio.h>
#include <stdlib.h>
#include "list.h"

struct seq_node {
    int num;
    struct list_head link;
};                                                                                                                                                            
            
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)
{
    int hash, length = 0;
    struct seq_node *node;
    struct list_head *heads = malloc(n_size * sizeof(*heads));

    for (int i = 0; i < n_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (int i = 0; i < n_size; i++) {
        if (!find(nums[i], n_size, heads)) {
            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]);
        }
    }

    for (int i = 0; i < n_size; i++) {
        int len = 0;
        int num;
        node = find(nums[i], n_size, heads);
        while (node) {
            len++;
            num = node->num;
            list_del(&node->link);

            int left = num, right = num;
            while ((node = find(LLL, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            while ((node = find(RRR, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        }
    }

    return length;
}

## 作答

* LLL = `--left`
* RRR = `++right`

:::success
延伸問題:

- [x] 1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
- [ ] 2. 嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼
:::

## 延伸問題: 1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作

* 題目中的程式碼是以數學上集合 (set) 的概念搭配 hash table 實作的解法。這裡的 hash talbe 是第 25 行的 `heads` 指標所指向的 object。此 hash table 可容納的節點數為 `nums` 陣列的大小。
* 第 10~19 行的 `find()` 函式負責在 hash table 中尋找指定的數值 (`nums[i]`)。若此數值存在 hash table 中，則返回該資料節點。否則，返回 NULL。
* 第 27~28 行的 `for` 迴圈對 hash table 進行初始化。假設 `nums = [100,4,1,200,1,100,3,2]` ，則初始化後的 hash table 如下圖所示。


* 第 30~37 行的 `for` 迴圈把 `nums` 陣列中的所有元素插入 hash table 中。在插入的過程中，若發現 `nums[i]` 已經存在 hash table 中，則不予插入。所以 `nums[4]` 與 `nums[5]` 會被跳過。這段程式碼完成後，hash table 的狀態如下圖所示。


* 第 39~61 行的 `for` 迴圈從頭開始逐一走訪 `nums` 陣列中的每個元素。而針對某一元素 `nums[i]`，在第 43~60 行的 `while` 迴圈中，以 `nums[i]` 為中心，在 hash table 中向左方找 `nusm[i] - 1`，向右方找 `nums[i] + 1`。
* 如上圖所示，若 `nums` 陣列中有連續數列 (consequtive sequence)，則會分布在 `nums[i]` 的左右兩邊。所以只要在 hash table 中找到連續數列中的任一元素，就可以找到其他元素。進而算出最長連續數列的長度。
* 且第 49~52 與 54~57 行的 `while` 迴圈中，會把找到的連續數列自 hash table 中移除。所以，某個連續數列的長度只會被計算一次。

## 延伸問題: 2. 嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼

* working

---

# 答案卷

[2022 年 Linux 核心設計第 1 週隨堂測驗 (A)](https://docs.google.com/forms/d/e/1FAIpQLScNBvG2yT71YuR6QKy1cBsWc7XRdBf7WC5kHbYx7T-D-sS5uw/viewscore?viewscore=AE0zAgDtG4-ufPPdMhlL1wO9PGa7udiZx6kq4LCrheDv8mR3BxbMZepeXVwHob-AmQ)
[2022 年 Linux 核心設計第 1 週隨堂測驗 (B)](https://docs.google.com/forms/d/e/1FAIpQLSfp8gdYnBkNxx4EacIAzQjlxMQiNeLnrfyuznBdsnTcslouaA/viewscore?viewscore=AE0zAgBQKklsAS2SnWOls4a4YnkYH9hb9VNHSaFrt6Tr5_iE9-LtZ1JXDm3XORbh7g)

---