本文共 5271 字，大约阅读时间需要 17 分钟。
1. 概述
以邻接表管理（adjacency.c）为例，描述一种HASH表中的HASH桶、冲突链表等要素的管理方式。推荐以示例中的方式实现HASH表。 冲突链表采用linux_list.h中定义的hlist接口实现，相比list（参考），头节点仅有一个指针，也就节省了HASH桶的空间。 另外，桶的大小应定义为2的n次幂减1，这样在计算HASH值时，可以用与运算替代取模运算，避免除法提高效率。
2. 冲突链表管理
2.1. 位置
list.h
2.2. 数据结构
| /* * 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; };
struct hlist_node { struct hlist_node *next, **pprev; }; |
2.3. 使用方法
1. 应用时，在链表的头节点数据结构中包含struct hlist_head成员；中间节点的数据结构中包含struct hlist_node成员；
2. 头节点的struct hlist_head成员应初始化（将first置为NULL）；
3. 在并行执行环境下使用时，需考虑对链表进行加锁保护；
4. 插入、删除、遍历等操作见下面的接口。
2.4. 接口
2.4.1. HLIST_HEAD
· 原型 HLIST_HEAD(name)
· 功能 定义链表头节点变量，并初始化
· 参数 name：头节点变量名
2.4.2. INIT_HLIST_HEAD
· 原型 INIT_HLIST_HEAD(ptr)
· 功能 初始化链表头节点
· 参数 ptr：头节点指针
2.4.3. INIT_HLIST_NODE
· 原型 void INIT_HLIST_NODE(struct hlist_node *h)
· 功能 初始化中间节点（将next、pprev置NULL）
· 参数 h：节点指针
2.4.4. hlist_unhashed
· 原型 int hlist_unhashed(const struct hlist_node *h)
· 功能 节点是否没有加入到链表
· 参数 h：节点指针
2.4.5. hlist_empty
· 原型 int hlist_empty(const struct hlist_head *h)
· 功能 链表是否为空
· 参数 h：头节点指针
2.4.6. hlist_del
· 原型 void hlist_del(struct hlist_node *n)
· 功能 删除节点，并将节点的next、pprev置为非空的无效指针。
· 参数 h：待删除节点的指针
2.4.7. hlist_del_init
· 原型 void hlist_del_init(struct hlist_node *n)
· 功能 删除节点，并将节点的next、pprev置为NULL。
· 参数 h：待删除节点的指针
2.4.8. hlist_add_head
· 原型 void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
· 功能 将节点加入到链表的头部
· 参数 n：节点的指针 h：头节点的指针
2.4.9. hlist_add_before
· 原型 void hlist_add_before(struct hlist_node *n, struct hlist_node *next)
· 功能 将新节点加入到当前节点之前
· 参数 n：新节点 next：当前节点
· 说明 n、next不能为空
2.4.10. hlist_add_after
· 原型 void hlist_add_after(struct hlist_node *n, struct hlist_node *next)
· 功能 将新节点加入到当前节点之后
· 参数 n：当前节点 next：新节点
· 说明 n、next不能为空
2.4.11. hlist_entry
· 原型 hlist_entry(ptr, type, member)
· 功能 获取包含该节点成员的数据结构的指针
· 参数 ptr：struct hlist_node成员的指针 type：struct hlist_node所在数据结构的类型 member：struct hlist_node的成员名
2.4.12. hlist_for_each
· 原型 hlist_for_each(pos, head)
· 功能 遍历链表所有节点
· 参数 pos：struct hlist_node成员的指针 head：链表的头节点指针
· 说明 需根据pos调用hlist_entry转换为struct hlist_node所在数据结构的指针后再使用； 遍历完后，pos指向的是空。
2.4.13. hlist_for_each_safe
· 原型 hlist_for_each_safe(pos, n, head)
· 功能 遍历链表所有节点，允许有节点删除的操作
· 参数 pos：struct hlist_node成员的指针 n：临时变量，struct hlist_node的指针 head：链表的头节点指针
· 说明 需根据pos调用hlist_entry转换为struct hlist_node所在数据结构的指针后再使用； 遍历完后，pos指向的是空。
2.4.14. hlist_for_each_entry
· 原型 hlist_for_each_entry(tpos, pos, head, member)
· 功能 遍历链表所有节点
· 参数 tpos：struct hlist_node所在数据结构的指针 pos：struct hlist_node成员的指针 head：链表的头节点指针 member：struct hlist_node的成员名
· 说明 遍历完后，pos指向的是空。
2.4.15. hlist_for_each_entry_continue
· 原型 hlist_for_each_entry_continue(tpos, pos, member)
· 功能 从当前节点之后遍历链表
· 参数 tpos：struct hlist_node所在数据结构的指针 pos：struct hlist_node成员的指针，当前节点 member：struct hlist_node的成员名
· 说明 遍历完后，pos指向的是空。
2.4.16. hlist_for_each_entry_from
· 原型 hlist_for_each_entry_from(tpos, pos, member)
· 功能 从当前节点开始遍历链表
· 参数 tpos：struct hlist_node所在数据结构的指针,当前节点 pos：struct hlist_node成员的指针，当前节点（也就是&tpos->member) member：struct hlist_node的成员名
· 说明 遍历完后，pos指向的是空。
2.4.17. hlist_for_each_entry_safe
· 原型 hlist_for_each_entry_safe(tpos, pos, n, head, member)
· 功能 遍历链表所有节点，允许有节点删除的操作。
· 参数 tpos：struct hlist_node所在数据结构的指针 pos：struct hlist_node成员的指针 n：临时变量，struct hlist_node成员的指针 head：链表的头节点指针 member：struct hlist_node的成员名
· 说明 遍历完后，pos指向的是空。
3. 示例
HASH实现
/* 注：本例重点是HASH表的实现，忽略了其他一些代码*/ #include#define ADJ_TBL_HASH_MASK 0x1FFFF /* 定义桶大小 */ /* 关键字 */struct adj_key{ u16 vrf_id; u16 l3_ifindex; u16 l2_ifindex; u16 pad1; union{ u32 addr4; struct in6_addr addr6; } nexthop;}; /* 定义链表节点 */struct adjacency{ struct hlist_node hlist; struct adj_key key;}; /* HASH表 */struct adjacency_table { struct hlist_head *buckets; int mask; int cnt;}; struct adjacency_table adj_tbl; /* 计算HASH值 */u32 adj_hash(struct adj_key *pkey){ int i, *p32, hash_val; for (i = 0, p32=(int *)pkey, hash_val = 0; i < (sizeof(struct adj_key) / sizeof(int)); i++) hash_val ^= *p32++; return hash_val & ADJ_TBL_HASH_MASK;} /* 分配并初始化HASH桶 */void adj_table_init(){ adj_tbl.buckets = malloc(sizeof(struct hlist_head) * (ADJ_TBL_HASH_MASK + 1)); memset(adj_tbl.buckets, 0, sizeof(struct hlist_head) * (ADJ_TBL_HASH_MASK + 1)); adj_tbl.mask = ADJ_TBL_HASH_MASK; adj_tbl.cnt = 0;} /* 根据关键字查找节点 */struct adjacency *adj_lookup(struct adj_key *pkey){ struct adjacency *e; struct hlist_node *node; u32 hash_val = adj_hash(pkey); adj_lock(); hlist_for_each_entry(e, node, &adj_tbl.buckets[hash_val], hlist) { if (memcmp(pkey, &e->key, sizeof(struct adj_key)) == 0) { adj_unlock(); return e; } } adj_unlock(); return NULL;} /* 创建节点并加入HASH表 */struct adjacency *adj_create(struct adj_key *pkey){ struct adjacency *e; int ret; e = adj_alloc(); if (e == NULL) { return NULL; } e->key = *pkey; adj_lock(); hlist_add_head(&e->hlist, &adj_tbl.buckets[adj_hash(pkey)]); adj_tbl.cnt++; adj_unlock(); return e;} /* 删除节点 */void adj_destroy(struct adjacency *e){ adj_lock(); hlist_del(&e->hlist); adj_tbl.cnt--; adj_unlock();}
转载地址：http://ifqci.baihongyu.com/