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