Linux çekirdeğinde çift işaretçi kullanımı Karma liste uygulaması

Question

Bağlantılı liste ve karma tablo Linux çekirdeği uygulamasını anlamaya çalışıyorum. Uygulamanın bir bağlantısı here'dur. Bağlı liste uygulamasını anladım. Ama çift göstericilerin neden hlistede kullanıldığını biraz karıştırdım (** pprev). Hlist için bağlantı here. Listenin başı sadece bir işaretçi gerektirdiğinden ve yer tasarrufu sağladığı için karma listenin uygulanmasında hlistenin kullanıldığını anlıyorum. Neden tek bir işaretçi kullanılarak yapılmaz (sadece * bağlantılı listeye benzeyen)? Lütfen bana yardım et.

Answer 1

nedeni yorumların birinde bulunabilir

: yerine pprev ** ait * önceki olsaydı

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 */ 

ve biz bellekten tasarruf çalışıyoruz çünkü biz * prev içermez baş, sonra bizim hList uygulaması şuna benzer:

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

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

prev işaretçi kafasına işaret edemez Bildirimi, ya da (**pprev aksine) head->first. prevhlist_add_head() yukarıdaki imeplementation içinde, işaret ilgisi yoktur

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

Bildirim: biz hlist_add_before() uygulamak zaman göreceğiniz gibi bu hList uygulanmasını zorlaştırmaktadır. Eğer hlist_add_before() uyguladıklarında Yani, şimdi şuna benzer: şimdi yığın head itmek için ekstra push talimat gerektirir hlist_add_before(), yanı head geçmek gerekir

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

dikkat edin. Ayrıca, uygulamada daha da yavaşlayan bir koşullu kontrol var.

**pprev yerine *prev ile diğer hlist işlemlerini uygulamayı deneyin ve uygulamanızın linux çekirdeğinde gördüğünüzden daha yavaş olacağını göreceksiniz.