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 */ 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 */ 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 */ 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 */ 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 */ 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 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
