57 	 !heap->compare(heap->array[(i)], heap->array[heap_parent(i)]))
73 heap_check(isc_heap_t *heap) {  in heap_check()  argument
75 	for (i = 1; i <= heap->last; i++) {  in heap_check()
86 	isc_heap_t *heap;  in isc_heap_create()  local
91 	heap = isc_mem_get(mctx, sizeof(*heap));  in isc_heap_create()
92 	heap->magic = HEAP_MAGIC;  in isc_heap_create()
93 	heap->size = 0;  in isc_heap_create()
94 	heap->mctx = NULL;  in isc_heap_create()
95 	isc_mem_attach(mctx, &heap->mctx);  in isc_heap_create()
97 		heap->size_increment = SIZE_INCREMENT;  in isc_heap_create()
99 		heap->size_increment = size_increment;  in isc_heap_create()
101 	heap->last = 0;  in isc_heap_create()
102 	heap->array = NULL;  in isc_heap_create()
103 	heap->compare = compare;  in isc_heap_create()
104 	heap->index = idx;  in isc_heap_create()
106 	*heapp = heap;  in isc_heap_create()
111 	isc_heap_t *heap;  in isc_heap_destroy()  local
114 	heap = *heapp;  in isc_heap_destroy()
116 	REQUIRE(VALID_HEAP(heap));  in isc_heap_destroy()
118 	if (heap->array != NULL) {  in isc_heap_destroy()
119 		isc_mem_put(heap->mctx, heap->array,  in isc_heap_destroy()
120 			    heap->size * sizeof(void *));  in isc_heap_destroy()
122 	heap->magic = 0;  in isc_heap_destroy()
123 	isc_mem_putanddetach(&heap->mctx, heap, sizeof(*heap));  in isc_heap_destroy()
127 resize(isc_heap_t *heap) {  in resize()  argument
131 	REQUIRE(VALID_HEAP(heap));  in resize()
133 	new_size = heap->size + heap->size_increment;  in resize()
134 	new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *));  in resize()
135 	if (heap->array != NULL) {  in resize()
136 		memmove(new_array, heap->array, heap->size * sizeof(void *));  in resize()
137 		isc_mem_put(heap->mctx, heap->array,  in resize()
138 			    heap->size * sizeof(void *));  in resize()
140 	heap->size = new_size;  in resize()
141 	heap->array = new_array;  in resize()
145 float_up(isc_heap_t *heap, unsigned int i, void *elt) {  in float_up()  argument
148 	for (p = heap_parent(i); i > 1 && heap->compare(elt, heap->array[p]);  in float_up()
151 		heap->array[i] = heap->array[p];  in float_up()
152 		if (heap->index != NULL) {  in float_up()
153 			(heap->index)(heap->array[i], i);  in float_up()
156 	heap->array[i] = elt;  in float_up()
157 	if (heap->index != NULL) {  in float_up()
158 		(heap->index)(heap->array[i], i);  in float_up()
162 	heap_check(heap);  in float_up()
166 sink_down(isc_heap_t *heap, unsigned int i, void *elt) {  in sink_down()  argument
168 	size = heap->last;  in sink_down()
174 		    heap->compare(heap->array[j + 1], heap->array[j]))  in sink_down()
178 		if (heap->compare(elt, heap->array[j])) {  in sink_down()
181 		heap->array[i] = heap->array[j];  in sink_down()
182 		if (heap->index != NULL) {  in sink_down()
183 			(heap->index)(heap->array[i], i);  in sink_down()
187 	heap->array[i] = elt;  in sink_down()
188 	if (heap->index != NULL) {  in sink_down()
189 		(heap->index)(heap->array[i], i);  in sink_down()
193 	heap_check(heap);  in sink_down()
197 isc_heap_insert(isc_heap_t *heap, void *elt) {  in isc_heap_insert()  argument
200 	REQUIRE(VALID_HEAP(heap));  in isc_heap_insert()
202 	heap_check(heap);  in isc_heap_insert()
203 	new_last = heap->last + 1;  in isc_heap_insert()
205 	if (new_last >= heap->size) {  in isc_heap_insert()
206 		resize(heap);  in isc_heap_insert()
208 	heap->last = new_last;  in isc_heap_insert()
210 	float_up(heap, new_last, elt);  in isc_heap_insert()
214 isc_heap_delete(isc_heap_t *heap, unsigned int idx) {  in isc_heap_delete()  argument
218 	REQUIRE(VALID_HEAP(heap));  in isc_heap_delete()
219 	REQUIRE(idx >= 1 && idx <= heap->last);  in isc_heap_delete()
221 	heap_check(heap);  in isc_heap_delete()
222 	if (heap->index != NULL) {  in isc_heap_delete()
223 		(heap->index)(heap->array[idx], 0);  in isc_heap_delete()
225 	if (idx == heap->last) {  in isc_heap_delete()
226 		heap->array[heap->last] = NULL;  in isc_heap_delete()
227 		heap->last--;  in isc_heap_delete()
228 		heap_check(heap);  in isc_heap_delete()
230 		elt = heap->array[heap->last];  in isc_heap_delete()
231 		heap->array[heap->last] = NULL;  in isc_heap_delete()
232 		heap->last--;  in isc_heap_delete()
234 		less = heap->compare(elt, heap->array[idx]);  in isc_heap_delete()
235 		heap->array[idx] = elt;  in isc_heap_delete()
237 			float_up(heap, idx, heap->array[idx]);  in isc_heap_delete()
239 			sink_down(heap, idx, heap->array[idx]);  in isc_heap_delete()
245 isc_heap_increased(isc_heap_t *heap, unsigned int idx) {  in isc_heap_increased()  argument
246 	REQUIRE(VALID_HEAP(heap));  in isc_heap_increased()
247 	REQUIRE(idx >= 1 && idx <= heap->last);  in isc_heap_increased()
249 	float_up(heap, idx, heap->array[idx]);  in isc_heap_increased()
253 isc_heap_decreased(isc_heap_t *heap, unsigned int idx) {  in isc_heap_decreased()  argument
254 	REQUIRE(VALID_HEAP(heap));  in isc_heap_decreased()
255 	REQUIRE(idx >= 1 && idx <= heap->last);  in isc_heap_decreased()
257 	sink_down(heap, idx, heap->array[idx]);  in isc_heap_decreased()
261 isc_heap_element(isc_heap_t *heap, unsigned int idx) {  in isc_heap_element()  argument
262 	REQUIRE(VALID_HEAP(heap));  in isc_heap_element()
265 	heap_check(heap);  in isc_heap_element()
266 	if (idx <= heap->last) {  in isc_heap_element()
267 		return (heap->array[idx]);  in isc_heap_element()
273 isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) {  in isc_heap_foreach()  argument
276 	REQUIRE(VALID_HEAP(heap));  in isc_heap_foreach()
279 	for (i = 1; i <= heap->last; i++) {  in isc_heap_foreach()
280 		(action)(heap->array[i], uap);  in isc_heap_foreach()