]>
Commit | Line | Data |
---|---|---|
1 | /* | |
2 | * libkmod - interface to kernel module operations | |
3 | * | |
4 | * Copyright (C) 2011-2013 ProFUSION embedded systems | |
5 | * | |
6 | * This library is free software; you can redistribute it and/or | |
7 | * modify it under the terms of the GNU Lesser General Public | |
8 | * License as published by the Free Software Foundation; either | |
9 | * version 2.1 of the License, or (at your option) any later version. | |
10 | * | |
11 | * This library is distributed in the hope that it will be useful, | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * Lesser General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU Lesser General Public | |
17 | * License along with this library; if not, see <http://www.gnu.org/licenses/>. | |
18 | */ | |
19 | ||
20 | #include <errno.h> | |
21 | #include <inttypes.h> | |
22 | #include <stdlib.h> | |
23 | #include <string.h> | |
24 | ||
25 | #include <shared/hash.h> | |
26 | #include <shared/util.h> | |
27 | ||
28 | struct hash_entry { | |
29 | const char *key; | |
30 | const void *value; | |
31 | }; | |
32 | ||
33 | struct hash_bucket { | |
34 | struct hash_entry *entries; | |
35 | unsigned int used; | |
36 | unsigned int total; | |
37 | }; | |
38 | ||
39 | struct hash { | |
40 | unsigned int count; | |
41 | unsigned int step; | |
42 | unsigned int n_buckets; | |
43 | void (*free_value)(void *value); | |
44 | struct hash_bucket buckets[]; | |
45 | }; | |
46 | ||
47 | struct hash *hash_new(unsigned int n_buckets, | |
48 | void (*free_value)(void *value)) | |
49 | { | |
50 | struct hash *hash; | |
51 | ||
52 | n_buckets = ALIGN_POWER2(n_buckets); | |
53 | hash = calloc(1, sizeof(struct hash) + | |
54 | n_buckets * sizeof(struct hash_bucket)); | |
55 | if (hash == NULL) | |
56 | return NULL; | |
57 | hash->n_buckets = n_buckets; | |
58 | hash->free_value = free_value; | |
59 | hash->step = n_buckets / 32; | |
60 | if (hash->step == 0) | |
61 | hash->step = 4; | |
62 | else if (hash->step > 64) | |
63 | hash->step = 64; | |
64 | return hash; | |
65 | } | |
66 | ||
67 | void hash_free(struct hash *hash) | |
68 | { | |
69 | struct hash_bucket *bucket, *bucket_end; | |
70 | ||
71 | if (hash == NULL) | |
72 | return; | |
73 | ||
74 | bucket = hash->buckets; | |
75 | bucket_end = bucket + hash->n_buckets; | |
76 | for (; bucket < bucket_end; bucket++) { | |
77 | if (hash->free_value) { | |
78 | struct hash_entry *entry, *entry_end; | |
79 | entry = bucket->entries; | |
80 | entry_end = entry + bucket->used; | |
81 | for (; entry < entry_end; entry++) | |
82 | hash->free_value((void *)entry->value); | |
83 | } | |
84 | free(bucket->entries); | |
85 | } | |
86 | free(hash); | |
87 | } | |
88 | ||
89 | static inline unsigned int hash_superfast(const char *key, unsigned int len) | |
90 | { | |
91 | /* Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html) | |
92 | * used by WebCore (http://webkit.org/blog/8/hashtables-part-2/) | |
93 | * EFL's eina and possible others. | |
94 | */ | |
95 | unsigned int tmp, hash = len, rem = len & 3; | |
96 | ||
97 | len /= 4; | |
98 | ||
99 | /* Main loop */ | |
100 | for (; len > 0; len--) { | |
101 | hash += get_unaligned((uint16_t *) key); | |
102 | tmp = (get_unaligned((uint16_t *)(key + 2)) << 11) ^ hash; | |
103 | hash = (hash << 16) ^ tmp; | |
104 | key += 4; | |
105 | hash += hash >> 11; | |
106 | } | |
107 | ||
108 | /* Handle end cases */ | |
109 | switch (rem) { | |
110 | case 3: | |
111 | hash += get_unaligned((uint16_t *) key); | |
112 | hash ^= hash << 16; | |
113 | hash ^= key[2] << 18; | |
114 | hash += hash >> 11; | |
115 | break; | |
116 | ||
117 | case 2: | |
118 | hash += get_unaligned((uint16_t *) key); | |
119 | hash ^= hash << 11; | |
120 | hash += hash >> 17; | |
121 | break; | |
122 | ||
123 | case 1: | |
124 | hash += *key; | |
125 | hash ^= hash << 10; | |
126 | hash += hash >> 1; | |
127 | } | |
128 | ||
129 | /* Force "avalanching" of final 127 bits */ | |
130 | hash ^= hash << 3; | |
131 | hash += hash >> 5; | |
132 | hash ^= hash << 4; | |
133 | hash += hash >> 17; | |
134 | hash ^= hash << 25; | |
135 | hash += hash >> 6; | |
136 | ||
137 | return hash; | |
138 | } | |
139 | ||
140 | /* | |
141 | * add or replace key in hash map. | |
142 | * | |
143 | * none of key or value are copied, just references are remembered as is, | |
144 | * make sure they are live while pair exists in hash! | |
145 | */ | |
146 | int hash_add(struct hash *hash, const char *key, const void *value) | |
147 | { | |
148 | unsigned int keylen = strlen(key); | |
149 | unsigned int hashval = hash_superfast(key, keylen); | |
150 | unsigned int pos = hashval & (hash->n_buckets - 1); | |
151 | struct hash_bucket *bucket = hash->buckets + pos; | |
152 | struct hash_entry *entry, *entry_end; | |
153 | ||
154 | if (bucket->used + 1 >= bucket->total) { | |
155 | unsigned new_total = bucket->total + hash->step; | |
156 | size_t size = new_total * sizeof(struct hash_entry); | |
157 | struct hash_entry *tmp = realloc(bucket->entries, size); | |
158 | if (tmp == NULL) | |
159 | return -errno; | |
160 | bucket->entries = tmp; | |
161 | bucket->total = new_total; | |
162 | } | |
163 | ||
164 | entry = bucket->entries; | |
165 | entry_end = entry + bucket->used; | |
166 | for (; entry < entry_end; entry++) { | |
167 | int c = strcmp(key, entry->key); | |
168 | if (c == 0) { | |
169 | if (hash->free_value) | |
170 | hash->free_value((void *)entry->value); | |
171 | entry->key = key; | |
172 | entry->value = value; | |
173 | return 0; | |
174 | } else if (c < 0) { | |
175 | memmove(entry + 1, entry, | |
176 | (entry_end - entry) * sizeof(struct hash_entry)); | |
177 | break; | |
178 | } | |
179 | } | |
180 | ||
181 | entry->key = key; | |
182 | entry->value = value; | |
183 | bucket->used++; | |
184 | hash->count++; | |
185 | return 0; | |
186 | } | |
187 | ||
188 | /* similar to hash_add(), but fails if key already exists */ | |
189 | int hash_add_unique(struct hash *hash, const char *key, const void *value) | |
190 | { | |
191 | unsigned int keylen = strlen(key); | |
192 | unsigned int hashval = hash_superfast(key, keylen); | |
193 | unsigned int pos = hashval & (hash->n_buckets - 1); | |
194 | struct hash_bucket *bucket = hash->buckets + pos; | |
195 | struct hash_entry *entry, *entry_end; | |
196 | ||
197 | if (bucket->used + 1 >= bucket->total) { | |
198 | unsigned new_total = bucket->total + hash->step; | |
199 | size_t size = new_total * sizeof(struct hash_entry); | |
200 | struct hash_entry *tmp = realloc(bucket->entries, size); | |
201 | if (tmp == NULL) | |
202 | return -errno; | |
203 | bucket->entries = tmp; | |
204 | bucket->total = new_total; | |
205 | } | |
206 | ||
207 | entry = bucket->entries; | |
208 | entry_end = entry + bucket->used; | |
209 | for (; entry < entry_end; entry++) { | |
210 | int c = strcmp(key, entry->key); | |
211 | if (c == 0) | |
212 | return -EEXIST; | |
213 | else if (c < 0) { | |
214 | memmove(entry + 1, entry, | |
215 | (entry_end - entry) * sizeof(struct hash_entry)); | |
216 | break; | |
217 | } | |
218 | } | |
219 | ||
220 | entry->key = key; | |
221 | entry->value = value; | |
222 | bucket->used++; | |
223 | hash->count++; | |
224 | return 0; | |
225 | } | |
226 | ||
227 | static int hash_entry_cmp(const void *pa, const void *pb) | |
228 | { | |
229 | const struct hash_entry *a = pa; | |
230 | const struct hash_entry *b = pb; | |
231 | return strcmp(a->key, b->key); | |
232 | } | |
233 | ||
234 | void *hash_find(const struct hash *hash, const char *key) | |
235 | { | |
236 | unsigned int keylen = strlen(key); | |
237 | unsigned int hashval = hash_superfast(key, keylen); | |
238 | unsigned int pos = hashval & (hash->n_buckets - 1); | |
239 | const struct hash_bucket *bucket = hash->buckets + pos; | |
240 | const struct hash_entry se = { | |
241 | .key = key, | |
242 | .value = NULL | |
243 | }; | |
244 | const struct hash_entry *entry = bsearch( | |
245 | &se, bucket->entries, bucket->used, | |
246 | sizeof(struct hash_entry), hash_entry_cmp); | |
247 | if (entry == NULL) | |
248 | return NULL; | |
249 | return (void *)entry->value; | |
250 | } | |
251 | ||
252 | int hash_del(struct hash *hash, const char *key) | |
253 | { | |
254 | unsigned int keylen = strlen(key); | |
255 | unsigned int hashval = hash_superfast(key, keylen); | |
256 | unsigned int pos = hashval & (hash->n_buckets - 1); | |
257 | unsigned int steps_used, steps_total; | |
258 | struct hash_bucket *bucket = hash->buckets + pos; | |
259 | struct hash_entry *entry, *entry_end; | |
260 | const struct hash_entry se = { | |
261 | .key = key, | |
262 | .value = NULL | |
263 | }; | |
264 | ||
265 | entry = bsearch(&se, bucket->entries, bucket->used, | |
266 | sizeof(struct hash_entry), hash_entry_cmp); | |
267 | if (entry == NULL) | |
268 | return -ENOENT; | |
269 | ||
270 | if (hash->free_value) | |
271 | hash->free_value((void *)entry->value); | |
272 | ||
273 | entry_end = bucket->entries + bucket->used; | |
274 | memmove(entry, entry + 1, | |
275 | (entry_end - entry) * sizeof(struct hash_entry)); | |
276 | ||
277 | bucket->used--; | |
278 | hash->count--; | |
279 | ||
280 | steps_used = bucket->used / hash->step; | |
281 | steps_total = bucket->total / hash->step; | |
282 | if (steps_used + 1 < steps_total) { | |
283 | size_t size = (steps_used + 1) * | |
284 | hash->step * sizeof(struct hash_entry); | |
285 | struct hash_entry *tmp = realloc(bucket->entries, size); | |
286 | if (tmp) { | |
287 | bucket->entries = tmp; | |
288 | bucket->total = (steps_used + 1) * hash->step; | |
289 | } | |
290 | } | |
291 | ||
292 | return 0; | |
293 | } | |
294 | ||
295 | unsigned int hash_get_count(const struct hash *hash) | |
296 | { | |
297 | return hash->count; | |
298 | } | |
299 | ||
300 | void hash_iter_init(const struct hash *hash, struct hash_iter *iter) | |
301 | { | |
302 | iter->hash = hash; | |
303 | iter->bucket = 0; | |
304 | iter->entry = -1; | |
305 | } | |
306 | ||
307 | bool hash_iter_next(struct hash_iter *iter, const char **key, | |
308 | const void **value) | |
309 | { | |
310 | const struct hash_bucket *b = iter->hash->buckets + iter->bucket; | |
311 | const struct hash_entry *e; | |
312 | ||
313 | iter->entry++; | |
314 | ||
315 | if (iter->entry >= b->used) { | |
316 | iter->entry = 0; | |
317 | ||
318 | for (iter->bucket++; iter->bucket < iter->hash->n_buckets; | |
319 | iter->bucket++) { | |
320 | b = iter->hash->buckets + iter->bucket; | |
321 | ||
322 | if (b->used > 0) | |
323 | break; | |
324 | } | |
325 | ||
326 | if (iter->bucket >= iter->hash->n_buckets) | |
327 | return false; | |
328 | } | |
329 | ||
330 | e = b->entries + iter->entry; | |
331 | ||
332 | if (value != NULL) | |
333 | *value = e->value; | |
334 | if (key != NULL) | |
335 | *key = e->key; | |
336 | ||
337 | return true; | |
338 | } |