1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3 * 4 * Copyright (c) 1998-2010 Luigi Rizzo, Universita` di Pisa 5 * All rights reserved 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29 /* 30 * Binary heap and hash tables, header file 31 * 32 * $FreeBSD$ 33 */ 34 35 #ifndef _IP_DN_HEAP_H 36 #define _IP_DN_HEAP_H 37 38 #define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0) 39 #define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0) 40 41 /* 42 * This module implements a binary heap supporting random extraction. 43 * 44 * A heap entry contains an uint64_t key and a pointer to object. 45 * DN_KEY_LT(a,b) returns true if key 'a' is smaller than 'b' 46 * 47 * The heap is a struct dn_heap plus a dynamically allocated 48 * array of dn_heap_entry entries. 'size' represents the size of 49 * the array, 'elements' count entries in use. The topmost 50 * element has the smallest key. 51 * The heap supports ordered insert, and extract from the top. 52 * To extract an object from the middle of the heap, we the object 53 * must reserve an 'int32_t' to store the position of the object 54 * in the heap itself, and the location of this field must be 55 * passed as an argument to heap_init() -- use -1 if the feature 56 * is not used. 57 */ 58 struct dn_heap_entry { 59 uint64_t key; /* sorting key, smallest comes first */ 60 void *object; /* object pointer */ 61 }; 62 63 struct dn_heap { 64 int size; /* the size of the array */ 65 int elements; /* elements in use */ 66 int ofs; /* offset in the object of heap index */ 67 struct dn_heap_entry *p; /* array of "size" entries */ 68 }; 69 70 enum { 71 HEAP_SCAN_DEL = 1, 72 HEAP_SCAN_END = 2, 73 }; 74 75 /* 76 * heap_init() reinitializes the heap setting the size and the offset 77 * of the index for random extraction (use -1 if not used). 78 * The 'elements' counter is set to 0. 79 * 80 * SET_HEAP_OFS() indicates where, in the object, is stored the index 81 * for random extractions from the heap. 82 * 83 * heap_free() frees the memory associated to a heap. 84 * 85 * heap_insert() adds a key-pointer pair to the heap 86 * 87 * HEAP_TOP() returns a pointer to the top element of the heap, 88 * but makes no checks on its existence (XXX should we change ?) 89 * 90 * heap_extract() removes the entry at the top, returning the pointer. 91 * (the key should have been read before). 92 * 93 * heap_scan() invokes a callback on each entry of the heap. 94 * The callback can return a combination of HEAP_SCAN_DEL and 95 * HEAP_SCAN_END. HEAP_SCAN_DEL means the current element must 96 * be removed, and HEAP_SCAN_END means to terminate the scan. 97 * heap_scan() returns the number of elements removed. 98 * Because the order is not guaranteed, we should use heap_scan() 99 * only as a last resort mechanism. 100 */ 101 #define HEAP_TOP(h) ((h)->p) 102 #define SET_HEAP_OFS(h, n) do { (h)->ofs = n; } while (0) 103 int heap_init(struct dn_heap *h, int size, int ofs); 104 int heap_insert(struct dn_heap *h, uint64_t key1, void *p); 105 void heap_extract(struct dn_heap *h, void *obj); 106 void heap_free(struct dn_heap *h); 107 int heap_scan(struct dn_heap *, int (*)(void *, uintptr_t), uintptr_t); 108 109 /*------------------------------------------------------ 110 * This module implements a generic hash table with support for 111 * running callbacks on the entire table. To avoid allocating 112 * memory during hash table operations, objects must reserve 113 * space for a link field. XXX if the heap is moderately full, 114 * an SLIST suffices, and we can tolerate the cost of a hash 115 * computation on each removal. 116 * 117 * dn_ht_init() initializes the table, setting the number of 118 * buckets, the offset of the link field, the main callbacks. 119 * Callbacks are: 120 * 121 * hash(key, flags, arg) called to return a bucket index. 122 * match(obj, key, flags, arg) called to determine if key 123 * matches the current 'obj' in the heap 124 * newh(key, flags, arg) optional, used to allocate a new 125 * object during insertions. 126 * 127 * dn_ht_free() frees the heap or unlink elements. 128 * DNHT_REMOVE unlink elements, 0 frees the heap. 129 * You need two calls to do both. 130 * 131 * dn_ht_find() is the main lookup function, which can also be 132 * used to insert or delete elements in the hash table. 133 * The final 'arg' is passed to all callbacks. 134 * 135 * dn_ht_scan() is used to invoke a callback on all entries of 136 * the heap, or possibly on just one bucket. The callback 137 * is invoked with a pointer to the object, and must return 138 * one of DNHT_SCAN_DEL or DNHT_SCAN_END to request the 139 * removal of the object from the heap and the end of the 140 * scan, respectively. 141 * 142 * dn_ht_scan_bucket() is similar to dn_ht_scan(), except that it scans 143 * only the specific bucket of the table. The bucket is a in-out 144 * parameter and return a valid bucket number if the original 145 * is invalid. 146 * 147 * A combination of flags can be used to modify the operation 148 * of the dn_ht_find(), and of the callbacks: 149 * 150 * DNHT_KEY_IS_OBJ means the key is the object pointer. 151 * It is usually of interest for the hash and match functions. 152 * 153 * DNHT_MATCH_PTR during a lookup, match pointers instead 154 * of calling match(). Normally used when removing specific 155 * entries. Does not imply KEY_IS_OBJ as the latter _is_ used 156 * by the match function. 157 * 158 * DNHT_INSERT insert the element if not found. 159 * Calls new() to allocates a new object unless 160 * DNHT_KEY_IS_OBJ is set. 161 * 162 * DNHT_UNIQUE only insert if object not found. 163 * XXX should it imply DNHT_INSERT ? 164 * 165 * DNHT_REMOVE remove objects if we find them. 166 */ 167 struct dn_ht; /* should be opaque */ 168 169 struct dn_ht *dn_ht_init(struct dn_ht *, int buckets, int ofs, 170 uint32_t (*hash)(uintptr_t, int, void *), 171 int (*match)(void *, uintptr_t, int, void *), 172 void *(*newh)(uintptr_t, int, void *)); 173 void dn_ht_free(struct dn_ht *, int flags); 174 175 void *dn_ht_find(struct dn_ht *, uintptr_t, int, void *); 176 int dn_ht_scan(struct dn_ht *, int (*)(void *, void *), void *); 177 int dn_ht_scan_bucket(struct dn_ht *, int * , int (*)(void *, void *), void *); 178 int dn_ht_entries(struct dn_ht *); 179 180 enum { /* flags values. 181 * first two are returned by the scan callback to indicate 182 * to delete the matching element or to end the scan 183 */ 184 DNHT_SCAN_DEL = 0x0001, 185 DNHT_SCAN_END = 0x0002, 186 DNHT_KEY_IS_OBJ = 0x0004, /* key is the obj pointer */ 187 DNHT_MATCH_PTR = 0x0008, /* match by pointer, not match() */ 188 DNHT_INSERT = 0x0010, /* insert if not found */ 189 DNHT_UNIQUE = 0x0020, /* report error if already there */ 190 DNHT_REMOVE = 0x0040, /* remove on find or dn_ht_free */ 191 }; 192 193 #endif /* _IP_DN_HEAP_H */ 194