在linux內核中使用雙指針哈希列表實現

Question

我想了解Linux內核實現的鏈表和哈希表。實施的鏈接是here。我瞭解鏈接列表的實現。但是我對hlist（** pprev）中使用雙指針的原因感到困惑。 hlist的鏈接是here。我知道hlist用於執行散列表，因爲列表的頭部只需要一個指針並且節省了空間。爲什麼不能使用單個指針來完成（就像鏈表一樣* prev）？請幫幫我。

Answer 1

之所以可以在評論的一個發現：

547/* 
548 * Double linked lists with a single pointer list head. 
549 * Mostly useful for hash tables where the two pointer list head is 
550 * too wasteful. 
551 * You lose the ability to access the tail in O(1). 
552 */ 

如果你有*分組，而不是** pprev，因爲我們正試圖以節省內存，不包括*分組中頭，那麼我們hlist實施看起來是這樣的：

struct hlist_head { 
    struct hlist_node *first = null; 
}; 

struct hlist_node { 
    struct hlist_node *next; 
    struct hlist_node *prev; 
}; 

注意，prev指針不能指向頭部，或head->first（不像**pprev）。這個複雜的hlist實施，你會看到，當我們實現hlist_add_before()：

void 
hlist_init(struct hlist_head *head) { 
    head->first = null; 
} 

void 
hlist_add_head(struct hlist_head *head, struct hlist_node *node) { 
    struct hlist_node *next = head->first; 

    head->first = node; 
    node->next = next; 
    node->prev = NULL; 
    if (next) { 
    next->prev = node; 
    } 
} 

注意prev沒有任何指向，在hlist_add_head()上述imeplementation。所以，現在當你實現hlist_add_before()它看起來像這樣：

void 
hlist_add_before(struct hlist_head *head, 
       struct hlist_node *node, 
       struct hlist_next *next) { 
    hlist_node *prev = next->prev; 

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

    if (prev) { 
    prev->next = node; 
    } else { 
    head->first = node; 
    } 
} 

注意，現在我們需要在head傳遞以及對hlist_add_before()，這需要在棧上推head額外push指令。此外，還有一個額外的條件檢查實施，這進一步減慢了事情。

現在，嘗試執行其他hlist操作，使用*prev而不是**pprev，並且您會發現您的實現將比您在Linux內核中看到的要慢。