1
2
3
4
5
6
7#include <linux/kernel.h>
8#include <linux/slab.h>
9#include <linux/errno.h>
10#include <linux/sched.h>
11#include "hashtab.h"
12
13struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key),
14 int (*keycmp)(struct hashtab *h, const void *key1, const void *key2),
15 u32 size)
16{
17 struct hashtab *p;
18 u32 i;
19
20 p = kzalloc(sizeof(*p), GFP_KERNEL);
21 if (!p)
22 return p;
23
24 p->size = size;
25 p->nel = 0;
26 p->hash_value = hash_value;
27 p->keycmp = keycmp;
28 p->htable = kmalloc_array(size, sizeof(*p->htable), GFP_KERNEL);
29 if (!p->htable) {
30 kfree(p);
31 return NULL;
32 }
33
34 for (i = 0; i < size; i++)
35 p->htable[i] = NULL;
36
37 return p;
38}
39
40int hashtab_insert(struct hashtab *h, void *key, void *datum)
41{
42 u32 hvalue;
43 struct hashtab_node *prev, *cur, *newnode;
44
45 cond_resched();
46
47 if (!h || h->nel == HASHTAB_MAX_NODES)
48 return -EINVAL;
49
50 hvalue = h->hash_value(h, key);
51 prev = NULL;
52 cur = h->htable[hvalue];
53 while (cur && h->keycmp(h, key, cur->key) > 0) {
54 prev = cur;
55 cur = cur->next;
56 }
57
58 if (cur && (h->keycmp(h, key, cur->key) == 0))
59 return -EEXIST;
60
61 newnode = kzalloc(sizeof(*newnode), GFP_KERNEL);
62 if (!newnode)
63 return -ENOMEM;
64 newnode->key = key;
65 newnode->datum = datum;
66 if (prev) {
67 newnode->next = prev->next;
68 prev->next = newnode;
69 } else {
70 newnode->next = h->htable[hvalue];
71 h->htable[hvalue] = newnode;
72 }
73
74 h->nel++;
75 return 0;
76}
77
78void *hashtab_search(struct hashtab *h, const void *key)
79{
80 u32 hvalue;
81 struct hashtab_node *cur;
82
83 if (!h)
84 return NULL;
85
86 hvalue = h->hash_value(h, key);
87 cur = h->htable[hvalue];
88 while (cur && h->keycmp(h, key, cur->key) > 0)
89 cur = cur->next;
90
91 if (!cur || (h->keycmp(h, key, cur->key) != 0))
92 return NULL;
93
94 return cur->datum;
95}
96
97void hashtab_destroy(struct hashtab *h)
98{
99 u32 i;
100 struct hashtab_node *cur, *temp;
101
102 if (!h)
103 return;
104
105 for (i = 0; i < h->size; i++) {
106 cur = h->htable[i];
107 while (cur) {
108 temp = cur;
109 cur = cur->next;
110 kfree(temp);
111 }
112 h->htable[i] = NULL;
113 }
114
115 kfree(h->htable);
116 h->htable = NULL;
117
118 kfree(h);
119}
120
121int hashtab_map(struct hashtab *h,
122 int (*apply)(void *k, void *d, void *args),
123 void *args)
124{
125 u32 i;
126 int ret;
127 struct hashtab_node *cur;
128
129 if (!h)
130 return 0;
131
132 for (i = 0; i < h->size; i++) {
133 cur = h->htable[i];
134 while (cur) {
135 ret = apply(cur->key, cur->datum, args);
136 if (ret)
137 return ret;
138 cur = cur->next;
139 }
140 }
141 return 0;
142}
143
144
145void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
146{
147 u32 i, chain_len, slots_used, max_chain_len;
148 struct hashtab_node *cur;
149
150 slots_used = 0;
151 max_chain_len = 0;
152 for (slots_used = max_chain_len = i = 0; i < h->size; i++) {
153 cur = h->htable[i];
154 if (cur) {
155 slots_used++;
156 chain_len = 0;
157 while (cur) {
158 chain_len++;
159 cur = cur->next;
160 }
161
162 if (chain_len > max_chain_len)
163 max_chain_len = chain_len;
164 }
165 }
166
167 info->slots_used = slots_used;
168 info->max_chain_len = max_chain_len;
169}
170