Debian Codegraph @

lib/hashtable.c

raw
1 /* SPDX-License-Identifier: LGPL-2.1-only */
2 /*
3 * Copyright (c) 2012 Cumulus Networks, Inc
4 */
5
6 #include "nl-default.h"
7
8 #include "hashtable-api.h"
9
10 #include <netlink/object.h>
11 #include <netlink/hash.h>
12 #include <netlink/hashtable.h>
13
14 #include "nl-aux-core/nl-core.h"
15
16 /**
17 * @ingroup core_types
18 * @defgroup hashtable Hashtable
19 * @{
20 */
21
22 /* Generic helper to handle regular and resizeable hash tables */
23 static nl_hash_table_t *_nl_hash_table_init(nl_hash_table_t *ht, int size)
24 {
25 ht->nodes = calloc(size, sizeof(*ht->nodes));
26 if (!ht->nodes) {
27 return NULL;
28 }
29
30 ht->size = size;
31
32 return ht;
33 }
34
35 /**
36 * Allocate hashtable
37 * @arg size Size of hashtable in number of elements
38 *
39 * @return Allocated hashtable or NULL.
40 */
41 nl_hash_table_t *nl_hash_table_alloc(int size)
42 {
43 nl_hash_table_t *ht;
44
45 ht = calloc(1, sizeof(*ht));
46 if (!ht)
47 return NULL;
48
49 return _nl_hash_table_init(ht, size);
50 }
51
52 /* Generic helper to handle regular and resizeable hash tables */
53 static void _nl_hash_table_free(nl_hash_table_t *ht)
54 {
55 int i;
56
57 for (i = 0; i < ht->size; i++) {
58 nl_hash_node_t *node = ht->nodes[i];
59 nl_hash_node_t *saved_node;
60
61 while (node) {
62 saved_node = node;
63 node = node->next;
64 nl_object_put(saved_node->obj);
65 free(saved_node);
66 }
67 }
68
69 free(ht->nodes);
70 }
71
72 /**
73 * Free hashtable including all nodes
74 * @arg ht Hashtable
75 *
76 * @note Reference counter of all objects in the hashtable will be decremented.
77 */
78 void nl_hash_table_free(nl_hash_table_t *ht)
79 {
80 _nl_hash_table_free(ht);
81 free(ht);
82 }
83
84 /**
85 * Lookup identical object in hashtable
86 * @arg ht Hashtable
87 * @arg obj Object to lookup
88 *
89 * Generates hashkey for `obj` and traverses the corresponding chain calling
90 * `nl_object_identical()` on each trying to find a match.
91 *
92 * @return Pointer to object if match was found or NULL.
93 */
94 struct nl_object *nl_hash_table_lookup(nl_hash_table_t *ht,
95 struct nl_object *obj)
96 {
97 nl_hash_node_t *node;
98 uint32_t key_hash;
99
100 nl_object_keygen(obj, &key_hash, ht->size);
101 node = ht->nodes[key_hash];
102
103 while (node) {
104 if (nl_object_identical(node->obj, obj))
105 return node->obj;
106 node = node->next;
107 }
108
109 return NULL;
110 }
111
112 /**
113 * Add object to hashtable
114 * @arg ht Hashtable
115 * @arg obj Object to add
116 *
117 * Adds `obj` to the hashtable. Object type must support hashing, otherwise all
118 * objects will be added to the chain `0`.
119 *
120 * @note The reference counter of the object is incremented.
121 *
122 * @return 0 on success or a negative error code
123 * @retval -NLE_EXIST Identical object already present in hashtable
124 */
125 int nl_hash_table_add(nl_hash_table_t *ht, struct nl_object *obj)
126 {
127 nl_hash_node_t *node;
128 uint32_t key_hash;
129
130 nl_object_keygen(obj, &key_hash, ht->size);
131 node = ht->nodes[key_hash];
132
133 while (node) {
134 if (nl_object_identical(node->obj, obj)) {
135 NL_DBG(2,
136 "Warning: Add to hashtable found duplicate...\n");
137 return -NLE_EXIST;
138 }
139 node = node->next;
140 }
141
142 NL_DBG(5, "adding cache entry of obj %p in table %p, with hash 0x%x\n",
143 obj, ht, key_hash);
144
145 node = malloc(sizeof(nl_hash_node_t));
146 if (!node)
147 return -NLE_NOMEM;
148 nl_object_get(obj);
149 node->obj = obj;
150 node->key = key_hash;
151 node->key_size = sizeof(uint32_t);
152 node->next = ht->nodes[key_hash];
153 ht->nodes[key_hash] = node;
154
155 return 0;
156 }
157
158 /**
159 * Remove object from hashtable
160 * @arg ht Hashtable
161 * @arg obj Object to remove
162 *
163 * Remove `obj` from hashtable if it exists.
164 *
165 * @note Reference counter of object will be decremented.
166 *
167 * @return 0 on success or a negative error code.
168 * @retval -NLE_OBJ_NOTFOUND Object not present in hashtable.
169 */
170 int nl_hash_table_del(nl_hash_table_t *ht, struct nl_object *obj)
171 {
172 nl_hash_node_t *node, *prev;
173 uint32_t key_hash;
174
175 nl_object_keygen(obj, &key_hash, ht->size);
176 prev = node = ht->nodes[key_hash];
177
178 while (node) {
179 if (nl_object_identical(node->obj, obj)) {
180 nl_object_put(obj);
181
182 NL_DBG(5,
183 "deleting cache entry of obj %p in table %p, with"
184 " hash 0x%x\n",
185 obj, ht, key_hash);
186
187 if (node == ht->nodes[key_hash])
188 ht->nodes[key_hash] = node->next;
189 else
190 prev->next = node->next;
191
192 free(node);
193
194 return 0;
195 }
196 prev = node;
197 node = node->next;
198 }
199
200 return -NLE_OBJ_NOTFOUND;
201 }
202
203 uint32_t nl_hash(void *k, size_t length, uint32_t initval)
204 {
205 return (__nl_hash((char *)k, length, initval));
206 }
207
208 typedef struct nl_rhash_table {
209 struct nl_hash_table hash_table;
210 int orig_size; /* Original size of hashtable at creation time */
211
212 /* Number of elements currently stored in the table. Needed to
213 * determine when the table needs to be resized.
214 */
215 int nelements;
216 } nl_rhash_table_t;
217
218 /* Internal load factor threshold at which the table will be resized. The
219 * value is represented as a fraction where NL_HT_LOAD_NUM / NL_HT_LOAD_DEN
220 * is the maximal allowed load factor.
221 *
222 * A value of 3/4 (0.75) provides a good trade-off between memory usage and
223 * lookup performance for a chaining hash table.
224 */
225 #define NL_HT_LOAD_NUM 3
226 #define NL_HT_LOAD_DEN 4
227
228 /**
229 * Private helper which performs a rehash of the table to a new size. On
230 * success the table fields (size/nodes) are updated and 0 is returned.
231 * On allocation failure the table is left untouched and -NLE_NOMEM is
232 * returned so that the caller can gracefully continue operating with the
233 * original (but possibly crowded) table.
234 */
235 static int nl_rhash_table_resize(nl_rhash_table_t *ht, int new_size)
236 {
237 nl_hash_node_t **new_nodes;
238 int i;
239
240 if (new_size <= 0)
241 return 0;
242
243 new_nodes = calloc(new_size, sizeof(*new_nodes));
244 if (!new_nodes)
245 return -NLE_NOMEM;
246
247 /* Re-hash all existing nodes into the new bucket array. */
248 for (i = 0; i < ht->hash_table.size; i++) {
249 nl_hash_node_t *node = ht->hash_table.nodes[i];
250 while (node) {
251 nl_hash_node_t *next = node->next;
252 uint32_t new_hash;
253
254 nl_object_keygen(node->obj, &new_hash, new_size);
255 node->key = new_hash;
256
257 /* Insert at head of the new bucket. */
258 node->next = new_nodes[new_hash];
259 new_nodes[new_hash] = node;
260
261 node = next;
262 }
263 }
264
265 free(ht->hash_table.nodes);
266 ht->hash_table.nodes = new_nodes;
267 ht->hash_table.size = new_size;
268
269 return 0;
270 }
271
272 #define NL_INIT_RHASH_ENTRIES 8
273
274 /**
275 * Allocate resizeable hashtable
276 *
277 * @return Allocated hashtable or NULL.
278 */
279 nl_rhash_table_t *nl_rhash_table_alloc()
280 {
281 nl_rhash_table_t *ht;
282
283 ht = calloc(1, sizeof(*ht));
284 if (!ht)
285 goto errout;
286
287 if (!_nl_hash_table_init(&ht->hash_table, NL_INIT_RHASH_ENTRIES)) {
288 goto errout;
289 }
290
291 ht->orig_size = NL_INIT_RHASH_ENTRIES;
292 ht->nelements = 0;
293
294 return ht;
295 errout:
296 free(ht);
297 return NULL;
298 }
299
300 /**
301 * Free resizeable hashtable including all nodes
302 * @arg ht Resizeable Hashtable
303 *
304 * @note Reference counter of all objects in the hashtable will be decremented.
305 */
306 void nl_rhash_table_free(nl_rhash_table_t *ht)
307 {
308 _nl_hash_table_free(&ht->hash_table);
309 free(ht);
310 }
311
312 /**
313 * Lookup identical object in resizeable hashtable
314 * @arg ht Resizeable Hashtable
315 * @arg obj Object to lookup
316 *
317 * Generates hashkey for `obj` and traverses the corresponding chain calling
318 * `nl_object_identical()` on each trying to find a match.
319 *
320 * @return Pointer to object if match was found or NULL.
321 */
322 struct nl_object *nl_rhash_table_lookup(nl_rhash_table_t *ht,
323 struct nl_object *obj)
324 {
325 return nl_hash_table_lookup(&ht->hash_table, obj);
326 }
327
328 /**
329 * Add object to resizeable hashtable
330 * @arg ht Resizeable Hashtable
331 * @arg obj Object to add
332 *
333 * Adds `obj` to the resizeable hashtable. Object type must support hashing,
334 * otherwise all objects will be added to the chain `0`.
335 *
336 * @note The reference counter of the object is incremented.
337 *
338 * @return 0 on success or a negative error code
339 * @retval -NLE_EXIST Identical object already present in hashtable
340 */
341 int nl_rhash_table_add(nl_rhash_table_t *ht, struct nl_object *obj)
342 {
343 int size;
344 int rc;
345
346 rc = nl_hash_table_add(&ht->hash_table, obj);
347 if (rc < 0)
348 return rc;
349
350 if (obj->ce_ops->oo_keygen == NULL)
351 return 0;
352
353 /* Update element count and resize if load factor exceeded */
354 ht->nelements++;
355
356 size = ht->hash_table.size;
357 if (ht->nelements * NL_HT_LOAD_DEN > size * NL_HT_LOAD_NUM) {
358 /* Ignore allocation failure – operating with the old table
359 * keeps us functional albeit slower.
360 */
361 nl_rhash_table_resize(ht, size * 2);
362 }
363
364 return 0;
365 }
366
367 /**
368 * Remove object from resizeable hashtable
369 * @arg ht Resizeable Hashtable
370 * @arg obj Object to remove
371 *
372 * Remove `obj` from resizeable hashtable if it exists.
373 *
374 * @note Reference counter of object will be decremented.
375 *
376 * @return 0 on success or a negative error code.
377 * @retval -NLE_OBJ_NOTFOUND Object not present in hashtable.
378 */
379 int nl_rhash_table_del(nl_rhash_table_t *ht, struct nl_object *obj)
380 {
381 int size;
382 int rc;
383
384 rc = nl_hash_table_del(&ht->hash_table, obj);
385 if (rc < 0)
386 return rc;
387
388 if (obj->ce_ops->oo_keygen == NULL)
389 return 0;
390
391 /* Decrement element count; shrink table if it became sparse.
392 * We keep this simple and only shrink when the table is more than
393 * 4 times sparser than our desired load factor.
394 */
395 if (ht->nelements > 0) {
396 ht->nelements--;
397 }
398 size = ht->hash_table.size;
399 if (size > ht->orig_size &&
400 ht->nelements * NL_HT_LOAD_DEN < (size / 4) * NL_HT_LOAD_NUM) {
401 int new_size = size / 2;
402
403 if (new_size < ht->orig_size)
404 new_size = ht->orig_size;
405
406 nl_rhash_table_resize(ht, new_size);
407 }
408
409 return 0;
410 }
411
412 /** @} */