]>
Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
1da177e4 LT |
2 | /* |
3 | * Implementation of the hash table type. | |
4 | * | |
7efbb60b | 5 | * Author : Stephen Smalley, <sds@tycho.nsa.gov> |
1da177e4 LT |
6 | */ |
7 | #include <linux/kernel.h> | |
8 | #include <linux/slab.h> | |
9 | #include <linux/errno.h> | |
ed1c9642 | 10 | #include <linux/sched.h> |
1da177e4 LT |
11 | #include "hashtab.h" |
12 | ||
bb242497 | 13 | struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key), |
719a2f8e EP |
14 | int (*keycmp)(struct hashtab *h, const void *key1, const void *key2), |
15 | u32 size) | |
1da177e4 LT |
16 | { |
17 | struct hashtab *p; | |
18 | u32 i; | |
19 | ||
89d155ef | 20 | p = kzalloc(sizeof(*p), GFP_KERNEL); |
cb8d21e3 | 21 | if (!p) |
1da177e4 LT |
22 | return p; |
23 | ||
1da177e4 LT |
24 | p->size = size; |
25 | p->nel = 0; | |
26 | p->hash_value = hash_value; | |
27 | p->keycmp = keycmp; | |
2f00e680 | 28 | p->htable = kmalloc_array(size, sizeof(*p->htable), GFP_KERNEL); |
cb8d21e3 | 29 | if (!p->htable) { |
1da177e4 LT |
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 | ||
40 | int hashtab_insert(struct hashtab *h, void *key, void *datum) | |
41 | { | |
42 | u32 hvalue; | |
43 | struct hashtab_node *prev, *cur, *newnode; | |
44 | ||
ed1c9642 DJ |
45 | cond_resched(); |
46 | ||
1da177e4 LT |
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 | ||
89d155ef | 61 | newnode = kzalloc(sizeof(*newnode), GFP_KERNEL); |
cb8d21e3 | 62 | if (!newnode) |
1da177e4 | 63 | return -ENOMEM; |
1da177e4 LT |
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 | ||
bb242497 | 78 | void *hashtab_search(struct hashtab *h, const void *key) |
1da177e4 LT |
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]; | |
dbc74c65 | 88 | while (cur && h->keycmp(h, key, cur->key) > 0) |
1da177e4 LT |
89 | cur = cur->next; |
90 | ||
cb8d21e3 | 91 | if (!cur || (h->keycmp(h, key, cur->key) != 0)) |
1da177e4 LT |
92 | return NULL; |
93 | ||
94 | return cur->datum; | |
95 | } | |
96 | ||
97 | void 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]; | |
dbc74c65 | 107 | while (cur) { |
1da177e4 LT |
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 | ||
121 | int 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]; | |
dbc74c65 | 134 | while (cur) { |
1da177e4 LT |
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 | ||
145 | void 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 | } |