1204591Sluigi/*- 2204591Sluigi * Copyright (c) 1998-2002,2010 Luigi Rizzo, Universita` di Pisa 3204591Sluigi * All rights reserved 4204591Sluigi * 5204591Sluigi * Redistribution and use in source and binary forms, with or without 6204591Sluigi * modification, are permitted provided that the following conditions 7204591Sluigi * are met: 8204591Sluigi * 1. Redistributions of source code must retain the above copyright 9204591Sluigi * notice, this list of conditions and the following disclaimer. 10204591Sluigi * 2. Redistributions in binary form must reproduce the above copyright 11204591Sluigi * notice, this list of conditions and the following disclaimer in the 12204591Sluigi * documentation and/or other materials provided with the distribution. 13204591Sluigi * 14204591Sluigi * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15204591Sluigi * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16204591Sluigi * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17204591Sluigi * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18204591Sluigi * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19204591Sluigi * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20204591Sluigi * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21204591Sluigi * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22204591Sluigi * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23204591Sluigi * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24204591Sluigi * SUCH DAMAGE. 25204591Sluigi */ 26204591Sluigi 27204591Sluigi/* 28204591Sluigi * Binary heap and hash tables, used in dummynet 29204591Sluigi * 30204591Sluigi * $FreeBSD$ 31204591Sluigi */ 32204591Sluigi 33204591Sluigi#include <sys/cdefs.h> 34204591Sluigi#include <sys/param.h> 35204591Sluigi#ifdef _KERNEL 36204591Sluigi__FBSDID("$FreeBSD$"); 37204591Sluigi#include <sys/systm.h> 38204591Sluigi#include <sys/malloc.h> 39204591Sluigi#include <sys/kernel.h> 40240494Sglebius#include <netpfil/ipfw/dn_heap.h> 41204591Sluigi#ifndef log 42204591Sluigi#define log(x, arg...) 43204591Sluigi#endif 44204591Sluigi 45204591Sluigi#else /* !_KERNEL */ 46204591Sluigi 47204591Sluigi#include <stdio.h> 48204591Sluigi#include <dn_test.h> 49204591Sluigi#include <strings.h> 50204591Sluigi#include <stdlib.h> 51204591Sluigi 52204591Sluigi#include "dn_heap.h" 53204591Sluigi#define log(x, arg...) fprintf(stderr, ## arg) 54204591Sluigi#define panic(x...) fprintf(stderr, ## x), exit(1) 55285361Sluigi#define MALLOC_DEFINE(a, b, c) volatile int __dummy__ ## a __attribute__((__unused__)) 56204591Sluigistatic void *my_malloc(int s) { return malloc(s); } 57204591Sluigistatic void my_free(void *p) { free(p); } 58204591Sluigi#define malloc(s, t, w) my_malloc(s) 59204591Sluigi#define free(p, t) my_free(p) 60204591Sluigi#endif /* !_KERNEL */ 61204591Sluigi 62227293Sedstatic MALLOC_DEFINE(M_DN_HEAP, "dummynet", "dummynet heap"); 63204591Sluigi 64204591Sluigi/* 65204591Sluigi * Heap management functions. 66204591Sluigi * 67204591Sluigi * In the heap, first node is element 0. Children of i are 2i+1 and 2i+2. 68204591Sluigi * Some macros help finding parent/children so we can optimize them. 69204591Sluigi * 70204591Sluigi * heap_init() is called to expand the heap when needed. 71204591Sluigi * Increment size in blocks of 16 entries. 72204591Sluigi * Returns 1 on error, 0 on success 73204591Sluigi */ 74204591Sluigi#define HEAP_FATHER(x) ( ( (x) - 1 ) / 2 ) 75204591Sluigi#define HEAP_LEFT(x) ( (x)+(x) + 1 ) 76204591Sluigi#define HEAP_SWAP(a, b, buffer) { buffer = a ; a = b ; b = buffer ; } 77204591Sluigi#define HEAP_INCREMENT 15 78204591Sluigi 79204591Sluigistatic int 80204591Sluigiheap_resize(struct dn_heap *h, unsigned int new_size) 81204591Sluigi{ 82204591Sluigi struct dn_heap_entry *p; 83204591Sluigi 84294855Sluigi if ((unsigned int)h->size >= new_size ) /* have enough room */ 85204591Sluigi return 0; 86204591Sluigi#if 1 /* round to the next power of 2 */ 87204591Sluigi new_size |= new_size >> 1; 88204591Sluigi new_size |= new_size >> 2; 89204591Sluigi new_size |= new_size >> 4; 90204591Sluigi new_size |= new_size >> 8; 91204591Sluigi new_size |= new_size >> 16; 92204591Sluigi#else 93204591Sluigi new_size = (new_size + HEAP_INCREMENT ) & ~HEAP_INCREMENT; 94204591Sluigi#endif 95204591Sluigi p = malloc(new_size * sizeof(*p), M_DN_HEAP, M_NOWAIT); 96204591Sluigi if (p == NULL) { 97204591Sluigi printf("--- %s, resize %d failed\n", __func__, new_size ); 98204591Sluigi return 1; /* error */ 99204591Sluigi } 100204591Sluigi if (h->size > 0) { 101204591Sluigi bcopy(h->p, p, h->size * sizeof(*p) ); 102204591Sluigi free(h->p, M_DN_HEAP); 103204591Sluigi } 104204591Sluigi h->p = p; 105204591Sluigi h->size = new_size; 106204591Sluigi return 0; 107204591Sluigi} 108204591Sluigi 109204591Sluigiint 110204591Sluigiheap_init(struct dn_heap *h, int size, int ofs) 111204591Sluigi{ 112204591Sluigi if (heap_resize(h, size)) 113204591Sluigi return 1; 114204591Sluigi h->elements = 0; 115204591Sluigi h->ofs = ofs; 116204591Sluigi return 0; 117204591Sluigi} 118204591Sluigi 119204591Sluigi/* 120204591Sluigi * Insert element in heap. Normally, p != NULL, we insert p in 121204591Sluigi * a new position and bubble up. If p == NULL, then the element is 122204591Sluigi * already in place, and key is the position where to start the 123204591Sluigi * bubble-up. 124204591Sluigi * Returns 1 on failure (cannot allocate new heap entry) 125204591Sluigi * 126204591Sluigi * If ofs > 0 the position (index, int) of the element in the heap is 127204591Sluigi * also stored in the element itself at the given offset in bytes. 128204591Sluigi */ 129204591Sluigi#define SET_OFFSET(h, i) do { \ 130204591Sluigi if (h->ofs > 0) \ 131204591Sluigi *((int32_t *)((char *)(h->p[i].object) + h->ofs)) = i; \ 132204591Sluigi } while (0) 133204591Sluigi/* 134204591Sluigi * RESET_OFFSET is used for sanity checks. It sets ofs 135204591Sluigi * to an invalid value. 136204591Sluigi */ 137204591Sluigi#define RESET_OFFSET(h, i) do { \ 138204591Sluigi if (h->ofs > 0) \ 139204591Sluigi *((int32_t *)((char *)(h->p[i].object) + h->ofs)) = -16; \ 140204591Sluigi } while (0) 141204591Sluigi 142204591Sluigiint 143204591Sluigiheap_insert(struct dn_heap *h, uint64_t key1, void *p) 144204591Sluigi{ 145204591Sluigi int son = h->elements; 146204591Sluigi 147204591Sluigi //log("%s key %llu p %p\n", __FUNCTION__, key1, p); 148204591Sluigi if (p == NULL) { /* data already there, set starting point */ 149204591Sluigi son = key1; 150204591Sluigi } else { /* insert new element at the end, possibly resize */ 151204591Sluigi son = h->elements; 152204591Sluigi if (son == h->size) /* need resize... */ 153204591Sluigi // XXX expand by 16 or so 154204591Sluigi if (heap_resize(h, h->elements+16) ) 155204591Sluigi return 1; /* failure... */ 156204591Sluigi h->p[son].object = p; 157204591Sluigi h->p[son].key = key1; 158204591Sluigi h->elements++; 159204591Sluigi } 160204591Sluigi /* make sure that son >= father along the path */ 161204591Sluigi while (son > 0) { 162204591Sluigi int father = HEAP_FATHER(son); 163204591Sluigi struct dn_heap_entry tmp; 164204591Sluigi 165204591Sluigi if (DN_KEY_LT( h->p[father].key, h->p[son].key ) ) 166204591Sluigi break; /* found right position */ 167204591Sluigi /* son smaller than father, swap and repeat */ 168204591Sluigi HEAP_SWAP(h->p[son], h->p[father], tmp); 169204591Sluigi SET_OFFSET(h, son); 170204591Sluigi son = father; 171204591Sluigi } 172204591Sluigi SET_OFFSET(h, son); 173204591Sluigi return 0; 174204591Sluigi} 175204591Sluigi 176204591Sluigi/* 177204591Sluigi * remove top element from heap, or obj if obj != NULL 178204591Sluigi */ 179204591Sluigivoid 180204591Sluigiheap_extract(struct dn_heap *h, void *obj) 181204591Sluigi{ 182204591Sluigi int child, father, max = h->elements - 1; 183204591Sluigi 184204591Sluigi if (max < 0) { 185204591Sluigi printf("--- %s: empty heap 0x%p\n", __FUNCTION__, h); 186204591Sluigi return; 187204591Sluigi } 188204591Sluigi if (obj == NULL) 189204591Sluigi father = 0; /* default: move up smallest child */ 190204591Sluigi else { /* extract specific element, index is at offset */ 191204591Sluigi if (h->ofs <= 0) 192204591Sluigi panic("%s: extract from middle not set on %p\n", 193204591Sluigi __FUNCTION__, h); 194204591Sluigi father = *((int *)((char *)obj + h->ofs)); 195204591Sluigi if (father < 0 || father >= h->elements) { 196204591Sluigi panic("%s: father %d out of bound 0..%d\n", 197204591Sluigi __FUNCTION__, father, h->elements); 198204591Sluigi } 199204591Sluigi } 200204591Sluigi /* 201204591Sluigi * below, father is the index of the empty element, which 202204591Sluigi * we replace at each step with the smallest child until we 203204591Sluigi * reach the bottom level. 204204591Sluigi */ 205204591Sluigi // XXX why removing RESET_OFFSET increases runtime by 10% ? 206204591Sluigi RESET_OFFSET(h, father); 207204591Sluigi while ( (child = HEAP_LEFT(father)) <= max ) { 208204591Sluigi if (child != max && 209204591Sluigi DN_KEY_LT(h->p[child+1].key, h->p[child].key) ) 210204591Sluigi child++; /* take right child, otherwise left */ 211204591Sluigi h->p[father] = h->p[child]; 212204591Sluigi SET_OFFSET(h, father); 213204591Sluigi father = child; 214204591Sluigi } 215204591Sluigi h->elements--; 216204591Sluigi if (father != max) { 217204591Sluigi /* 218204591Sluigi * Fill hole with last entry and bubble up, 219204591Sluigi * reusing the insert code 220204591Sluigi */ 221204591Sluigi h->p[father] = h->p[max]; 222204591Sluigi heap_insert(h, father, NULL); 223204591Sluigi } 224204591Sluigi} 225204591Sluigi 226204591Sluigi#if 0 227204591Sluigi/* 228204591Sluigi * change object position and update references 229204591Sluigi * XXX this one is never used! 230204591Sluigi */ 231204591Sluigistatic void 232204591Sluigiheap_move(struct dn_heap *h, uint64_t new_key, void *object) 233204591Sluigi{ 234204591Sluigi int temp, i, max = h->elements-1; 235204591Sluigi struct dn_heap_entry *p, buf; 236204591Sluigi 237204591Sluigi if (h->ofs <= 0) 238204591Sluigi panic("cannot move items on this heap"); 239204591Sluigi p = h->p; /* shortcut */ 240204591Sluigi 241204591Sluigi i = *((int *)((char *)object + h->ofs)); 242204591Sluigi if (DN_KEY_LT(new_key, p[i].key) ) { /* must move up */ 243204591Sluigi p[i].key = new_key; 244204591Sluigi for (; i>0 && 245204591Sluigi DN_KEY_LT(new_key, p[(temp = HEAP_FATHER(i))].key); 246204591Sluigi i = temp ) { /* bubble up */ 247204591Sluigi HEAP_SWAP(p[i], p[temp], buf); 248204591Sluigi SET_OFFSET(h, i); 249204591Sluigi } 250204591Sluigi } else { /* must move down */ 251204591Sluigi p[i].key = new_key; 252204591Sluigi while ( (temp = HEAP_LEFT(i)) <= max ) { 253204591Sluigi /* found left child */ 254204591Sluigi if (temp != max && 255204591Sluigi DN_KEY_LT(p[temp+1].key, p[temp].key)) 256204591Sluigi temp++; /* select child with min key */ 257204591Sluigi if (DN_KEY_LT(>p[temp].key, new_key)) { 258204591Sluigi /* go down */ 259204591Sluigi HEAP_SWAP(p[i], p[temp], buf); 260204591Sluigi SET_OFFSET(h, i); 261204591Sluigi } else 262204591Sluigi break; 263204591Sluigi i = temp; 264204591Sluigi } 265204591Sluigi } 266204591Sluigi SET_OFFSET(h, i); 267204591Sluigi} 268204591Sluigi#endif /* heap_move, unused */ 269204591Sluigi 270204591Sluigi/* 271204591Sluigi * heapify() will reorganize data inside an array to maintain the 272204591Sluigi * heap property. It is needed when we delete a bunch of entries. 273204591Sluigi */ 274204591Sluigistatic void 275204591Sluigiheapify(struct dn_heap *h) 276204591Sluigi{ 277204591Sluigi int i; 278204591Sluigi 279204591Sluigi for (i = 0; i < h->elements; i++ ) 280204591Sluigi heap_insert(h, i , NULL); 281204591Sluigi} 282204591Sluigi 283204591Sluigiint 284204591Sluigiheap_scan(struct dn_heap *h, int (*fn)(void *, uintptr_t), 285204591Sluigi uintptr_t arg) 286204591Sluigi{ 287204591Sluigi int i, ret, found; 288204591Sluigi 289204591Sluigi for (i = found = 0 ; i < h->elements ;) { 290204591Sluigi ret = fn(h->p[i].object, arg); 291204591Sluigi if (ret & HEAP_SCAN_DEL) { 292204591Sluigi h->elements-- ; 293204591Sluigi h->p[i] = h->p[h->elements] ; 294204591Sluigi found++ ; 295204591Sluigi } else 296204591Sluigi i++ ; 297204591Sluigi if (ret & HEAP_SCAN_END) 298204591Sluigi break; 299204591Sluigi } 300204591Sluigi if (found) 301204591Sluigi heapify(h); 302204591Sluigi return found; 303204591Sluigi} 304204591Sluigi 305204591Sluigi/* 306204591Sluigi * cleanup the heap and free data structure 307204591Sluigi */ 308204591Sluigivoid 309204591Sluigiheap_free(struct dn_heap *h) 310204591Sluigi{ 311204591Sluigi if (h->size >0 ) 312204591Sluigi free(h->p, M_DN_HEAP); 313204591Sluigi bzero(h, sizeof(*h) ); 314204591Sluigi} 315204591Sluigi 316204591Sluigi/* 317204591Sluigi * hash table support. 318204591Sluigi */ 319204591Sluigi 320204591Sluigistruct dn_ht { 321204591Sluigi int buckets; /* how many buckets, really buckets - 1*/ 322204591Sluigi int entries; /* how many entries */ 323204591Sluigi int ofs; /* offset of link field */ 324204591Sluigi uint32_t (*hash)(uintptr_t, int, void *arg); 325204591Sluigi int (*match)(void *_el, uintptr_t key, int, void *); 326204865Sluigi void *(*newh)(uintptr_t, int, void *); 327204591Sluigi void **ht; /* bucket heads */ 328204591Sluigi}; 329204591Sluigi/* 330204591Sluigi * Initialize, allocating bucket pointers inline. 331204591Sluigi * Recycle previous record if possible. 332204865Sluigi * If the 'newh' function is not supplied, we assume that the 333204591Sluigi * key passed to ht_find is the same object to be stored in. 334204591Sluigi */ 335204591Sluigistruct dn_ht * 336204591Sluigidn_ht_init(struct dn_ht *ht, int buckets, int ofs, 337204591Sluigi uint32_t (*h)(uintptr_t, int, void *), 338204591Sluigi int (*match)(void *, uintptr_t, int, void *), 339204865Sluigi void *(*newh)(uintptr_t, int, void *)) 340204591Sluigi{ 341204591Sluigi int l; 342204591Sluigi 343204591Sluigi /* 344204591Sluigi * Notes about rounding bucket size to a power of two. 345204591Sluigi * Given the original bucket size, we compute the nearest lower and 346204591Sluigi * higher power of two, minus 1 (respectively b_min and b_max) because 347204591Sluigi * this value will be used to do an AND with the index returned 348204591Sluigi * by hash function. 349204591Sluigi * To choice between these two values, the original bucket size is 350204591Sluigi * compared with b_min. If the original size is greater than 4/3 b_min, 351204591Sluigi * we round the bucket size to b_max, else to b_min. 352204591Sluigi * This ratio try to round to the nearest power of two, advantaging 353204591Sluigi * the greater size if the different between two power is relatively 354204591Sluigi * big. 355204591Sluigi * Rounding the bucket size to a power of two avoid the use of 356204591Sluigi * module when calculating the correct bucket. 357204591Sluigi * The ht->buckets variable store the bucket size - 1 to simply 358204591Sluigi * do an AND between the index returned by hash function and ht->bucket 359204591Sluigi * instead of a module. 360204591Sluigi */ 361204591Sluigi int b_min; /* min buckets */ 362204591Sluigi int b_max; /* max buckets */ 363204591Sluigi int b_ori; /* original buckets */ 364204591Sluigi 365204591Sluigi if (h == NULL || match == NULL) { 366204591Sluigi printf("--- missing hash or match function"); 367204591Sluigi return NULL; 368204591Sluigi } 369204591Sluigi if (buckets < 1 || buckets > 65536) 370204591Sluigi return NULL; 371204591Sluigi 372204591Sluigi b_ori = buckets; 373204591Sluigi /* calculate next power of 2, - 1*/ 374204591Sluigi buckets |= buckets >> 1; 375204591Sluigi buckets |= buckets >> 2; 376204591Sluigi buckets |= buckets >> 4; 377204591Sluigi buckets |= buckets >> 8; 378204591Sluigi buckets |= buckets >> 16; 379204591Sluigi 380204591Sluigi b_max = buckets; /* Next power */ 381204591Sluigi b_min = buckets >> 1; /* Previous power */ 382204591Sluigi 383204591Sluigi /* Calculate the 'nearest' bucket size */ 384204591Sluigi if (b_min * 4000 / 3000 < b_ori) 385204591Sluigi buckets = b_max; 386204591Sluigi else 387204591Sluigi buckets = b_min; 388204591Sluigi 389204591Sluigi if (ht) { /* see if we can reuse */ 390204591Sluigi if (buckets <= ht->buckets) { 391204591Sluigi ht->buckets = buckets; 392204591Sluigi } else { 393204591Sluigi /* free pointers if not allocated inline */ 394204591Sluigi if (ht->ht != (void *)(ht + 1)) 395204591Sluigi free(ht->ht, M_DN_HEAP); 396204591Sluigi free(ht, M_DN_HEAP); 397204591Sluigi ht = NULL; 398204591Sluigi } 399204591Sluigi } 400204591Sluigi if (ht == NULL) { 401204591Sluigi /* Allocate buckets + 1 entries because buckets is use to 402204591Sluigi * do the AND with the index returned by hash function 403204591Sluigi */ 404204591Sluigi l = sizeof(*ht) + (buckets + 1) * sizeof(void **); 405204591Sluigi ht = malloc(l, M_DN_HEAP, M_NOWAIT | M_ZERO); 406204591Sluigi } 407204591Sluigi if (ht) { 408204591Sluigi ht->ht = (void **)(ht + 1); 409204591Sluigi ht->buckets = buckets; 410204591Sluigi ht->ofs = ofs; 411204591Sluigi ht->hash = h; 412204591Sluigi ht->match = match; 413204865Sluigi ht->newh = newh; 414204591Sluigi } 415204591Sluigi return ht; 416204591Sluigi} 417204591Sluigi 418204591Sluigi/* dummy callback for dn_ht_free to unlink all */ 419204591Sluigistatic int 420204591Sluigido_del(void *obj, void *arg) 421204591Sluigi{ 422294855Sluigi (void)obj; 423294855Sluigi (void)arg; 424204591Sluigi return DNHT_SCAN_DEL; 425204591Sluigi} 426204591Sluigi 427204591Sluigivoid 428204591Sluigidn_ht_free(struct dn_ht *ht, int flags) 429204591Sluigi{ 430204591Sluigi if (ht == NULL) 431204591Sluigi return; 432204591Sluigi if (flags & DNHT_REMOVE) { 433204591Sluigi (void)dn_ht_scan(ht, do_del, NULL); 434204591Sluigi } else { 435204591Sluigi if (ht->ht && ht->ht != (void *)(ht + 1)) 436204591Sluigi free(ht->ht, M_DN_HEAP); 437204591Sluigi free(ht, M_DN_HEAP); 438204591Sluigi } 439204591Sluigi} 440204591Sluigi 441204591Sluigiint 442204591Sluigidn_ht_entries(struct dn_ht *ht) 443204591Sluigi{ 444204591Sluigi return ht ? ht->entries : 0; 445204591Sluigi} 446204591Sluigi 447204591Sluigi/* lookup and optionally create or delete element */ 448204591Sluigivoid * 449204591Sluigidn_ht_find(struct dn_ht *ht, uintptr_t key, int flags, void *arg) 450204591Sluigi{ 451204591Sluigi int i; 452204591Sluigi void **pp, *p; 453204591Sluigi 454204591Sluigi if (ht == NULL) /* easy on an empty hash */ 455204591Sluigi return NULL; 456204591Sluigi i = (ht->buckets == 1) ? 0 : 457204591Sluigi (ht->hash(key, flags, arg) & ht->buckets); 458204591Sluigi 459204591Sluigi for (pp = &ht->ht[i]; (p = *pp); pp = (void **)((char *)p + ht->ofs)) { 460204591Sluigi if (flags & DNHT_MATCH_PTR) { 461204591Sluigi if (key == (uintptr_t)p) 462204591Sluigi break; 463204591Sluigi } else if (ht->match(p, key, flags, arg)) /* found match */ 464204591Sluigi break; 465204591Sluigi } 466204591Sluigi if (p) { 467204591Sluigi if (flags & DNHT_REMOVE) { 468204591Sluigi /* link in the next element */ 469204591Sluigi *pp = *(void **)((char *)p + ht->ofs); 470204591Sluigi *(void **)((char *)p + ht->ofs) = NULL; 471204591Sluigi ht->entries--; 472204591Sluigi } 473204591Sluigi } else if (flags & DNHT_INSERT) { 474204591Sluigi // printf("%s before calling new, bucket %d ofs %d\n", 475204591Sluigi // __FUNCTION__, i, ht->ofs); 476204865Sluigi p = ht->newh ? ht->newh(key, flags, arg) : (void *)key; 477204865Sluigi // printf("%s newh returns %p\n", __FUNCTION__, p); 478204591Sluigi if (p) { 479204591Sluigi ht->entries++; 480204591Sluigi *(void **)((char *)p + ht->ofs) = ht->ht[i]; 481204591Sluigi ht->ht[i] = p; 482204591Sluigi } 483204591Sluigi } 484204591Sluigi return p; 485204591Sluigi} 486204591Sluigi 487204591Sluigi/* 488204591Sluigi * do a scan with the option to delete the object. Extract next before 489204591Sluigi * running the callback because the element may be destroyed there. 490204591Sluigi */ 491204591Sluigiint 492204591Sluigidn_ht_scan(struct dn_ht *ht, int (*fn)(void *, void *), void *arg) 493204591Sluigi{ 494204591Sluigi int i, ret, found = 0; 495204591Sluigi void **curp, *cur, *next; 496204591Sluigi 497204591Sluigi if (ht == NULL || fn == NULL) 498204591Sluigi return 0; 499204591Sluigi for (i = 0; i <= ht->buckets; i++) { 500204591Sluigi curp = &ht->ht[i]; 501204591Sluigi while ( (cur = *curp) != NULL) { 502204591Sluigi next = *(void **)((char *)cur + ht->ofs); 503204591Sluigi ret = fn(cur, arg); 504204591Sluigi if (ret & DNHT_SCAN_DEL) { 505204591Sluigi found++; 506204591Sluigi ht->entries--; 507204591Sluigi *curp = next; 508204591Sluigi } else { 509204591Sluigi curp = (void **)((char *)cur + ht->ofs); 510204591Sluigi } 511204591Sluigi if (ret & DNHT_SCAN_END) 512204591Sluigi return found; 513204591Sluigi } 514204591Sluigi } 515204591Sluigi return found; 516204591Sluigi} 517204591Sluigi 518204591Sluigi/* 519210119Sluigi * Similar to dn_ht_scan(), except that the scan is performed only 520204591Sluigi * in the bucket 'bucket'. The function returns a correct bucket number if 521210119Sluigi * the original is invalid. 522210119Sluigi * If the callback returns DNHT_SCAN_END, the function move the ht->ht[i] 523210119Sluigi * pointer to the last entry processed. Moreover, the bucket number passed 524210119Sluigi * by caller is decremented, because usually the caller increment it. 525204591Sluigi */ 526204591Sluigiint 527204591Sluigidn_ht_scan_bucket(struct dn_ht *ht, int *bucket, int (*fn)(void *, void *), 528204591Sluigi void *arg) 529204591Sluigi{ 530204591Sluigi int i, ret, found = 0; 531204591Sluigi void **curp, *cur, *next; 532204591Sluigi 533204591Sluigi if (ht == NULL || fn == NULL) 534204591Sluigi return 0; 535204591Sluigi if (*bucket > ht->buckets) 536204591Sluigi *bucket = 0; 537204591Sluigi i = *bucket; 538204591Sluigi 539204591Sluigi curp = &ht->ht[i]; 540204591Sluigi while ( (cur = *curp) != NULL) { 541204591Sluigi next = *(void **)((char *)cur + ht->ofs); 542204591Sluigi ret = fn(cur, arg); 543204591Sluigi if (ret & DNHT_SCAN_DEL) { 544204591Sluigi found++; 545204591Sluigi ht->entries--; 546204591Sluigi *curp = next; 547204591Sluigi } else { 548204591Sluigi curp = (void **)((char *)cur + ht->ofs); 549204591Sluigi } 550204591Sluigi if (ret & DNHT_SCAN_END) 551204591Sluigi return found; 552204591Sluigi } 553204591Sluigi return found; 554204591Sluigi} 555