From owner-svn-src-user@FreeBSD.ORG Tue Jan 12 10:13:10 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 714C91065676; Tue, 12 Jan 2010 10:13:10 +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 26B738FC1E; Tue, 12 Jan 2010 10:13:10 +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 o0CADASW051758; Tue, 12 Jan 2010 10:13:10 GMT (envelope-from luigi@svn.freebsd.org) Received: (from luigi@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id o0CADANl051755; Tue, 12 Jan 2010 10:13:10 GMT (envelope-from luigi@svn.freebsd.org) Message-Id: <201001121013.o0CADANl051755@svn.freebsd.org> From: Luigi Rizzo Date: Tue, 12 Jan 2010 10:13:10 +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: r202149 - 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 10:13:10 -0000 Author: luigi Date: Tue Jan 12 10:13:09 2010 New Revision: 202149 URL: http://svn.freebsd.org/changeset/base/202149 Log: add removal code, fix some bugs 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 10:06:32 2010 (r202148) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c Tue Jan 12 10:13:09 2010 (r202149) @@ -292,9 +292,15 @@ heap_free(struct dn_heap *h) } /* - * hash table -*/ + * hash table support. + */ +/* + * Initialize, allocating bucket pointers inline. + * Recycle previous record if possible. + * If the 'new' function is not supplied, we assume that the + * key passed to ht_find is the same object to be stored in. + */ struct dn_ht * dn_ht_init(struct dn_ht *ht, int buckets, int ofs, int (*h)(void *, uintptr_t arg), @@ -336,19 +342,19 @@ dn_ht_init(struct dn_ht *ht, int buckets /* lookup and optionally create element */ void * -dn_ht_find(struct dn_ht *ht, void *obj, int create) +dn_ht_find(struct dn_ht *ht, void *key, int create) { int i; void *p; - i = (ht->buckets == 1) ? 0 : ht->hash(obj, ht->arg) % ht->buckets; + i = (ht->buckets == 1) ? 0 : ht->hash(key, 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)) + if (ht->match(p, key, ht->arg)) break; } if (p == NULL && create) { - p = ht->new(obj, ht->arg); + p = ht->new ? ht->new(key, ht->arg) : key; if (p) { ht->entries++; *(void **)((char *)p + ht->ofs) = ht->ht[i]; @@ -381,6 +387,29 @@ dn_ht_scan(struct dn_ht *ht, int (*fn)(v return found; } +/* + * remove obj from the table, using key to find the slot. + * Returns obj if found, NULL if not found + */ +void * +dn_ht_remove(struct dn_ht *ht, void *obj, void *key) +{ + int i; + void **pp, *p; + + i = (ht->buckets == 1) ? 0 : ht->hash(obj, ht->arg) % ht->buckets; + // log(1, "find %p in bucket %d\n", obj, i); + for (pp = &ht->ht[i]; (p = *pp); pp = (void **)((char *)p + ht->ofs)) { + if (p != obj) + continue; + /* link in the next element */ + *pp = *(void **)((char *)p + ht->ofs); + *(void **)((char *)p + ht->ofs) = NULL; + ht->entries--; + return obj; + } + return NULL; /* failed */ +} #ifndef _KERNEL /* @@ -393,10 +422,23 @@ struct x { char buf[0]; }; -int hfn(void *_x, uintptr_t arg) +int hfn1(void *_x, uintptr_t arg) { - char *p = _x; - return p[0]; + return *(char *)_x; +} +int matchfn1(void *_x, void *_obj, uintptr_t arg) +{ + return (strcmp(((struct x *)_x)->buf, _obj) == 0); +} + +int hfn2(void *_x, uintptr_t arg) +{ + return ((struct x *)_x)->buf[0]; +} +int matchfn2(void *_x, void *_obj, uintptr_t arg) +{ + return (strcmp(((struct x *)_x)->buf, + ((struct x *)_obj)->buf) == 0); } void *newfn(void *_x, uintptr_t arg) @@ -409,12 +451,6 @@ void *newfn(void *_x, uintptr_t arg) 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", @@ -433,17 +469,28 @@ static void test_hash() { char **p; - struct dn_ht *h = dn_ht_init(NULL, 10, 0, hfn, matchfn, newfn, - 0); + struct dn_ht *h; + void *x = NULL; + + /* first, find and allocate */ + h = dn_ht_init(NULL, 10, 0, hfn1, matchfn1, newfn, 0); for (p = strings; *p; p++) { dn_ht_find(h, *p, 1); } dn_ht_scan(h, doprint, 0); + printf("/* second -- find without allocate */\n"); + h = dn_ht_init(NULL, 10, 0, hfn2, matchfn2, NULL, 0); for (p = strings; *p; p++) { -// dn_ht_scan(h, doprint, HEAP_SCAN_DEL); - dn_ht_find(h, *p, 1); + void **y = newfn(*p, 0); + if (x == NULL) + x = y; + dn_ht_find(h, y, 1); } + dn_ht_scan(h, doprint, 0); + printf("remove %p gives %p\n", x, dn_ht_remove(h, x, x)); + printf("remove %p gives %p\n", x, dn_ht_remove(h, x, x)); + dn_ht_scan(h, doprint, 0); } int Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Tue Jan 12 10:06:32 2010 (r202148) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Tue Jan 12 10:13:09 2010 (r202149) @@ -98,11 +98,12 @@ struct dn_ht { 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), + 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); +void *dn_ht_find(struct dn_ht *, void *key, int create); +void *dn_ht_remove(struct dn_ht *, void *obj, void *key); enum { DN_HT_SCAN_DEL = 1,