1054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart/* 2054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * netlink/hashtable.c Netlink hashtable Utilities 3054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 4054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * This library is free software; you can redistribute it and/or 5054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * modify it under the terms of the GNU Lesser General Public 6054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * License as published by the Free Software Foundation version 2.1 7054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * of the License. 8054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 9054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * Copyright (c) 2012 Cumulus Networks, Inc 10054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart */ 11054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart#include <string.h> 12054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart#include <netlink-private/netlink.h> 13054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart#include <netlink/object.h> 14054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart#include <netlink/hash.h> 15054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart#include <netlink/hashtable.h> 16054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 17054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart/** 18054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @ingroup core_types 19054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @defgroup hashtable Hashtable 20054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @{ 21054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart */ 22054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 23054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart/** 24054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * Allocate hashtable 25054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @arg size Size of hashtable in number of elements 26054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 27054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @return Allocated hashtable or NULL. 28054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart */ 29054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewartnl_hash_table_t *nl_hash_table_alloc(int size) 30054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart{ 31054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_hash_table_t *ht; 32054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 33054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart ht = calloc(1, sizeof (*ht)); 34054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart if (!ht) 35054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart goto errout; 36054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 37054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart ht->nodes = calloc(size, sizeof (*ht->nodes)); 38054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart if (!ht->nodes) { 39054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart free(ht); 40054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart goto errout; 41054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart } 42054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 43054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart ht->size = size; 44054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 45054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart return ht; 46054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewarterrout: 47054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart return NULL; 48054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart} 49054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 50054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart/** 51054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * Free hashtable including all nodes 52054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @arg ht Hashtable 53054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 54054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @note Reference counter of all objects in the hashtable will be decremented. 55054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart */ 56054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewartvoid nl_hash_table_free(nl_hash_table_t *ht) 57054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart{ 58054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart int i; 59054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 60054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart for(i = 0; i < ht->size; i++) { 61054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_hash_node_t *node = ht->nodes[i]; 62054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_hash_node_t *saved_node; 63054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 64054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart while (node) { 65054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart saved_node = node; 66054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart node = node->next; 67054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_object_put(saved_node->obj); 68054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart free(saved_node); 69054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart } 70054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart } 71054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 72054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart free(ht->nodes); 73054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart free(ht); 74054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart} 75054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 76054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart/** 77054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * Lookup identical object in hashtable 78054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @arg ht Hashtable 79054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @arg obj Object to lookup 80054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 81054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * Generates hashkey for `obj` and traverses the corresponding chain calling 82054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * `nl_object_identical()` on each trying to find a match. 83054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 84054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @return Pointer to object if match was found or NULL. 85054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart */ 86054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewartstruct nl_object* nl_hash_table_lookup(nl_hash_table_t *ht, 87054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart struct nl_object *obj) 88054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart{ 89054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_hash_node_t *node; 90054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart uint32_t key_hash; 91054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 92054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_object_keygen(obj, &key_hash, ht->size); 93054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart node = ht->nodes[key_hash]; 94054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 95054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart while (node) { 96054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart if (nl_object_identical(node->obj, obj)) 97054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart return node->obj; 98054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart node = node->next; 99054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart } 100054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 101054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart return NULL; 102054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart} 103054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 104054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart/** 105054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * Add object to hashtable 106054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @arg ht Hashtable 107054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @arg obj Object to add 108054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 109054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * Adds `obj` to the hashtable. Object type must support hashing, otherwise all 110054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * objects will be added to the chain `0`. 111054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 112054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @note The reference counter of the object is incremented. 113054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 114054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @return 0 on success or a negative error code 115054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @retval -NLE_EXIST Identical object already present in hashtable 116054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart */ 117054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewartint nl_hash_table_add(nl_hash_table_t *ht, struct nl_object *obj) 118054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart{ 119054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_hash_node_t *node; 120054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart uint32_t key_hash; 121054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 122054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_object_keygen(obj, &key_hash, ht->size); 123054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart node = ht->nodes[key_hash]; 124054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 125054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart while (node) { 126054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart if (nl_object_identical(node->obj, obj)) { 127054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart NL_DBG(2, "Warning: Add to hashtable found duplicate...\n"); 128054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart return -NLE_EXIST; 129054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart } 130054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart node = node->next; 131054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart } 132054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 133054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart NL_DBG (5, "adding cache entry of obj %p in table %p, with hash 0x%x\n", 134054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart obj, ht, key_hash); 135054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 136054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart node = malloc(sizeof(nl_hash_node_t)); 137054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart if (!node) 138054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart return -NLE_NOMEM; 139054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_object_get(obj); 140054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart node->obj = obj; 141054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart node->key = key_hash; 142054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart node->key_size = sizeof(uint32_t); 143054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart node->next = ht->nodes[key_hash]; 144054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart ht->nodes[key_hash] = node; 145054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 146054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart return 0; 147054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart} 148054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 149054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart/** 150054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * Remove object from hashtable 151054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @arg ht Hashtable 152054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @arg obj Object to remove 153054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 154054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * Remove `obj` from hashtable if it exists. 155054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 156054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @note Reference counter of object will be decremented. 157054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * 158054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @return 0 on success or a negative error code. 159054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart * @retval -NLE_OBJ_NOTFOUND Object not present in hashtable. 160054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart */ 161054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewartint nl_hash_table_del(nl_hash_table_t *ht, struct nl_object *obj) 162054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart{ 163054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_hash_node_t *node, *prev; 164054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart uint32_t key_hash; 165054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 166054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_object_keygen(obj, &key_hash, ht->size); 167054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart prev = node = ht->nodes[key_hash]; 168054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 169054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart while (node) { 170054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart if (nl_object_identical(node->obj, obj)) { 171054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart nl_object_put(obj); 172054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 173054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart NL_DBG (5, "deleting cache entry of obj %p in table %p, with" 174054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart " hash 0x%x\n", obj, ht, key_hash); 175054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 176054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart if (node == ht->nodes[key_hash]) 177054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart ht->nodes[key_hash] = node->next; 178054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart else 179054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart prev->next = node->next; 180054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 181054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart free(node); 182054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 183054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart return 0; 184054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart } 185054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart prev = node; 186054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart node = node->next; 187054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart } 188054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 189054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart return -NLE_OBJ_NOTFOUND; 190054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart} 191054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 192054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewartuint32_t nl_hash(void *k, size_t length, uint32_t initval) 193054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart{ 194054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart return(__nl_hash(k, length, initval)); 195054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart} 196054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart 197054c80d775f2ae9b8f50260bdfcb821e99c0da2aPaul Stewart/** @} */ 198