"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.17.5/lib/isc/heap.c" (4 Sep 2020, 6440 Bytes) of package /linux/misc/dns/bind9/9.17.5/bind-9.17.5.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "heap.c" see the Fossies "Dox" file reference documentation.

    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 http://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 /*! \file
   13  * Heap implementation of priority queues adapted from the following:
   14  *
   15  *  \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest,
   16  *  MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7.
   17  *
   18  *  \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988,
   19  *  ISBN 0-201-06673-4, chapter 11.
   20  */
   21 
   22 #include <stdbool.h>
   23 
   24 #include <isc/heap.h>
   25 #include <isc/magic.h>
   26 #include <isc/mem.h>
   27 #include <isc/string.h> /* Required for memmove. */
   28 #include <isc/util.h>
   29 
   30 /*@{*/
   31 /*%
   32  * Note: to make heap_parent and heap_left easy to compute, the first
   33  * element of the heap array is not used; i.e. heap subscripts are 1-based,
   34  * not 0-based.  The parent is index/2, and the left-child is index*2.
   35  * The right child is index*2+1.
   36  */
   37 #define heap_parent(i) ((i) >> 1)
   38 #define heap_left(i)   ((i) << 1)
   39 /*@}*/
   40 
   41 #define SIZE_INCREMENT 1024
   42 
   43 #define HEAP_MAGIC    ISC_MAGIC('H', 'E', 'A', 'P')
   44 #define VALID_HEAP(h) ISC_MAGIC_VALID(h, HEAP_MAGIC)
   45 
   46 /*%
   47  * When the heap is in a consistent state, the following invariant
   48  * holds true: for every element i > 1, heap_parent(i) has a priority
   49  * higher than or equal to that of i.
   50  */
   51 #define HEAPCONDITION(i) \
   52     ((i) == 1 ||     \
   53      !heap->compare(heap->array[(i)], heap->array[heap_parent(i)]))
   54 
   55 /*% ISC heap structure. */
   56 struct isc_heap {
   57     unsigned int magic;
   58     isc_mem_t *mctx;
   59     unsigned int size;
   60     unsigned int size_increment;
   61     unsigned int last;
   62     void **array;
   63     isc_heapcompare_t compare;
   64     isc_heapindex_t index;
   65 };
   66 
   67 #ifdef ISC_HEAP_CHECK
   68 static void
   69 heap_check(isc_heap_t *heap) {
   70     unsigned int i;
   71     for (i = 1; i <= heap->last; i++) {
   72         INSIST(HEAPCONDITION(i));
   73     }
   74 }
   75 #else /* ifdef ISC_HEAP_CHECK */
   76 #define heap_check(x) (void)0
   77 #endif /* ifdef ISC_HEAP_CHECK */
   78 
   79 isc_result_t
   80 isc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare, isc_heapindex_t idx,
   81         unsigned int size_increment, isc_heap_t **heapp) {
   82     isc_heap_t *heap;
   83 
   84     REQUIRE(heapp != NULL && *heapp == NULL);
   85     REQUIRE(compare != NULL);
   86 
   87     heap = isc_mem_get(mctx, sizeof(*heap));
   88     heap->magic = HEAP_MAGIC;
   89     heap->size = 0;
   90     heap->mctx = NULL;
   91     isc_mem_attach(mctx, &heap->mctx);
   92     if (size_increment == 0) {
   93         heap->size_increment = SIZE_INCREMENT;
   94     } else {
   95         heap->size_increment = size_increment;
   96     }
   97     heap->last = 0;
   98     heap->array = NULL;
   99     heap->compare = compare;
  100     heap->index = idx;
  101 
  102     *heapp = heap;
  103 
  104     return (ISC_R_SUCCESS);
  105 }
  106 
  107 void
  108 isc_heap_destroy(isc_heap_t **heapp) {
  109     isc_heap_t *heap;
  110 
  111     REQUIRE(heapp != NULL);
  112     heap = *heapp;
  113     *heapp = NULL;
  114     REQUIRE(VALID_HEAP(heap));
  115 
  116     if (heap->array != NULL) {
  117         isc_mem_put(heap->mctx, heap->array,
  118                 heap->size * sizeof(void *));
  119     }
  120     heap->magic = 0;
  121     isc_mem_putanddetach(&heap->mctx, heap, sizeof(*heap));
  122 }
  123 
  124 static bool
  125 resize(isc_heap_t *heap) {
  126     void **new_array;
  127     unsigned int new_size;
  128 
  129     REQUIRE(VALID_HEAP(heap));
  130 
  131     new_size = heap->size + heap->size_increment;
  132     new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *));
  133     if (heap->array != NULL) {
  134         memmove(new_array, heap->array, heap->size * sizeof(void *));
  135         isc_mem_put(heap->mctx, heap->array,
  136                 heap->size * sizeof(void *));
  137     }
  138     heap->size = new_size;
  139     heap->array = new_array;
  140 
  141     return (true);
  142 }
  143 
  144 static void
  145 float_up(isc_heap_t *heap, unsigned int i, void *elt) {
  146     unsigned int p;
  147 
  148     for (p = heap_parent(i); i > 1 && heap->compare(elt, heap->array[p]);
  149          i = p, p = heap_parent(i))
  150     {
  151         heap->array[i] = heap->array[p];
  152         if (heap->index != NULL) {
  153             (heap->index)(heap->array[i], i);
  154         }
  155     }
  156     heap->array[i] = elt;
  157     if (heap->index != NULL) {
  158         (heap->index)(heap->array[i], i);
  159     }
  160 
  161     INSIST(HEAPCONDITION(i));
  162     heap_check(heap);
  163 }
  164 
  165 static void
  166 sink_down(isc_heap_t *heap, unsigned int i, void *elt) {
  167     unsigned int j, size, half_size;
  168     size = heap->last;
  169     half_size = size / 2;
  170     while (i <= half_size) {
  171         /* Find the smallest of the (at most) two children. */
  172         j = heap_left(i);
  173         if (j < size &&
  174             heap->compare(heap->array[j + 1], heap->array[j])) {
  175             j++;
  176         }
  177         if (heap->compare(elt, heap->array[j])) {
  178             break;
  179         }
  180         heap->array[i] = heap->array[j];
  181         if (heap->index != NULL) {
  182             (heap->index)(heap->array[i], i);
  183         }
  184         i = j;
  185     }
  186     heap->array[i] = elt;
  187     if (heap->index != NULL) {
  188         (heap->index)(heap->array[i], i);
  189     }
  190 
  191     INSIST(HEAPCONDITION(i));
  192     heap_check(heap);
  193 }
  194 
  195 isc_result_t
  196 isc_heap_insert(isc_heap_t *heap, void *elt) {
  197     unsigned int new_last;
  198 
  199     REQUIRE(VALID_HEAP(heap));
  200 
  201     heap_check(heap);
  202     new_last = heap->last + 1;
  203     RUNTIME_CHECK(new_last > 0); /* overflow check */
  204     if (new_last >= heap->size && !resize(heap)) {
  205         return (ISC_R_NOMEMORY);
  206     }
  207     heap->last = new_last;
  208 
  209     float_up(heap, new_last, elt);
  210 
  211     return (ISC_R_SUCCESS);
  212 }
  213 
  214 void
  215 isc_heap_delete(isc_heap_t *heap, unsigned int idx) {
  216     void *elt;
  217     bool less;
  218 
  219     REQUIRE(VALID_HEAP(heap));
  220     REQUIRE(idx >= 1 && idx <= heap->last);
  221 
  222     heap_check(heap);
  223     if (heap->index != NULL) {
  224         (heap->index)(heap->array[idx], 0);
  225     }
  226     if (idx == heap->last) {
  227         heap->array[heap->last] = NULL;
  228         heap->last--;
  229         heap_check(heap);
  230     } else {
  231         elt = heap->array[heap->last];
  232         heap->array[heap->last] = NULL;
  233         heap->last--;
  234 
  235         less = heap->compare(elt, heap->array[idx]);
  236         heap->array[idx] = elt;
  237         if (less) {
  238             float_up(heap, idx, heap->array[idx]);
  239         } else {
  240             sink_down(heap, idx, heap->array[idx]);
  241         }
  242     }
  243 }
  244 
  245 void
  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
  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 *
  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     }
  270     return (NULL);
  271 }
  272 
  273 void
  274 isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) {
  275     unsigned int i;
  276 
  277     REQUIRE(VALID_HEAP(heap));
  278     REQUIRE(action != NULL);
  279 
  280     for (i = 1; i <= heap->last; i++) {
  281         (action)(heap->array[i], uap);
  282     }
  283 }