external/bsd/ntp/dist/lib/isc/heap.c

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