/*
* Binary heap and hash tables, used in dummynet
*
- * $Id: dn_heap.c 5646 2010-03-08 12:48:30Z luigi $
+ * $Id: dn_heap.c 7119 2010-07-15 13:51:07Z luigi $
*/
#include <sys/cdefs.h>
return ht ? ht->entries : 0;
}
-/* lookup and optionally create or delete element */
+/*
+ * Helper function to scan a bucket in the hash table, it
+ * can only be called on a non-empty bucket for a valid table.
+ *
+ * In lookup and scan, consider ht->ht[i] as pointing to the tail
+ * of the queue (head is NEXTP(tail). The 'empty' value is irrelevant.
+ * While searching, start analysing p = head, end when p == tail.
+ * Note that 'tail' is a cache of the _original_ ht->ht[i]
+ * and is used to check for loop termination. If you remove
+ * it, you must also adjust 'p' when deleting the 'tail' element.
+ */
+#define NEXT(_h, _p) *((void **)((char *)(_p) + (_h)->ofs))
+static int
+dn_ht_scan_body(struct dn_ht *ht, int *bucket,
+ int (*fn)(void *, void *), void *arg)
+{
+ int ret, found = 0, i = *bucket;
+ void *tail, *pp, *p, *nextp;
+
+ pp = tail = ht->ht[i];
+ do {
+ p = NEXT(ht, pp);
+ nextp = NEXT(ht, p);
+ ret = fn(p, arg);
+ if ((ret & DNHT_SCAN_DEL) == 0) {
+ pp = p; /* prepare for next loop */
+ } else {
+ found++;
+ ht->entries--;
+ /* skip current element */
+ if (pp != p)
+ /* pp == p implies p == tail */
+ NEXT(ht, pp) = nextp;
+ if (p == tail)
+ ht->ht[i] = (pp != p) ? pp : NULL;
+ }
+ if (ret & DNHT_SCAN_END) {
+ /* Update ht->ht[i] before returning */
+ ht->ht[i] = (ht->ht[i] == NULL) ? NULL : pp;
+ return found;
+ }
+ } while (p != tail);
+
+ (*bucket)++;
+ return found;
+}
+
+/*
+ * lookup and optionally create or delete element.
+ * This is an optimized version of the scan so it is coded
+ * inline.
+ */
void *
dn_ht_find(struct dn_ht *ht, uintptr_t key, int flags, void *arg)
{
- int i;
- void **pp, *p;
+ int i, found;
+ void *tail, *pp, *p; /* pp is the prev element, pp is current */
if (ht == NULL) /* easy on an empty hash */
return NULL;
i = (ht->buckets == 1) ? 0 :
(ht->hash(key, flags, arg) & ht->buckets);
- for (pp = &ht->ht[i]; (p = *pp); pp = (void **)((char *)p + ht->ofs)) {
- if (flags & DNHT_MATCH_PTR) {
- if (key == (uintptr_t)p)
- break;
- } else if (ht->match(p, key, flags, arg)) /* found match */
- break;
+ pp = tail = ht->ht[i];
+ if (tail) { /* non empty, try a lookup */
+ do {
+ p = NEXT(ht, pp);
+ found = (flags & DNHT_MATCH_PTR) ? key == (uintptr_t)p :
+ ht->match(p, key, flags, arg);
+ if (!found)
+ continue;
+ if (flags & DNHT_REMOVE) {
+ ht->entries--;
+ if (p != pp) /* skip current element */
+ NEXT(ht, pp) = NEXT(ht, p);
+ if (p == tail)
+ ht->ht[i] = (pp != p) ? pp : NULL;
+ }
+ return p;
+ } while ( (pp = p) != tail);
}
+ /* not found */
+ if ((flags & DNHT_INSERT) == 0)
+ return NULL;
+ p = ht->newh ? ht->newh(key, flags, arg) : (void *)key;
if (p) {
- if (flags & DNHT_REMOVE) {
- /* link in the next element */
- *pp = *(void **)((char *)p + ht->ofs);
- *(void **)((char *)p + ht->ofs) = NULL;
- ht->entries--;
- }
- } else if (flags & DNHT_INSERT) {
- // printf("%s before calling new, bucket %d ofs %d\n",
- // __FUNCTION__, i, ht->ofs);
- p = ht->newh ? ht->newh(key, flags, arg) : (void *)key;
- // printf("%s newh returns %p\n", __FUNCTION__, p);
- if (p) {
- ht->entries++;
- *(void **)((char *)p + ht->ofs) = ht->ht[i];
- ht->ht[i] = p;
+ ht->entries++;
+ if (tail == NULL) {
+ ht->ht[i] = NEXT(ht, p) = p;
+ } else {
+ NEXT(ht, p) = NEXT(ht, tail);
+ NEXT(ht, tail) = p;
}
}
+
return p;
}
/*
- * do a scan with the option to delete the object. Extract next before
- * running the callback because the element may be destroyed there.
+ * do a scan with the option to delete the object.
+ * Similar to the lookup, but the match function is different,
+ * and we extract 'next' before running the callback because
+ * the element may be destroyed there.
*/
int
dn_ht_scan(struct dn_ht *ht, int (*fn)(void *, void *), void *arg)
{
- int i, ret, found = 0;
- void **curp, *cur, *next;
+ int i, bucket, found = 0;
if (ht == NULL || fn == NULL)
return 0;
for (i = 0; i <= ht->buckets; i++) {
- curp = &ht->ht[i];
- while ( (cur = *curp) != NULL) {
- next = *(void **)((char *)cur + ht->ofs);
- ret = fn(cur, arg);
- if (ret & DNHT_SCAN_DEL) {
- found++;
- ht->entries--;
- *curp = next;
- } else {
- curp = (void **)((char *)cur + ht->ofs);
- }
- if (ret & DNHT_SCAN_END)
+ if (ht->ht[i] == NULL)
+ continue; /* empty bucket */
+ bucket = i;
+ found += dn_ht_scan_body(ht, &bucket, fn, arg);
+ if (bucket == i) /* early exit */
return found;
- }
}
return found;
}
/*
- * Similar to dn_ht_scan(), except thah the scan is performed only
+ * Similar to dn_ht_scan(), except that the scan is performed only
* in the bucket 'bucket'. The function returns a correct bucket number if
- * the original is invalid
+ * the original is invalid.
+ * If the callback returns DNHT_SCAN_END, the function move the ht->ht[i]
+ * pointer to the last entry processed. Moreover, the bucket number passed
+ * by caller is decremented, because usually the caller increment it.
*/
int
dn_ht_scan_bucket(struct dn_ht *ht, int *bucket, int (*fn)(void *, void *),
void *arg)
{
- int i, ret, found = 0;
- void **curp, *cur, *next;
-
if (ht == NULL || fn == NULL)
return 0;
- if (*bucket > ht->buckets)
+ if (*bucket > ht->buckets || *bucket < 0)
*bucket = 0;
- i = *bucket;
-
- curp = &ht->ht[i];
- while ( (cur = *curp) != NULL) {
- next = *(void **)((char *)cur + ht->ofs);
- ret = fn(cur, arg);
- if (ret & DNHT_SCAN_DEL) {
- found++;
- ht->entries--;
- *curp = next;
- } else {
- curp = (void **)((char *)cur + ht->ofs);
- }
- if (ret & DNHT_SCAN_END)
- return found;
- }
- return found;
+ if (ht->ht[*bucket] == NULL) {
+ (*bucket)++;
+ return 0;
+ } else
+ return dn_ht_scan_body(ht, bucket, fn, arg);
}
-
git://git.onelab.eu / ipfw.git / blobdiff