1 /* 2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 3 * 4 * Permission to use, copy, modify, and/or distribute this software for any 5 * purpose with or without fee is hereby granted, provided that the above 6 * copyright notice and this permission notice appear in all copies. 7 * 8 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 9 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 10 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 11 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 12 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 13 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 14 * PERFORMANCE OF THIS SOFTWARE. 15 */ 16 17 /* $Id: heap.c,v 1.7 2020/09/14 08:40:44 florian Exp $ */ 18 19 /*! \file 20 * Heap implementation of priority queues adapted from the following: 21 * 22 * \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest, 23 * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7. 24 * 25 * \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988, 26 * ISBN 0-201-06673-4, chapter 11. 27 */ 28 29 #include <stdlib.h> 30 #include <isc/heap.h> 31 #include <string.h> 32 #include <isc/util.h> 33 34 /*@{*/ 35 /*% 36 * Note: to make heap_parent and heap_left easy to compute, the first 37 * element of the heap array is not used; i.e. heap subscripts are 1-based, 38 * not 0-based. The parent is index/2, and the left-child is index*2. 39 * The right child is index*2+1. 40 */ 41 #define heap_parent(i) ((i) >> 1) 42 #define heap_left(i) ((i) << 1) 43 /*@}*/ 44 45 #define SIZE_INCREMENT 1024 46 47 /*% 48 * When the heap is in a consistent state, the following invariant 49 * holds true: for every element i > 1, heap_parent(i) has a priority 50 * higher than or equal to that of i. 51 */ 52 #define HEAPCONDITION(i) ((i) == 1 || \ 53 ! heap->compare(heap->array[(i)], \ 54 heap->array[heap_parent(i)])) 55 56 /*% ISC heap structure. */ 57 struct isc_heap { 58 unsigned int size; 59 unsigned int size_increment; 60 unsigned int last; 61 void **array; 62 isc_heapcompare_t compare; 63 isc_heapindex_t index; 64 }; 65 66 isc_result_t 67 isc_heap_create(isc_heapcompare_t compare, 68 isc_heapindex_t idx, unsigned int size_increment, 69 isc_heap_t **heapp) 70 { 71 isc_heap_t *heap; 72 73 REQUIRE(heapp != NULL && *heapp == NULL); 74 REQUIRE(compare != NULL); 75 76 heap = malloc(sizeof(*heap)); 77 if (heap == NULL) 78 return (ISC_R_NOMEMORY); 79 heap->size = 0; 80 if (size_increment == 0) 81 heap->size_increment = SIZE_INCREMENT; 82 else 83 heap->size_increment = size_increment; 84 heap->last = 0; 85 heap->array = NULL; 86 heap->compare = compare; 87 heap->index = idx; 88 89 *heapp = heap; 90 91 return (ISC_R_SUCCESS); 92 } 93 94 void 95 isc_heap_destroy(isc_heap_t **heapp) { 96 isc_heap_t *heap; 97 98 REQUIRE(heapp != NULL); 99 heap = *heapp; 100 101 free(heap->array); 102 free(heap); 103 104 *heapp = NULL; 105 } 106 107 static int 108 resize(isc_heap_t *heap) { 109 void **new_array; 110 unsigned int new_size; 111 112 new_size = heap->size + heap->size_increment; 113 new_array = reallocarray(NULL, new_size, sizeof(void *)); 114 if (new_array == NULL) 115 return (0); 116 if (heap->array != NULL) { 117 memmove(new_array, heap->array, heap->size * sizeof(void *)); 118 free(heap->array); 119 } 120 heap->size = new_size; 121 heap->array = new_array; 122 123 return (1); 124 } 125 126 static void 127 float_up(isc_heap_t *heap, unsigned int i, void *elt) { 128 unsigned int p; 129 130 for (p = heap_parent(i) ; 131 i > 1 && heap->compare(elt, heap->array[p]) ; 132 i = p, p = heap_parent(i)) { 133 heap->array[i] = heap->array[p]; 134 if (heap->index != NULL) 135 (heap->index)(heap->array[i], i); 136 } 137 heap->array[i] = elt; 138 if (heap->index != NULL) 139 (heap->index)(heap->array[i], i); 140 141 INSIST(HEAPCONDITION(i)); 142 } 143 144 static void 145 sink_down(isc_heap_t *heap, unsigned int i, void *elt) { 146 unsigned int j, size, half_size; 147 size = heap->last; 148 half_size = size / 2; 149 while (i <= half_size) { 150 /* Find the smallest of the (at most) two children. */ 151 j = heap_left(i); 152 if (j < size && heap->compare(heap->array[j+1], 153 heap->array[j])) 154 j++; 155 if (heap->compare(elt, heap->array[j])) 156 break; 157 heap->array[i] = heap->array[j]; 158 if (heap->index != NULL) 159 (heap->index)(heap->array[i], i); 160 i = j; 161 } 162 heap->array[i] = elt; 163 if (heap->index != NULL) 164 (heap->index)(heap->array[i], i); 165 166 INSIST(HEAPCONDITION(i)); 167 } 168 169 isc_result_t 170 isc_heap_insert(isc_heap_t *heap, void *elt) { 171 unsigned int new_last; 172 173 new_last = heap->last + 1; 174 RUNTIME_CHECK(new_last > 0); /* overflow check */ 175 if (new_last >= heap->size && !resize(heap)) 176 return (ISC_R_NOMEMORY); 177 heap->last = new_last; 178 179 float_up(heap, new_last, elt); 180 181 return (ISC_R_SUCCESS); 182 } 183 184 void 185 isc_heap_delete(isc_heap_t *heap, unsigned int idx) { 186 void *elt; 187 int less; 188 189 REQUIRE(idx >= 1 && idx <= heap->last); 190 191 if (heap->index != NULL) 192 (heap->index)(heap->array[idx], 0); 193 if (idx == heap->last) { 194 heap->array[heap->last] = NULL; 195 heap->last--; 196 } else { 197 elt = heap->array[heap->last]; 198 heap->array[heap->last] = NULL; 199 heap->last--; 200 201 less = heap->compare(elt, heap->array[idx]); 202 heap->array[idx] = elt; 203 if (less) 204 float_up(heap, idx, heap->array[idx]); 205 else 206 sink_down(heap, idx, heap->array[idx]); 207 } 208 } 209 210 void 211 isc_heap_increased(isc_heap_t *heap, unsigned int idx) { 212 REQUIRE(idx >= 1 && idx <= heap->last); 213 214 float_up(heap, idx, heap->array[idx]); 215 } 216 217 void 218 isc_heap_decreased(isc_heap_t *heap, unsigned int idx) { 219 REQUIRE(idx >= 1 && idx <= heap->last); 220 221 sink_down(heap, idx, heap->array[idx]); 222 } 223 224 void * 225 isc_heap_element(isc_heap_t *heap, unsigned int idx) { 226 REQUIRE(idx >= 1); 227 228 if (idx <= heap->last) 229 return (heap->array[idx]); 230 return (NULL); 231 } 232