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