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