usr/src/lib/libresolv2/common/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 #include "port_before.h"
  29
  30 #include <stddef.h>
  31 #include <stdlib.h>
  32 #include <errno.h>
  33
  34 #include "port_after.h"
  35
  36 #include <isc/heap.h>
  37
  38 /*%
  39  * Note: to make heap_parent and heap_left easy to compute, the first
  40  * element of the heap array is not used; i.e. heap subscripts are 1-based,
  41  * not 0-based.
  42  */
  43 #define heap_parent(i) ((i) >> 1)
  44 #define heap_left(i) ((i) << 1)
  45
  46 #define ARRAY_SIZE_INCREMENT 512
  47
  48 heap_context
  49 heap_new(heap_higher_priority_func higher_priority, heap_index_func index,
  50          int array_size_increment) {
  51         heap_context ctx;
  52
  53         if (higher_priority == NULL)
  54                 return (NULL);
  55
  56         ctx = (heap_context)malloc(sizeof (struct heap_context));
  57         if (ctx == NULL)
  58                 return (NULL);
  59
  60         ctx->array_size = 0;
  61         if (array_size_increment == 0)
  62                 ctx->array_size_increment = ARRAY_SIZE_INCREMENT;
  63         else
  64                 ctx->array_size_increment = array_size_increment;
  65         ctx->heap_size = 0;
  66         ctx->heap = NULL;
  67         ctx->higher_priority = higher_priority;
  68         ctx->index = index;
  69         return (ctx);
  70 }
  71
  72 int
  73 heap_free(heap_context ctx) {
  74         if (ctx == NULL) {
  75                 errno = EINVAL;
  76                 return (-1);
  77         }
  78
  79         if (ctx->heap != NULL)
  80                 free(ctx->heap);
  81         free(ctx);
  82
  83         return (0);
  84 }
  85
  86 static int
  87 heap_resize(heap_context ctx) {
  88         void **new_heap;
  89
  90         ctx->array_size += ctx->array_size_increment;
  91         new_heap = (void **)realloc(ctx->heap,
  92                                     (ctx->array_size) * (sizeof (void *)));
  93         if (new_heap == NULL) {
  94                 errno = ENOMEM;
  95                 return (-1);
  96         }
  97         ctx->heap = new_heap;
  98         return (0);
  99 }
 100
 101 static void
 102 float_up(heap_context ctx, int i, void *elt) {
 103         int p;
 104
 105         for ( p = heap_parent(i);
 106               i > 1 && ctx->higher_priority(elt, ctx->heap[p]);
 107               i = p, p = heap_parent(i) ) {
 108                 ctx->heap[i] = ctx->heap[p];
 109                 if (ctx->index != NULL)
 110                         (ctx->index)(ctx->heap[i], i);
 111         }
 112         ctx->heap[i] = elt;
 113         if (ctx->index != NULL)
 114                 (ctx->index)(ctx->heap[i], i);
 115 }
 116
 117 static void
 118 sink_down(heap_context ctx, int i, void *elt) {
 119         int j, size, half_size;
 120
 121         size = ctx->heap_size;
 122         half_size = size / 2;
 123         while (i <= half_size) {
 124                 /* find smallest of the (at most) two children */
 125                 j = heap_left(i);
 126                 if (j < size && ctx->higher_priority(ctx->heap[j+1],
 127                                                      ctx->heap[j]))
 128                         j++;
 129                 if (ctx->higher_priority(elt, ctx->heap[j]))
 130                         break;
 131                 ctx->heap[i] = ctx->heap[j];
 132                 if (ctx->index != NULL)
 133                         (ctx->index)(ctx->heap[i], i);
 134                 i = j;
 135         }
 136         ctx->heap[i] = elt;
 137         if (ctx->index != NULL)
 138                 (ctx->index)(ctx->heap[i], i);
 139 }
 140
 141 int
 142 heap_insert(heap_context ctx, void *elt) {
 143         int i;
 144
 145         if (ctx == NULL || elt == NULL) {
 146                 errno = EINVAL;
 147                 return (-1);
 148         }
 149
 150         i = ++ctx->heap_size;
 151         if (ctx->heap_size >= ctx->array_size && heap_resize(ctx) < 0)
 152                 return (-1);
 153
 154         float_up(ctx, i, elt);
 155
 156         return (0);
 157 }
 158
 159 int
 160 heap_delete(heap_context ctx, int i) {
 161         void *elt;
 162         int less;
 163
 164         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 165                 errno = EINVAL;
 166                 return (-1);
 167         }
 168
 169         if (i == ctx->heap_size) {
 170                 ctx->heap_size--;
 171         } else {
 172                 elt = ctx->heap[ctx->heap_size--];
 173                 less = ctx->higher_priority(elt, ctx->heap[i]);
 174                 ctx->heap[i] = elt;
 175                 if (less)
 176                         float_up(ctx, i, ctx->heap[i]);
 177                 else
 178                         sink_down(ctx, i, ctx->heap[i]);
 179         }
 180
 181         return (0);
 182 }
 183
 184 int
 185 heap_increased(heap_context ctx, int i) {
 186         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 187                 errno = EINVAL;
 188                 return (-1);
 189         }
 190
 191         float_up(ctx, i, ctx->heap[i]);
 192
 193         return (0);
 194 }
 195
 196 int
 197 heap_decreased(heap_context ctx, int i) {
 198         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 199                 errno = EINVAL;
 200                 return (-1);
 201         }
 202
 203         sink_down(ctx, i, ctx->heap[i]);
 204
 205         return (0);
 206 }
 207
 208 void *
 209 heap_element(heap_context ctx, int i) {
 210         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 211                 errno = EINVAL;
 212                 return (NULL);
 213         }
 214
 215         return (ctx->heap[i]);
 216 }
 217
 218 int
 219 heap_for_each(heap_context ctx, heap_for_each_func action, void *uap) {
 220         int i;
 221
 222         if (ctx == NULL || action == NULL) {
 223                 errno = EINVAL;
 224                 return (-1);
 225         }
 226
 227         for (i = 1; i <= ctx->heap_size; i++)
 228                 (action)(ctx->heap[i], uap);
 229         return (0);
 230 }
 231
 232 /*! \file */