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 #if !defined(LINT) && !defined(CODECENTER)
  29 static const char rcsid[] = "$Id: heap.c,v 1.4 2006/03/09 23:57:56 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         free(ctx->heap);
  84         free(ctx);
  85
  86         return (0);
  87 }
  88
  89 static int
  90 heap_resize(heap_context ctx) {
  91         void **new_heap;
  92
  93         ctx->array_size += ctx->array_size_increment;
  94         new_heap = (void **)reallocarray(ctx->heap, ctx->array_size,
  95             sizeof (void *));
  96         if (new_heap == NULL) {
  97                 errno = ENOMEM;
  98                 return (-1);
  99         }
 100         ctx->heap = new_heap;
 101         return (0);
 102 }
 103
 104 static void
 105 float_up(heap_context ctx, int i, void *elt) {
 106         int p;
 107
 108         for ( p = heap_parent(i);
 109               i > 1 && ctx->higher_priority(elt, ctx->heap[p]);
 110               i = p, p = heap_parent(i) ) {
 111                 ctx->heap[i] = ctx->heap[p];
 112                 if (ctx->index != NULL)
 113                         (ctx->index)(ctx->heap[i], i);
 114         }
 115         ctx->heap[i] = elt;
 116         if (ctx->index != NULL)
 117                 (ctx->index)(ctx->heap[i], i);
 118 }
 119
 120 static void
 121 sink_down(heap_context ctx, int i, void *elt) {
 122         int j, size, half_size;
 123
 124         size = ctx->heap_size;
 125         half_size = size / 2;
 126         while (i <= half_size) {
 127                 /* find smallest of the (at most) two children */
 128                 j = heap_left(i);
 129                 if (j < size && ctx->higher_priority(ctx->heap[j+1],
 130                                                      ctx->heap[j]))
 131                         j++;
 132                 if (ctx->higher_priority(elt, ctx->heap[j]))
 133                         break;
 134                 ctx->heap[i] = ctx->heap[j];
 135                 if (ctx->index != NULL)
 136                         (ctx->index)(ctx->heap[i], i);
 137                 i = j;
 138         }
 139         ctx->heap[i] = elt;
 140         if (ctx->index != NULL)
 141                 (ctx->index)(ctx->heap[i], i);
 142 }
 143
 144 int
 145 heap_insert(heap_context ctx, void *elt) {
 146         int i;
 147
 148         if (ctx == NULL || elt == NULL) {
 149                 errno = EINVAL;
 150                 return (-1);
 151         }
 152
 153         i = ++ctx->heap_size;
 154         if (ctx->heap_size >= ctx->array_size && heap_resize(ctx) < 0)
 155                 return (-1);
 156
 157         float_up(ctx, i, elt);
 158
 159         return (0);
 160 }
 161
 162 int
 163 heap_delete(heap_context ctx, int i) {
 164         void *elt;
 165         int less;
 166
 167         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 168                 errno = EINVAL;
 169                 return (-1);
 170         }
 171
 172         if (i == ctx->heap_size) {
 173                 ctx->heap_size--;
 174         } else {
 175                 elt = ctx->heap[ctx->heap_size--];
 176                 less = ctx->higher_priority(elt, ctx->heap[i]);
 177                 ctx->heap[i] = elt;
 178                 if (less)
 179                         float_up(ctx, i, ctx->heap[i]);
 180                 else
 181                         sink_down(ctx, i, ctx->heap[i]);
 182         }
 183
 184         return (0);
 185 }
 186
 187 int
 188 heap_increased(heap_context ctx, int i) {
 189         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 190                 errno = EINVAL;
 191                 return (-1);
 192         }
 193
 194         float_up(ctx, i, ctx->heap[i]);
 195
 196         return (0);
 197 }
 198
 199 int
 200 heap_decreased(heap_context ctx, int i) {
 201         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 202                 errno = EINVAL;
 203                 return (-1);
 204         }
 205
 206         sink_down(ctx, i, ctx->heap[i]);
 207
 208         return (0);
 209 }
 210
 211 void *
 212 heap_element(heap_context ctx, int i) {
 213         if (ctx == NULL || i < 1 || i > ctx->heap_size) {
 214                 errno = EINVAL;
 215                 return (NULL);
 216         }
 217
 218         return (ctx->heap[i]);
 219 }
 220
 221 int
 222 heap_for_each(heap_context ctx, heap_for_each_func action, void *uap) {
 223         int i;
 224
 225         if (ctx == NULL || action == NULL) {
 226                 errno = EINVAL;
 227                 return (-1);
 228         }
 229
 230         for (i = 1; i <= ctx->heap_size; i++)
 231                 (action)(ctx->heap[i], uap);
 232         return (0);
 233 }
 234
 235 /*! \file */