Linux内核hlist数据结构分析
在内核编程中哈希链表hlist使用非常多，比如在openvswitch中流表的存储中就使用了（见[1]）。
hlist的表头仅有一个指向首节点的指针，而没有指向尾节点的指针，这样在有很多个buckets的HASH表中存储的表头就能减少一半的空间消耗。 和hlist相关的数据结构如下，桶中存储的 hlist_head 是具有相同hash值的entry构成的链表，每个entry包含一个 hlist_node 成员，通过它链入到这个哈希链表中。 struct
hlist_head { struct
hlist_node *
first
;
};
//next指向下一个节点 // pprev指向前一个节点的next域 struct
hlist_node { struct
hlist_node *
next
, **
pprev
;
};
结构图为： 
文章图片
由于头结点和其他节点的类型不一致，这样就不能使用普通的prev指针指向前一个节点（否则处理的时候还要讨论是否是第一个节点，没有通用性），这里设计者的巧妙之处就是pprev指针指向前一个节点的next，统一了后续所有的节点。
一些有用的宏： //头结点初始化 #define
HLIST_HEAD_INIT { .first = NULL } //构造一个名为name的头结点 #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)
1.删除节点 next得到当前节点的下一个节点，pprev是前一个节点的next字段的地址，那么*pprev就指向的是当前这个节点，那么
*pprev=next 就把当前节点更新为下一个节点了，如果n不是最后一个节点，还要设置next->pprev. 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;
}
2.插入节点 （1）头插入：让插入的节点成为链表的第一个节点，依次更新相应的指针，示意图如下。 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
;
} （2）在已知节点next之前/之后插入，通过自己画图，很容易理解清楚。 /* 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;
}
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
;
}
3.通过看一个节点h的pprev是否为空，判断其是否在哈希链表中。 static inline
int
hlist_unhashed (
const
struct
hlist_node *h) { return
!h->
pprev
;
}
4.哈希链表的遍历（iterate）相关代码 //通过一个字段member的地址 ptr，得到包含它的容器的地址 #define
hlist_entry(ptr, type, member) container_of(ptr,type,member)
//用 pos作为游标来遍历这个链表， prefetch是数据预取 #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)
//通用的哈希链表遍历，其中 pos指向当前节点， tpos指向的包含hlist_node的当前结构体的指针 #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 existing point * @ tpos: the type * to use as a loop counter. * @ pos:the &struct hlist_node to use as a loop counter. * @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 existing point * @ tpos: the type * to use as a loop counter. * @ pos:the &struct hlist_node to use as a loop counter. * @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 counter. * @ pos:the &struct hlist_node to use as a loop counter. * @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)
推荐阅读
- 期刊|期刊 | 国内核心期刊之（北大核心）
- Linux下面如何查看tomcat已经使用多少线程
- Beego打包部署到Linux
- Linux|109 个实用 shell 脚本
- linux定时任务contab
- 芯灵思SinlinxA33开发板Linux内核定时器编程
- day16-Linux|day16-Linux 软件管理
- 如何在阿里云linux上部署java项目
- 嵌入式（编译内核、根文件系统等）
- mac|mac 链接linux服务器 如何在Mac上连接服务器