src/heap.c

   1 /* $Id$ */
   2
   3 /*
   4  *                            COPYRIGHT
   5  *
   6  *  PCB, interactive printed circuit board design
   7  *  Copyright (C) 1994,1995,1996 Thomas Nau
   8  *  Copyright (C) 1998,1999,2000,2001 harry eaton
   9  *
  10  *  This program is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License as published by
  12  *  the Free Software Foundation; either version 2 of the License, or
  13  *  (at your option) any later version.
  14  *
  15  *  This program is distributed in the hope that it will be useful,
  16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  *  GNU General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License
  21  *  along with this program; if not, write to the Free Software
  22  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  23  *
  24  *  Contact addresses for paper mail and Email:
  25  *  harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
  26  *  haceaton@aplcomm.jhuapl.edu
  27  *
  28  */
  29
  30 /* this file, heap.c, was written and is
  31  * Copyright (c) 2001 C. Scott Ananian.
  32  */
  33
  34 /* operations on heaps.
  35  */
  36
  37 #ifdef HAVE_CONFIG_H
  38 #include "config.h"
  39 #endif
  40
  41 #include "global.h"
  42
  43 #include <assert.h>
  44
  45 #include "heap.h"
  46
  47 #ifdef HAVE_LIBDMALLOC
  48 #include <dmalloc.h>
  49 #endif
  50
  51 RCSID ("$Id$");
  52
  53
  54 /* define this for more thorough self-checking of data structures */
  55 #undef SLOW_ASSERTIONS
  56
  57 /* ---------------------------------------------------------------------------
  58  * some local prototypes
  59  */
  60
  61 /* ---------------------------------------------------------------------------
  62  * some local types
  63  */
  64 struct heap_element
  65 {
  66   cost_t cost;
  67   void *data;
  68 };
  69 struct heap_struct
  70 {
  71   struct heap_element *element;
  72   int size, max;
  73 };
  74
  75 /* ---------------------------------------------------------------------------
  76  * some local identifiers
  77  */
  78 static cost_t MIN_COST = 0;
  79
  80 /* ---------------------------------------------------------------------------
  81  * functions.
  82  */
  83 /* helper functions for assertions */
  84 #ifndef NDEBUG
  85 #ifdef SLOW_ASSERTIONS
  86 static int
  87 __heap_is_good_slow (heap_t * heap)
  88 {
  89   int i;
  90   /* heap condition: key in each node should be smaller than in its children */
  91   /* alternatively (and this is what we check): key in each node should be
  92    * larger than (or equal to) key of its parent. */
  93   /* note that array element[0] is not used (except as a sentinel) */
  94   for (i = 2; i < heap->size; i++)
  95     if (heap->element[i].cost < heap->element[i / 2].cost)
  96       return 0;
  97   return 1;
  98 }
  99 #endif /* SLOW_ASSERTIONS */
 100 static int
 101 __heap_is_good (heap_t * heap)
 102 {
 103   return heap && (heap->max == 0 || heap->element) &&
 104     (heap->max >= 0) && (heap->size >= 0) &&
 105     (heap->max == 0 || heap->size < heap->max) &&
 106 #ifdef SLOW_ASSERTIONS
 107     __heap_is_good_slow (heap) &&
 108 #endif
 109     1;
 110 }
 111 #endif /* ! NDEBUG */
 112
 113 /* create an empty heap */
 114 heap_t *
 115 heap_create ()
 116 {
 117   heap_t *heap;
 118   /* initialize MIN_COST if necessary */
 119   if (MIN_COST == 0)
 120     MIN_COST = -1e23;
 121   assert (MIN_COST < 0);
 122   /* okay, create empty heap */
 123   heap = calloc (1, sizeof (*heap));
 124   assert (heap);
 125   assert (__heap_is_good (heap));
 126   return heap;
 127 }
 128
 129 /* destroy a heap */
 130 void
 131 heap_destroy (heap_t ** heap)
 132 {
 133   assert (heap && *heap);
 134   assert (__heap_is_good (*heap));
 135   if ((*heap)->element)
 136     free ((*heap)->element);
 137   free (*heap);
 138   *heap = NULL;
 139 }
 140
 141 /* free all elements in the heap */
 142 void heap_free (heap_t *heap, void (*freefunc) (void *))
 143 {
 144   assert (heap);
 145   assert (__heap_is_good (heap));
 146   for ( ; heap->size; heap->size--)
 147    {
 148      if (heap->element[heap->size].data)
 149        freefunc (heap->element[heap->size].data);
 150    }
 151 }
 152
 153 /* -- mutation -- */
 154 static void
 155 __upheap (heap_t * heap, int k)
 156 {
 157   struct heap_element v;
 158
 159   assert (heap && heap->size < heap->max);
 160   assert (k <= heap->size);
 161
 162   v = heap->element[k];
 163   heap->element[0].cost = MIN_COST;
 164   for (v = heap->element[k]; heap->element[k / 2].cost > v.cost; k = k / 2)
 165     heap->element[k] = heap->element[k / 2];
 166   heap->element[k] = v;
 167 }
 168
 169 void
 170 heap_insert (heap_t * heap, cost_t cost, void *data)
 171 {
 172   assert (heap && __heap_is_good (heap));
 173   assert (cost >= MIN_COST);
 174
 175   /* determine whether we need to grow the heap */
 176   if (heap->size + 1 >= heap->max)
 177     {
 178       heap->max *= 2;
 179       if (heap->max == 0)
 180         heap->max = 256;                /* default initial heap size */
 181       heap->element =
 182         realloc (heap->element, heap->max * sizeof (*heap->element));
 183     }
 184   heap->size++;
 185   assert (heap->size < heap->max);
 186   heap->element[heap->size].cost = cost;
 187   heap->element[heap->size].data = data;
 188   __upheap (heap, heap->size);  /* fix heap condition violation */
 189   assert (__heap_is_good (heap));
 190   return;
 191 }
 192
 193 /* this procedure moves down the heap, exchanging the node at position
 194  * k with the smaller of its two children as necessary and stopping when
 195  * the node at k is smaller than both children or the bottom is reached.
 196  */
 197 static void
 198 __downheap (heap_t * heap, int k)
 199 {
 200   struct heap_element v;
 201
 202   assert (heap && heap->size < heap->max);
 203   assert (k <= heap->size);
 204
 205   v = heap->element[k];
 206   while (k <= heap->size / 2)
 207     {
 208       int j = k + k;
 209       if (j < heap->size && heap->element[j].cost > heap->element[j + 1].cost)
 210         j++;
 211       if (v.cost < heap->element[j].cost)
 212         break;
 213       heap->element[k] = heap->element[j];
 214       k = j;
 215     }
 216   heap->element[k] = v;
 217 }
 218
 219 void *
 220 heap_remove_smallest (heap_t * heap)
 221 {
 222   struct heap_element v;
 223   assert (heap && __heap_is_good (heap));
 224   assert (heap->size > 0);
 225   assert (heap->max > 1);
 226
 227   v = heap->element[1];
 228   heap->element[1] = heap->element[heap->size--];
 229   if (heap->size > 0)
 230     __downheap (heap, 1);
 231
 232   assert (__heap_is_good (heap));
 233   return v.data;
 234 }
 235
 236 void *
 237 heap_replace (heap_t * heap, cost_t cost, void *data)
 238 {
 239   assert (heap && __heap_is_good (heap));
 240
 241   if (heap_is_empty (heap))
 242     return data;
 243
 244   assert (heap->size > 0);
 245   assert (heap->max > 1);
 246
 247   heap->element[0].cost = cost;
 248   heap->element[0].data = data;
 249   __downheap (heap, 0);         /* ooh, tricky! */
 250
 251   assert (__heap_is_good (heap));
 252   return heap->element[0].data;
 253 }
 254
 255 /* -- interrogation -- */
 256 int
 257 heap_is_empty (heap_t * heap)
 258 {
 259   assert (__heap_is_good (heap));
 260   return heap->size == 0;
 261 }
 262
 263 /* -- size -- */
 264 int
 265 heap_size (heap_t * heap)
 266 {
 267   assert (__heap_is_good (heap));
 268   return heap->size;
 269 }
 270