summaryrefslogtreecommitdiff
path: root/src/hash.c
diff options
context:
space:
mode:
authorPablo Neira Ayuso <pablo@netfilter.org>2009-01-15 23:19:57 +0100
committerPablo Neira Ayuso <pablo@netfilter.org>2009-01-15 23:19:57 +0100
commit50339f96638eed35dac2b673b64cc6f1eb96406c (patch)
tree20dbb60fd3c41994da7cd7ad8888185c681fadb1 /src/hash.c
parentb28224b0326636ff5832b38817b7720f48070ee7 (diff)
downloadconntrack-tools-50339f96638eed35dac2b673b64cc6f1eb96406c.tar.gz
conntrack-tools-50339f96638eed35dac2b673b64cc6f1eb96406c.zip
src: rework of the hash-cache infrastructure
Currently, the caching system is implemented in a two layer architecture: hashtable (inner layer) and cache (upper layer). This patch reworks the hash-cache infrastructure to solve some initial design problems to make it more flexible, the main strong points of this patch are: * Memory handling is done in the cache layer, not in the inner hashtable layer. This removes one of the main dependencies between the hashtable and the cache classes. * Remove excessive encapsulation: the former cache used to hide a lot of details of the inner hashtable implementation. * Fix over-hashing of some operations: lookup-delete-add required three hash calculations. Similarly, the update-or-add operation required two hash calculations. Now, we calculate the hash once and re-use the value how many times as we need. This patch simplifies the caching system. As a result, we save ~130 lines of code. Small code means and less complexity means less chance to have bugs. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Diffstat (limited to 'src/hash.c')
-rw-r--r--src/hash.c136
1 files changed, 39 insertions, 97 deletions
diff --git a/src/hash.c b/src/hash.c
index 1edb977..9c9ea5b 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -1,5 +1,5 @@
/*
- * (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
@@ -19,32 +19,13 @@
*/
#include "hash.h"
-#include "slist.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 = calloc(size, 1);
- if (n == NULL)
- return NULL;
- memcpy(n->data, data, datasize);
-
- return n;
-}
-
-void hashtable_destroy_node(struct hashtable_node *h)
-{
- free(h);
-}
-
struct hashtable *
-hashtable_create(int hashsize, int limit, int datasize,
+hashtable_create(int hashsize, int limit,
uint32_t (*hash)(const void *data,
const struct hashtable *table),
int (*compare)(const void *data1, const void *data2))
@@ -52,7 +33,7 @@ hashtable_create(int hashsize, int limit, int datasize,
int i;
struct hashtable *h;
int size = sizeof(struct hashtable)
- + hashsize * sizeof(struct slist_head);
+ + hashsize * sizeof(struct list_head);
h = (struct hashtable *) calloc(size, 1);
if (h == NULL) {
@@ -61,11 +42,10 @@ hashtable_create(int hashsize, int limit, int datasize,
}
for (i=0; i<hashsize; i++)
- INIT_SLIST_HEAD(h->members[i]);
+ INIT_LIST_HEAD(&h->members[i]);
h->hashsize = hashsize;
h->limit = limit;
- h->datasize = datasize;
h->hash = hash;
h->compare = compare;
@@ -74,112 +54,74 @@ hashtable_create(int hashsize, int limit, int datasize,
void hashtable_destroy(struct hashtable *h)
{
- hashtable_flush(h);
free(h);
}
-void *hashtable_add(struct hashtable *table, void *data)
+int hashtable_hash(const struct hashtable *table, const void *data)
{
- struct slist_head *e;
- struct hashtable_node *n;
- uint32_t id;
-
- /* hash table is full */
- if (table->count >= table->limit) {
- errno = ENOSPC;
- return NULL;
- }
-
- 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 NULL;
- }
- }
-
- 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_find(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 list_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;
+ list_for_each(e, &table->members[id]) {
+ n = list_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;
+ list_add(&n->head, &table->members[id]);
+ table->count++;
+ return 0;
+}
+
+void hashtable_del(struct hashtable *table, struct hashtable_node *n)
+{
+ list_del(&n->head);
+ table->count--;
}
int hashtable_flush(struct hashtable *table)
{
uint32_t i;
- struct slist_head *e, *next, *prev;
+ struct list_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++) {
+ list_for_each_safe(e, tmp, &table->members[i]) {
+ n = list_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 (*iterate)(void *data1, struct hashtable_node *n))
{
uint32_t i;
- struct slist_head *e, *next, *prev;
+ struct list_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)
+ list_for_each_safe(e, tmp, &table->members[i]) {
+ n = list_entry(e, struct hashtable_node, head);
+ if (iterate(data, n) == -1)
return -1;
}
}