리눅스 커널에서 더블 포인터 사용 해시리스트 구현

Question

리눅스 커널의 링크드리스트와 해시 테이블 구현을 이해하려고합니다. 구현 링크는 here입니다. 연결된 목록 구현을 이해했습니다. 하지만 난 왜 두 포인터가 hlist (** pprev)에서 사용되고 있는지 혼란 스럽다. hlist에 대한 링크는 here입니다. 나는 목록의 머리가 단지 하나의 포인터를 필요로하고 그것이 공간을 절약하기 때문에 hlist가 해시 테이블의 구현에 사용된다는 것을 이해한다. 단일 포인터 (링크 된 목록과 같은 * prev)를 사용하여 수행 할 수없는 이유는 무엇입니까? 도와주세요.

Answer 1

그 이유는 코멘트 중 하나에서 찾을 수 있습니다

: 대신 pprev **의 * 이전 한 경우

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

, 우리는 메모리를 저장하려고하기 때문에, 우리는에 * 이전에 포함되지 않습니다 머리는, 다음 우리 hlist 구현은 다음과 같습니다

이

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

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

prev 포인터가 머리를 가리 할 수없는 공지 사항, 또는 (**pprev 달리) head->first. prev이 hlist_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()를 구현할 때 살펴 보 겠지만 이것은 hlist 구현을 복잡하게한다. 당신이 hlist_add_before()을 구현할 때, 지금은 다음과 같습니다 : 지금 우리는 스택에 head를 밀어 추가 push 명령을 필요로 hlist_add_before()에뿐만 아니라 head에 전달해야

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

알 수 있습니다. 게다가 구현에 추가적인 조건부 검사가있어 상황이 더욱 느려집니다.

**pprev 대신 *prev 대신 다른 hlist 작업을 구현해보십시오. 그러면 구현이 Linux 커널에서 본 것보다 느려질 것입니다.