X-Git-Url: http://git.onelab.eu/?p=ipfw.git;a=blobdiff_plain;f=dummynet2%2Fdn_heap.c;fp=dummynet2%2Fdn_heap.c;h=a56d185e01ef8ac6045ed4e838dcf4b65bc4af8e;hp=390ae8dd1e3b7f4fc3a7b86abae46452c74c3b1d;hb=28a7fe9d930667786b902af6697c01eb87694173;hpb=2a8b6c544cf5ea3c84f763144c7ecfa79daea969 diff --git a/dummynet2/dn_heap.c b/dummynet2/dn_heap.c index 390ae8d..a56d185 100644 --- a/dummynet2/dn_heap.c +++ b/dummynet2/dn_heap.c @@ -27,7 +27,7 @@ /* * 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 @@ -442,109 +442,147 @@ dn_ht_entries(struct dn_ht *ht) 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); } -