contrib/bind-9.3/lib/bind/isc/heap.c

   1 /*
   2  * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (c) 1997,1999 by Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
  10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11  * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
  12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  15  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /*
  19  * Heap implementation of priority queues adapted from the following:
  20  *
  21  *      _Introduction to Algorithms_, Cormen, Leiserson, and Rivest,
  22  *      MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7.
  23  *
  24  *      _Algorithms_, Second Edition, Sedgewick, Addison-Wesley, 1988,
  25  *      ISBN 0-201-06673-4, chapter 11.
  26  */
  27
  28 #if !defined(LINT) && !defined(CODECENTER)
  29 static const char rcsid[] = "$Id: heap.c,v 1.1.206.2 2006/03/10 00:17:21 marka Exp $";
  30 #endif /* not lint */
  31
  32 #include "port_before.h"
  33
  34 #include <stddef.h>
  35 #include <stdlib.h>
  36 #include <errno.h>
  37
  38 #include "port_after.h"
  39
  40 #include <isc/heap.h>
  41
  42 /*
  43  * Note: to make heap_parent and heap_left easy to compute, the first
  44  * element of the heap array is not used; i.e. heap subscripts are 1-based,
  45  * not 0-based.
  46  */
  47 #define heap_parent(i) ((i) >> 1)
  48 #define heap_left(i) ((i) << 1)
  49
  50 #define ARRAY_SIZE_INCREMENT 512
  51
  52 heap_context
  53 heap_new(heap_higher_priority_func higher_priority, heap_index_func index,
  54          int array_size_increment) {
  55         heap_context ctx;
  56
  57         if (higher_priority == NULL)
  58                 return (NULL);
  59
  60         ctx = (heap_context)malloc(sizeof (struct heap_context));
  61         if (ctx == NULL)
  62                 return (NULL);
  63
  64         ctx->array_size = 0;
  65         if (array_size_increment == 0)
  66                 ctx->array_size_increment = ARRAY_SIZE_INCREMENT;
  67         else
  68                 ctx->array_size_increment = array_size_increment;
  69         ctx->heap_size = 0;
  70         ctx->heap = NULL;
  71         ctx->higher_priority = higher_priority;
  72         ctx->index = index;
  73         return (ctx);
  74 }
  75
  76 int
  77 heap_free(heap_context ctx) {
  78         if (ctx == NULL) {
  79                 errno = EINVAL;
  80                 return (-1);
  81         }
  82
  83         if (ctx->heap != NULL)
  84                 free(ctx->heap);
  85         free(ctx);
  86
  87         return (0);
  88 }
  89
  90 static int
  91 heap_resize(heap_context ctx) {
  92         void **new_heap;
  93
  94         ctx->array_size += ctx->array_size_increment;
  95         new_heap = (void **)realloc(ctx->heap,
  96                                     (ctx->array_size) * (sizeof (void *)));
  97         if (new_heap == NULL) {
  98                 errno = ENOMEM;
  99                 return (-1);
 100         }
 101         ctx->heap = new_heap;
 102         return (0);
 103 }
 104
 105 static void
 106 float_up(heap_context ctx, int i, void *elt) {
 107         int p;
 108
 109         for ( p = heap_parent(i);
 110               i > 1 && ctx->higher_priority(elt, ctx->heap[p]);
 111               i = p, p = heap_parent(i) ) {
 112                 ctx->heap[i] = ctx->heap[p];
 113                 if (ctx->index != NULL)
 114                         (ctx->index)(ctx->heap[i], i);
 115         }
 116         ctx->heap[i] = elt;
 117         if (ctx->index != NULL)
 118                 (ctx->index)(ctx->heap[i], i);
 119 }
 120
 121 static void
 122 sink_down(heap_context ctx, int i, void *elt) {
 123         int j, size, half_size;
 124
 125         size = ctx->heap_size;
 126         half_size = size / 2;
 127         while (i <= half_size) {
 128                 /* find smallest of the (at most) two children */
 129                 j = heap_left(i);
 130                 if (j < size && ctx->higher_priority(ctx->heap[j+1],
 131                                                      ctx->heap[j]))
 132                         j++;
 133                 if (ctx->higher_priority(elt, ctx->heap[j]))
 134                         break;
 135                 ctx->heap[i] = ctx->heap[j];
 136                 if (ctx->index != NULL)
 137                         (ctx->index)(ctx->heap[i], i);
 138                 i = j;
 139         }
 140         ctx->heap[i] = elt;
 141         if (ctx->index != NULL)
 142                 (ctx->index)(ctx->heap[i], i);
 143 }
 144
 145 int
 146 heap_insert(heap_context ctx, void *elt) {
 147         int i;
 148
 149         if (ctx == NULL || elt == NULL) {
 150                 errno = EINVAL;
 151                 return (-1);
 152         }
 153
 154         i = ++ctx->heap_size;
 155         if (ctx->heap_size >= ctx->array_size && heap_resize(ctx) < 0)
 156                 return (-1);
 157
 158         float_up(ctx, i, elt);
 159
 160         return (0);
 161 }
 162
 163 int
 164 heap_delete(heap_context ctx, int i) {
 165         void *elt;
 166         int less;
 167
 168         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 169                 errno = EINVAL;
 170                 return (-1);
 171         }
 172
 173         if (i == ctx->heap_size) {
 174                 ctx->heap_size--;
 175         } else {
 176                 elt = ctx->heap[ctx->heap_size--];
 177                 less = ctx->higher_priority(elt, ctx->heap[i]);
 178                 ctx->heap[i] = elt;
 179                 if (less)
 180                         float_up(ctx, i, ctx->heap[i]);
 181                 else
 182                         sink_down(ctx, i, ctx->heap[i]);
 183         }
 184
 185         return (0);
 186 }
 187
 188 int
 189 heap_increased(heap_context ctx, int i) {
 190         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 191                 errno = EINVAL;
 192                 return (-1);
 193         }
 194
 195         float_up(ctx, i, ctx->heap[i]);
 196
 197         return (0);
 198 }
 199
 200 int
 201 heap_decreased(heap_context ctx, int i) {
 202         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 203                 errno = EINVAL;
 204                 return (-1);
 205         }
 206
 207         sink_down(ctx, i, ctx->heap[i]);
 208
 209         return (0);
 210 }
 211
 212 void *
 213 heap_element(heap_context ctx, int i) {
 214         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 215                 errno = EINVAL;
 216                 return (NULL);
 217         }
 218
 219         return (ctx->heap[i]);
 220 }
 221
 222 int
 223 heap_for_each(heap_context ctx, heap_for_each_func action, void *uap) {
 224         int i;
 225
 226         if (ctx == NULL || action == NULL) {
 227                 errno = EINVAL;
 228                 return (-1);
 229         }
 230
 231         for (i = 1; i <= ctx->heap_size; i++)
 232                 (action)(ctx->heap[i], uap);
 233         return (0);
 234 }