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