1204591Sluigi/*- 2204591Sluigi * Copyright (c) 1998-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, header file 29204591Sluigi * 30204591Sluigi * $FreeBSD$ 31204591Sluigi */ 32204591Sluigi 33204591Sluigi#ifndef _IP_DN_HEAP_H 34204591Sluigi#define _IP_DN_HEAP_H 35204591Sluigi 36204591Sluigi#define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0) 37204591Sluigi#define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0) 38204591Sluigi 39204591Sluigi/* 40204591Sluigi * This module implements a binary heap supporting random extraction. 41204591Sluigi * 42204591Sluigi * A heap entry contains an uint64_t key and a pointer to object. 43204591Sluigi * DN_KEY_LT(a,b) returns true if key 'a' is smaller than 'b' 44204591Sluigi * 45204591Sluigi * The heap is a struct dn_heap plus a dynamically allocated 46204591Sluigi * array of dn_heap_entry entries. 'size' represents the size of 47204591Sluigi * the array, 'elements' count entries in use. The topmost 48204591Sluigi * element has the smallest key. 49204591Sluigi * The heap supports ordered insert, and extract from the top. 50204591Sluigi * To extract an object from the middle of the heap, we the object 51204591Sluigi * must reserve an 'int32_t' to store the position of the object 52204591Sluigi * in the heap itself, and the location of this field must be 53204591Sluigi * passed as an argument to heap_init() -- use -1 if the feature 54204591Sluigi * is not used. 55204591Sluigi */ 56204591Sluigistruct dn_heap_entry { 57204591Sluigi uint64_t key; /* sorting key, smallest comes first */ 58204591Sluigi void *object; /* object pointer */ 59204591Sluigi}; 60204591Sluigi 61204591Sluigistruct dn_heap { 62204591Sluigi int size; /* the size of the array */ 63204591Sluigi int elements; /* elements in use */ 64204591Sluigi int ofs; /* offset in the object of heap index */ 65204591Sluigi struct dn_heap_entry *p; /* array of "size" entries */ 66204591Sluigi}; 67204591Sluigi 68204591Sluigienum { 69204591Sluigi HEAP_SCAN_DEL = 1, 70204591Sluigi HEAP_SCAN_END = 2, 71204591Sluigi}; 72204591Sluigi 73204591Sluigi/* 74204591Sluigi * heap_init() reinitializes the heap setting the size and the offset 75204591Sluigi * of the index for random extraction (use -1 if not used). 76204591Sluigi * The 'elements' counter is set to 0. 77204591Sluigi * 78204591Sluigi * SET_HEAP_OFS() indicates where, in the object, is stored the index 79204591Sluigi * for random extractions from the heap. 80204591Sluigi * 81204591Sluigi * heap_free() frees the memory associated to a heap. 82204591Sluigi * 83204591Sluigi * heap_insert() adds a key-pointer pair to the heap 84204591Sluigi * 85204591Sluigi * HEAP_TOP() returns a pointer to the top element of the heap, 86204591Sluigi * but makes no checks on its existance (XXX should we change ?) 87204591Sluigi * 88204591Sluigi * heap_extract() removes the entry at the top, returing the pointer. 89204591Sluigi * (the key should have been read before). 90204591Sluigi * 91204591Sluigi * heap_scan() invokes a callback on each entry of the heap. 92204591Sluigi * The callback can return a combination of HEAP_SCAN_DEL and 93204591Sluigi * HEAP_SCAN_END. HEAP_SCAN_DEL means the current element must 94204591Sluigi * be removed, and HEAP_SCAN_END means to terminate the scan. 95204591Sluigi * heap_scan() returns the number of elements removed. 96204591Sluigi * Because the order is not guaranteed, we should use heap_scan() 97204591Sluigi * only as a last resort mechanism. 98204591Sluigi */ 99204591Sluigi#define HEAP_TOP(h) ((h)->p) 100204591Sluigi#define SET_HEAP_OFS(h, n) do { (h)->ofs = n; } while (0) 101204591Sluigiint heap_init(struct dn_heap *h, int size, int ofs); 102204591Sluigiint heap_insert(struct dn_heap *h, uint64_t key1, void *p); 103204591Sluigivoid heap_extract(struct dn_heap *h, void *obj); 104204591Sluigivoid heap_free(struct dn_heap *h); 105204591Sluigiint heap_scan(struct dn_heap *, int (*)(void *, uintptr_t), uintptr_t); 106204591Sluigi 107204591Sluigi/*------------------------------------------------------ 108204591Sluigi * This module implements a generic hash table with support for 109204591Sluigi * running callbacks on the entire table. To avoid allocating 110204591Sluigi * memory during hash table operations, objects must reserve 111204591Sluigi * space for a link field. XXX if the heap is moderately full, 112204591Sluigi * an SLIST suffices, and we can tolerate the cost of a hash 113204591Sluigi * computation on each removal. 114204591Sluigi * 115204591Sluigi * dn_ht_init() initializes the table, setting the number of 116204591Sluigi * buckets, the offset of the link field, the main callbacks. 117204591Sluigi * Callbacks are: 118204591Sluigi * 119204591Sluigi * hash(key, flags, arg) called to return a bucket index. 120204591Sluigi * match(obj, key, flags, arg) called to determine if key 121204591Sluigi * matches the current 'obj' in the heap 122204865Sluigi * newh(key, flags, arg) optional, used to allocate a new 123204591Sluigi * object during insertions. 124204591Sluigi * 125204591Sluigi * dn_ht_free() frees the heap or unlink elements. 126204591Sluigi * DNHT_REMOVE unlink elements, 0 frees the heap. 127204591Sluigi * You need two calls to do both. 128204591Sluigi * 129204591Sluigi * dn_ht_find() is the main lookup function, which can also be 130204591Sluigi * used to insert or delete elements in the hash table. 131204591Sluigi * The final 'arg' is passed to all callbacks. 132204591Sluigi * 133204591Sluigi * dn_ht_scan() is used to invoke a callback on all entries of 134204591Sluigi * the heap, or possibly on just one bucket. The callback 135204591Sluigi * is invoked with a pointer to the object, and must return 136204591Sluigi * one of DNHT_SCAN_DEL or DNHT_SCAN_END to request the 137204591Sluigi * removal of the object from the heap and the end of the 138204591Sluigi * scan, respectively. 139204591Sluigi * 140204591Sluigi * dn_ht_scan_bucket() is similar to dn_ht_scan(), except that it scans 141204591Sluigi * only the specific bucket of the table. The bucket is a in-out 142204591Sluigi * parameter and return a valid bucket number if the original 143204591Sluigi * is invalid. 144204591Sluigi * 145204591Sluigi * A combination of flags can be used to modify the operation 146204591Sluigi * of the dn_ht_find(), and of the callbacks: 147204591Sluigi * 148204591Sluigi * DNHT_KEY_IS_OBJ means the key is the object pointer. 149204591Sluigi * It is usally of interest for the hash and match functions. 150204591Sluigi * 151204591Sluigi * DNHT_MATCH_PTR during a lookup, match pointers instead 152204591Sluigi * of calling match(). Normally used when removing specific 153204591Sluigi * entries. Does not imply KEY_IS_OBJ as the latter _is_ used 154204591Sluigi * by the match function. 155204591Sluigi * 156204591Sluigi * DNHT_INSERT insert the element if not found. 157204591Sluigi * Calls new() to allocates a new object unless 158204591Sluigi * DNHT_KEY_IS_OBJ is set. 159204591Sluigi * 160204591Sluigi * DNHT_UNIQUE only insert if object not found. 161204591Sluigi * XXX should it imply DNHT_INSERT ? 162204591Sluigi * 163204591Sluigi * DNHT_REMOVE remove objects if we find them. 164204591Sluigi */ 165204591Sluigistruct dn_ht; /* should be opaque */ 166204591Sluigi 167204591Sluigistruct dn_ht *dn_ht_init(struct dn_ht *, int buckets, int ofs, 168204591Sluigi uint32_t (*hash)(uintptr_t, int, void *), 169204591Sluigi int (*match)(void *, uintptr_t, int, void *), 170204865Sluigi void *(*newh)(uintptr_t, int, void *)); 171204591Sluigivoid dn_ht_free(struct dn_ht *, int flags); 172204591Sluigi 173204591Sluigivoid *dn_ht_find(struct dn_ht *, uintptr_t, int, void *); 174204591Sluigiint dn_ht_scan(struct dn_ht *, int (*)(void *, void *), void *); 175204591Sluigiint dn_ht_scan_bucket(struct dn_ht *, int * , int (*)(void *, void *), void *); 176204591Sluigiint dn_ht_entries(struct dn_ht *); 177204591Sluigi 178204591Sluigienum { /* flags values. 179204591Sluigi * first two are returned by the scan callback to indicate 180204591Sluigi * to delete the matching element or to end the scan 181204591Sluigi */ 182204591Sluigi DNHT_SCAN_DEL = 0x0001, 183204591Sluigi DNHT_SCAN_END = 0x0002, 184204591Sluigi DNHT_KEY_IS_OBJ = 0x0004, /* key is the obj pointer */ 185204591Sluigi DNHT_MATCH_PTR = 0x0008, /* match by pointer, not match() */ 186204591Sluigi DNHT_INSERT = 0x0010, /* insert if not found */ 187204591Sluigi DNHT_UNIQUE = 0x0020, /* report error if already there */ 188204591Sluigi DNHT_REMOVE = 0x0040, /* remove on find or dn_ht_free */ 189204591Sluigi}; 190204591Sluigi 191204591Sluigi#endif /* _IP_DN_HEAP_H */ 192