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