当前位置：首页 > article >正文

linux内核数据结构之哈希表

article 2025/2/22 11:55:25

1数据结构

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next;
    struct hlist_node **pprev;
};

2 操作函数

初始化

struct hlist_head *hash_table;
//初始化
for (i = 0; i < 1024; i++) {
	INIT_HLIST_NODE(&hash_table[i]);
}

赋值

struct vsd_node {
struct hlist_node hash_node;
u16 vsd_id;
u8 local_id;
u8  act_id;
} ;
u32 hash_index;
struct vsd_node *new_node;
new_node->vsd_id = 10;
new_node->local_id = 11;
new_node->act_id =15;

hash_index = (vsd_id + local_id )%(1024);

hlist_add_head(&new_node->hash_node,&hash_table[hash_index]);

3底层实现

static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
 h->next = NULL;
 h->pprev = NULL;
}

/**
 * hlist_add_head - add a new entry at the beginning of the hlist
 * @n: new entry to be added
 * @h: hlist head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
 struct hlist_node *first = h->first;
 WRITE_ONCE(n->next, first);
 if (first)
  WRITE_ONCE(first->pprev, &n->next);
 WRITE_ONCE(h->first, n);
 WRITE_ONCE(n->pprev, &h->first);
}