Lines Matching defs:heap
1 /* $NetBSD: heap.c,v 1.8 2025/01/26 16:25:37 christos Exp $ */
28 #include <isc/heap.h>
38 * element of the heap array is not used; i.e. heap subscripts are 1-based,
52 * When the heap is in a consistent state, the following invariant
58 !heap->compare(heap->array[(i)], heap->array[heap_parent(i)]))
60 /*% ISC heap structure. */
74 heap_check(isc_heap_t *heap) {
76 for (i = 1; i <= heap->last; i++) {
87 isc_heap_t *heap;
92 heap = isc_mem_get(mctx, sizeof(*heap));
93 heap->magic = HEAP_MAGIC;
94 heap->size = 0;
95 heap->mctx = NULL;
96 isc_mem_attach(mctx, &heap->mctx);
98 heap->size_increment = SIZE_INCREMENT;
100 heap->size_increment = size_increment;
102 heap->last = 0;
103 heap->array = NULL;
104 heap->compare = compare;
105 heap->index = idx;
107 *heapp = heap;
112 isc_heap_t *heap;
115 heap = *heapp;
117 REQUIRE(VALID_HEAP(heap));
119 if (heap->array != NULL) {
120 isc_mem_cput(heap->mctx, heap->array, heap->size,
123 heap->magic = 0;
124 isc_mem_putanddetach(&heap->mctx, heap, sizeof(*heap));
128 resize(isc_heap_t *heap) {
131 REQUIRE(VALID_HEAP(heap));
133 new_size = ISC_CHECKED_ADD(heap->size, heap->size_increment);
135 old_bytes = ISC_CHECKED_MUL(heap->size, sizeof(void *));
137 heap->size = new_size;
138 heap->array = isc_mem_creget(heap->mctx, heap->array, old_bytes,
143 float_up(isc_heap_t *heap, unsigned int i, void *elt) {
146 for (p = heap_parent(i); i > 1 && heap->compare(elt, heap->array[p]);
149 heap->array[i] = heap->array[p];
150 if (heap->index != NULL) {
151 (heap->index)(heap->array[i], i);
154 heap->array[i] = elt;
155 if (heap->index != NULL) {
156 (heap->index)(heap->array[i], i);
160 heap_check(heap);
164 sink_down(isc_heap_t *heap, unsigned int i, void *elt) {
166 size = heap->last;
172 heap->compare(heap->array[j + 1], heap->array[j]))
176 if (heap->compare(elt, heap->array[j])) {
179 heap->array[i] = heap->array[j];
180 if (heap->index != NULL) {
181 (heap->index)(heap->array[i], i);
185 heap->array[i] = elt;
186 if (heap->index != NULL) {
187 (heap->index)(heap->array[i], i);
191 heap_check(heap);
195 isc_heap_insert(isc_heap_t *heap, void *elt) {
198 REQUIRE(VALID_HEAP(heap));
200 heap_check(heap);
201 new_last = heap->last + 1;
203 if (new_last >= heap->size) {
204 resize(heap);
206 heap->last = new_last;
208 float_up(heap, new_last, elt);
212 isc_heap_delete(isc_heap_t *heap, unsigned int idx) {
216 REQUIRE(VALID_HEAP(heap));
217 REQUIRE(idx >= 1 && idx <= heap->last);
219 heap_check(heap);
220 if (heap->index != NULL) {
221 (heap->index)(heap->array[idx], 0);
223 if (idx == heap->last) {
224 heap->array[heap->last] = NULL;
225 heap->last--;
226 heap_check(heap);
228 elt = heap->array[heap->last];
229 heap->array[heap->last] = NULL;
230 heap->last--;
232 less = heap->compare(elt, heap->array[idx]);
233 heap->array[idx] = elt;
235 float_up(heap, idx, heap->array[idx]);
237 sink_down(heap, idx, heap->array[idx]);
243 isc_heap_increased(isc_heap_t *heap, unsigned int idx) {
244 REQUIRE(VALID_HEAP(heap));
245 REQUIRE(idx >= 1 && idx <= heap->last);
247 float_up(heap, idx, heap->array[idx]);
251 isc_heap_decreased(isc_heap_t *heap, unsigned int idx) {
252 REQUIRE(VALID_HEAP(heap));
253 REQUIRE(idx >= 1 && idx <= heap->last);
255 sink_down(heap, idx, heap->array[idx]);
259 isc_heap_element(isc_heap_t *heap, unsigned int idx) {
260 REQUIRE(VALID_HEAP(heap));
263 heap_check(heap);
264 if (idx <= heap->last) {
265 return heap->array[idx];
271 isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) {
274 REQUIRE(VALID_HEAP(heap));
277 for (i = 1; i <= heap->last; i++) {
278 (action)(heap->array[i], uap);