लिनक्स कर्नेल हैश सूची कार्यान्वयन में डबल पॉइंटर का उपयोग

Question

मैं लिंक्ड सूची और हैश तालिका के लिनक्स कर्नेल कार्यान्वयन को समझने की कोशिश कर रहा हूं। कार्यान्वयन का एक लिंक here है। मैं लिंक्ड सूची कार्यान्वयन को समझ गया। लेकिन मैं थोड़ा उलझन में हूं कि क्यों hlist (** pprev) में डबल पॉइंटर्स का उपयोग किया जा रहा है। हिस्ट्री के लिए लिंक here है। मैं समझता हूं कि हैश सूची का उपयोग हैश तालिका के कार्यान्वयन में किया जाता है क्योंकि सूची के प्रमुख को केवल एक सूचक की आवश्यकता होती है और यह स्थान बचाती है। एकल सूचक का उपयोग करके यह क्यों नहीं किया जा सकता है (बस * लिंक की गई सूची की तरह पिछला)? क्रिप्या मेरि सहायता करे।

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() लागू देखेंगे: prevhlist_add_head() के ऊपर imeplementation में, इंगित करने के लिए कुछ भी नहीं है

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

सूचना है कि। तो, अब जब आप 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; 
    } 
} 

सूचना है कि अब हम hlist_add_before(), जो स्टैक पर head धकेलने के लिए एक अतिरिक्त push अनुदेश की आवश्यकता के लिए head में पारित करने के लिए और साथ ही जरूरत है। इसके अलावा, कार्यान्वयन में एक अतिरिक्त सशर्त जांच है, जो आगे चीजों को धीमा कर देती है।

अब **pprev के बजाय *prev के साथ अन्य hlist संचालन को लागू करने का प्रयास करें, और आप पाएंगे कि आपका कार्यान्वयन लिनक्स कर्नेल में जो देखा गया उससे धीमा होने वाला है।