linux kernel 下的hash 和链表 应用_linux 内核 hash 表 大小

记得很久以前，写linux 内核模块的时候，使用linux内核态下的hash表，非常简单好用，这个也可以用在用户态，linux上或者windows上都可以使用。

1、定义一个节点node

#include "hlist.h"
typedef struct node {  
	unsigned char ch;
	int  this_data;

	struct list_head  i_list;
	struct hlist_node i_hash;

	char str_data[32];
	int end_data;
} *pnode;
1
2
3
4
5
6
7
8
9
10
11

2、加入hash的size

#define HASHSIZE 0xff
这里可以自己修改大小的

2.1 定义hash算法函数

这个函数定义的比较简单，简单使用整形，不超过hash表的大小

unsigned int gethash(int c)  
{  
    return (c & HASHSIZE);  
} 
1
2
3
4

2.2 如果key为字符串，也可以使用字符算hash函数

	//加法hash,需要平均分配到各个线程中
	static int hash_add(const char* key, int prime)
	{

		int hash, i;
		int len = strlen(key);
		for (hash = len, i = 0; i < len; i++)
			hash += key[i];
		return (hash % prime);
	}
1
2
3
4
5
6
7
8
9
10

3、写几个添加删除的函数

//插入函数
int node_insert(int value)
{
	struct node *p = (pnode)malloc(sizeof(*p));
	if (!p) {
		printf("malloc failed.\n");
		return -1;
	}
	p->this_data = value;
	sprintf(p->str_data, "data:%d", value);
	int hash = gethash(value);
	if (hash < HASHSIZE)
	{
		hlist_add_head(&p->i_hash, &hlist[hash]);
		return 0;
	}
	return -1;
}
//搜索函数
struct node * node_search(int value)
{
	struct hlist_node *hp;
	int hash = gethash(value);
	hlist_for_each(hp, &hlist[hash]) {
		struct node *p = hlist_entry(hp, struct node, i_hash);
		if (value == p->this_data)
		{
			return p;
		}
	}
	return NULL;
}
//删除函数
int node_delete(int value)
{
	int hash,num = 0;
	struct hlist_node *hp;
	struct hlist_node *hn;
	hash = gethash(value);
	hlist_for_each_safe(hp, hn, &hlist[hash]) {
		struct node *p = hlist_entry(hp, struct node, i_hash);
		printf("hlist_del: %s\n", p->str_data);
		if(value == p->this_data)
		hlist_del(hp);
		++num;
	}
	return num;
}
//清空所有
int node_delete_all()
{
	struct hlist_node *hp;
	struct hlist_node *hn;
	for (int i = 0; i < HASHSIZE; i++)
	{
		hlist_for_each_safe(hp, hn, &hlist[i])
		{
			struct node* p = hlist_entry(hp, struct node, i_hash);
			hlist_del(hp);
			free(p);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

最后写测试函数main

int main(int argc, char* argv[])
{
    unsigned int hash;  
	//struct list_head *list;
 
  
    for (hash = 0; hash <= HASHSIZE; hash++) {  
        INIT_HLIST_HEAD(&hlist[hash]);  
    }  
  
	for (int i = 10; i < 106; i++)
	{
		node_insert(i);
	}

	for (int i = 12; i < 30; i++)
	{
		pnode v = node_search(i);
		if (v != NULL)
		{
			printf("find it:%s\n", v->str_data);
		}
	}
	pnode v = node_search(1000);
	if (v == NULL)
		printf("not find it\n");
	node_delete_all();

    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

在windows下使用vs2017 执行，没有一个警告，执行结果快速正常
在linux下使用cmake 编译执行，一样没有一个警告，正常执行。
这种c写的代码非常好用，而且有一个好处是，嵌入式下不用依赖任何库，灵活，短短几乎话，既可以做链表，又可以做hash表，好用！
如果用户找不到hlist.h,可以从我这里直接下载，包含windows vs2017工程，linux cmakefile 文件，centos7 和 windows 测试。
hlist通用hash表