1 /*
2 * Copyright (C) 2013-2022 Cisco Systems, Inc. and/or its affiliates. All rights reserved.
3 * Copyright (C) 2007-2013 Sourcefire, Inc.
4 *
5 * Authors: Török Edvin
6 *
7 * Summary: Hash-table and -set data structures.
8 *
9 * Acknowledgements: hash32shift() is an implementation of Thomas Wang's
10 * 32-bit integer hash function:
11 * http://www.cris.com/~Ttwang/tech/inthash.htm
12 *
13 * This program is free software; you can redistribute it and/or modify
14 * it under the terms of the GNU General Public License version 2 as
15 * published by the Free Software Foundation.
16 *
17 * This program is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License
23 * along with this program; if not, write to the Free Software
24 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
25 * MA 02110-1301, USA.
26 */
27 #include <stdlib.h>
28 #include <stdio.h>
29 #include <string.h>
30
31 #include "clamav.h"
32 #include "clamav-config.h"
33 #include "others.h"
34 #include "hashtab.h"
35
36 #define MODULE_NAME "hashtab: "
37
38 static const char DELETED_KEY[] = "";
39 #define DELETED_HTU32_KEY ((uint32_t)(-1))
40
nearest_power(unsigned long num)41 static unsigned long nearest_power(unsigned long num)
42 {
43 unsigned long n = 64;
44
45 while (n < num) {
46 n <<= 1;
47 if (n == 0) {
48 return num;
49 }
50 }
51 return n;
52 }
53
54 #ifdef PROFILE_HASHTABLE
55 /* I know, this is ugly, most of these functions get a const s, that gets its const-ness discarded,
56 * and then these functions modify something the compiler assumes is readonly.
57 * Please, never use PROFILE_HASHTABLE in production code, and in releases. Use it for development only!*/
58
PROFILE_INIT(struct cli_hashtable * s)59 static inline void PROFILE_INIT(struct cli_hashtable *s)
60 {
61 memset(&s->PROFILE_STRUCT, 0, sizeof(s->PROFILE_STRUCT));
62 }
63
PROFILE_CALC_HASH(struct cli_hashtable * s)64 static inline void PROFILE_CALC_HASH(struct cli_hashtable *s)
65 {
66 s->PROFILE_STRUCT.calc_hash++;
67 }
68
PROFILE_FIND_ELEMENT(struct cli_hashtable * s)69 static inline void PROFILE_FIND_ELEMENT(struct cli_hashtable *s)
70 {
71 s->PROFILE_STRUCT.find_req++;
72 }
73
PROFILE_FIND_NOTFOUND(struct cli_hashtable * s,size_t tries)74 static inline void PROFILE_FIND_NOTFOUND(struct cli_hashtable *s, size_t tries)
75 {
76 s->PROFILE_STRUCT.not_found++;
77 s->PROFILE_STRUCT.not_found_tries += tries;
78 }
79
PROFILE_FIND_FOUND(struct cli_hashtable * s,size_t tries)80 static inline void PROFILE_FIND_FOUND(struct cli_hashtable *s, size_t tries)
81 {
82 s->PROFILE_STRUCT.found++;
83 s->PROFILE_STRUCT.found_tries += tries;
84 }
85
PROFILE_HASH_EXHAUSTED(struct cli_hashtable * s)86 static inline void PROFILE_HASH_EXHAUSTED(struct cli_hashtable *s)
87 {
88 s->PROFILE_STRUCT.hash_exhausted++;
89 }
90
PROFILE_GROW_START(struct cli_hashtable * s)91 static inline void PROFILE_GROW_START(struct cli_hashtable *s)
92 {
93 s->PROFILE_STRUCT.grow++;
94 }
95
PROFILE_GROW_FOUND(struct cli_hashtable * s,size_t tries)96 static inline void PROFILE_GROW_FOUND(struct cli_hashtable *s, size_t tries)
97 {
98 s->PROFILE_STRUCT.grow_found++;
99 s->PROFILE_STRUCT.grow_found_tries += tries;
100 }
101
PROFILE_GROW_DONE(struct cli_hashtable * s)102 static inline void PROFILE_GROW_DONE(struct cli_hashtable *s)
103 {
104 }
105
PROFILE_DELETED_REUSE(struct cli_hashtable * s,size_t tries)106 static inline void PROFILE_DELETED_REUSE(struct cli_hashtable *s, size_t tries)
107 {
108 s->PROFILE_STRUCT.deleted_reuse++;
109 s->PROFILE_STRUCT.deleted_tries += tries;
110 }
111
PROFILE_INSERT(struct cli_hashtable * s,size_t tries)112 static inline void PROFILE_INSERT(struct cli_hashtable *s, size_t tries)
113 {
114 s->PROFILE_STRUCT.inserts++;
115 s->PROFILE_STRUCT.insert_tries += tries;
116 }
117
PROFILE_DATA_UPDATE(struct cli_hashtable * s,size_t tries)118 static inline void PROFILE_DATA_UPDATE(struct cli_hashtable *s, size_t tries)
119 {
120 s->PROFILE_STRUCT.update++;
121 s->PROFILE_STRUCT.update_tries += tries;
122 }
123
PROFILE_HASH_DELETE(struct cli_hashtable * s)124 static inline void PROFILE_HASH_DELETE(struct cli_hashtable *s)
125 {
126 s->PROFILE_STRUCT.deletes++;
127 }
128
PROFILE_HASH_CLEAR(struct cli_hashtable * s)129 static inline void PROFILE_HASH_CLEAR(struct cli_hashtable *s)
130 {
131 s->PROFILE_STRUCT.clear++;
132 }
133
PROFILE_REPORT(const struct cli_hashtable * s)134 static inline void PROFILE_REPORT(const struct cli_hashtable *s)
135 {
136 size_t lookups, queries, insert_tries, inserts;
137 cli_dbgmsg("--------Hashtable usage report for %p--------------\n", (const void *)s);
138 cli_dbgmsg("hash function calculations:%ld\n", s->PROFILE_STRUCT.calc_hash);
139 cli_dbgmsg("successful finds/total searches: %ld/%ld; lookups: %ld\n", s->PROFILE_STRUCT.found, s->PROFILE_STRUCT.find_req, s->PROFILE_STRUCT.found_tries);
140 cli_dbgmsg("unsuccessful finds/total searches: %ld/%ld; lookups: %ld\n", s->PROFILE_STRUCT.not_found, s->PROFILE_STRUCT.find_req, s->PROFILE_STRUCT.not_found_tries);
141 cli_dbgmsg("successful finds during grow:%ld; lookups: %ld\n", s->PROFILE_STRUCT.grow_found, s->PROFILE_STRUCT.grow_found_tries);
142 lookups = s->PROFILE_STRUCT.found_tries + s->PROFILE_STRUCT.not_found_tries + s->PROFILE_STRUCT.grow_found_tries;
143 queries = s->PROFILE_STRUCT.find_req + s->PROFILE_STRUCT.grow_found;
144 cli_dbgmsg("Find Lookups/total queries: %ld/%ld = %3f\n", lookups, queries, lookups * 1.0 / queries);
145 insert_tries = s->PROFILE_STRUCT.insert_tries + s->PROFILE_STRUCT.update_tries + s->PROFILE_STRUCT.deleted_tries;
146
147 cli_dbgmsg("new item insert tries/new items: %ld/%ld\n", s->PROFILE_STRUCT.insert_tries, s->PROFILE_STRUCT.inserts);
148 cli_dbgmsg("update tries/updates: %ld/%ld\n", s->PROFILE_STRUCT.update_tries, s->PROFILE_STRUCT.update);
149 cli_dbgmsg("deleted item reuse tries/deleted&reused items: %ld/%ld\n", s->PROFILE_STRUCT.deleted_tries, s->PROFILE_STRUCT.deleted_reuse);
150 inserts = s->PROFILE_STRUCT.inserts + s->PROFILE_STRUCT.update + s->PROFILE_STRUCT.deleted_reuse;
151 cli_dbgmsg("Insert tries/total inserts: %ld/%ld = %3f\n", insert_tries, inserts, insert_tries * 1.0 / inserts);
152
153 cli_dbgmsg("Grows: %ld, Deletes : %ld, hashtable clears: %ld\n", s->PROFILE_STRUCT.grow, s->PROFILE_STRUCT.deletes, s->PROFILE_STRUCT.clear);
154 cli_dbgmsg("--------Report end-------------\n");
155 }
156
157 #else
158 #define PROFILE_INIT(s)
159 #define PROFILE_CALC_HASH(s)
160 #define PROFILE_FIND_ELEMENT(s)
161 #define PROFILE_FIND_NOTFOUND(s, tries)
162 #define PROFILE_FIND_FOUND(s, tries)
163 #define PROFILE_HASH_EXHAUSTED(s)
164 #define PROFILE_GROW_START(s)
165 #define PROFILE_GROW_FOUND(s, tries)
166 #define PROFILE_GROW_DONE(s)
167 #define PROFILE_DELETED_REUSE(s, tries)
168 #define PROFILE_INSERT(s, tries)
169 #define PROFILE_DATA_UPDATE(s, tries)
170 #define PROFILE_HASH_DELETE(s)
171 #define PROFILE_HASH_CLEAR(s)
172 #define PROFILE_REPORT(s)
173 #endif
174
cli_hashtab_init(struct cli_hashtable * s,size_t capacity)175 int cli_hashtab_init(struct cli_hashtable *s, size_t capacity)
176 {
177 if (!s)
178 return CL_ENULLARG;
179
180 PROFILE_INIT(s);
181
182 capacity = nearest_power(capacity);
183 s->htable = cli_calloc(capacity, sizeof(*s->htable));
184 if (!s->htable)
185 return CL_EMEM;
186 s->capacity = capacity;
187 s->used = 0;
188 s->maxfill = 8 * capacity / 10;
189 return 0;
190 }
191
cli_htu32_init(struct cli_htu32 * s,size_t capacity,mpool_t * mempool)192 int cli_htu32_init(struct cli_htu32 *s, size_t capacity, mpool_t *mempool)
193 {
194 if (!s)
195 return CL_ENULLARG;
196
197 PROFILE_INIT(s);
198
199 capacity = nearest_power(capacity);
200 s->htable = MPOOL_CALLOC(mempool, capacity, sizeof(*s->htable));
201 if (!s->htable)
202 return CL_EMEM;
203 s->capacity = capacity;
204 s->used = 0;
205 s->maxfill = 8 * capacity / 10;
206 return 0;
207 }
208
hash32shift(uint32_t key)209 static inline uint32_t hash32shift(uint32_t key)
210 {
211 key = ~key + (key << 15);
212 key = key ^ (key >> 12);
213 key = key + (key << 2);
214 key = key ^ (key >> 4);
215 key = (key + (key << 3)) + (key << 11);
216 key = key ^ (key >> 16);
217 return key;
218 }
219
hash(const unsigned char * k,const size_t len,const size_t SIZE)220 static inline size_t hash(const unsigned char *k, const size_t len, const size_t SIZE)
221 {
222 size_t Hash = 1;
223 size_t i;
224 for (i = 0; i < len; i++) {
225 /* a simple add is good, because we use the mixing function below */
226 Hash += k[i];
227 /* mixing function */
228 Hash = hash32shift(Hash);
229 }
230 /* SIZE is power of 2 */
231 return Hash & (SIZE - 1);
232 }
233
hash_htu32(uint32_t k,const size_t SIZE)234 static inline size_t hash_htu32(uint32_t k, const size_t SIZE)
235 {
236 /* mixing function */
237 size_t Hash = hash32shift(k);
238 /* SIZE is power of 2 */
239 return Hash & (SIZE - 1);
240 }
241
242 /* if returned element has key==NULL, then key was not found in table */
cli_hashtab_find(const struct cli_hashtable * s,const char * key,const size_t len)243 struct cli_element *cli_hashtab_find(const struct cli_hashtable *s, const char *key, const size_t len)
244 {
245 struct cli_element *element;
246 size_t tries = 1;
247 size_t idx;
248
249 if (!s)
250 return NULL;
251 PROFILE_CALC_HASH(s);
252 PROFILE_FIND_ELEMENT(s);
253 idx = hash((const unsigned char *)key, len, s->capacity);
254 element = &s->htable[idx];
255 do {
256 if (!element->key) {
257 PROFILE_FIND_NOTFOUND(s, tries);
258 return NULL; /* element not found, place is empty*/
259 } else if (element->key != DELETED_KEY && len == element->len && (key == element->key || strncmp(key, element->key, len) == 0)) {
260 PROFILE_FIND_FOUND(s, tries);
261 return element; /* found */
262 } else {
263 idx = (idx + tries++) & (s->capacity - 1);
264 element = &s->htable[idx];
265 }
266 } while (tries <= s->capacity);
267 PROFILE_HASH_EXHAUSTED(s);
268 return NULL; /* not found */
269 }
270
cli_htu32_find(const struct cli_htu32 * s,uint32_t key)271 const struct cli_htu32_element *cli_htu32_find(const struct cli_htu32 *s, uint32_t key)
272 {
273 struct cli_htu32_element *element;
274 size_t tries = 1;
275 size_t idx;
276
277 if (!s)
278 return NULL;
279 PROFILE_CALC_HASH(s);
280 PROFILE_FIND_ELEMENT(s);
281 idx = hash_htu32(key, s->capacity);
282 element = &s->htable[idx];
283 do {
284 if (!element->key) {
285 PROFILE_FIND_NOTFOUND(s, tries);
286 return NULL; /* element not found, place is empty */
287 } else if (key == element->key) {
288 PROFILE_FIND_FOUND(s, tries);
289 return element; /* found */
290 } else {
291 idx = (idx + tries++) & (s->capacity - 1);
292 element = &s->htable[idx];
293 }
294 } while (tries <= s->capacity);
295 PROFILE_HASH_EXHAUSTED(s);
296 return NULL; /* not found */
297 }
298
299 /* linear enumeration - start with current = NULL, returns next item if present or NULL if not */
cli_htu32_next(const struct cli_htu32 * s,const struct cli_htu32_element * current)300 const struct cli_htu32_element *cli_htu32_next(const struct cli_htu32 *s, const struct cli_htu32_element *current)
301 {
302 size_t ncur;
303 if (!s || !s->capacity)
304 return NULL;
305
306 if (!current)
307 ncur = 0;
308 else {
309 ncur = current - s->htable;
310 if (ncur >= s->capacity)
311 return NULL;
312
313 ncur++;
314 }
315 for (; ncur < s->capacity; ncur++) {
316 const struct cli_htu32_element *item = &s->htable[ncur & (s->capacity - 1)];
317 if (item->key && item->key != DELETED_HTU32_KEY)
318 return item;
319 }
320 return NULL;
321 }
322
cli_hashtab_grow(struct cli_hashtable * s)323 static int cli_hashtab_grow(struct cli_hashtable *s)
324 {
325 const size_t new_capacity = nearest_power(s->capacity + 1);
326 struct cli_element *htable;
327 size_t i, idx, used = 0;
328
329 cli_dbgmsg("hashtab.c: new capacity: %llu\n", (long long unsigned)new_capacity);
330 if (new_capacity == s->capacity) {
331 cli_errmsg("hashtab.c: capacity problem growing from: %llu\n", (long long unsigned)s->capacity);
332 return CL_EMEM;
333 }
334 htable = cli_calloc(new_capacity, sizeof(*s->htable));
335 if (!htable) {
336 return CL_EMEM;
337 }
338
339 PROFILE_GROW_START(s);
340 cli_dbgmsg("hashtab.c: Warning: growing open-addressing hashtables is slow. Either allocate more storage when initializing, or use other hashtable types!\n");
341 for (i = 0; i < s->capacity; i++) {
342 if (s->htable[i].key && s->htable[i].key != DELETED_KEY) {
343 struct cli_element *element;
344 size_t tries = 1;
345
346 PROFILE_CALC_HASH(s);
347 idx = hash((const unsigned char *)s->htable[i].key, s->htable[i].len, new_capacity);
348 element = &htable[idx];
349
350 while (element->key && tries <= new_capacity) {
351 idx = (idx + tries++) & (new_capacity - 1);
352 element = &htable[idx];
353 }
354 if (!element->key) {
355 /* copy element from old hashtable to new */
356 PROFILE_GROW_FOUND(s, tries);
357 *element = s->htable[i];
358 used++;
359 } else {
360 cli_errmsg("hashtab.c: Impossible - unable to rehash table");
361 free(htable);
362 return CL_EMEM; /* this means we didn't find enough room for all elements in the new table, should never happen */
363 }
364 }
365 }
366 free(s->htable);
367 s->htable = htable;
368 s->used = used;
369 s->capacity = new_capacity;
370 s->maxfill = new_capacity * 8 / 10;
371 cli_dbgmsg("Table %p size after grow:%llu\n", (void *)s, (long long unsigned)s->capacity);
372 PROFILE_GROW_DONE(s);
373 return CL_SUCCESS;
374 }
375
376 #ifndef USE_MPOOL
377 #define cli_htu32_grow(A, B) cli_htu32_grow(A)
378 #endif
379
cli_htu32_grow(struct cli_htu32 * s,mpool_t * mempool)380 static int cli_htu32_grow(struct cli_htu32 *s, mpool_t *mempool)
381 {
382 const size_t new_capacity = nearest_power(s->capacity + 1);
383 struct cli_htu32_element *htable = MPOOL_CALLOC(mempool, new_capacity, sizeof(*s->htable));
384 size_t i, idx, used = 0;
385 cli_dbgmsg("hashtab.c: new capacity: %llu\n", (long long unsigned)new_capacity);
386 if (new_capacity == s->capacity || !htable)
387 return CL_EMEM;
388
389 PROFILE_GROW_START(s);
390
391 for (i = 0; i < s->capacity; i++) {
392 if (s->htable[i].key && s->htable[i].key != DELETED_HTU32_KEY) {
393 struct cli_htu32_element *element;
394 size_t tries = 1;
395
396 PROFILE_CALC_HASH(s);
397 idx = hash_htu32(s->htable[i].key, new_capacity);
398 element = &htable[idx];
399
400 while (element->key && tries <= new_capacity) {
401 idx = (idx + tries++) & (new_capacity - 1);
402 element = &htable[idx];
403 }
404 if (!element->key) {
405 /* copy element from old hashtable to new */
406 PROFILE_GROW_FOUND(s, tries);
407 *element = s->htable[i];
408 used++;
409 } else {
410 cli_errmsg("hashtab.c: Impossible - unable to rehash table");
411 return CL_EMEM; /* this means we didn't find enough room for all elements in the new table, should never happen */
412 }
413 }
414 }
415 MPOOL_FREE(mempool, s->htable);
416 s->htable = htable;
417 s->used = used;
418 s->capacity = new_capacity;
419 s->maxfill = new_capacity * 8 / 10;
420 cli_dbgmsg("Table %p size after grow:%llu\n", (void *)s, (long long unsigned)s->capacity);
421 PROFILE_GROW_DONE(s);
422 return CL_SUCCESS;
423 }
424
cli_hashtab_insert(struct cli_hashtable * s,const char * key,const size_t len,const cli_element_data data)425 const struct cli_element *cli_hashtab_insert(struct cli_hashtable *s, const char *key, const size_t len, const cli_element_data data)
426 {
427 struct cli_element *element;
428 struct cli_element *deleted_element = NULL;
429 size_t tries = 1;
430 size_t idx;
431 if (!s)
432 return NULL;
433 if (s->used > s->maxfill) {
434 cli_dbgmsg("hashtab.c:Growing hashtable %p, because it has exceeded maxfill, old size:%llu\n", (void *)s, (long long unsigned)s->capacity);
435 cli_hashtab_grow(s);
436 }
437 do {
438 PROFILE_CALC_HASH(s);
439 idx = hash((const unsigned char *)key, len, s->capacity);
440 element = &s->htable[idx];
441
442 do {
443 if (!element->key) {
444 char *thekey;
445 /* element not found, place is empty, insert*/
446 if (deleted_element) {
447 /* reuse deleted elements*/
448 element = deleted_element;
449 PROFILE_DELETED_REUSE(s, tries);
450 } else {
451 PROFILE_INSERT(s, tries);
452 }
453 thekey = cli_malloc(len + 1);
454 if (!thekey) {
455 cli_errmsg("hashtab.c: Unable to allocate memory for thekey\n");
456 return NULL;
457 }
458 strncpy(thekey, key, len + 1);
459 thekey[len] = '\0';
460 element->key = thekey;
461 element->data = data;
462 element->len = len;
463 s->used++;
464 return element;
465 } else if (element->key == DELETED_KEY) {
466 deleted_element = element;
467 element->key = NULL;
468 } else if (len == element->len && strncmp(key, element->key, len) == 0) {
469 PROFILE_DATA_UPDATE(s, tries);
470 element->data = data; /* key found, update */
471 return element;
472 } else {
473 idx = (idx + tries++) % s->capacity;
474 element = &s->htable[idx];
475 }
476 } while (tries <= s->capacity);
477 /* no free place found*/
478 PROFILE_HASH_EXHAUSTED(s);
479 cli_dbgmsg("hashtab.c: Growing hashtable %p, because its full, old size:%llu.\n", (void *)s, (long long unsigned)s->capacity);
480 } while (cli_hashtab_grow(s) >= 0);
481 cli_warnmsg("hashtab.c: Unable to grow hashtable\n");
482 return NULL;
483 }
484
cli_htu32_insert(struct cli_htu32 * s,const struct cli_htu32_element * item,mpool_t * mempool)485 int cli_htu32_insert(struct cli_htu32 *s, const struct cli_htu32_element *item, mpool_t *mempool)
486 {
487 struct cli_htu32_element *element;
488 struct cli_htu32_element *deleted_element = NULL;
489 size_t tries = 1;
490 size_t idx;
491 int ret;
492
493 if (!s)
494 return CL_ENULLARG;
495 if (s->used > s->maxfill) {
496 cli_dbgmsg("hashtab.c:Growing hashtable %p, because it has exceeded maxfill, old size:%llu\n", (void *)s, (long long unsigned)s->capacity);
497 cli_htu32_grow(s, mempool);
498 }
499 do {
500 PROFILE_CALC_HASH(s);
501 idx = hash_htu32(item->key, s->capacity);
502 element = &s->htable[idx];
503
504 do {
505 if (!element->key) {
506 /* element not found, place is empty, insert*/
507 if (deleted_element) {
508 /* reuse deleted elements*/
509 element = deleted_element;
510 PROFILE_DELETED_REUSE(s, tries);
511 } else {
512 PROFILE_INSERT(s, tries);
513 }
514 *element = *item;
515 s->used++;
516 return 0;
517 } else if (element->key == DELETED_HTU32_KEY) {
518 deleted_element = element;
519 element->key = 0;
520 } else if (item->key == element->key) {
521 PROFILE_DATA_UPDATE(s, tries);
522 element->data = item->data; /* key found, update */
523 return 0;
524 } else {
525 idx = (idx + tries++) % s->capacity;
526 element = &s->htable[idx];
527 }
528 } while (tries <= s->capacity);
529 /* no free place found*/
530 PROFILE_HASH_EXHAUSTED(s);
531 cli_dbgmsg("hashtab.c: Growing hashtable %p, because its full, old size:%llu.\n", (void *)s, (long long unsigned)s->capacity);
532 } while ((ret = cli_htu32_grow(s, mempool)) >= 0);
533 cli_warnmsg("hashtab.c: Unable to grow hashtable\n");
534 return ret;
535 }
536
cli_hashtab_delete(struct cli_hashtable * s,const char * key,const size_t len)537 void cli_hashtab_delete(struct cli_hashtable *s, const char *key, const size_t len)
538 {
539 struct cli_element *el = cli_hashtab_find(s, key, len);
540 if (!el || el->key == DELETED_KEY)
541 return;
542 free((void *)el->key);
543 el->key = DELETED_KEY;
544 }
545
cli_htu32_delete(struct cli_htu32 * s,uint32_t key)546 void cli_htu32_delete(struct cli_htu32 *s, uint32_t key)
547 {
548 struct cli_htu32_element *el = (struct cli_htu32_element *)cli_htu32_find(s, key);
549 if (el)
550 el->key = DELETED_HTU32_KEY;
551 }
552
cli_hashtab_clear(struct cli_hashtable * s)553 void cli_hashtab_clear(struct cli_hashtable *s)
554 {
555 size_t i;
556 PROFILE_HASH_CLEAR(s);
557 for (i = 0; i < s->capacity; i++) {
558 if (s->htable[i].key && s->htable[i].key != DELETED_KEY)
559 free((void *)s->htable[i].key);
560 }
561 if (s->htable)
562 memset(s->htable, 0, s->capacity * sizeof(*s->htable));
563 s->used = 0;
564 }
565
cli_htu32_clear(struct cli_htu32 * s)566 void cli_htu32_clear(struct cli_htu32 *s)
567 {
568 PROFILE_HASH_CLEAR(s);
569 if (s->htable)
570 memset(s->htable, 0, s->capacity * sizeof(struct cli_htu32_element));
571 s->used = 0;
572 }
573
cli_hashtab_free(struct cli_hashtable * s)574 void cli_hashtab_free(struct cli_hashtable *s)
575 {
576 cli_hashtab_clear(s);
577 free(s->htable);
578 s->htable = NULL;
579 s->capacity = 0;
580 }
581
cli_htu32_free(struct cli_htu32 * s,mpool_t * mempool)582 void cli_htu32_free(struct cli_htu32 *s, mpool_t *mempool)
583 {
584 MPOOL_FREE(mempool, s->htable);
585 s->htable = NULL;
586 s->capacity = 0;
587 }
588
cli_htu32_numitems(struct cli_htu32 * s)589 size_t cli_htu32_numitems(struct cli_htu32 *s)
590 {
591 if (!s) return 0;
592 return s->capacity;
593 }
594
cli_hashtab_store(const struct cli_hashtable * s,FILE * out)595 int cli_hashtab_store(const struct cli_hashtable *s, FILE *out)
596 {
597 size_t i;
598 for (i = 0; i < s->capacity; i++) {
599 const struct cli_element *e = &s->htable[i];
600 if (e->key && e->key != DELETED_KEY) {
601 fprintf(out, "%ld %s\n", e->data, e->key);
602 }
603 }
604 return CL_SUCCESS;
605 }
606
cli_hashtab_generate_c(const struct cli_hashtable * s,const char * name)607 int cli_hashtab_generate_c(const struct cli_hashtable *s, const char *name)
608 {
609 size_t i;
610 printf("/* TODO: include GPL headers */\n");
611 printf("#include <hashtab.h>\n");
612 printf("static struct cli_element %s_elements[] = {\n", name);
613 for (i = 0; i < s->capacity; i++) {
614 const struct cli_element *e = &s->htable[i];
615 if (!e->key)
616 printf("\t{NULL,0,0},\n");
617 else if (e->key == DELETED_KEY)
618 printf("\t{DELETED_KEY,0,0},\n");
619 else
620 printf("\t{\"%s\", %ld, %llu},\n", e->key, e->data, (long long unsigned)e->len);
621 }
622 printf("};\n");
623 printf("const struct cli_hashtable %s = {\n", name);
624 printf("\t%s_elements, %llu, %llu, %llu", name, (long long unsigned)s->capacity,
625 (long long unsigned)s->used, (long long unsigned)s->maxfill);
626 printf("\n};\n");
627
628 PROFILE_REPORT(s);
629 return 0;
630 }
631
cli_hashtab_load(FILE * in,struct cli_hashtable * s)632 int cli_hashtab_load(FILE *in, struct cli_hashtable *s)
633 {
634 char line[1024];
635 while (fgets(line, sizeof(line), in)) {
636 char l[1024];
637 int val;
638 sscanf(line, "%d %1023s", &val, l);
639 cli_hashtab_insert(s, l, strlen(l), val);
640 }
641 return CL_SUCCESS;
642 }
643
644 /* Initialize hashset. @initial_capacity is rounded to nearest power of 2.
645 * Load factor is between 50 and 99. When capacity*load_factor/100 is reached, the hashset is growed */
cli_hashset_init(struct cli_hashset * hs,size_t initial_capacity,uint8_t load_factor)646 int cli_hashset_init(struct cli_hashset *hs, size_t initial_capacity, uint8_t load_factor)
647 {
648 if (load_factor < 50 || load_factor > 99) {
649 cli_dbgmsg(MODULE_NAME "Invalid load factor: %u, using default of 80%%\n", load_factor);
650 load_factor = 80;
651 }
652 initial_capacity = nearest_power(initial_capacity);
653 hs->limit = initial_capacity * load_factor / 100;
654 hs->capacity = initial_capacity;
655 hs->mask = initial_capacity - 1;
656 hs->count = 0;
657 hs->keys = cli_malloc(initial_capacity * sizeof(*hs->keys));
658 hs->mempool = NULL;
659 if (!hs->keys) {
660 cli_errmsg("hashtab.c: Unable to allocate memory for hs->keys\n");
661 return CL_EMEM;
662 }
663 hs->bitmap = cli_calloc(initial_capacity >> 5, sizeof(*hs->bitmap));
664 if (!hs->bitmap) {
665 free(hs->keys);
666 cli_errmsg("hashtab.c: Unable to allocate memory for hs->bitmap\n");
667 return CL_EMEM;
668 }
669 return 0;
670 }
671
cli_hashset_init_pool(struct cli_hashset * hs,size_t initial_capacity,uint8_t load_factor,mpool_t * mempool)672 int cli_hashset_init_pool(struct cli_hashset *hs, size_t initial_capacity, uint8_t load_factor, mpool_t *mempool)
673 {
674 if (load_factor < 50 || load_factor > 99) {
675 cli_dbgmsg(MODULE_NAME "Invalid load factor: %u, using default of 80%%\n", load_factor);
676 load_factor = 80;
677 }
678 initial_capacity = nearest_power(initial_capacity);
679 hs->limit = initial_capacity * load_factor / 100;
680 hs->capacity = initial_capacity;
681 hs->mask = initial_capacity - 1;
682 hs->count = 0;
683 hs->mempool = mempool;
684 hs->keys = MPOOL_MALLOC(mempool, initial_capacity * sizeof(*hs->keys));
685 if (!hs->keys) {
686 cli_errmsg("hashtab.c: Unable to allocate memory pool for hs->keys\n");
687 return CL_EMEM;
688 }
689 hs->bitmap = MPOOL_CALLOC(mempool, initial_capacity >> 5, sizeof(*hs->bitmap));
690 if (!hs->bitmap) {
691 MPOOL_FREE(mempool, hs->keys);
692 cli_errmsg("hashtab.c: Unable to allocate/initialize memory for hs->keys\n");
693 return CL_EMEM;
694 }
695 return 0;
696 }
697
cli_hashset_destroy(struct cli_hashset * hs)698 void cli_hashset_destroy(struct cli_hashset *hs)
699 {
700 cli_dbgmsg(MODULE_NAME "Freeing hashset, elements: %u, capacity: %u\n", hs->count, hs->capacity);
701 if (hs->mempool) {
702 MPOOL_FREE(hs->mempool, hs->keys);
703 MPOOL_FREE(hs->mempool, hs->bitmap);
704 } else {
705 free(hs->keys);
706 free(hs->bitmap);
707 }
708 hs->keys = hs->bitmap = NULL;
709 hs->capacity = 0;
710 }
711
712 #define BITMAP_CONTAINS(bmap, val) ((bmap)[(val) >> 5] & ((uint64_t)1 << ((val)&0x1f)))
713 #define BITMAP_INSERT(bmap, val) ((bmap)[(val) >> 5] |= ((uint64_t)1 << ((val)&0x1f)))
714 #define BITMAP_REMOVE(bmap, val) ((bmap)[(val) >> 5] &= ~((uint64_t)1 << ((val)&0x1f)))
715
716 /*
717 * searches the hashset for the @key.
718 * Returns the position the key is at, or a candidate position where it could be inserted.
719 */
cli_hashset_search(const struct cli_hashset * hs,const uint32_t key)720 static inline size_t cli_hashset_search(const struct cli_hashset *hs, const uint32_t key)
721 {
722 /* calculate hash value for this key, and map it to our table */
723 size_t idx = hash32shift(key) & (hs->mask);
724 size_t tries = 1;
725
726 /* check whether the entry is used, and if the key matches */
727 while (BITMAP_CONTAINS(hs->bitmap, idx) && (hs->keys[idx] != key)) {
728 /* entry used, key different -> collision */
729 idx = (idx + tries++) & (hs->mask);
730 /* quadratic probing, with c1 = c2 = 1/2, guaranteed to walk the entire table
731 * for table sizes power of 2.*/
732 }
733 /* we have either found the key, or a candidate insertion position */
734 return idx;
735 }
736
cli_hashset_addkey_internal(struct cli_hashset * hs,const uint32_t key)737 static void cli_hashset_addkey_internal(struct cli_hashset *hs, const uint32_t key)
738 {
739 const size_t idx = cli_hashset_search(hs, key);
740 /* we know hashtable is not full, when this method is called */
741
742 if (!BITMAP_CONTAINS(hs->bitmap, idx)) {
743 /* add new key */
744 BITMAP_INSERT(hs->bitmap, idx);
745 hs->keys[idx] = key;
746 hs->count++;
747 }
748 }
749
cli_hashset_grow(struct cli_hashset * hs)750 static int cli_hashset_grow(struct cli_hashset *hs)
751 {
752 struct cli_hashset new_hs;
753 size_t i;
754 int rc;
755
756 /* in-place growing is not possible, since the new keys
757 * will hash to different locations. */
758 cli_dbgmsg(MODULE_NAME "Growing hashset, used: %u, capacity: %u\n", hs->count, hs->capacity);
759 /* create a bigger hashset */
760
761 if (hs->mempool)
762 rc = cli_hashset_init_pool(&new_hs, hs->capacity << 1, hs->limit * 100 / hs->capacity, hs->mempool);
763 else
764 rc = cli_hashset_init(&new_hs, hs->capacity << 1, hs->limit * 100 / hs->capacity);
765 if (rc != 0)
766 return rc;
767 /* and copy keys */
768 for (i = 0; i < hs->capacity; i++) {
769 if (BITMAP_CONTAINS(hs->bitmap, i)) {
770 const size_t key = hs->keys[i];
771 cli_hashset_addkey_internal(&new_hs, key);
772 }
773 }
774 cli_hashset_destroy(hs);
775 /* replace old hashset with new one */
776 *hs = new_hs;
777 return 0;
778 }
779
cli_hashset_addkey(struct cli_hashset * hs,const uint32_t key)780 int cli_hashset_addkey(struct cli_hashset *hs, const uint32_t key)
781 {
782 /* check that we didn't reach the load factor.
783 * Even if we don't know yet whether we'd add this key */
784 if (hs->count + 1 > hs->limit) {
785 int rc = cli_hashset_grow(hs);
786 if (rc) {
787 return rc;
788 }
789 }
790 cli_hashset_addkey_internal(hs, key);
791 return 0;
792 }
793
cli_hashset_removekey(struct cli_hashset * hs,const uint32_t key)794 int cli_hashset_removekey(struct cli_hashset *hs, const uint32_t key)
795 {
796 const size_t idx = cli_hashset_search(hs, key);
797 if (BITMAP_CONTAINS(hs->bitmap, idx)) {
798 BITMAP_REMOVE(hs->bitmap, idx);
799 hs->keys[idx] = 0;
800 hs->count--;
801 return 0;
802 }
803 return -1;
804 }
805
cli_hashset_contains(const struct cli_hashset * hs,const uint32_t key)806 int cli_hashset_contains(const struct cli_hashset *hs, const uint32_t key)
807 {
808 const size_t idx = cli_hashset_search(hs, key);
809 return BITMAP_CONTAINS(hs->bitmap, idx);
810 }
811
cli_hashset_toarray(const struct cli_hashset * hs,uint32_t ** array)812 ssize_t cli_hashset_toarray(const struct cli_hashset *hs, uint32_t **array)
813 {
814 size_t i, j;
815 uint32_t *arr;
816
817 if (!array) {
818 return CL_ENULLARG;
819 }
820 *array = arr = cli_malloc(hs->count * sizeof(*arr));
821 if (!arr) {
822 cli_errmsg("hashtab.c: Unable to allocate memory for array\n");
823 return CL_EMEM;
824 }
825
826 for (i = 0, j = 0; i < hs->capacity && j < hs->count; i++) {
827 if (BITMAP_CONTAINS(hs->bitmap, i)) {
828 arr[j++] = hs->keys[i];
829 }
830 }
831 return j;
832 }
833
cli_hashset_init_noalloc(struct cli_hashset * hs)834 void cli_hashset_init_noalloc(struct cli_hashset *hs)
835 {
836 memset(hs, 0, sizeof(*hs));
837 }
838
cli_hashset_contains_maybe_noalloc(const struct cli_hashset * hs,const uint32_t key)839 int cli_hashset_contains_maybe_noalloc(const struct cli_hashset *hs, const uint32_t key)
840 {
841 if (!hs->keys)
842 return 0;
843 return cli_hashset_contains(hs, key);
844 }
845
cli_map_init(struct cli_map * m,int32_t keysize,int32_t valuesize,int32_t capacity)846 int cli_map_init(struct cli_map *m, int32_t keysize, int32_t valuesize,
847 int32_t capacity)
848 {
849 if (keysize <= 0 || valuesize < 0 || capacity <= 0)
850 return -CL_EARG;
851 memset(m, 0, sizeof(*m));
852 cli_hashtab_init(&m->htab, 16);
853 m->keysize = keysize;
854 m->valuesize = valuesize;
855 m->last_insert = -1;
856 m->last_find = -1;
857 return 0;
858 }
859
cli_map_addkey(struct cli_map * m,const void * key,int32_t keysize)860 int cli_map_addkey(struct cli_map *m, const void *key, int32_t keysize)
861 {
862 unsigned n;
863 struct cli_element *el;
864 if (m->keysize != keysize)
865 return -CL_EARG;
866 el = cli_hashtab_find(&m->htab, key, keysize);
867 if (el) {
868 m->last_insert = el->data;
869 return 0;
870 }
871 n = m->nvalues + 1;
872 if (m->valuesize) {
873 void *v;
874 v = cli_realloc(m->u.sized_values, n * m->valuesize);
875 if (!v)
876 return -CL_EMEM;
877 m->u.sized_values = v;
878 memset((char *)m->u.sized_values + (n - 1) * m->valuesize, 0, m->valuesize);
879 } else {
880 struct cli_map_value *v;
881 v = cli_realloc(m->u.unsized_values, n * sizeof(*m->u.unsized_values));
882 if (!v)
883 return -CL_EMEM;
884 m->u.unsized_values = v;
885 memset(&m->u.unsized_values[n - 1], 0, sizeof(*m->u.unsized_values));
886 }
887 m->nvalues = n;
888 if (!cli_hashtab_insert(&m->htab, key, keysize, n - 1))
889 return -CL_EMEM;
890 m->last_insert = n - 1;
891 return 1;
892 }
893
cli_map_removekey(struct cli_map * m,const void * key,int32_t keysize)894 int cli_map_removekey(struct cli_map *m, const void *key, int32_t keysize)
895 {
896 struct cli_element *el;
897 if (m->keysize != keysize)
898 return -CL_EARG;
899 el = cli_hashtab_find(&m->htab, key, keysize);
900 if (!el)
901 return 0;
902 if (el->data >= m->nvalues || el->data < 0)
903 return -CL_EARG;
904 if (!m->valuesize) {
905 struct cli_map_value *v = &m->u.unsized_values[el->data];
906 free(v->value);
907 v->value = NULL;
908 v->valuesize = 0;
909 } else {
910 char *v = (char *)m->u.sized_values + el->data * m->valuesize;
911 memset(v, 0, m->valuesize);
912 }
913 cli_hashtab_delete(&m->htab, key, keysize);
914 return 1;
915 }
916
cli_map_setvalue(struct cli_map * m,const void * value,int32_t valuesize)917 int cli_map_setvalue(struct cli_map *m, const void *value, int32_t valuesize)
918 {
919 if ((m->valuesize && m->valuesize != valuesize) || (uint32_t)(m->last_insert) >= m->nvalues || m->last_insert < 0)
920 return -CL_EARG;
921 if (m->valuesize) {
922 memcpy((char *)m->u.sized_values + m->last_insert * m->valuesize,
923 value, valuesize);
924 } else {
925 struct cli_map_value *v = &m->u.unsized_values[m->last_insert];
926 if (v->value)
927 free(v->value);
928 v->value = cli_malloc(valuesize);
929 if (!v->value) {
930 cli_errmsg("hashtab.c: Unable to allocate memory for v->value\n");
931 return -CL_EMEM;
932 }
933 memcpy(v->value, value, valuesize);
934 v->valuesize = valuesize;
935 }
936 return 0;
937 }
938
cli_map_find(struct cli_map * m,const void * key,int32_t keysize)939 int cli_map_find(struct cli_map *m, const void *key, int32_t keysize)
940 {
941 struct cli_element *el;
942 if (m->keysize != keysize)
943 return -CL_EARG;
944 el = cli_hashtab_find(&m->htab, key, keysize);
945 if (!el)
946 return 0;
947 m->last_find = el->data;
948 return 1;
949 }
950
cli_map_getvalue_size(struct cli_map * m)951 int cli_map_getvalue_size(struct cli_map *m)
952 {
953 if (m->valuesize)
954 return m->valuesize;
955 if (m->last_find < 0 || (uint32_t)(m->last_find) >= m->nvalues)
956 return -CL_EARG;
957 return m->u.unsized_values[m->last_find].valuesize;
958 }
959
cli_map_getvalue(struct cli_map * m)960 void *cli_map_getvalue(struct cli_map *m)
961 {
962 if (m->last_find < 0 || (uint32_t)(m->last_find) >= m->nvalues)
963 return NULL;
964 if (m->valuesize)
965 return (char *)m->u.sized_values + m->last_find * m->valuesize;
966 return m->u.unsized_values[m->last_find].value;
967 }
968
cli_map_delete(struct cli_map * m)969 void cli_map_delete(struct cli_map *m)
970 {
971 cli_hashtab_free(&m->htab);
972 if (!m->valuesize) {
973 unsigned i;
974 for (i = 0; i < m->nvalues; i++)
975 free(m->u.unsized_values[i].value);
976 free(m->u.unsized_values);
977 } else {
978 free(m->u.sized_values);
979 }
980 memset(m, 0, sizeof(*m));
981 }
982