From c6f89ed02f04ac4984be34418774a7b06ff54f79 Mon Sep 17 00:00:00 2001 From: roopa Date: Fri, 9 Nov 2012 14:41:32 -0800 Subject: Add nl hashtable structures and access functions This patch adds the required structures and access functions to create and manage hashtables for netlink cache objects Signed-off-by: Shrijeet Mukherjee Signed-off-by: Nolan Leake Signed-off-by: Roopa Prabhu Reviewed-by: Wilson Kok Signed-off-by: Thomas Graf --- include/netlink/hashtable.h | 52 ++++++++++++++++ include/netlink/object-api.h | 10 +++ include/netlink/object.h | 2 + lib/Makefile.am | 2 +- lib/hashtable.c | 141 +++++++++++++++++++++++++++++++++++++++++++ lib/object.c | 21 +++++++ 6 files changed, 227 insertions(+), 1 deletion(-) create mode 100644 include/netlink/hashtable.h create mode 100644 lib/hashtable.c diff --git a/include/netlink/hashtable.h b/include/netlink/hashtable.h new file mode 100644 index 0000000..d9e6ee4 --- /dev/null +++ b/include/netlink/hashtable.h @@ -0,0 +1,52 @@ +/* + * netlink/hashtable.h Netlink hashtable Utilities + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation version 2.1 + * of the License. + * + * Copyright (c) 2012 Cumulus Networks, Inc + */ + +#ifndef NETLINK_HASHTABLE_H_ +#define NETLINK_HASHTABLE_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct nl_hash_node { + uint32_t key; + uint32_t key_size; + struct nl_object * obj; + struct nl_hash_node * next; +} nl_hash_node_t; + +typedef struct nl_hash_table { + int size; + nl_hash_node_t ** nodes; +} nl_hash_table_t; + +/* Default hash table size */ +#define NL_MAX_HASH_ENTRIES 1024 + +/* Access Functions */ +extern nl_hash_table_t * nl_hash_table_alloc(int size); +extern void nl_hash_table_free(nl_hash_table_t *ht); + +extern int nl_hash_table_add(nl_hash_table_t *ht, + struct nl_object *obj); +extern int nl_hash_table_del(nl_hash_table_t *ht, + struct nl_object *obj); + +extern struct nl_object * nl_hash_table_lookup(nl_hash_table_t *ht, + struct nl_object *obj); +extern uint32_t nl_hash(void *k, size_t length, + uint32_t initval); + +#ifdef __cplusplus +} +#endif + +#endif /* NETLINK_HASHTABLE_H_ */ diff --git a/include/netlink/object-api.h b/include/netlink/object-api.h index ec2192b..ae6180a 100644 --- a/include/netlink/object-api.h +++ b/include/netlink/object-api.h @@ -348,6 +348,16 @@ struct nl_object_ops */ int (*oo_update)(struct nl_object *, struct nl_object *); + /** + * Hash Key generator function + * + * When called returns a hash key for the object being + * referenced. This key will be used by higher level hash functions + * to build association lists. Each object type gets to specify + * it's own key formulation + */ + void (*oo_keygen)(struct nl_object *, uint32_t *, uint32_t); + char *(*oo_attrs2str)(int, char *, size_t); /** diff --git a/include/netlink/object.h b/include/netlink/object.h index 788ae48..f25713e 100644 --- a/include/netlink/object.h +++ b/include/netlink/object.h @@ -50,6 +50,8 @@ extern char * nl_object_attrs2str(struct nl_object *, size_t); extern char * nl_object_attr_list(struct nl_object *, char *, size_t); +extern void nl_object_keygen(struct nl_object *, + uint32_t *, uint32_t); /* Marks */ extern void nl_object_mark(struct nl_object *); diff --git a/lib/Makefile.am b/lib/Makefile.am index c79ba29..7481941 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -18,7 +18,7 @@ lib_LTLIBRARIES = \ libnl_3_la_SOURCES = \ addr.c attr.c cache.c cache_mngr.c cache_mngt.c data.c \ error.c handlers.c msg.c nl.c object.c socket.c utils.c \ - version.c hash.c + version.c hash.c hashtable.c libnl_genl_3_la_LIBADD = libnl-3.la libnl_genl_3_la_SOURCES = \ diff --git a/lib/hashtable.c b/lib/hashtable.c new file mode 100644 index 0000000..59cd91e --- /dev/null +++ b/lib/hashtable.c @@ -0,0 +1,141 @@ +/* + * netlink/hashtable.c Netlink hashtable Utilities + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation version 2.1 + * of the License. + * + * Copyright (c) 2012 Cumulus Networks, Inc + */ +#include +#include +#include +#include +#include + +nl_hash_table_t *nl_hash_table_alloc(int size) +{ + nl_hash_table_t *ht; + + ht = calloc(1, sizeof (*ht)); + if (!ht) + goto errout; + + ht->nodes = calloc(size, sizeof (*ht->nodes)); + if (!ht->nodes) { + free(ht); + goto errout; + } + + ht->size = size; + + return ht; +errout: + return NULL; +} + +void nl_hash_table_free(nl_hash_table_t *ht) +{ + int i; + + for(i = 0; i < ht->size; i++) { + nl_hash_node_t *node = ht->nodes[i]; + nl_hash_node_t *saved_node; + + while (node) { + saved_node = node; + node = node->next; + free(saved_node); + } + } + + free(ht->nodes); + free(ht); +} + +struct nl_object* nl_hash_table_lookup(nl_hash_table_t *ht, + struct nl_object *obj) +{ + nl_hash_node_t *node; + uint32_t key_hash; + + nl_object_keygen(obj, &key_hash, ht->size); + node = ht->nodes[key_hash]; + + while (node) { + if (nl_object_identical(node->obj, obj)) + return node->obj; + node = node->next; + } + + return NULL; +} + +int nl_hash_table_add(nl_hash_table_t *ht, struct nl_object *obj) +{ + nl_hash_node_t *node; + uint32_t key_hash; + + nl_object_keygen(obj, &key_hash, ht->size); + node = ht->nodes[key_hash]; + + while (node) { + if (nl_object_identical(node->obj, obj)) { + NL_DBG(2, "Warning: Add to hashtable found duplicate...\n"); + return -NLE_EXIST; + } + node = node->next; + } + + NL_DBG (5, "adding cache entry of obj %p in table %p, with hash 0x%x\n", + obj, ht, key_hash); + + node = malloc(sizeof(nl_hash_node_t)); + if (!node) + return -NLE_NOMEM; + nl_object_get(obj); + node->obj = obj; + node->key = key_hash; + node->key_size = sizeof(uint32_t); + node->next = ht->nodes[key_hash]; + ht->nodes[key_hash] = node; + + return 0; +} + +int nl_hash_table_del(nl_hash_table_t *ht, struct nl_object *obj) +{ + nl_hash_node_t *node, *prev; + uint32_t key_hash; + + nl_object_keygen(obj, &key_hash, ht->size); + prev = node = ht->nodes[key_hash]; + + while (node) { + if (nl_object_identical(node->obj, obj)) { + nl_object_put(obj); + + NL_DBG (5, "deleting cache entry of obj %p in table %p, with" + " hash 0x%x\n", obj, ht, key_hash); + + if (node == ht->nodes[key_hash]) + ht->nodes[key_hash] = node->next; + else + prev->next = node->next; + + free(node); + + return 0; + } + prev = node; + node = node->next; + } + + return -1; +} + +uint32_t nl_hash(void *k, size_t length, uint32_t initval) +{ + return(hash(k, length, initval)); +} diff --git a/lib/object.c b/lib/object.c index d58f9a7..024062e 100644 --- a/lib/object.c +++ b/lib/object.c @@ -413,6 +413,27 @@ char *nl_object_attr_list(struct nl_object *obj, char *buf, size_t len) return nl_object_attrs2str(obj, obj->ce_mask, buf, len); } +/** + * Generate object hash key + * @arg obj the object + * @arg hashkey destination buffer to be used for key stream + * @arg hashtbl_sz hash table size + * + * @return hash key in destination buffer + */ +void nl_object_keygen(struct nl_object *obj, uint32_t *hashkey, + uint32_t hashtbl_sz) +{ + struct nl_object_ops *ops = obj_ops(obj); + + if (ops->oo_keygen) + ops->oo_keygen(obj, hashkey, hashtbl_sz); + else + *hashkey = 0; + + return; +} + /** @} */ /** -- cgit v1.2.1