1 /* $NetBSD: heap.c,v 1.7 2023/01/25 21:43:31 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 7 * 8 * This Source Code Form is subject to the terms of the Mozilla Public 9 * License, v. 2.0. If a copy of the MPL was not distributed with this 10 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 11 * 12 * See the COPYRIGHT file distributed with this work for additional 13 * information regarding copyright ownership. 14 */ 15 16 /*! \file 17 * Heap implementation of priority queues adapted from the following: 18 * 19 * \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest, 20 * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7. 21 * 22 * \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988, 23 * ISBN 0-201-06673-4, chapter 11. 24 */ 25 26 #include <stdbool.h> 27 28 #include <isc/heap.h> 29 #include <isc/magic.h> 30 #include <isc/mem.h> 31 #include <isc/string.h> /* Required for memmove. */ 32 #include <isc/util.h> 33 34 /*@{*/ 35 /*% 36 * Note: to make heap_parent and heap_left easy to compute, the first 37 * element of the heap array is not used; i.e. heap subscripts are 1-based, 38 * not 0-based. The parent is index/2, and the left-child is index*2. 39 * The right child is index*2+1. 40 */ 41 #define heap_parent(i) ((i) >> 1) 42 #define heap_left(i) ((i) << 1) 43 /*@}*/ 44 45 #define SIZE_INCREMENT 1024 46 47 #define HEAP_MAGIC ISC_MAGIC('H', 'E', 'A', 'P') 48 #define VALID_HEAP(h) ISC_MAGIC_VALID(h, HEAP_MAGIC) 49 50 /*% 51 * When the heap is in a consistent state, the following invariant 52 * holds true: for every element i > 1, heap_parent(i) has a priority 53 * higher than or equal to that of i. 54 */ 55 #define HEAPCONDITION(i) \ 56 ((i) == 1 || \ 57 !heap->compare(heap->array[(i)], heap->array[heap_parent(i)])) 58 59 /*% ISC heap structure. */ 60 struct isc_heap { 61 unsigned int magic; 62 isc_mem_t *mctx; 63 unsigned int size; 64 unsigned int size_increment; 65 unsigned int last; 66 void **array; 67 isc_heapcompare_t compare; 68 isc_heapindex_t index; 69 }; 70 71 #ifdef ISC_HEAP_CHECK 72 static void 73 heap_check(isc_heap_t *heap) { 74 unsigned int i; 75 for (i = 1; i <= heap->last; i++) { 76 INSIST(HEAPCONDITION(i)); 77 } 78 } 79 #else /* ifdef ISC_HEAP_CHECK */ 80 #define heap_check(x) (void)0 81 #endif /* ifdef ISC_HEAP_CHECK */ 82 83 void 84 isc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare, isc_heapindex_t idx, 85 unsigned int size_increment, isc_heap_t **heapp) { 86 isc_heap_t *heap; 87 88 REQUIRE(heapp != NULL && *heapp == NULL); 89 REQUIRE(compare != NULL); 90 91 heap = isc_mem_get(mctx, sizeof(*heap)); 92 heap->magic = HEAP_MAGIC; 93 heap->size = 0; 94 heap->mctx = NULL; 95 isc_mem_attach(mctx, &heap->mctx); 96 if (size_increment == 0) { 97 heap->size_increment = SIZE_INCREMENT; 98 } else { 99 heap->size_increment = size_increment; 100 } 101 heap->last = 0; 102 heap->array = NULL; 103 heap->compare = compare; 104 heap->index = idx; 105 106 *heapp = heap; 107 } 108 109 void 110 isc_heap_destroy(isc_heap_t **heapp) { 111 isc_heap_t *heap; 112 113 REQUIRE(heapp != NULL); 114 heap = *heapp; 115 *heapp = NULL; 116 REQUIRE(VALID_HEAP(heap)); 117 118 if (heap->array != NULL) { 119 isc_mem_put(heap->mctx, heap->array, 120 heap->size * sizeof(void *)); 121 } 122 heap->magic = 0; 123 isc_mem_putanddetach(&heap->mctx, heap, sizeof(*heap)); 124 } 125 126 static void 127 resize(isc_heap_t *heap) { 128 void **new_array; 129 unsigned int new_size; 130 131 REQUIRE(VALID_HEAP(heap)); 132 133 new_size = heap->size + heap->size_increment; 134 new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *)); 135 if (heap->array != NULL) { 136 memmove(new_array, heap->array, heap->size * sizeof(void *)); 137 isc_mem_put(heap->mctx, heap->array, 138 heap->size * sizeof(void *)); 139 } 140 heap->size = new_size; 141 heap->array = new_array; 142 } 143 144 static void 145 float_up(isc_heap_t *heap, unsigned int i, void *elt) { 146 unsigned int p; 147 148 for (p = heap_parent(i); i > 1 && heap->compare(elt, heap->array[p]); 149 i = p, p = heap_parent(i)) 150 { 151 heap->array[i] = heap->array[p]; 152 if (heap->index != NULL) { 153 (heap->index)(heap->array[i], i); 154 } 155 } 156 heap->array[i] = elt; 157 if (heap->index != NULL) { 158 (heap->index)(heap->array[i], i); 159 } 160 161 INSIST(HEAPCONDITION(i)); 162 heap_check(heap); 163 } 164 165 static void 166 sink_down(isc_heap_t *heap, unsigned int i, void *elt) { 167 unsigned int j, size, half_size; 168 size = heap->last; 169 half_size = size / 2; 170 while (i <= half_size) { 171 /* Find the smallest of the (at most) two children. */ 172 j = heap_left(i); 173 if (j < size && 174 heap->compare(heap->array[j + 1], heap->array[j])) 175 { 176 j++; 177 } 178 if (heap->compare(elt, heap->array[j])) { 179 break; 180 } 181 heap->array[i] = heap->array[j]; 182 if (heap->index != NULL) { 183 (heap->index)(heap->array[i], i); 184 } 185 i = j; 186 } 187 heap->array[i] = elt; 188 if (heap->index != NULL) { 189 (heap->index)(heap->array[i], i); 190 } 191 192 INSIST(HEAPCONDITION(i)); 193 heap_check(heap); 194 } 195 196 void 197 isc_heap_insert(isc_heap_t *heap, void *elt) { 198 unsigned int new_last; 199 200 REQUIRE(VALID_HEAP(heap)); 201 202 heap_check(heap); 203 new_last = heap->last + 1; 204 RUNTIME_CHECK(new_last > 0); /* overflow check */ 205 if (new_last >= heap->size) { 206 resize(heap); 207 } 208 heap->last = new_last; 209 210 float_up(heap, new_last, elt); 211 } 212 213 void 214 isc_heap_delete(isc_heap_t *heap, unsigned int idx) { 215 void *elt; 216 bool less; 217 218 REQUIRE(VALID_HEAP(heap)); 219 REQUIRE(idx >= 1 && idx <= heap->last); 220 221 heap_check(heap); 222 if (heap->index != NULL) { 223 (heap->index)(heap->array[idx], 0); 224 } 225 if (idx == heap->last) { 226 heap->array[heap->last] = NULL; 227 heap->last--; 228 heap_check(heap); 229 } else { 230 elt = heap->array[heap->last]; 231 heap->array[heap->last] = NULL; 232 heap->last--; 233 234 less = heap->compare(elt, heap->array[idx]); 235 heap->array[idx] = elt; 236 if (less) { 237 float_up(heap, idx, heap->array[idx]); 238 } else { 239 sink_down(heap, idx, heap->array[idx]); 240 } 241 } 242 } 243 244 void 245 isc_heap_increased(isc_heap_t *heap, unsigned int idx) { 246 REQUIRE(VALID_HEAP(heap)); 247 REQUIRE(idx >= 1 && idx <= heap->last); 248 249 float_up(heap, idx, heap->array[idx]); 250 } 251 252 void 253 isc_heap_decreased(isc_heap_t *heap, unsigned int idx) { 254 REQUIRE(VALID_HEAP(heap)); 255 REQUIRE(idx >= 1 && idx <= heap->last); 256 257 sink_down(heap, idx, heap->array[idx]); 258 } 259 260 void * 261 isc_heap_element(isc_heap_t *heap, unsigned int idx) { 262 REQUIRE(VALID_HEAP(heap)); 263 REQUIRE(idx >= 1); 264 265 heap_check(heap); 266 if (idx <= heap->last) { 267 return (heap->array[idx]); 268 } 269 return (NULL); 270 } 271 272 void 273 isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) { 274 unsigned int i; 275 276 REQUIRE(VALID_HEAP(heap)); 277 REQUIRE(action != NULL); 278 279 for (i = 1; i <= heap->last; i++) { 280 (action)(heap->array[i], uap); 281 } 282 } 283