hashmap.c 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241
  1. // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
  2. /*
  3. * Generic non-thread safe hash map implementation.
  4. *
  5. * Copyright (c) 2019 Facebook
  6. */
  7. #include <stdint.h>
  8. #include <stdlib.h>
  9. #include <stdio.h>
  10. #include <errno.h>
  11. #include <linux/err.h>
  12. #include "hashmap.h"
  13. /* make sure libbpf doesn't use kernel-only integer typedefs */
  14. #pragma GCC poison u8 u16 u32 u64 s8 s16 s32 s64
  15. /* prevent accidental re-addition of reallocarray() */
  16. #pragma GCC poison reallocarray
  17. /* start with 4 buckets */
  18. #define HASHMAP_MIN_CAP_BITS 2
  19. static void hashmap_add_entry(struct hashmap_entry **pprev,
  20. struct hashmap_entry *entry)
  21. {
  22. entry->next = *pprev;
  23. *pprev = entry;
  24. }
  25. static void hashmap_del_entry(struct hashmap_entry **pprev,
  26. struct hashmap_entry *entry)
  27. {
  28. *pprev = entry->next;
  29. entry->next = NULL;
  30. }
  31. void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
  32. hashmap_equal_fn equal_fn, void *ctx)
  33. {
  34. map->hash_fn = hash_fn;
  35. map->equal_fn = equal_fn;
  36. map->ctx = ctx;
  37. map->buckets = NULL;
  38. map->cap = 0;
  39. map->cap_bits = 0;
  40. map->sz = 0;
  41. }
  42. struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
  43. hashmap_equal_fn equal_fn,
  44. void *ctx)
  45. {
  46. struct hashmap *map = malloc(sizeof(struct hashmap));
  47. if (!map)
  48. return ERR_PTR(-ENOMEM);
  49. hashmap__init(map, hash_fn, equal_fn, ctx);
  50. return map;
  51. }
  52. void hashmap__clear(struct hashmap *map)
  53. {
  54. struct hashmap_entry *cur, *tmp;
  55. size_t bkt;
  56. hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
  57. free(cur);
  58. }
  59. free(map->buckets);
  60. map->buckets = NULL;
  61. map->cap = map->cap_bits = map->sz = 0;
  62. }
  63. void hashmap__free(struct hashmap *map)
  64. {
  65. if (!map)
  66. return;
  67. hashmap__clear(map);
  68. free(map);
  69. }
  70. size_t hashmap__size(const struct hashmap *map)
  71. {
  72. return map->sz;
  73. }
  74. size_t hashmap__capacity(const struct hashmap *map)
  75. {
  76. return map->cap;
  77. }
  78. static bool hashmap_needs_to_grow(struct hashmap *map)
  79. {
  80. /* grow if empty or more than 75% filled */
  81. return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap);
  82. }
  83. static int hashmap_grow(struct hashmap *map)
  84. {
  85. struct hashmap_entry **new_buckets;
  86. struct hashmap_entry *cur, *tmp;
  87. size_t new_cap_bits, new_cap;
  88. size_t h, bkt;
  89. new_cap_bits = map->cap_bits + 1;
  90. if (new_cap_bits < HASHMAP_MIN_CAP_BITS)
  91. new_cap_bits = HASHMAP_MIN_CAP_BITS;
  92. new_cap = 1UL << new_cap_bits;
  93. new_buckets = calloc(new_cap, sizeof(new_buckets[0]));
  94. if (!new_buckets)
  95. return -ENOMEM;
  96. hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
  97. h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits);
  98. hashmap_add_entry(&new_buckets[h], cur);
  99. }
  100. map->cap = new_cap;
  101. map->cap_bits = new_cap_bits;
  102. free(map->buckets);
  103. map->buckets = new_buckets;
  104. return 0;
  105. }
  106. static bool hashmap_find_entry(const struct hashmap *map,
  107. const void *key, size_t hash,
  108. struct hashmap_entry ***pprev,
  109. struct hashmap_entry **entry)
  110. {
  111. struct hashmap_entry *cur, **prev_ptr;
  112. if (!map->buckets)
  113. return false;
  114. for (prev_ptr = &map->buckets[hash], cur = *prev_ptr;
  115. cur;
  116. prev_ptr = &cur->next, cur = cur->next) {
  117. if (map->equal_fn(cur->key, key, map->ctx)) {
  118. if (pprev)
  119. *pprev = prev_ptr;
  120. *entry = cur;
  121. return true;
  122. }
  123. }
  124. return false;
  125. }
  126. int hashmap__insert(struct hashmap *map, const void *key, void *value,
  127. enum hashmap_insert_strategy strategy,
  128. const void **old_key, void **old_value)
  129. {
  130. struct hashmap_entry *entry;
  131. size_t h;
  132. int err;
  133. if (old_key)
  134. *old_key = NULL;
  135. if (old_value)
  136. *old_value = NULL;
  137. h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
  138. if (strategy != HASHMAP_APPEND &&
  139. hashmap_find_entry(map, key, h, NULL, &entry)) {
  140. if (old_key)
  141. *old_key = entry->key;
  142. if (old_value)
  143. *old_value = entry->value;
  144. if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) {
  145. entry->key = key;
  146. entry->value = value;
  147. return 0;
  148. } else if (strategy == HASHMAP_ADD) {
  149. return -EEXIST;
  150. }
  151. }
  152. if (strategy == HASHMAP_UPDATE)
  153. return -ENOENT;
  154. if (hashmap_needs_to_grow(map)) {
  155. err = hashmap_grow(map);
  156. if (err)
  157. return err;
  158. h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
  159. }
  160. entry = malloc(sizeof(struct hashmap_entry));
  161. if (!entry)
  162. return -ENOMEM;
  163. entry->key = key;
  164. entry->value = value;
  165. hashmap_add_entry(&map->buckets[h], entry);
  166. map->sz++;
  167. return 0;
  168. }
  169. bool hashmap__find(const struct hashmap *map, const void *key, void **value)
  170. {
  171. struct hashmap_entry *entry;
  172. size_t h;
  173. h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
  174. if (!hashmap_find_entry(map, key, h, NULL, &entry))
  175. return false;
  176. if (value)
  177. *value = entry->value;
  178. return true;
  179. }
  180. bool hashmap__delete(struct hashmap *map, const void *key,
  181. const void **old_key, void **old_value)
  182. {
  183. struct hashmap_entry **pprev, *entry;
  184. size_t h;
  185. h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
  186. if (!hashmap_find_entry(map, key, h, &pprev, &entry))
  187. return false;
  188. if (old_key)
  189. *old_key = entry->key;
  190. if (old_value)
  191. *old_value = entry->value;
  192. hashmap_del_entry(pprev, entry);
  193. free(entry);
  194. map->sz--;
  195. return true;
  196. }