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;
245
246 if (!bucket->entries)
247 return NULL;
248
249 entry = bsearch(&se, bucket->entries, bucket->used,
250 sizeof(struct hash_entry), hash_entry_cmp);
251
252 return entry ? (void *)entry->value : NULL;
253 }
254
hash_del(struct hash * hash,const char * key)255 int hash_del(struct hash *hash, const char *key)
256 {
257 unsigned int keylen = strlen(key);
258 unsigned int hashval = hash_superfast(key, keylen);
259 unsigned int pos = hashval & (hash->n_buckets - 1);
260 unsigned int steps_used, steps_total;
261 struct hash_bucket *bucket = hash->buckets + pos;
262 struct hash_entry *entry, *entry_end;
263 const struct hash_entry se = {
264 .key = key,
265 .value = NULL
266 };
267
268 entry = bsearch(&se, bucket->entries, bucket->used,
269 sizeof(struct hash_entry), hash_entry_cmp);
270 if (entry == NULL)
271 return -ENOENT;
272
273 if (hash->free_value)
274 hash->free_value((void *)entry->value);
275
276 entry_end = bucket->entries + bucket->used;
277 memmove(entry, entry + 1,
278 (entry_end - entry) * sizeof(struct hash_entry));
279
280 bucket->used--;
281 hash->count--;
282
283 steps_used = bucket->used / hash->step;
284 steps_total = bucket->total / hash->step;
285 if (steps_used + 1 < steps_total) {
286 size_t size = (steps_used + 1) *
287 hash->step * sizeof(struct hash_entry);
288 struct hash_entry *tmp = realloc(bucket->entries, size);
289 if (tmp) {
290 bucket->entries = tmp;
291 bucket->total = (steps_used + 1) * hash->step;
292 }
293 }
294
295 return 0;
296 }
297
hash_get_count(const struct hash * hash)298 unsigned int hash_get_count(const struct hash *hash)
299 {
300 return hash->count;
301 }
302
hash_iter_init(const struct hash * hash,struct hash_iter * iter)303 void hash_iter_init(const struct hash *hash, struct hash_iter *iter)
304 {
305 iter->hash = hash;
306 iter->bucket = 0;
307 iter->entry = -1;
308 }
309
hash_iter_next(struct hash_iter * iter,const char ** key,const void ** value)310 bool hash_iter_next(struct hash_iter *iter, const char **key,
311 const void **value)
312 {
313 const struct hash_bucket *b = iter->hash->buckets + iter->bucket;
314 const struct hash_entry *e;
315
316 iter->entry++;
317
318 if (iter->entry >= b->used) {
319 iter->entry = 0;
320
321 for (iter->bucket++; iter->bucket < iter->hash->n_buckets;
322 iter->bucket++) {
323 b = iter->hash->buckets + iter->bucket;
324
325 if (b->used > 0)
326 break;
327 }
328
329 if (iter->bucket >= iter->hash->n_buckets)
330 return false;
331 }
332
333 e = b->entries + iter->entry;
334
335 if (value != NULL)
336 *value = e->value;
337 if (key != NULL)
338 *key = e->key;
339
340 return true;
341 }
342