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