hlist 해시 링크

hlist 해시 링크 는 커 널 에서 자주 사용 하 는 데이터 구조 로 일반 링크 와 다 르 기 때문에 hlist 해시 링크 를 분석 하여 여러분 에 게 도움 이 되 기 를 바 랍 니 다.include / linux / list. h 에 list 링크 와 hlist 해시 링크 구조의 정의 가 있 습 니 다. 다음은 모두 그들의 정 의 를 보 여 줍 니 다. 비교 할 수 있 습 니 다. struct list_head {
struct list_head *next, *prev;
};struct hlist_head {struct hlist_node *first;};
struct hlist_node {struct hlist_node *next, **pprev;};
더 블 헤드 (next, prev) 의 더 블 링크 는 Hash 표 에 있어 '너무 낭비 적' 이기 때문에 Hash 표 전용 hlist 데이터 구 조 를 따로 설계 했다. 단일 포인터 표 두 쌍 순환 링크 표, hlist 의 표 두 는 첫 번 째 노드 를 가리 키 는 지침 만 있 고 끝 노드 를 가리 키 는 지침 이 없다.이렇게 하면 대량의 Hash 표 에 저 장 된 헤더 가 공간 소 모 를 절반 으로 줄 일 수 있다.pprev 는 hlist 가 완전한 순환 링크 가 아니 기 때문에 사용 할 수 밖 에 없습니다.list 에서 표 두 와 노드 는 같은 데이터 구조 이 고 prev 를 직접 사용 하 는 것 은 문제 가 없습니다.hlist 에서 표 두 는 prev 도 없고 next 도 없고 first 만 있 습 니 다.표 두 의 first 지침, 즉 표 두 의 first 지침 을 통일 적 으로 수정 하기 위해 서 는 새로 삽 입 된 노드 를 가리 키 는 부분 을 수정 해 야 합 니 다. hlist 는 pprev 를 설계 하 였 습 니 다.hlist 노드 의 pprev 는 이전 노드 를 가리 키 는 지침 이 아니 라 이전 노드 (표 머리 일 수 있 음) 의 next (표 머리 에 대해 first) 지침 (struct list head * pprev) 을 가리 키 며 표 머리 에 삽 입 된 동작 은 일치 하 는 '* (node - > pprev)' 을 통 해 이전 노드 의 next (또는 first) 지침 을 방문 하고 수정 할 수 있 습 니 다.주: pprev 는 이전 노드 의 next 지침 을 가리 키 며, next 는 hlist 를 가리 키 고 있 습 니 다.node 의 지침, 그래서 pprev 는 hlist 를 가리 키 는 것 입 니 다.node 의 지침.
메모: pprev 는 list 를 향 한 prev 처럼 hlist 를 가리 키 는 것 으로 이해 할 수 있 습 니 다.node 의 지침, 또 hlistnode 의 첫 번 째 요소 next 는 hlist 를 가리 키 는 것 입 니 다.node 의 지침, pprev 도 next 를 가리 키 는 지침 입 니 다. 즉, pprev 는 hlist 를 가리 키 는 지침 입 니 다.node 의 지침.struct hlist_node Prev;
struct hlist_node *pprev = (struct hlist_node *) Prev = (struct hlist_node *) (struct hlist_node * next) = struct hlist_node ** next;
다음은 hlist 에서 자주 사용 하 는 매크로 입 니 다. #define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)다음은 hlist 만 열거 합 니 다.add_before 조작 함수, 기타 hlist 링크 조작 함수 조작 방법 유사.이 함수 의 인자 next 는 비어 있 을 수 없습니다.그것 은 next 앞 에 n 노드 를 넣 었 다.함수 의 실현 은 list 에 대응 하 는 함수 와 유사 합 니 다.static inline void __hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
}
static inline void hlist_add_before(struct hlist_node *n,struct hlist_node *next){n->pprev = next->pprev;n->next = next;next->pprev = &n->next;*(n->pprev) = n;} #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
#define hlist_for_each(pos, head) /
for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); /
pos = pos->next)
 
 주소http://blog.chinaunix.net/u/12592/showart.php?id=451619