Date: Tue, 12 Jan 2010 10:13:10 +0000 (UTC) From: Luigi Rizzo <luigi@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r202149 - user/luigi/ipfw3-head/sys/netinet/ipfw Message-ID: <201001121013.o0CADANl051755@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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,
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001121013.o0CADANl051755>