lib/isc/heap.c

32 #include <isc/heap.h>
41  * element of the heap array is not used; i.e. heap subscripts are 1-based,
55  * When the heap is in a consistent state, the following invariant
60 			  ! heap->compare(heap->array[(i)], \
61 					  heap->array[heap_parent(i)]))
63 /*% ISC heap structure. */
80 	isc_heap_t *heap;
85 	heap = isc_mem_get(mctx, sizeof(*heap));
86 	if (heap == NULL)
88 	heap->magic = HEAP_MAGIC;
89 	heap->size = 0;
90 	heap->mctx = NULL;
91 	isc_mem_attach(mctx, &heap->mctx);
93 		heap->size_increment = SIZE_INCREMENT;
95 		heap->size_increment = size_increment;
96 	heap->last = 0;
97 	heap->array = NULL;
98 	heap->compare = compare;
99 	heap->index = index;
101 	*heapp = heap;
108 	isc_heap_t *heap;
111 	heap = *heapp;
112 	REQUIRE(VALID_HEAP(heap));
114 	if (heap->array != NULL)
115 		isc_mem_put(heap->mctx, heap->array,
116 			    heap->size * sizeof(void *));
117 	heap->magic = 0;
118 	isc_mem_putanddetach(&heap->mctx, heap, sizeof(*heap));
124 resize(isc_heap_t *heap) {
128 	REQUIRE(VALID_HEAP(heap));
130 	new_size = heap->size + heap->size_increment;
131 	new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *));
134 	if (heap->array != NULL) {
135 		memcpy(new_array, heap->array, heap->size * sizeof(void *));
136 		isc_mem_put(heap->mctx, heap->array,
137 			    heap->size * sizeof(void *));
139 	heap->size = new_size;
140 	heap->array = new_array;
146 float_up(isc_heap_t *heap, unsigned int i, void *elt) {
150 	     i > 1 && heap->compare(elt, heap->array[p]) ;
152 		heap->array[i] = heap->array[p];
153 		if (heap->index != NULL)
154 			(heap->index)(heap->array[i], i);
156 	heap->array[i] = elt;
157 	if (heap->index != NULL)
158 		(heap->index)(heap->array[i], i);
164 sink_down(isc_heap_t *heap, unsigned int i, void *elt) {
166 	size = heap->last;
171 		if (j < size && heap->compare(heap->array[j+1],
172 					      heap->array[j]))
174 		if (heap->compare(elt, heap->array[j]))
176 		heap->array[i] = heap->array[j];
177 		if (heap->index != NULL)
178 			(heap->index)(heap->array[i], i);
181 	heap->array[i] = elt;
182 	if (heap->index != NULL)
183 		(heap->index)(heap->array[i], i);
189 isc_heap_insert(isc_heap_t *heap, void *elt) {
192 	REQUIRE(VALID_HEAP(heap));
194 	new_last = heap->last + 1;
196 	if (new_last >= heap->size && !resize(heap))
198 	heap->last = new_last;
200 	float_up(heap, new_last, elt);
206 isc_heap_delete(isc_heap_t *heap, unsigned int index) {
210 	REQUIRE(VALID_HEAP(heap));
211 	REQUIRE(index >= 1 && index <= heap->last);
213 	if (index == heap->last) {
214 		heap->array[heap->last] = NULL;
215 		heap->last--;
217 		elt = heap->array[heap->last];
218 		heap->array[heap->last] = NULL;
219 		heap->last--;
221 		less = heap->compare(elt, heap->array[index]);
222 		heap->array[index] = elt;
224 			float_up(heap, index, heap->array[index]);
226 			sink_down(heap, index, heap->array[index]);
231 isc_heap_increased(isc_heap_t *heap, unsigned int index) {
232 	REQUIRE(VALID_HEAP(heap));
233 	REQUIRE(index >= 1 && index <= heap->last);
235 	float_up(heap, index, heap->array[index]);
239 isc_heap_decreased(isc_heap_t *heap, unsigned int index) {
240 	REQUIRE(VALID_HEAP(heap));
241 	REQUIRE(index >= 1 && index <= heap->last);
243 	sink_down(heap, index, heap->array[index]);
247 isc_heap_element(isc_heap_t *heap, unsigned int index) {
248 	REQUIRE(VALID_HEAP(heap));
251 	if (index <= heap->last)
252 		return (heap->array[index]);
257 isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) {
260 	REQUIRE(VALID_HEAP(heap));
263 	for (i = 1 ; i <= heap->last ; i++)
264 		(action)(heap->array[i], uap);