1 /* $NetBSD: hash.c,v 1.1.1.2 2009/12/02 00:26:11 haad Exp $ */
2
3 /*
4 * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.
5 * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved.
6 *
7 * This file is part of the device-mapper userspace tools.
8 *
9 * This copyrighted material is made available to anyone wishing to use,
10 * modify, copy, or redistribute it subject to the terms and conditions
11 * of the GNU Lesser General Public License v.2.1.
12 *
13 * You should have received a copy of the GNU Lesser General Public License
14 * along with this program; if not, write to the Free Software Foundation,
15 * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 */
17
18 #include "dmlib.h"
19
20 struct dm_hash_node {
21 struct dm_hash_node *next;
22 void *data;
23 unsigned keylen;
24 char key[0];
25 };
26
27 struct dm_hash_table {
28 unsigned num_nodes;
29 unsigned num_slots;
30 struct dm_hash_node **slots;
31 };
32
33 /* Permutation of the Integers 0 through 255 */
34 static unsigned char _nums[] = {
35 1, 14, 110, 25, 97, 174, 132, 119, 138, 170, 125, 118, 27, 233, 140, 51,
36 87, 197, 177, 107, 234, 169, 56, 68, 30, 7, 173, 73, 188, 40, 36, 65,
37 49, 213, 104, 190, 57, 211, 148, 223, 48, 115, 15, 2, 67, 186, 210, 28,
38 12, 181, 103, 70, 22, 58, 75, 78, 183, 167, 238, 157, 124, 147, 172,
39 144,
40 176, 161, 141, 86, 60, 66, 128, 83, 156, 241, 79, 46, 168, 198, 41, 254,
41 178, 85, 253, 237, 250, 154, 133, 88, 35, 206, 95, 116, 252, 192, 54,
42 221,
43 102, 218, 255, 240, 82, 106, 158, 201, 61, 3, 89, 9, 42, 155, 159, 93,
44 166, 80, 50, 34, 175, 195, 100, 99, 26, 150, 16, 145, 4, 33, 8, 189,
45 121, 64, 77, 72, 208, 245, 130, 122, 143, 55, 105, 134, 29, 164, 185,
46 194,
47 193, 239, 101, 242, 5, 171, 126, 11, 74, 59, 137, 228, 108, 191, 232,
48 139,
49 6, 24, 81, 20, 127, 17, 91, 92, 251, 151, 225, 207, 21, 98, 113, 112,
50 84, 226, 18, 214, 199, 187, 13, 32, 94, 220, 224, 212, 247, 204, 196,
51 43,
52 249, 236, 45, 244, 111, 182, 153, 136, 129, 90, 217, 202, 19, 165, 231,
53 71,
54 230, 142, 96, 227, 62, 179, 246, 114, 162, 53, 160, 215, 205, 180, 47,
55 109,
56 44, 38, 31, 149, 135, 0, 216, 52, 63, 23, 37, 69, 39, 117, 146, 184,
57 163, 200, 222, 235, 248, 243, 219, 10, 152, 131, 123, 229, 203, 76, 120,
58 209
59 };
60
_create_node(const char * str,unsigned len)61 static struct dm_hash_node *_create_node(const char *str, unsigned len)
62 {
63 struct dm_hash_node *n = dm_malloc(sizeof(*n) + len);
64
65 if (n) {
66 memcpy(n->key, str, len);
67 n->keylen = len;
68 }
69
70 return n;
71 }
72
_hash(const char * str,unsigned len)73 static unsigned long _hash(const char *str, unsigned len)
74 {
75 unsigned long h = 0, g;
76 unsigned i;
77
78 for (i = 0; i < len; i++) {
79 h <<= 4;
80 h += _nums[(unsigned char) *str++];
81 g = h & ((unsigned long) 0xf << 16u);
82 if (g) {
83 h ^= g >> 16u;
84 h ^= g >> 5u;
85 }
86 }
87
88 return h;
89 }
90
dm_hash_create(unsigned size_hint)91 struct dm_hash_table *dm_hash_create(unsigned size_hint)
92 {
93 size_t len;
94 unsigned new_size = 16u;
95 struct dm_hash_table *hc = dm_malloc(sizeof(*hc));
96
97 if (!hc) {
98 stack;
99 return 0;
100 }
101
102 memset(hc, 0, sizeof(*hc));
103
104 /* round size hint up to a power of two */
105 while (new_size < size_hint)
106 new_size = new_size << 1;
107
108 hc->num_slots = new_size;
109 len = sizeof(*(hc->slots)) * new_size;
110 if (!(hc->slots = dm_malloc(len))) {
111 stack;
112 goto bad;
113 }
114 memset(hc->slots, 0, len);
115 return hc;
116
117 bad:
118 dm_free(hc->slots);
119 dm_free(hc);
120 return 0;
121 }
122
_free_nodes(struct dm_hash_table * t)123 static void _free_nodes(struct dm_hash_table *t)
124 {
125 struct dm_hash_node *c, *n;
126 unsigned i;
127
128 for (i = 0; i < t->num_slots; i++)
129 for (c = t->slots[i]; c; c = n) {
130 n = c->next;
131 dm_free(c);
132 }
133 }
134
dm_hash_destroy(struct dm_hash_table * t)135 void dm_hash_destroy(struct dm_hash_table *t)
136 {
137 _free_nodes(t);
138 dm_free(t->slots);
139 dm_free(t);
140 }
141
_find(struct dm_hash_table * t,const char * key,uint32_t len)142 static struct dm_hash_node **_find(struct dm_hash_table *t, const char *key,
143 uint32_t len)
144 {
145 unsigned h = _hash(key, len) & (t->num_slots - 1);
146 struct dm_hash_node **c;
147
148 for (c = &t->slots[h]; *c; c = &((*c)->next)) {
149 if ((*c)->keylen != len)
150 continue;
151
152 if (!memcmp(key, (*c)->key, len))
153 break;
154 }
155
156 return c;
157 }
158
dm_hash_lookup_binary(struct dm_hash_table * t,const char * key,uint32_t len)159 void *dm_hash_lookup_binary(struct dm_hash_table *t, const char *key,
160 uint32_t len)
161 {
162 struct dm_hash_node **c = _find(t, key, len);
163
164 return *c ? (*c)->data : 0;
165 }
166
dm_hash_insert_binary(struct dm_hash_table * t,const char * key,uint32_t len,void * data)167 int dm_hash_insert_binary(struct dm_hash_table *t, const char *key,
168 uint32_t len, void *data)
169 {
170 struct dm_hash_node **c = _find(t, key, len);
171
172 if (*c)
173 (*c)->data = data;
174 else {
175 struct dm_hash_node *n = _create_node(key, len);
176
177 if (!n)
178 return 0;
179
180 n->data = data;
181 n->next = 0;
182 *c = n;
183 t->num_nodes++;
184 }
185
186 return 1;
187 }
188
dm_hash_remove_binary(struct dm_hash_table * t,const char * key,uint32_t len)189 void dm_hash_remove_binary(struct dm_hash_table *t, const char *key,
190 uint32_t len)
191 {
192 struct dm_hash_node **c = _find(t, key, len);
193
194 if (*c) {
195 struct dm_hash_node *old = *c;
196 *c = (*c)->next;
197 dm_free(old);
198 t->num_nodes--;
199 }
200 }
201
dm_hash_lookup(struct dm_hash_table * t,const char * key)202 void *dm_hash_lookup(struct dm_hash_table *t, const char *key)
203 {
204 return dm_hash_lookup_binary(t, key, strlen(key) + 1);
205 }
206
dm_hash_insert(struct dm_hash_table * t,const char * key,void * data)207 int dm_hash_insert(struct dm_hash_table *t, const char *key, void *data)
208 {
209 return dm_hash_insert_binary(t, key, strlen(key) + 1, data);
210 }
211
dm_hash_remove(struct dm_hash_table * t,const char * key)212 void dm_hash_remove(struct dm_hash_table *t, const char *key)
213 {
214 dm_hash_remove_binary(t, key, strlen(key) + 1);
215 }
216
dm_hash_get_num_entries(struct dm_hash_table * t)217 unsigned dm_hash_get_num_entries(struct dm_hash_table *t)
218 {
219 return t->num_nodes;
220 }
221
dm_hash_iter(struct dm_hash_table * t,dm_hash_iterate_fn f)222 void dm_hash_iter(struct dm_hash_table *t, dm_hash_iterate_fn f)
223 {
224 struct dm_hash_node *c, *n;
225 unsigned i;
226
227 for (i = 0; i < t->num_slots; i++)
228 for (c = t->slots[i]; c; c = n) {
229 n = c->next;
230 f(c->data);
231 }
232 }
233
dm_hash_wipe(struct dm_hash_table * t)234 void dm_hash_wipe(struct dm_hash_table *t)
235 {
236 _free_nodes(t);
237 memset(t->slots, 0, sizeof(struct dm_hash_node *) * t->num_slots);
238 t->num_nodes = 0u;
239 }
240
dm_hash_get_key(struct dm_hash_table * t __attribute ((unused)),struct dm_hash_node * n)241 char *dm_hash_get_key(struct dm_hash_table *t __attribute((unused)),
242 struct dm_hash_node *n)
243 {
244 return n->key;
245 }
246
dm_hash_get_data(struct dm_hash_table * t __attribute ((unused)),struct dm_hash_node * n)247 void *dm_hash_get_data(struct dm_hash_table *t __attribute((unused)),
248 struct dm_hash_node *n)
249 {
250 return n->data;
251 }
252
_next_slot(struct dm_hash_table * t,unsigned s)253 static struct dm_hash_node *_next_slot(struct dm_hash_table *t, unsigned s)
254 {
255 struct dm_hash_node *c = NULL;
256 unsigned i;
257
258 for (i = s; i < t->num_slots && !c; i++)
259 c = t->slots[i];
260
261 return c;
262 }
263
dm_hash_get_first(struct dm_hash_table * t)264 struct dm_hash_node *dm_hash_get_first(struct dm_hash_table *t)
265 {
266 return _next_slot(t, 0);
267 }
268
dm_hash_get_next(struct dm_hash_table * t,struct dm_hash_node * n)269 struct dm_hash_node *dm_hash_get_next(struct dm_hash_table *t, struct dm_hash_node *n)
270 {
271 unsigned h = _hash(n->key, n->keylen) & (t->num_slots - 1);
272
273 return n->next ? n->next : _next_slot(t, h + 1);
274 }
275