* [PATCH 2/6] NFCT: change `pollinterval' behaviour
2010-01-13 11:42 [PATCH 0/6] ulogd2 updates for NFCT Pablo Neira Ayuso
2010-01-13 11:42 ` [PATCH 1/6] NFCT: cleanup constructor and destructor functions Pablo Neira Ayuso
@ 2010-01-13 11:42 ` Pablo Neira Ayuso
2010-01-13 11:43 ` [PATCH 3/6] NFCT: use new hashtable implementation for better performance Pablo Neira Ayuso
` (3 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Pablo Neira Ayuso @ 2010-01-13 11:42 UTC (permalink / raw)
To: netfilter-devel
This patch adds support for poll-based logging. Basically,
ulogd polls from the kernel periodically to log entries. You
can use the `pollinterval' option in the configuration file to
set the polling period.
This patch changes the current behaviour of `pollinterval'
that allowed to mix both the event-driven logging with
polling periodically from the kernel. I have tried to look
for anyone in google (and asking Eric Leblond) using this
feature but I found noone.
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
input/flow/ulogd_inpflow_NFCT.c | 128 +++++++++++++++++++++++++++++++++++++--
ulogd.conf.in | 1
2 files changed, 121 insertions(+), 8 deletions(-)
diff --git a/input/flow/ulogd_inpflow_NFCT.c b/input/flow/ulogd_inpflow_NFCT.c
index 9ef4eae..d76649e 100644
--- a/input/flow/ulogd_inpflow_NFCT.c
+++ b/input/flow/ulogd_inpflow_NFCT.c
@@ -567,7 +567,6 @@ do_propagate_ct(struct ulogd_pluginstance *upi,
propagate_ct(upi, ct, type, ts);
}
-/* XXX: pollinterval needs a different handler */
static int event_handler(enum nf_conntrack_msg_type type,
struct nf_conntrack *ct,
void *data)
@@ -646,6 +645,40 @@ static int event_handler(enum nf_conntrack_msg_type type,
return NFCT_CB_CONTINUE;
}
+static int
+polling_handler(enum nf_conntrack_msg_type type,
+ struct nf_conntrack *ct, void *data)
+{
+ struct ulogd_pluginstance *upi = data;
+ struct nfct_pluginstance *cpi =
+ (struct nfct_pluginstance *) upi->private;
+ struct ct_timestamp *ts = NULL;
+ struct ct_timestamp tmp = {
+ .ct = ct,
+ };
+
+ switch(type) {
+ case NFCT_T_UPDATE:
+ ts = hashtable_get(cpi->ct_active, &tmp);
+ if (ts)
+ nfct_copy(ts->ct, ct, NFCT_CP_META);
+ else {
+ ts = hashtable_add(cpi->ct_active, &tmp);
+ if (ts == NULL)
+ return NFCT_CB_CONTINUE;
+
+ gettimeofday(&ts->time[START], NULL);
+ return NFCT_CB_STOLEN;
+ }
+ break;
+ default:
+ ulogd_log(ULOGD_NOTICE, "unknown netlink message type\n");
+ break;
+ }
+
+ return NFCT_CB_CONTINUE;
+}
+
static int setnlbufsiz(struct ulogd_pluginstance *upi, int size)
{
struct nfct_pluginstance *cpi =
@@ -804,13 +837,15 @@ static int get_ctr_zero(struct ulogd_pluginstance *upi)
return nfct_query(cpi->cth, NFCT_Q_DUMP_RESET, &family);
}
-static void getctr_timer_cb(struct ulogd_timer *t, void *data)
+static void polling_timer_cb(struct ulogd_timer *t, void *data)
{
struct ulogd_pluginstance *upi = data;
struct nfct_pluginstance *cpi =
(struct nfct_pluginstance *)upi->private;
+ int family = AF_UNSPEC;
- get_ctr_zero(upi);
+ nfct_query(cpi->pgh, NFCT_Q_DUMP, &family);
+ hashtable_iterate(cpi->ct_active, upi, do_purge);
ulogd_add_timer(&cpi->timer, pollint_ce(upi->config_kset).u.value);
}
@@ -825,7 +860,7 @@ static int configure_nfct(struct ulogd_pluginstance *upi,
if (ret < 0)
return ret;
- ulogd_init_timer(&cpi->timer, upi, getctr_timer_cb);
+ ulogd_init_timer(&cpi->timer, upi, polling_timer_cb);
if (pollint_ce(upi->config_kset).u.value != 0)
ulogd_add_timer(&cpi->timer,
pollint_ce(upi->config_kset).u.value);
@@ -843,7 +878,7 @@ static void overrun_timeout(struct ulogd_timer *a, void *data)
nfct_send(cpi->ovh, NFCT_Q_DUMP, &family);
}
-static int constructor_nfct(struct ulogd_pluginstance *upi)
+static int constructor_nfct_events(struct ulogd_pluginstance *upi)
{
struct nfct_pluginstance *cpi =
(struct nfct_pluginstance *)upi->private;
@@ -916,6 +951,7 @@ static int constructor_nfct(struct ulogd_pluginstance *upi)
}
}
+ ulogd_log(ULOGD_NOTICE, "NFCT plugin working in event mode\n");
return 0;
err_pgh:
@@ -930,9 +966,61 @@ err_cth:
return -1;
}
-static int destructor_nfct(struct ulogd_pluginstance *pi)
+static int constructor_nfct_polling(struct ulogd_pluginstance *upi)
{
- struct nfct_pluginstance *cpi = (void *) pi->private;
+ struct nfct_pluginstance *cpi =
+ (struct nfct_pluginstance *)upi->private;
+
+ if (usehash_ce(upi->config_kset).u.value == 0) {
+ ulogd_log(ULOGD_FATAL, "NFCT polling mode requires "
+ "the hashtable\n");
+ goto err;
+ }
+
+ cpi->pgh = nfct_open(NFNL_SUBSYS_CTNETLINK, 0);
+ if (!cpi->pgh) {
+ ulogd_log(ULOGD_FATAL, "error opening ctnetlink\n");
+ goto err;
+ }
+ nfct_callback_register(cpi->pgh, NFCT_T_ALL, &polling_handler, upi);
+
+ cpi->ct_active =
+ hashtable_create(buckets_ce(upi->config_kset).u.value,
+ maxentries_ce(upi->config_kset).u.value,
+ sizeof(struct ct_timestamp),
+ hash,
+ compare);
+ if (!cpi->ct_active) {
+ ulogd_log(ULOGD_FATAL, "error allocating hash\n");
+ goto err_hashtable;
+ }
+
+ ulogd_log(ULOGD_NOTICE, "NFCT working in polling mode\n");
+ return 0;
+
+err_hashtable:
+ nfct_close(cpi->pgh);
+err:
+ return -1;
+}
+
+static int constructor_nfct(struct ulogd_pluginstance *upi)
+{
+ if (pollint_ce(upi->config_kset).u.value == 0) {
+ /* listen to ctnetlink events. */
+ return constructor_nfct_events(upi);
+ } else {
+ /* poll from ctnetlink periodically. */
+ return constructor_nfct_polling(upi);
+ }
+ /* should not ever happen. */
+ ulogd_log(ULOGD_FATAL, "invalid NFCT configuration\n");
+ return -1;
+}
+
+static int destructor_nfct_events(struct ulogd_pluginstance *upi)
+{
+ struct nfct_pluginstance *cpi = (void *) upi->private;
int rc;
ulogd_unregister_fd(&cpi->nfct_fd);
@@ -942,7 +1030,7 @@ static int destructor_nfct(struct ulogd_pluginstance *pi)
return rc;
- if (usehash_ce(pi->config_kset).u.value != 0) {
+ if (usehash_ce(upi->config_kset).u.value != 0) {
ulogd_del_timer(&cpi->ov_timer);
ulogd_unregister_fd(&cpi->nfct_ov);
@@ -960,6 +1048,30 @@ static int destructor_nfct(struct ulogd_pluginstance *pi)
return 0;
}
+static int destructor_nfct_polling(struct ulogd_pluginstance *upi)
+{
+ int rc;
+ struct nfct_pluginstance *cpi = (void *)upi->private;
+
+ rc = nfct_close(cpi->pgh);
+ if (rc < 0)
+ return rc;
+
+ return 0;
+}
+
+static int destructor_nfct(struct ulogd_pluginstance *upi)
+{
+ if (pollint_ce(upi->config_kset).u.value == 0) {
+ return destructor_nfct_events(upi);
+ } else {
+ return destructor_nfct_polling(upi);
+ }
+ /* should not ever happen. */
+ ulogd_log(ULOGD_FATAL, "invalid NFCT configuration\n");
+ return -1;
+}
+
static void signal_nfct(struct ulogd_pluginstance *pi, int signal)
{
switch (signal) {
diff --git a/ulogd.conf.in b/ulogd.conf.in
index 4542fc4..b77d726 100644
--- a/ulogd.conf.in
+++ b/ulogd.conf.in
@@ -92,6 +92,7 @@ plugin="@libdir@/ulogd/ulogd_raw2packet_BASE.so"
#netlink_socket_buffer_size=217088
#netlink_socket_buffer_maxsize=1085440
#netlink_resync_timeout=60 # seconds to wait to perform resynchronization
+#pollinterval=10 # use poll-based logging instead of event-driven
[ct2]
#netlink_socket_buffer_size=217088
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH 3/6] NFCT: use new hashtable implementation for better performance
2010-01-13 11:42 [PATCH 0/6] ulogd2 updates for NFCT Pablo Neira Ayuso
2010-01-13 11:42 ` [PATCH 1/6] NFCT: cleanup constructor and destructor functions Pablo Neira Ayuso
2010-01-13 11:42 ` [PATCH 2/6] NFCT: change `pollinterval' behaviour Pablo Neira Ayuso
@ 2010-01-13 11:43 ` Pablo Neira Ayuso
2010-01-13 11:43 ` [PATCH 4/6] NFCT: split event handler if hashtable is used or not Pablo Neira Ayuso
` (2 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Pablo Neira Ayuso @ 2010-01-13 11:43 UTC (permalink / raw)
To: netfilter-devel
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>
---
include/ulogd/hash.h | 34 +++-----
input/flow/ulogd_inpflow_NFCT.c | 119 ++++++++++++++++++----------
src/hash.c | 168 +++++++++++++--------------------------
3 files changed, 152 insertions(+), 169 deletions(-)
diff --git a/include/ulogd/hash.h b/include/ulogd/hash.h
index 45d2f48..d4aedb8 100644
--- a/include/ulogd/hash.h
+++ b/include/ulogd/hash.h
@@ -2,8 +2,7 @@
#define _NF_SET_HASH_H_
#include <unistd.h>
-#include "slist.h"
-#include <ulogd/linuxlist.h>
+#include "linuxlist.h"
#include <stdint.h>
@@ -15,34 +14,31 @@ struct hashtable {
uint32_t limit;
uint32_t count;
uint32_t initval;
- uint32_t datasize;
+
+ uint32_t (*hash)(const void *data, const struct hashtable *table);
+ int (*compare)(const void *data1, const void *data2);
- uint32_t (*hash)(const void *data, struct hashtable *table);
- int (*compare)(const void *data1, const void *data2);
-
- struct slist_head members[0];
+ struct llist_head members[0];
};
struct hashtable_node {
- struct slist_head head;
- char data[0];
+ struct llist_head head;
};
-struct hashtable_node *hashtable_alloc_node(int datasize, void *data);
-void hashtable_destroy_node(struct hashtable_node *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));
void hashtable_destroy(struct hashtable *h);
-
-void *hashtable_add(struct hashtable *table, void *data);
-void *hashtable_get(struct hashtable *table, const void *data);
-int hashtable_del(struct hashtable *table, void *data);
+int hashtable_hash(const struct hashtable *table, const void *data);
+struct hashtable_node *hashtable_find(const struct hashtable *table, const void *data, int id);
+int hashtable_add(struct hashtable *table, struct hashtable_node *n, int id);
+void hashtable_del(struct hashtable *table, struct hashtable_node *node);
int hashtable_flush(struct hashtable *table);
int hashtable_iterate(struct hashtable *table, void *data,
- int (*iterate)(void *data1, void *data2));
+ int (*iterate)(void *data, void *n));
+int hashtable_iterate_limit(struct hashtable *table, void *data, uint32_t from, uint32_t steps, int (*iterate)(void *data1, void *n));
unsigned int hashtable_counter(const struct hashtable *table);
#endif
diff --git a/input/flow/ulogd_inpflow_NFCT.c b/input/flow/ulogd_inpflow_NFCT.c
index d76649e..96aa8ea 100644
--- a/input/flow/ulogd_inpflow_NFCT.c
+++ b/input/flow/ulogd_inpflow_NFCT.c
@@ -49,6 +49,7 @@
typedef enum TIMES_ { START, STOP, __TIME_MAX } TIMES;
struct ct_timestamp {
+ struct hashtable_node hashnode;
struct timeval time[__TIME_MAX];
struct nf_conntrack *ct;
};
@@ -380,7 +381,8 @@ static struct ulogd_key nfct_okeys[] = {
},
};
-static uint32_t __hash4(const struct nf_conntrack *ct, struct hashtable *table)
+static uint32_t
+__hash4(const struct nf_conntrack *ct, const struct hashtable *table)
{
unsigned int a, b;
@@ -402,7 +404,8 @@ static uint32_t __hash4(const struct nf_conntrack *ct, struct hashtable *table)
return ((uint64_t)jhash_2words(a, b, 0) * table->hashsize) >> 32;
}
-static uint32_t __hash6(const struct nf_conntrack *ct, struct hashtable *table)
+static uint32_t
+__hash6(const struct nf_conntrack *ct, const struct hashtable *table)
{
unsigned int a, b;
@@ -417,17 +420,17 @@ static uint32_t __hash6(const struct nf_conntrack *ct, struct hashtable *table)
return ((uint64_t)jhash_2words(a, b, 0) * table->hashsize) >> 32;
}
-static uint32_t hash(const void *data, struct hashtable *table)
+static uint32_t hash(const void *data, const struct hashtable *table)
{
int ret = 0;
- const struct ct_timestamp *ts = data;
+ const struct nf_conntrack *ct = data;
- switch(nfct_get_attr_u8(ts->ct, ATTR_L3PROTO)) {
+ switch(nfct_get_attr_u8(ct, ATTR_L3PROTO)) {
case AF_INET:
- ret = __hash4(ts->ct, table);
+ ret = __hash4(ct, table);
break;
case AF_INET6:
- ret = __hash6(ts->ct, table);
+ ret = __hash6(ct, table);
break;
default:
break;
@@ -439,9 +442,9 @@ static uint32_t hash(const void *data, struct hashtable *table)
static int compare(const void *data1, const void *data2)
{
const struct ct_timestamp *u1 = data1;
- const struct ct_timestamp *u2 = data2;
+ const struct nf_conntrack *ct = data2;
- return nfct_cmp(u1->ct, u2->ct, NFCT_CMP_ORIG | NFCT_CMP_REPL);
+ return nfct_cmp(u1->ct, ct, NFCT_CMP_ORIG | NFCT_CMP_REPL);
}
static int propagate_ct(struct ulogd_pluginstance *upi,
@@ -574,12 +577,13 @@ static int event_handler(enum nf_conntrack_msg_type type,
struct ulogd_pluginstance *upi = data;
struct nfct_pluginstance *cpi =
(struct nfct_pluginstance *) upi->private;
- struct ct_timestamp *ts = NULL;
- struct ct_timestamp tmp = {
- .ct = ct,
- };
+ struct ct_timestamp *ts;
+ int ret, id;
if (!usehash_ce(upi->config_kset).u.value) {
+ struct ct_timestamp tmp = {
+ .ct = ct,
+ };
switch(type) {
case NFCT_T_NEW:
gettimeofday(&tmp.time[START], NULL);
@@ -601,41 +605,61 @@ static int event_handler(enum nf_conntrack_msg_type type,
switch(type) {
case NFCT_T_NEW:
- ts = hashtable_add(cpi->ct_active, &tmp);
+ ts = calloc(sizeof(struct ct_timestamp), 1);
if (ts == NULL)
return NFCT_CB_CONTINUE;
+ ts->ct = ct;
gettimeofday(&ts->time[START], NULL);
+
+ id = hashtable_hash(cpi->ct_active, ct);
+ ret = hashtable_add(cpi->ct_active, &ts->hashnode, id);
+ if (ret < 0) {
+ free(ts);
+ return NFCT_CB_CONTINUE;
+ }
return NFCT_CB_STOLEN;
case NFCT_T_UPDATE:
- ts = hashtable_get(cpi->ct_active, &tmp);
+ id = hashtable_hash(cpi->ct_active, ct);
+ ts = (struct ct_timestamp *)
+ hashtable_find(cpi->ct_active, ct, id);
if (ts)
nfct_copy(ts->ct, ct, NFCT_CP_META);
else {
- ts = hashtable_add(cpi->ct_active, &tmp);
+ ts = calloc(sizeof(struct ct_timestamp), 1);
if (ts == NULL)
return NFCT_CB_CONTINUE;
+ ts->ct = ct;
gettimeofday(&ts->time[START], NULL);
+
+ ret = hashtable_add(cpi->ct_active, &ts->hashnode, id);
+ if (ret < 0) {
+ free(ts);
+ return NFCT_CB_CONTINUE;
+ }
return NFCT_CB_STOLEN;
}
break;
case NFCT_T_DESTROY:
- ts = hashtable_get(cpi->ct_active, &tmp);
+ id = hashtable_hash(cpi->ct_active, ct);
+ ts = (struct ct_timestamp *)
+ hashtable_find(cpi->ct_active, ct, id);
if (ts) {
gettimeofday(&ts->time[STOP], NULL);
do_propagate_ct(upi, ct, type, ts);
+ hashtable_del(cpi->ct_active, &ts->hashnode);
+ nfct_destroy(ts->ct);
+ free(ts);
} else {
+ struct ct_timestamp tmp = {
+ .ct = ct,
+ };
gettimeofday(&tmp.time[STOP], NULL);
tmp.time[START].tv_sec = 0;
tmp.time[START].tv_usec = 0;
do_propagate_ct(upi, ct, type, &tmp);
}
-
- if (ts) {
- hashtable_del(cpi->ct_active, ts);
- free(ts->ct);
- }
break;
default:
ulogd_log(ULOGD_NOTICE, "unknown netlink message type\n");
@@ -652,22 +676,29 @@ polling_handler(enum nf_conntrack_msg_type type,
struct ulogd_pluginstance *upi = data;
struct nfct_pluginstance *cpi =
(struct nfct_pluginstance *) upi->private;
- struct ct_timestamp *ts = NULL;
- struct ct_timestamp tmp = {
- .ct = ct,
- };
+ struct ct_timestamp *ts;
+ int ret, id;
switch(type) {
case NFCT_T_UPDATE:
- ts = hashtable_get(cpi->ct_active, &tmp);
+ id = hashtable_hash(cpi->ct_active, ct);
+ ts = (struct ct_timestamp *)
+ hashtable_find(cpi->ct_active, ct, id);
if (ts)
nfct_copy(ts->ct, ct, NFCT_CP_META);
else {
- ts = hashtable_add(cpi->ct_active, &tmp);
+ ts = calloc(sizeof(struct ct_timestamp), 1);
if (ts == NULL)
return NFCT_CB_CONTINUE;
+ ts->ct = ct;
gettimeofday(&ts->time[START], NULL);
+
+ ret = hashtable_add(cpi->ct_active, &ts->hashnode, id);
+ if (ret < 0) {
+ free(ts);
+ return NFCT_CB_CONTINUE;
+ }
return NFCT_CB_STOLEN;
}
break;
@@ -753,7 +784,8 @@ static int read_cb_nfct(int fd, unsigned int what, void *param)
static int do_free(void *data1, void *data2)
{
struct ct_timestamp *ts = data2;
- free(ts->ct);
+ nfct_destroy(ts->ct);
+ free(ts);
return 0;
}
@@ -770,8 +802,9 @@ static int do_purge(void *data1, void *data2)
ret = nfct_query(cpi->pgh, NFCT_Q_GET, ts->ct);
if (ret == -1 && errno == ENOENT) {
do_propagate_ct(upi, ts->ct, NFCT_T_DESTROY, ts);
- hashtable_del(cpi->ct_active, ts);
- free(ts->ct);
+ hashtable_del(cpi->ct_active, &ts->hashnode);
+ nfct_destroy(ts->ct);
+ free(ts);
}
return 0;
@@ -784,17 +817,25 @@ static int overrun_handler(enum nf_conntrack_msg_type type,
struct ulogd_pluginstance *upi = data;
struct nfct_pluginstance *cpi =
(struct nfct_pluginstance *) upi->private;
- struct ct_timestamp *ts, tmp = {
- .ct = ct,
- };
-
- /* if it does not exist, add it */
- if (!hashtable_get(cpi->ct_active, &tmp)) {
- ts = hashtable_add(cpi->ct_active, &tmp);
+ struct ct_timestamp *ts;
+ int id, ret;
+
+ id = hashtable_hash(cpi->ct_active, ct);
+ ts = (struct ct_timestamp *)
+ hashtable_find(cpi->ct_active, ct, id);
+ if (ts == NULL) {
+ ts = calloc(sizeof(struct ct_timestamp), 1);
if (ts == NULL)
return NFCT_CB_CONTINUE;
+ ts->ct = ct;
gettimeofday(&ts->time[START], NULL); /* do our best here */
+
+ ret = hashtable_add(cpi->ct_active, &ts->hashnode, id);
+ if (ret < 0) {
+ free(ts);
+ return NFCT_CB_CONTINUE;
+ }
return NFCT_CB_STOLEN;
}
@@ -912,7 +953,6 @@ static int constructor_nfct_events(struct ulogd_pluginstance *upi)
cpi->ct_active =
hashtable_create(buckets_ce(upi->config_kset).u.value,
maxentries_ce(upi->config_kset).u.value,
- sizeof(struct ct_timestamp),
hash,
compare);
if (!cpi->ct_active) {
@@ -987,7 +1027,6 @@ static int constructor_nfct_polling(struct ulogd_pluginstance *upi)
cpi->ct_active =
hashtable_create(buckets_ce(upi->config_kset).u.value,
maxentries_ce(upi->config_kset).u.value,
- sizeof(struct ct_timestamp),
hash,
compare);
if (!cpi->ct_active) {
diff --git a/src/hash.c b/src/hash.c
index 700678c..1d99130 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -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)
^ permalink raw reply related [flat|nested] 7+ messages in thread