contributed by < eleanorLYJ
>
要完成 list_insert_before,此函式的功能為,將新的 item 插入到 list 中的特定 item 之前。
在完成函式之前,先看 list_item 的結構
p
是指向 list_item_t 指標的指標,因為看到 *p = item
故能得知,迴圈跑完, p
會移到 before
的前一個位置的 next
,也就是 item 插入的位置。
因此由此推論,迴圈是從 list 的開頭開始跌代,接著每次先對 p 做dereference 得到該指標的下一個地址,然後發現下一個地址等於 before
,停止迭代。
開平方根
hash table
從題目敘述得知 hash table 的基礎概念
hlist_head 只使用一個 first 指標指向 hlist_node,沒有指向串列尾節點的指標。
hash table 主要是由一個 hlist_head 的動態陣列所構成,每個 entry 指向一個由 struct hlist_node 構成的非環狀 doubly linked list ,hash table 長度依照 bits 給定,可知大小為 2 的冪。
先看需要的雜湊表的結構。
find_key()
是要找值為 key 所在的 struct hash_key
,若找不到就返回 NULL。
find_key 的實現細節為,先找 key 所在的 hlist,然後迭代 hlist 並逐一比較節點找是否有 key。其中為使用 container_of
找在 p 所在的 struct hash_key
的位置,比較成員 key 是否等於參數的 key。
以下補充 container_of 的定義。
map_add() 函式則負責新增一對 key 與 data 到 hash table 中。如果 key 已經存在,返回,不更新 data。如果不存在,則創建依參數而產生的 hash_key (kn
),並將其插入到對應的 hlist_head 中。插入操作會確保新的 node 被正確地連接到鏈結串列的頭部,並更新相關的前驅節點指標 pprev。