//双向链表对于hash表来说太浪费了 //因此设计了单向链表,但是,这样在访问尾节点时间上就不再是O(1)的时间复杂度 /* * Double linked lists with a single pointer list head. * Mostly useful for hash tables where the two pointer list head is * too wasteful. * You lose the ability to access the tail in O(1). */ struct hlist_head { struct hlist_node *first; }; //双循环链表 //pprev存放的是前一个节点的next指针 //对于链表头来说则是first //对于链表节点来说则是next的地址 //这样做的主要目的是通过后面节点,也能修改前一个节点的值(next) //为什么不采用next和prev的结构呢(采用同一般链表的结构)?? //首先,除第一个节点(非头结点)以外的其他节点采用一般链表结构是没有问题的; //但是,对于第一个节点来说,存在着操作上与其他节点的不一致 //第一个hlist_node 的next指向没有问题,但是prev是指向前一个即hlist_head的头结点 //因此,此时的prev的类型是hlist_node,头结点是单链hlist_node的first //这样在访问上prev只能指向first的值,此时prev和first的值是一致的,因此失去了prev原为 //指向前一个节点的意义,因此为了实现prev的功能,以及为了统一所有hash链表的操作, //采用了指向指针(双重指针)的操作,即可以通过pprev存储first的地址,起到修改和访问的作用 struct hlist_node { struct hlist_node *next, **pprev; }; #define HLIST_HEAD_INIT { .first = NULL } #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) //初始化hash链表节点 static inline void INIT_HLIST_NODE(struct hlist_node *h) { h->next = NULL; h->pprev = NULL; } //判断该hash是否有值??? static inline int hlist_unhashed(const struct hlist_node *h) { return !h->pprev; } //判断是否为空 static inline int hlist_empty(const struct hlist_head *h) { return !h->first; } //删除一个节点 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_del(struct hlist_node *n) { __hlist_del(n); n->next = LIST_POISON1; n->pprev = LIST_POISON2; } static inline void hlist_del_init(struct hlist_node *n) { if (!hlist_unhashed(n)) {//不为空,删除并初始化 __hlist_del(n); INIT_HLIST_NODE(n); } } //插入在头结点之后的位置 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) { struct hlist_node *first = h->first; n->next = first; if (first) first->pprev = &n->next; h->first = n; n->pprev = &h->first; } //在next节点之前,加入n /* next must be != NULL */ 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; } //在节点n之后插入next static inline void hlist_add_after(struct hlist_node *n, struct hlist_node *next) { next->next = n->next; n->next = next; next->pprev = &n->next; if(next->next) next->next->pprev = &next->next; } /* * Move a list from one list head to another. Fixup the pprev * reference of the first entry if it exists. */ //将一个链表从一个头结点移至另一个头结点 //并将old的节点置为null static inline void hlist_move_list(struct hlist_head *old, struct hlist_head *new) { new->first = old->first; if (new->first) new->first->pprev = &new->first; old->first = NULL; } //取出指针对应的结构体成员 #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) #define hlist_for_each_safe(pos, n, head) \ for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \ pos = n) /** * hlist_for_each_entry - iterate over list of given type * @tpos: the type * to use as a loop cursor. * @pos: the &struct hlist_node to use as a loop cursor. * @head: the head for your list. * @member: the name of the hlist_node within the struct. */ #define hlist_for_each_entry(tpos, pos, head, member) \ for (pos = (head)->first; \ pos && ({ prefetch(pos->next); 1;}) && \ ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ pos = pos->next) /** * hlist_for_each_entry_continue - iterate over a hlist continuing after current point * @tpos: the type * to use as a loop cursor. * @pos: the &struct hlist_node to use as a loop cursor. * @member: the name of the hlist_node within the struct. */ #define hlist_for_each_entry_continue(tpos, pos, member) \ for (pos = (pos)->next; \ pos && ({ prefetch(pos->next); 1;}) && \ ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ pos = pos->next) /** * hlist_for_each_entry_from - iterate over a hlist continuing from current point * @tpos: the type * to use as a loop cursor. * @pos: the &struct hlist_node to use as a loop cursor. * @member: the name of the hlist_node within the struct. */ #define hlist_for_each_entry_from(tpos, pos, member) \ for (; pos && ({ prefetch(pos->next); 1;}) && \ ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ pos = pos->next) /** * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry * @tpos: the type * to use as a loop cursor. * @pos: the &struct hlist_node to use as a loop cursor. * @n: another &struct hlist_node to use as temporary storage * @head: the head for your list. * @member: the name of the hlist_node within the struct. */ #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \ for (pos = (head)->first; \ pos && ({ n = pos->next; 1; }) && \ ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ pos = n) #endif