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
hash_new(unsigned int n_buckets,void (* free_value)(void * value))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
hash_free(struct hash * hash)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
hash_superfast(const char * key,unsigned int len)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 */
hash_add(struct hash * hash,const char * key,const void * value)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 */
hash_add_unique(struct hash * hash,const char * key,const void * value)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
hash_entry_cmp(const void * pa,const void * pb)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
hash_find(const struct hash * hash,const char * key)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
hash_del(struct hash * hash,const char * key)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
hash_get_count(const struct hash * hash)295 unsigned int hash_get_count(const struct hash *hash)
296 {
297 return hash->count;
298 }
299
hash_iter_init(const struct hash * hash,struct hash_iter * iter)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
hash_iter_next(struct hash_iter * iter,const char ** key,const void ** value)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 }
339