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 <netlink/object.h>
9 #include <netlink/hash.h>
10 #include <netlink/hashtable.h>
11
12 #include "nl-aux-core/nl-core.h"
13
14 /**
15 * @ingroup core_types
16 * @defgroup hashtable Hashtable
17 * @{
18 */
19
20 /**
21 * Allocate hashtable
22 * @arg size Size of hashtable in number of elements
23 *
24 * @return Allocated hashtable or NULL.
25 */
nl_hash_table_alloc(int size)26 nl_hash_table_t *nl_hash_table_alloc(int size)
27 {
28 nl_hash_table_t *ht;
29
30 ht = calloc(1, sizeof (*ht));
31 if (!ht)
32 goto errout;
33
34 ht->nodes = calloc(size, sizeof (*ht->nodes));
35 if (!ht->nodes) {
36 free(ht);
37 goto errout;
38 }
39
40 ht->size = size;
41
42 return ht;
43 errout:
44 return NULL;
45 }
46
47 /**
48 * Free hashtable including all nodes
49 * @arg ht Hashtable
50 *
51 * @note Reference counter of all objects in the hashtable will be decremented.
52 */
nl_hash_table_free(nl_hash_table_t * ht)53 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 free(ht);
71 }
72
73 /**
74 * Lookup identical object in hashtable
75 * @arg ht Hashtable
76 * @arg obj Object to lookup
77 *
78 * Generates hashkey for `obj` and traverses the corresponding chain calling
79 * `nl_object_identical()` on each trying to find a match.
80 *
81 * @return Pointer to object if match was found or NULL.
82 */
nl_hash_table_lookup(nl_hash_table_t * ht,struct nl_object * obj)83 struct nl_object* nl_hash_table_lookup(nl_hash_table_t *ht,
84 struct nl_object *obj)
85 {
86 nl_hash_node_t *node;
87 uint32_t key_hash;
88
89 nl_object_keygen(obj, &key_hash, ht->size);
90 node = ht->nodes[key_hash];
91
92 while (node) {
93 if (nl_object_identical(node->obj, obj))
94 return node->obj;
95 node = node->next;
96 }
97
98 return NULL;
99 }
100
101 /**
102 * Add object to hashtable
103 * @arg ht Hashtable
104 * @arg obj Object to add
105 *
106 * Adds `obj` to the hashtable. Object type must support hashing, otherwise all
107 * objects will be added to the chain `0`.
108 *
109 * @note The reference counter of the object is incremented.
110 *
111 * @return 0 on success or a negative error code
112 * @retval -NLE_EXIST Identical object already present in hashtable
113 */
nl_hash_table_add(nl_hash_table_t * ht,struct nl_object * obj)114 int nl_hash_table_add(nl_hash_table_t *ht, struct nl_object *obj)
115 {
116 nl_hash_node_t *node;
117 uint32_t key_hash;
118
119 nl_object_keygen(obj, &key_hash, ht->size);
120 node = ht->nodes[key_hash];
121
122 while (node) {
123 if (nl_object_identical(node->obj, obj)) {
124 NL_DBG(2, "Warning: Add to hashtable found duplicate...\n");
125 return -NLE_EXIST;
126 }
127 node = node->next;
128 }
129
130 NL_DBG (5, "adding cache entry of obj %p in table %p, with hash 0x%x\n",
131 obj, ht, key_hash);
132
133 node = malloc(sizeof(nl_hash_node_t));
134 if (!node)
135 return -NLE_NOMEM;
136 nl_object_get(obj);
137 node->obj = obj;
138 node->key = key_hash;
139 node->key_size = sizeof(uint32_t);
140 node->next = ht->nodes[key_hash];
141 ht->nodes[key_hash] = node;
142
143 return 0;
144 }
145
146 /**
147 * Remove object from hashtable
148 * @arg ht Hashtable
149 * @arg obj Object to remove
150 *
151 * Remove `obj` from hashtable if it exists.
152 *
153 * @note Reference counter of object will be decremented.
154 *
155 * @return 0 on success or a negative error code.
156 * @retval -NLE_OBJ_NOTFOUND Object not present in hashtable.
157 */
nl_hash_table_del(nl_hash_table_t * ht,struct nl_object * obj)158 int nl_hash_table_del(nl_hash_table_t *ht, struct nl_object *obj)
159 {
160 nl_hash_node_t *node, *prev;
161 uint32_t key_hash;
162
163 nl_object_keygen(obj, &key_hash, ht->size);
164 prev = node = ht->nodes[key_hash];
165
166 while (node) {
167 if (nl_object_identical(node->obj, obj)) {
168 nl_object_put(obj);
169
170 NL_DBG (5, "deleting cache entry of obj %p in table %p, with"
171 " hash 0x%x\n", obj, ht, key_hash);
172
173 if (node == ht->nodes[key_hash])
174 ht->nodes[key_hash] = node->next;
175 else
176 prev->next = node->next;
177
178 free(node);
179
180 return 0;
181 }
182 prev = node;
183 node = node->next;
184 }
185
186 return -NLE_OBJ_NOTFOUND;
187 }
188
nl_hash(void * k,size_t length,uint32_t initval)189 uint32_t nl_hash(void *k, size_t length, uint32_t initval)
190 {
191 return(__nl_hash((char *) k, length, initval));
192 }
193
194 /** @} */
195