libnl  3.5.0
hashtable.c
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  */
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  */
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  */
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  */
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  */
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 
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 /** @} */
void nl_object_get(struct nl_object *obj)
Acquire a reference on a object.
Definition: object.c:205
void nl_hash_table_free(nl_hash_table_t *ht)
Free hashtable including all nodes.
Definition: hashtable.c:57
nl_hash_table_t * nl_hash_table_alloc(int size)
Allocate hashtable.
Definition: hashtable.c:30
struct nl_object * nl_hash_table_lookup(nl_hash_table_t *ht, struct nl_object *obj)
Lookup identical object in hashtable.
Definition: hashtable.c:87
int nl_hash_table_add(nl_hash_table_t *ht, struct nl_object *obj)
Add object to hashtable.
Definition: hashtable.c:118
void nl_object_put(struct nl_object *obj)
Release a reference from an object.
Definition: object.c:216
int nl_object_identical(struct nl_object *a, struct nl_object *b)
Check if the identifiers of two objects are identical.
Definition: object.c:314
int nl_hash_table_del(nl_hash_table_t *ht, struct nl_object *obj)
Remove object from hashtable.
Definition: hashtable.c:162
void nl_object_keygen(struct nl_object *obj, uint32_t *hashkey, uint32_t hashtbl_sz)
Generate object hash key.
Definition: object.c:463