diff options
author | Pablo Neira Ayuso <pablo@netfilter.org> | 2010-01-11 19:15:49 +0100 |
---|---|---|
committer | Pablo Neira Ayuso <pablo@netfilter.org> | 2010-01-17 22:23:17 +0100 |
commit | ec9983fa23bc2e5a9c4bdf06c533c5e8ae483ade (patch) | |
tree | a54c1d7b7085cb92fc316605eb04671680350ab8 /src/hash.c | |
parent | 1f50a6a2d5a4ede3505f9298b25fc3e081cbc443 (diff) |
NFCT: use new hashtable implementation for better performance
This patch replaces the existing hashtable implementation with
a newer that provide better performance since it reduces the
number of hash computations.
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Diffstat (limited to 'src/hash.c')
-rw-r--r-- | src/hash.c | 168 |
1 files changed, 58 insertions, 110 deletions
@@ -1,6 +1,6 @@ /* - * (C) 2006-2007 by Pablo Neira Ayuso <pablo@netfilter.org> - * + * (C) 2006-2009 by Pablo Neira Ayuso <pablo@netfilter.org> + * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or @@ -18,55 +18,35 @@ * Description: generic hash table implementation */ -#include <ulogd/hash.h> -#include <ulogd/slist.h> +#include "ulogd/hash.h" #include <errno.h> #include <stdlib.h> #include <string.h> - -struct hashtable_node *hashtable_alloc_node(int datasize, void *data) -{ - struct hashtable_node *n; - int size = sizeof(struct hashtable_node) + datasize; - - n = malloc(size); - if (!n) - return NULL; - memset(n, 0, size); - memcpy(n->data, data, datasize); - - return n; -} - -void hashtable_destroy_node(struct hashtable_node *h) -{ - free(h); -} +#include <limits.h> struct hashtable * -hashtable_create(int hashsize, int limit, int datasize, - uint32_t (*hash)(const void *data, struct hashtable *table), +hashtable_create(int hashsize, int limit, + uint32_t (*hash)(const void *data, + const struct hashtable *table), int (*compare)(const void *data1, const void *data2)) { int i; struct hashtable *h; int size = sizeof(struct hashtable) - + hashsize * sizeof(struct slist_head); + + hashsize * sizeof(struct llist_head); - h = (struct hashtable *) malloc(size); - if (!h) { + h = (struct hashtable *) calloc(size, 1); + if (h == NULL) { errno = ENOMEM; return NULL; } - memset(h, 0, size); for (i=0; i<hashsize; i++) - INIT_SLIST_HEAD(h->members[i]); + INIT_LLIST_HEAD(&h->members[i]); h->hashsize = hashsize; h->limit = limit; - h->datasize = datasize; h->hash = hash; h->compare = compare; @@ -75,118 +55,86 @@ hashtable_create(int hashsize, int limit, int datasize, void hashtable_destroy(struct hashtable *h) { - if (h) { - hashtable_flush(h); - free(h); - } + free(h); } -void *hashtable_add(struct hashtable *table, void *data) +int hashtable_hash(const struct hashtable *table, const void *data) { - uint32_t id; - struct slist_head *e; - struct hashtable_node *n; - - /* hash table is full */ - if (table->count >= table->limit) { - errno = ENOSPC; - return 0; - } - - id = table->hash(data, table); - - slist_for_each(e, &table->members[id]) { - n = slist_entry(e, struct hashtable_node, head); - if (table->compare(n->data, data)) { - errno = EEXIST; - return 0; - } - } - - n = hashtable_alloc_node(table->datasize, data); - if (n == NULL) { - errno = ENOMEM; - return NULL; - } - - slist_add(&table->members[id], &n->head); - table->count++; - - return n->data; + return table->hash(data, table); } -void *hashtable_get(struct hashtable *table, const void *data) +struct hashtable_node * +hashtable_find(const struct hashtable *table, const void *data, int id) { - struct slist_head *e; - uint32_t id; + struct llist_head *e; struct hashtable_node *n; - id = table->hash(data, table); - - slist_for_each(e, &table->members[id]) { - n = slist_entry(e, struct hashtable_node, head); - if (table->compare(n->data, data)) - return n->data; + llist_for_each(e, &table->members[id]) { + n = llist_entry(e, struct hashtable_node, head); + if (table->compare(n, data)) { + return n; + } } - errno = ENOENT; return NULL; } -int hashtable_del(struct hashtable *table, void *data) +int hashtable_add(struct hashtable *table, struct hashtable_node *n, int id) { - struct slist_head *e, *next, *prev; - uint32_t id; - struct hashtable_node *n; - - id = table->hash(data, table); - - slist_for_each_safe(e, prev, next, &table->members[id]) { - n = slist_entry(e, struct hashtable_node, head); - if (table->compare(n->data, data)) { - slist_del(e, prev); - hashtable_destroy_node(n); - table->count--; - return 0; - } + /* hash table is full */ + if (table->count >= table->limit) { + errno = ENOSPC; + return -1; } - errno = ENOENT; - return -1; + llist_add(&n->head, &table->members[id]); + table->count++; + return 0; +} + +void hashtable_del(struct hashtable *table, struct hashtable_node *n) +{ + llist_del(&n->head); + table->count--; } int hashtable_flush(struct hashtable *table) { uint32_t i; - struct slist_head *e, *next, *prev; + struct llist_head *e, *tmp; struct hashtable_node *n; - for (i=0; i < table->hashsize; i++) - slist_for_each_safe(e, prev, next, &table->members[i]) { - n = slist_entry(e, struct hashtable_node, head); - slist_del(e, prev); - hashtable_destroy_node(n); + for (i=0; i < table->hashsize; i++) { + llist_for_each_safe(e, tmp, &table->members[i]) { + n = llist_entry(e, struct hashtable_node, head); + free(n); } - - table->count = 0; - + } return 0; } -int hashtable_iterate(struct hashtable *table, void *data, - int (*iterate)(void *data1, void *data2)) +int +hashtable_iterate_limit(struct hashtable *table, void *data, + uint32_t from, uint32_t steps, + int (*iterate)(void *data1, void *n)) { uint32_t i; - struct slist_head *e, *next, *prev; + struct llist_head *e, *tmp; struct hashtable_node *n; - for (i=0; i < table->hashsize; i++) { - slist_for_each_safe(e, prev, next, &table->members[i]) { - n = slist_entry(e, struct hashtable_node, head); - if (iterate(data, n->data) == -1) + for (i=from; i < table->hashsize && i < from+steps; i++) { + llist_for_each_safe(e, tmp, &table->members[i]) { + n = llist_entry(e, struct hashtable_node, head); + if (iterate(data, n) == -1) return -1; } } - return 0; + return i; +} + +int hashtable_iterate(struct hashtable *table, void *data, + int (*iterate)(void *data1, void *n)) +{ + return hashtable_iterate_limit(table, data, 0, UINT_MAX, iterate); } unsigned int hashtable_counter(const struct hashtable *table) |