contributed by < eric88525
>
解釋上述程式碼運作原理
研讀 Linux 核心原始程式碼 include/linux/hashtable.h 及對應的文件 How does the kernel implements Hashtables?,解釋 hash table 的設計和實作手法,並留意到 tools/include/linux/hash.h 的 GOLDEN_RATIO_PRIME,探討其實作考量
COND1 = head->next && (head->val == head->next->val)
COND2 = head->next && (head->val == head->next->val)
line 6-8
如果當前節點跟下一個節點重複,那就會持續移動head指標到最後一個重複的node
一開始指向頭
持續移動到直到最後一個重複節點
line 9
將最後重複節點的下一個位置,丟入下次遞迴並回傳,在本次遞迴中就成功跳過重複的數字
line 12
如果當前節點跟下一節點不重複,指定head->next為經過遞迴處理的後續節點
嘗試避免遞迴,寫出同樣作用的程式碼
line 6-7
宣告 curr 跟 head指向相同節點位址,**p 則是指向 head本身的位址
line 9
只要 curr一直有指向節點 while 就會持續
line 10-13
情況1發生:節點數字重複,讓curr移動到不重複片段的起點
line 14
改變 *p 為 curr 的位址,也就是 此時 head 會改為指向 curr,成功跳過重複節點
line 16-17
情況2發生,curr的數字不等於curr->next的數字,p就會改為 *p 所指向節點的 next 指標,最後讓curr往下移動
curr往下移動後,如果curr還是跟curr->next不一樣,p 就會再次移動到 *p 指到節點的 next 指標
此時碰上curr = curr->next 的情況
curr會透過 line 10-13 來移動到不重複的起點,並改變 *p 為 curr 的位址(此時 p 指向 2 的 next 指標,因此讓 2 的 next 指到 node 4),完成跳過兩個重複的 3
以類似 Linux 核心的 circular doubly-linked list 改寫,撰寫遞迴和迭代 (iterative) 的程式碼
MMM1 = list_for_each_entry_safe
MMM2 = list_for_each_entry
MMM3 = list_for_each_entry
MMM4 = list_last_entry
解釋上述程式碼的運作,撰寫完整的測試程式,指出其中可改進之處並實作
資料型態
函式
line 16-25
lRUCacheCreate: 創建 LRUCache 實體
如果 capacity傳入為3,那就會讓 hhead 為 size 3的指標陣列,
line 50-74
lRUCachePut: 將新的 key,value 加入LRUCache 結構
加入 key = 4, value = 44
line 54-60
會先幫 value 計算 hashkey,並到對應的 hhead[ hashkey ] 內查找是否曾有存過這個 hashkey,有的話就更新數值並把 dlink 移動到最前面,位置越靠前代表近期有使用過。
line 62-66
當 capacity == count 時,透過 list_last_entry 來讓 lru 指向距離 dhead 最遠的節點,並且從list中抽出
抽出後接續 line 66-74,加入到
line 66-74
將 *lru 指向節點,指派 key 和 value 後接上對應位置(dlink 接上dhead,hlink 接到 hhead )
測試在capacity = CAPACITY
的實體內塞入 TEST_SIZE
份資料
在 Linux 核心找出 LRU 相關程式碼並探討
LLL = --left
RRR = ++right
解釋上述程式碼的運作,撰寫完整的測試程式,指出其中可改進之處並實作
hash
,接著到對應的heads[hash]
查找有無num
,有則回傳節點位址heads
為size n_size
的陣列heads [hash]
中查找數字,如果此數字不存在就加入到 heads[hashkey]
後面第一個 num 為100,透過 find 找不到此數字,所以加入 heads[hash]
這裡的 hashkey = 100 % 6 = 4
nums[1] = 4,find 找不到此數字,加入 heads[hash]
最後完成所有數字的加入
nums[i]
開始,如 nums[i]
存在於結構中,向左右查找並更新最大長度指向100,移出結構,並往left = 99
right = 101
查找,更新length為1
指向4,移出結構,並往left = 3
left = 2
left = 1
right = 5
查找,更新length為 4
length
在 TEST_SIZE 大小的 int array中讓 MAX_LEN個數字為連續,函式回傳值應該等於 MAX_LEN
嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼