From owner-svn-src-user@FreeBSD.ORG Tue Jan 12 09:06:36 2010 Return-Path: Delivered-To: svn-src-user@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 94E881065679; Tue, 12 Jan 2010 09:06:36 +0000 (UTC) (envelope-from luigi@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id 840618FC13; Tue, 12 Jan 2010 09:06:36 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.3/8.14.3) with ESMTP id o0C96aWx036887; Tue, 12 Jan 2010 09:06:36 GMT (envelope-from luigi@svn.freebsd.org) Received: (from luigi@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id o0C96ade036886; Tue, 12 Jan 2010 09:06:36 GMT (envelope-from luigi@svn.freebsd.org) Message-Id: <201001120906.o0C96ade036886@svn.freebsd.org> From: Luigi Rizzo Date: Tue, 12 Jan 2010 09:06:36 +0000 (UTC) To: src-committers@freebsd.org, svn-src-user@freebsd.org X-SVN-Group: user MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r202145 - user/luigi/ipfw3-head/sys/netinet/ipfw X-BeenThere: svn-src-user@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the experimental " user" src tree" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 12 Jan 2010 09:06:36 -0000 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 + +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 */