# 2022q1 Homework1 (quiz1)
contributed by < [haoyu0970624763](https://github.com/haoyu0970624763) >

### LeetCode 1 [TWO Sum](https://leetcode.com/problems/two-sum/)
#### 解釋程式碼運作原理
先來看 **`twoSum` 函式** 的程式碼

int *twoSum(int *nums, int numsSize, int target, int *returnSize) {
  /* 雜湊表的建立 , 設置雜湊表的 entry 總數為 2^10=1024
   * 要設置除了 1024 以外的數字也可以
   * 通常來說雜湊表 entry 數越多 , 平均尋找時間越短 ,但記憶體消耗越大
   * */
  map_t *map = map_init(10);
  *returnSize = 0;
  int *ret = malloc(sizeof(int) * 2);
  /* if mallocing the memory of return address fail , direct to the end of code */
  if (!ret)
    goto bail;

  for (int i = 0; i < numsSize; i++) {
    /* 尋找當前 input 所對應之 target 之數字是否存在於雜湊表中
     * 例如：要找兩數相加為9 , 當前 input 為 2 , 就要找 7 這個數字是否存在於雜湊表 
     * */
    int *p = map_get(map, target - nums[i]);
    if (p) { /* found */
      ret[0] = i, ret[1] = *p;
      *returnSize = 2;
      break;
    }
    /* 如果當前 input 對應 target 之數字不存在於雜湊表中
     * 就把此 input 加至雜湊表裡面
     * */
    p = malloc(sizeof(int));
    *p = i;
    map_add(map, nums[i], p);
  }

bail:
  map_deinit(map);
  return ret;
}

第六行的 **`map_init` 函式**： 建立 hash table

entry 總數為 $2^{bits}$ , 此題設定成 1024 個 entry

#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++)
      /* 初始化雜湊表中的每一個 entry */
      (map->ht)[i].first = NULL;
  } else {
    free(map);
    map = NULL;
  }
  return map;
}

第十七行的 **`map_get` 函式** : 尋找特定數值是否存在於雜湊表

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

`map_get` 函式中的 **find_key**: 判斷給定的 key 值是否存在於雜湊表

/* 判斷特定 key 值是否存在於雜湊表 , 並回傳 */
static struct hash_key *find_key(map_t *map, int key) {
  /* hash(key, map->bits) 是計算此 key 值對應到哪個 entry
   * 在對應的 entry 中之串列中依序搜尋 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;
}

`find_key` 函式中的 **hash** : 去計算給定值的 hash 值

可參考
[黃金切割](https://zhuanlan.zhihu.com/p/40515974) ,
簡單來說 GOLDEN_RATIO 可以讓 input 平均分散在雜湊表中

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

第二十八行的 **`map_add` 函式** : 將 input 加至 雜湊表中

void map_add(map_t *map, int key, void *data) {
  /* 先看此 key 值是否存在於雜湊表中,不在的話再繼續 */
  struct hash_key *kn = find_key(map, key);
  if (kn)
    return; 
  /* 分配空間以及將資料複製到該節點 */
  kn = malloc(sizeof(struct hash_key));
  kn->key = key, kn->data = data;

  /* h 指向雜湊表中相對應 entry 的位址
   * first 指向雜湊表中相對應 entry 的首個節點位址
   * n 指向剛分配的資料結構中的 node 位址
   * */
  struct hlist_head *h = &map->ht[hash(key, map->bits)];
  struct hlist_node *n = &kn->node, *first = h->first;
  /* n->next = first 
   * 把原本雜湊表中相對應 entry 的首個節點接在新分配的節點後面
   * 
   * if (first) first->pprev = &n->next
   * 如果原本雜湊表中相對應 entry 的首個節點存在的話
   * 將他的 pprev 指向 指向新分配的節點的 next 位址
   * 
   * h->first = n 
   * 改變雜湊表中相對應 entry 所指向的首個節點
   * 
   * n->pprev = &h->first 
   * 將新分配的節點的 pprev 指向 指向雜湊表中相對應 entry 的位址
   * 可搭配題目上方的圖示可以更好的理解此部份
   * */
  n->next = first;
  if (first)
    first->pprev = &n->next;
  h->first = n;
  n->pprev = &h->first;
}

第三十二行的 **`map_deinit`函式** : 把原本建立的 hash table 的空間還給記憶體

void map_deinit(map_t *map) {
  if (!map)
    return;
  
  /* 造訪雜湊表中的每一個 entry*/
  for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
    struct hlist_head *head = &map->ht[i];
    /* 造訪雜湊表中的每一個 entry 內部連結的節點 */
    for (struct hlist_node *p = head->first; p;) {
      struct hash_key *kn = container_of(p, struct hash_key, node);
      /* n 紀錄目前節點
       * p 則移至下一個節點（主要是用來決定 loop 是否繼續之依據） */
      struct hlist_node *n = p;
      p = p->next;

      /* 如果當前的節點的 pprev 為空(非正常行為)
       * 跳至 bail 標籤 , 否則的話處理以下行為
       * */
      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);
}

#### Hash Table 設計與實做手法:
採用的方式是當有兩筆或以上的資料發生衝突時採用 chain 的方式 , 把同一個 bucket 的元素用鏈結串列連接起來

因此會希望
* hash collision 發生的機率降低
* 如果發生 collision 則希望隨機分佈在各 bucket 中 , 不希望集中在特定 bucket 使得 list 過長
* hash function 計算效率快

參考在 hash.h 註解第 31 行中出現的文章 [Linux Kernel Hash Table Behavior:
Analysis and Improvements](http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf)

我們可以發現本題的 hash function 採用的是 multiply and shift方法 , 由於 CPU 執行乘法運算的延遲通常低於除法運算,所以我們用此種方法取代常見的取餘數運算,
並且在上面的參考文章中的第 11 頁也有提及此觀點

上述引文中的 5-1 提及
:::info
The theory posits that machine
multiplication by a large number that is likely to cause
overflow is the same as finding the modulus by a
different number
:::
我們藉由乘上一個很大的數字使其 overflow，造成類似取餘數的結果 , 但讓這個運算從原本複雜的指令變成用簡單的乘法指令達成

`0x61C88647` 則是透過文中的演算法可以求出來的結果
(引文使用的是 INT_64, 我們這邊採用的是 INT_32) 所以算出來的結果不同 , 但概念上是相同的

### LeetCode 82 [Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

#### 避免遞迴的版本
此題的目的是將一個已經排序過的 singly-linked list 中重複的節點移除

解題想法：先把 singly-linked list 中的節點分成兩種狀況
* 節點為空
* 直接回傳 NUL
* 節點不為空：又可細分成兩種狀況
* 此節點之值與後面的節點值相同 , 因此需要刪除重複的值
* 此節點之值與後面的節點值不同

#include <stddef.h>

struct ListNode {
  int val;
  struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head) {
  /* node is empty*/
  if (!head)
    return NULL;

  /* node is not empty*/
  /* this node->val is equal to node->next->val */
  if (head->next && head->val == head->next->val) {
    /* check there are more than one repeated number equal to head node */
    while (head->next && head->val == head->next->val)
      head = head->next;
    // return the node which val is not equal to head node
    return deleteDuplicates(head->next);
  }
  /*
      this node->val is not equal to node->next->val
      directly return the next node
  */
  head->next = deleteDuplicates(head->next);
  return head;
}

以上程式為考試提供之參考解答

考量到 linked list 通常是用 mallloc 實做 , 若有節點不會再被使用到應呼叫 free 函式 , 以免造成 memory leak

修改上述程式的一小段部份

struct ListNode *deleteDuplicates(struct ListNode *head) {
  /* node is empty*/
  if (!head)
    return NULL;

  /* node is not empty*/
  /* this node->val is equal to node->next->val */
  if (head->next && head->val == head->next->val) {

    /* check there are more than one repeated number equal to head node */
    while (head->next && head->val == head->next->val) {
      struct ListNode *tmp = head;
      head = head->next;
      /* free the memory allocated to the duplicate  node */
      free(tmp);
    }
    struct ListNode *tmp = head;
    head = head->next;
    free(tmp);
    // return the node which val is not equal to head node
    return deleteDuplicates(head);
  }
  /*
      this node->val is not equal to node->next->val
      directly return the next node
  */
  head->next = deleteDuplicates(head->next);
  return head;
}

非遞迴版本：

最一開始的解題思路：
* Step1: 判斷串列是否為空,空則直接回傳NULL
* Step2: 判斷串列最前端的值是否為重複(也就是會不會更改到 head指標指向的位置) , 若重複則把串列前面重複值刪除且更改 head 指向的位置
* Step3 : 檢查修改過 head 後的串列是否為空,空則直接回傳NULL
* Step4 : 從被修改過的串列依序追蹤串列 , 檢查後兩個點是否有重複 , `current` 為現在跑到哪邊 , `prev` 紀錄一開始從哪個點開始追蹤 , `prev->next = current` 表示將原本的點的 next 換成沒重複的點,並回到step4直到 current 沒有下一個點為止

struct ListNode *deleteDuplicates(struct ListNode *head) {
  if (!head) {
    return NULL;
  }
  /* Deal with the duplicate case appear in head */
  while (head) {
    if (head->next && head->val == head->next->val) {
      while (head->next && head->val == head->next->val) {
        struct ListNode *tmp = head;
        head = head->next;
        /* free the memory allocated to the duplicate  node */
        free(tmp);
      }
      struct ListNode *tmp = head;
      head = head->next;
      free(tmp);
    } else {
      /* if no duplicate case appear in head , then out of the while loop*/
      break;
    }
  }

  if (!head) {
    return NULL;
  }
  /* use current to traverse the list */
  struct ListNode *current = head;

  /* In here , first node will definitely not equal to second node , if there
   * has second node */
  /* if list have just one node , we just return it , otherwise we deal with it
   */
  while (current->next) {
    /*
        Use variable prev to record now we traverse
        and simply check two nodes behind it are duplicate or not

        if two nodes behind it are duplicate , deal with it
        otherwise just traverse next node
    */
    if (current->next->next && current->next->val == current->next->next->val) {
      struct ListNode *prev = current;
      int same_value = current->next->val;
      current = current->next;
      while (current && current->val == same_value) {
        struct ListNode *tmp = current;
        current = current->next;
        /* free the memory allocated to the duplicate  node */
        free(tmp);
      }
      prev->next = current;
      current = prev;
    } else {
      current = current->next;
    }
  }
  return head;
}

上述程式需要處理兩種不同的 case
* 有改變 head 的
* 沒有改變 head 的

並且程式碼整體也偏長

使用 pointer to pointer 改寫老師給的範例

用這樣的方式可以不用多判斷目前的節點是不是 head 這個 node

struct ListNode *deleteDuplicates(struct ListNode *head) {
  if (!head)
    return NULL;
  
 if(!head->next)
     return head;

  struct ListNode **ptr= &head;
  struct ListNode *current = head;

  while (current) {
    if (current->next && current->val == current->next->val) {
      current = current->next;
      while (current->next && current->val == current->next->val)
        current = current->next;
      current = current->next;
      *ptr = current;
    } else {
      ptr = &(*ptr)->next;
      current = current->next;
    }
  }
  return head;
}

讓此題的程式碼相比自己寫的 version 1 精簡許多

:::info
這一題 LeetCode的討論區 以及 其他同學寫的程式碼

比較沒有在討論到要不要 free 掉不需要的 node 的空間

並且 C 不像其他語言有 garbage collection , 所以我認為理論上要對不需要的 node 空間進行回收 , 但回收空間這件事本身也需要執行時間 , 因此程式會相較沒回收空間來的慢
> 搭配閱讀 ==[Hazard pointer](https://hackmd.io/@sysprog/linux2021-summer-quiz2)==:
> 在沒有 garbage collection 的語言環境中，lock-free data 的主動釋放需要考慮是否有其他執行緒也同時在持有的問題，而 [hazard pointer](https://en.wikipedia.org/wiki/Hazard_pointer) (簡稱 `HP`) 是一種可以解決 lock-free data 在動態記憶體配置的問題之方法。之後探討並行程式設計時，就會實作 HP 一類的垃圾回收機制。因此，在本次測驗題中，其實就是先作預先準備。
> :notes: jserv
從不同觀點看
* 解題觀點來說 free 是拖慢效率的原因
* 系統觀點來說 這樣比較安全
:::

#### circular doubly-linked list 改寫
##### 迭代版本

struct ListNode {
  int val;
  struct ListNode *next;
  struct ListNode *prev;

};
struct ListNode *deleteDuplicates(struct ListNode *head) {
  if (!head)
    return NULL;

  struct ListNode **ptr= &head;
  struct ListNode *current = head;

  while (current) {
    if (current->next && current->val == current->next->val) {
      struct ListNode *tmp = current-> prev;
      while (current->next && current->val == current->next->val)
        current = current->next;
      
      tmp->next=current->next;
      current = current->next;
      current->prev = tmp;

      *ptr = current;
    } else {
      ptr = &(*ptr)->next;

      if(current->next){
        current = current->next;
      }
      else{
        current->next = head ;
      }
    }
  }
  return head;
}

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

#### 解析LRU Cache 程式碼
實做 **Least Recently Used (LRU) cache** 需要實做下列函式

* **LRUCache(int capacity)** : Initialize the LRU cache with positive size capacity
* **int get(int key)** : Return the value of the key if the key exists, otherwise return -1
* **void put(int key, int value)** : Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key

**get 跟 put 函式平均時間應為 $O(1)$**

此題使用 [lab0-c](https://github.com/sysprog21/lab0-c) 所提供的 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 實作 linux 風格的 LRU Cache

資料結構 `LRUNode`

typedef struct {
  int key, value;
  struct list_head hlink, dlink;
} LRUNode;

* key 紀錄此節點的 index 值
* value 紀錄此節點的值

資料結構 `LRUCache`

typedef struct {
  int capacity, count;
  struct list_head dhead, hheads[];
} LRUCache;

* capacity 紀錄 cache 的 entry 數
* count 紀錄 cache 當前的資料數

**首先解析`lRUCacheCreate()`**

`LRUCache` 須紀錄
* 1. 其 capicity 以及 當前資料數 (count) 其空間需要 malloc(sizeof(*obj))
* 2. hash table 的空間 malloc(capacity * sizeof(struct list_head))
* 3. 接著就是初始化

LRUCache *lRUCacheCreate(int capacity) {
  /* LRUCache 須紀錄
   * 1.capicity 以及 當前資料數 (count)
   * 其空間需要 malloc(sizeof(*obj))
   * 2.hash table 的空間
   * malloc(capacity * sizeof(struct list_head))
   */
  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;
}

接著從 `lRUCacheGet` 這個函式下去解析老師提供的 code

int lRUCacheGet(LRUCache *obj, int key) {
  LRUNode *lru;

  /* 根據給定的 key 值去計算其應該在 Cache 中的哪個 entry */
  int hash = key % obj->capacity;
  /* 根據計算出的 hash 值去尋找 cache 中 , 此 hash 值的  entry
   * 所以 &obj->hheads[hash] 表示 Cache 中對應的 entry 的 head
   * 而同一個 hash 值的 node 會用 linked list 串接起來 , 用 hlink 串連
   */
  list_for_each_entry(lru, &obj->hheads[hash], hlink) {
    if (lru->key == key) {
      /*
       *  如果有找到相同的 key 值 , 在這個瞬間此 key 值是最近被存取到的
       *  把此 key 值放到 cache 的 Least Recently node 的最前頭(最近使用)
       *  dhead 為 cache last reference time 的串列 , 用 dlink 串接
       */
      list_move(&lru->dlink, &obj->dhead);
      return lru->value;
    }
  }
  return -1;
}

解析完 `lRUCacheGet` 函式, 即可了解 `LRUNode` 此資料結構中各自內部成員的意義

**再接著解析 `lRUCachePut()`**

void lRUCachePut(LRUCache *obj, int key, int value) {
  LRUNode *lru;
  /* 根據給定的 key 值去計算其應該在 Cache 中的哪個 entry */
  int hash = key % obj->capacity;
  list_for_each_entry(lru, &obj->hheads[hash], hlink) {
    /* 若有相同的 key 值存在於 Cache 當中
     * 則把此 key 值的 node 放到 cache 的 Least Recently node 的最前頭(最近使用)
     * 並修改其 value 為新 put 的 value
     */
    if (lru->key == key) {
      list_move(&lru->dlink, &obj->dhead);
      lru->value = value;
      return;
    }
  }
  /* count 紀錄 Cache 中的資料數量
   * 如果 Cache 的資料數量 < capacity 則向記憶體要求 node 的空間
   * 否則的話 , 找出要取代的 node ( dhead's tail)
   */
  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;
}

解析完 `lRUCachePut` 函式, 即可了解 `LRUCache` 此資料結構中各自內部成員的意義

**最後解析`lRUCacheFree()`**

&obj->dhead 是根據 reference time 前後排序的 linked list , 把內部元素都 free 掉
以及 LRUCache free 掉就不會造成 memory leak 的問題

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

#### 題目為什麼要用這些資料結構之分析

* **此題之所以要用 `hash` 是因為這樣可以使平均搜尋時間複雜度為 $O(1)$**：
假設輸入的資料是平均分佈在各 entry 中 , 這樣可以使資料先找到 hash entry , 再進去 entry list 裡面搜尋
, 可以避免從 cache 的頭找到尾的 O(capacity) 時間
* **此題之所以要用 `linked list` 是因為可以使平均移動資料時間複雜度為 $O(1)$**：
而不管是 put 操作或是 get 操作都會修改到 referce time , 如果是用陣列實做的話 , 移動 data的時間是 O(capacity) , 用 linked list 實做的話則是 O(1)

#### 設計實驗的想法

**1. 根據測驗1的 [Hash Table 設計與實做手法](https://hackmd.io/bN7BKitBTUqzh3JGkJrMzg?view#Hash-Table-%E8%A8%AD%E8%A8%88%E8%88%87%E5%AF%A6%E5%81%9A%E6%89%8B%E6%B3%95)**

考量到 CPU 的乘法指令通常相較於除法指令迅速 , 我將原本題目中用到的 hash function (mod 取餘數) 改成像測驗一的形式

以下為簡易的測試程式

int main(int argc, char *argv[]) {
  LRUCache *test = lRUCacheCreate(1024);
  int IndexTable[1024];
  srand(1);
  for (int j=0; j < 1024 ;j++ ) {
    int index = abs(rand());
    int value = abs(rand());
    IndexTable[j]=index;
    lRUCachePut(test, index , value);
  }

  for (int j=0; j < 1024 ;j++ ) {
    lRUCacheGet(test, IndexTable[j]);
  }

  lRUCacheFree(test);
  return 0;
}

由於此目標是要測驗 hash function 的效能 , 所以我將此題的測試數目控制在 LRU cache 的 entry 數量之下 , 只需執行 Put 跟 Get 的指令 , 不涉及超出 entry 數量的節點時要刪除哪個節點的選擇

:::warning
文字訊息==不要==用圖片來展現，永遠要想到視覺障礙的朋友們。
:notes: jserv
:::

但測試之後發現 , 效能幾乎沒有差異 , 即使是關掉編譯器的自動優化之後 , 發現效能仍舊幾乎沒有差異

所以我判斷使用 hash 的部份在 LRU cache 中並不是效能上的重點

**2.刪除多餘的程式碼**

由於 dlink 並非是動態規劃的記憶體空間 , 將 lru free 掉 即可一併將 dlink free 掉

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

使用指令 `valgrind 執行檔` 可發現刪除 list_del(&lru->dlink) 程式依舊沒有 memory leak

**3. 檢查輸入是否合法的機制**

LRUCache *lRUCacheCreate(int capacity) {
  /* LRUCache 須紀錄
   * 1.capicity 以及 當前資料數 (count)
   * 其空間需要 malloc(sizeof(*obj))
   * 2.hash table 的空間
   * malloc(capacity * sizeof(struct list_head))
   */
  
  if (capacity <= 0) {
    exit(-1);
  }
    
  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;
}

int lRUCacheGet(LRUCache *obj, int key) {

  if (key < 0) {
    exit(-1);
  }
  LRUNode *lru;

  /* 根據給定的 key 值去計算其應該在 Cache 中的哪個 entry */
  int hash = key % obj->capacity;
  /* 根據計算出的 hash 值去尋找 cache 中 , 此 hash 值的  entry
   * 所以 &obj->hheads[hash] 表示 Cache 中對應的 entry 的 head
   * 而同一個 hash 值的 node 會用 linked list 串接起來 , 用 hlink 串連
   */
  list_for_each_entry(lru, &obj->hheads[hash], hlink) {
    if (lru->key == key) {
      /*  如果有找到相同的 key 值 , 在這個瞬間此 key 是最近被存取到的
       *  把此 key 值放到 cache 的 Least Recently node 的最前頭(最近使用)
       *  dhead 為 cache last reference time 的串列 , 用 dlink 串接
       */
      list_move(&lru->dlink, &obj->dhead);
      return lru->value;
    }
  }
  return -1;
}

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

  if (key < 0 || value < 0) {
    exit(-1);
  }
  LRUNode *lru;
  /* 根據給定的 key 值去計算其應該在 Cache 中的哪個 entry */
  int hash = Hash(key, 10);
  list_for_each_entry(lru, &obj->hheads[hash], hlink) {
    /* 若有相同的 key 值存在於 Cache 當中
     * 則把此 key 值的 node 放到 cache 的 Least Recently node 的最前頭(最近使用)
     * 並修改其 value 為新 put 的 value
     */
    if (lru->key == key) {
      list_move(&lru->dlink, &obj->dhead);
      lru->value = value;
      return;
    }
  }
  /* count 紀錄 Cache 中的資料數量
   * 如果 Cache 的資料數量 < capacity 則向記憶體要求 node 的空間
   * 否則的話 , 找出要取代的 node ( dhead's tail)
   */
  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;
}

#### 在 Linux 核心找出 LRU 相關程式碼並探討

[linux/include/linux/lru_cache.h](https://github.com/torvalds/linux/blob/9b76d71fa8be8c52dbc855ab516754f0c93e2980/include/linux/lru_cache.h) 以及 [linux/lib/lru_cache.c](https://github.com/torvalds/linux/blob/master/lib/lru_cache.c)

跟我們的 LRU cache 中顯而易見的不同主要有

1.在 linux 中 LRU cache 中有三種 list
* in_use: currently in use (refcnt > 0, lc_number != LC_FREE)
* lru: unused but ready to be reused or recycled (lc_refcnt == 0, lc_number != LC_FREE),
* free: unused but ready to be recycled (lc_refcnt == 0, lc_number == LC_FREE)

每一種 list 可以視作一種狀態

首先：**當 LRU cache 滿的時候 , linux 會把 cache 的一筆資料從 in_use list 放到 lru list 中** , 這樣做的目的是保存那些暫時沒使用但未來有可能使用到的資料,而我們
的寫法就沒辦法保留這些資料(用記憶體空間換取未來讀取時的效率)

如果 lru list 中有放置一段時間沒被使用的資料, 會被移至 free list 中

若 free list 積累了一定量的資料之後 , 會一次性的回收掉所有空間 , 而不是一個一個回收空間（相較於多次呼叫回收記憶體空間 , 一次回收多個記憶體空間的效能更好）

2.linux 中還考慮到多執行緒同時處理 LRU cache 的情況 , 因此有 lock , 我們寫的是簡化版 , 主要考慮單線程的情況

可以搭配
[lru_cache.c 簡易文件](https://docs.huihoo.com/doxygen/linux/kernel/3.7/lru__cache_8c.html) 參考可以更好的理解 linux 的 lru_cache 的原始碼

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

#### 改良版的LCS

用 LeetCode 的範例1 input [100,4,200,1,3,2] 來做說明

如果是這個 input , 原有的 code 會先找跟 100 相鄰的數字 , 因為沒有 99 或 101 所以最大長度暫時為 1

接著找跟 4 相鄰的數字 , 發現最大長度為 4

此時程式會再找 200 周圍的數字 , **但實際上 200 周圍的數字是不需要找的**

**因為根據 input 的長度來說 , 已經不可能找到比長度 4 還要更長的 sequence**

也就是說 此時再繼續找 sequence 完全只是多餘的動作

**解決方法: 每次找 sequence 時 , 同時紀錄剩下的 input 數為多少個**

如果當前最大的 sequence 長度超過剩餘的長度時 , 剩下的就不用再找了 , 因為繼續找也不可能超越當前的 sequence 長度

改良版附上程式解析如下

int longestConsecutive(int *nums, int n_size) {
  int hash, length = 0;
  int remain = n_size ;
  struct seq_node *node;
  /* heads 為 size 為 n_size 的 hash table*/
  struct list_head *heads = malloc(n_size * sizeof(*heads));

  /* 初始化每一個 hash table entry */
  for (int i = 0; i < n_size; i++)
    INIT_LIST_HEAD(&heads[i]);
  /* 如果 input 的數字不在相對應 hash table 的 entry 中
   * 則把此數字放入 hash table entry 的串列當中
   */
  for (int i = 0; i < n_size; i++) {
    if (!find(nums[i], n_size, heads)) {
      /* 因為 input 不一定為正數 , 所以如果是負數要先加負號再進行 hash */
      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;

    /* 看當前的 input 存不存在於hash table
     * 如果不存在表示 input 列表中有跟當前 input 相鄰的數
     * 已經被算進去 sequence 長度
     */
    node = find(nums[i], n_size, heads);
    remain--;
    if (node) {
      /* 若此 input 存在於 hash table中
       * 則 Longest Consecutive Sequence​長度+1
       * 先用 num 紀錄此數字
       * 並在串列中刪除此數 , 用意是避免之後重複的搜尋
       */
      len++;
      num = node->num;
      list_del(&node->link);

      int left = num, right = num;
      /* 找 num 相鄰的數字(負的方向)
       * 找到的話在串列中刪除此數 , 用意是避免之後重複的搜尋
       */
      while ((node = find(--left, n_size, heads))) {
        len++;
        list_del(&node->link);
        remain --;
      }
      /* 找 num 相鄰的數字(正的方向)
       * 找到的話在串列中刪除此數 , 用意是避免之後重複的搜尋
       */
      while ((node = find(++right, n_size, heads))) {
        len++;
        list_del(&node->link);
        remain --;
      }

      /* 判斷目前搜尋的相鄰數字長度有沒有大於當前之最大值 */
      length = len > length ? len : length;
      if(length >= remain){
          return length;
      }
    }
  }

  return length;
}


使用 LeetCode 測試也可發現這個程式碼已經快過 100 % 的 C 語言