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