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