在 Linux 内核中,hlist(哈希链表)是一种高效的数据结构,用于存储和管理数据
- 定义 hlist_node 结构体:
struct hlist_node { struct hlist_node *next; struct hlist_node **pprev; };
- 定义 hlist_head 结构体:
struct hlist_head { struct hlist_node *first; };
- 初始化 hlist_head:
#define HLIST_HEAD_INIT { .first = NULL } #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
- 初始化 hlist_node:
#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
- 向 hlist 中添加节点:
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; }
- 从 hlist 中删除节点:
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; }
在这个例子中,我们首先定义了 hlist_node 和 hlist_head 结构体。然后,我们提供了初始化这些结构体的宏。接下来,我们实现了向 hlist 中添加节点的函数 hlist_add_head()。最后,我们实现了从 hlist 中删除节点的函数 hlist_del()。
在 hlist_del() 函数中,我们首先获取要删除节点的下一个节点(next)和前一个节点的指针(pprev)。然后,我们将前一个节点的指针指向下一个节点。如果下一个节点存在,我们将其 pprev 指针指向前一个节点的指针。这样,我们就从 hlist 中删除了指定的节点。