src/heap.c

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