[PATCH 2/6] Add nl hashtable structures and access functions
roopa at cumulusnetworks.com
roopa at cumulusnetworks.com
Mon Nov 5 00:13:02 EST 2012
From: roopa <roopa at cumulusnetworks.com>
This patch adds the required structures and access functions to create
and manage hashtables for netlink cache objects
Signed-off-by: Shrijeet Mukherjee <shm at cumulusnetworks.com>
Signed-off-by: Nolan Leake <nolan at cumulusnetworks.com>
Signed-off-by: Roopa Prabhu <roopa at cumulusnetworks.com>
Reviewed-by: Wilson Kok <wkok at cumulusnetworks.com>
---
include/netlink/hashtable.h | 53 ++++++++++++++++
include/netlink/object-api.h | 9 +++
include/netlink/object.h | 2 +
lib/Makefile.am | 2 +-
lib/hashtable.c | 141 ++++++++++++++++++++++++++++++++++++++++++
lib/object.c | 21 ++++++
6 files changed, 227 insertions(+), 1 deletions(-)
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..3cd7875
--- /dev/null
+++ b/include/netlink/hashtable.h
@@ -0,0 +1,53 @@
+/*
+ * 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 16384
+#define NL_MAX_HASH_KEY 32
+
+/* 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 70a4ddd..0ed2a0c 100644
--- a/include/netlink/object-api.h
+++ b/include/netlink/object-api.h
@@ -335,6 +335,15 @@ struct nl_object_ops
int (*oo_compare)(struct nl_object *, struct nl_object *,
uint32_t, int);
+ /**
+ * 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 bbda5f5..210a488 100644
--- a/include/netlink/object.h
+++ b/include/netlink/object.h
@@ -48,6 +48,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 4d8d58d..4f6a003 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 <string.h>
+#include <netlink-local.h>
+#include <netlink/object.h>
+#include <netlink/hash.h>
+#include <netlink/hashtable.h>
+
+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 055a208..063c2e0 100644
--- a/lib/object.c
+++ b/lib/object.c
@@ -388,6 +388,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;
+}
+
/** @} */
/**
--
1.7.2.5
More information about the libnl
mailing list