svn commit: r202145 - user/luigi/ipfw3-head/sys/netinet/ipfw
Luigi Rizzo
luigi at FreeBSD.org
Tue Jan 12 09:06:36 UTC 2010
Author: luigi
Date: Tue Jan 12 09:06:36 2010
New Revision: 202145
URL: http://svn.freebsd.org/changeset/base/202145
Log:
add support for hash tables
Modified:
user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c
user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c Tue Jan 12 07:55:02 2010 (r202144)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c Tue Jan 12 09:06:36 2010 (r202145)
@@ -291,16 +291,170 @@ heap_free(struct dn_heap *h)
bzero(h, sizeof(*h) );
}
+/*
+ * hash table
+*/
+
+struct dn_ht *
+dn_ht_init(struct dn_ht *ht, int buckets, int ofs,
+ int (*h)(void *, uintptr_t arg),
+ int (*match)(void *, void *, uintptr_t arg),
+ void *(*new)(void *, uintptr_t arg), uintptr_t arg)
+{
+ int l;
+
+ if (h == NULL)
+ return NULL;
+ if (buckets < 1 || buckets > 65536)
+ return NULL;
+ if (ht) { /* see if we can reuse */
+ if (buckets <= ht->buckets) {
+ ht->buckets = buckets;
+ } else {
+ /* free pointers if not allocated inline */
+ if (ht->ht != (void *)(ht + 1))
+ free(ht->ht, M_DN_HEAP);
+ free(ht, M_DN_HEAP);
+ ht = NULL;
+ }
+ }
+ if (ht == NULL) {
+ l = sizeof(*ht) + buckets * sizeof(void **);
+ ht = malloc(l, M_DN_HEAP, M_NOWAIT);
+ }
+ if (ht) {
+ ht->ht = (void **)(ht + 1);
+ ht->buckets = buckets;
+ ht->ofs = ofs;
+ ht->hash = h;
+ ht->match = match;
+ ht->new = new;
+ ht->arg = arg;
+ }
+ return ht;
+}
+
+/* lookup and optionally create element */
+void *
+dn_ht_find(struct dn_ht *ht, void *obj, int create)
+{
+ int i;
+ void *p;
+
+ i = (ht->buckets == 1) ? 0 : ht->hash(obj, ht->arg) % ht->buckets;
+ // log(1, "find %p in bucket %d\n", obj, i);
+ for (p = ht->ht[i]; p; p = *(void **)((char *)p + ht->ofs)) {
+ if (ht->match(p, obj, ht->arg))
+ break;
+ }
+ if (p == NULL && create) {
+ p = ht->new(obj, ht->arg);
+ if (p) {
+ ht->entries++;
+ *(void **)((char *)p + ht->ofs) = ht->ht[i];
+ ht->ht[i] = p;
+ }
+ }
+ return p;
+}
+
+int
+dn_ht_scan(struct dn_ht *ht, int (*fn)(void *, uintptr_t), uintptr_t arg)
+{
+ int i, ret, found = 0;
+ void *p, **prev;
+
+ for (i = 0; i < ht->buckets; i++) {
+ prev = &ht->ht[i];
+ while ( (p = *prev) != NULL) {
+ ret = fn(p, arg);
+ if (ret & HEAP_SCAN_DEL) {
+ found++;
+ ht->entries--;
+ *prev = *(void **)((char *)p + ht->ofs);
+ }
+ if (ret & HEAP_SCAN_END)
+ return found;
+ prev = (void **)((char *)p + ht->ofs);
+ }
+ }
+ return found;
+}
+
+
#ifndef _KERNEL
/*
- * testing code for the heap
+ * testing code for the heap and hash table
*/
+#include <string.h>
+
+struct x {
+ struct x *ht_link;
+ char buf[0];
+};
+
+int hfn(void *_x, uintptr_t arg)
+{
+ char *p = _x;
+ return p[0];
+}
+
+void *newfn(void *_x, uintptr_t arg)
+{
+ char *s = _x;
+ struct x *p = malloc(sizeof(*p) + 1 + strlen(s),
+ M_DN_HEAP, 0);
+ if (p)
+ strcpy(p->buf, s);
+ return p;
+}
+
+int matchfn(void *_x, void *_obj, uintptr_t arg)
+{
+ struct x *x = _x;
+ return (strcmp(x->buf, _obj) == 0);
+}
+
+char *strings[] = {
+ "undici", "unico", "doppio", "devoto",
+ "uno", "due", "tre", "quattro", "cinque", "sei",
+ "uno", "due", "tre", "quattro", "cinque", "sei",
+ NULL,
+};
+
+int doprint(void *_x, uintptr_t arg)
+{
+ struct x *x = _x;
+ printf("found element <%s>\n", x->buf);
+ return arg;
+}
+
+static void
+test_hash()
+{
+ char **p;
+ struct dn_ht *h = dn_ht_init(NULL, 10, 0, hfn, matchfn, newfn,
+ 0);
+
+ for (p = strings; *p; p++) {
+ dn_ht_find(h, *p, 1);
+ }
+ dn_ht_scan(h, doprint, 0);
+ for (p = strings; *p; p++) {
+// dn_ht_scan(h, doprint, HEAP_SCAN_DEL);
+ dn_ht_find(h, *p, 1);
+ }
+}
+
int
main(int argc, char *argv[])
{
struct dn_heap h;
int i, n, n2, n3;
+ test_hash();
+ return 0;
+
/* n = elements, n2 = cycles */
n = (argc > 1) ? atoi(argv[1]) : 0;
if (n <= 0 || n > 1000000)
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Tue Jan 12 07:55:02 2010 (r202144)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Tue Jan 12 09:06:36 2010 (r202145)
@@ -83,4 +83,31 @@ enum {
*/
int heap_scan(struct dn_heap *, int (*)(void *, uintptr_t), uintptr_t);
+/*--- generic hash table support ---*/
+struct dn_ht {
+ int buckets; /* how many buckets */
+ int entries; /* how many entries */
+ int ofs; /* offset of link field */
+ uintptr_t arg; /* arg to hash function */
+ int (*hash)(void *, uintptr_t arg);
+ int (*match)(void *, void *, uintptr_t arg);
+ void *(*new)(void *, uintptr_t arg); /* object create function */
+ void **ht; /* bucket heads */
+};
+
+struct dn_ht *dn_ht_init(struct dn_ht *, int buckets, int ofs,
+ int (*h)(void *, uintptr_t arg),
+ int (*match)(void *, void *, uintptr_t arg),
+ void *(*new)(void *, uintptr_t arg),
+ uintptr_t arg);
+
+/* lookup and optionally create element */
+void *dn_ht_find(struct dn_ht *, void *obj, int create);
+
+enum {
+ DN_HT_SCAN_DEL = 1,
+ DN_HT_SCAN_END = 2,
+};
+int dn_ht_scan(struct dn_ht *, int (*)(void *, uintptr_t), uintptr_t);
+
#endif /* _IP_DN_HEAP_H */
More information about the svn-src-user
mailing list