Increase initial heap size from 32 to 256
[geda-pcb/gde.git] / src / heap.c
blob4959b58c888fed74fc9e20d3b01d5b9dc08b3776
1 /* $Id$ */
3 /*
4 * COPYRIGHT
6 * PCB, interactive printed circuit board design
7 * Copyright (C) 1994,1995,1996 Thomas Nau
8 * Copyright (C) 1998,1999,2000,2001 harry eaton
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.
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.
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.
24 * Contact addresses for paper mail and Email:
25 * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
26 * haceaton@aplcomm.jhuapl.edu
30 /* this file, heap.c, was written and is
31 * Copyright (c) 2001 C. Scott Ananian.
34 /* operations on heaps.
37 #ifdef HAVE_CONFIG_H
38 #include "config.h"
39 #endif
41 #include "global.h"
43 #include <assert.h>
45 #include "heap.h"
47 #ifdef HAVE_LIBDMALLOC
48 #include <dmalloc.h>
49 #endif
51 RCSID ("$Id$");
54 /* define this for more thorough self-checking of data structures */
55 #undef SLOW_ASSERTIONS
57 /* ---------------------------------------------------------------------------
58 * some local prototypes
61 /* ---------------------------------------------------------------------------
62 * some local types
64 struct heap_element
66 cost_t cost;
67 void *data;
69 struct heap_struct
71 struct heap_element *element;
72 int size, max;
75 /* ---------------------------------------------------------------------------
76 * some local identifiers
78 static cost_t MIN_COST = 0;
80 /* ---------------------------------------------------------------------------
81 * functions.
83 /* helper functions for assertions */
84 #ifndef NDEBUG
85 #ifdef SLOW_ASSERTIONS
86 static int
87 __heap_is_good_slow (heap_t * heap)
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;
99 #endif /* SLOW_ASSERTIONS */
100 static int
101 __heap_is_good (heap_t * heap)
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
111 #endif /* ! NDEBUG */
113 /* create an empty heap */
114 heap_t *
115 heap_create ()
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;
129 /* destroy a heap */
130 void
131 heap_destroy (heap_t ** heap)
133 assert (heap && *heap);
134 assert (__heap_is_good (*heap));
135 if ((*heap)->element)
136 free ((*heap)->element);
137 free (*heap);
138 *heap = NULL;
141 /* -- mutation -- */
142 static void
143 __upheap (heap_t * heap, int k)
145 struct heap_element v;
147 assert (heap && heap->size < heap->max);
148 assert (k <= heap->size);
150 v = heap->element[k];
151 heap->element[0].cost = MIN_COST;
152 for (v = heap->element[k]; heap->element[k / 2].cost > v.cost; k = k / 2)
153 heap->element[k] = heap->element[k / 2];
154 heap->element[k] = v;
157 void
158 heap_insert (heap_t * heap, cost_t cost, void *data)
160 assert (heap && __heap_is_good (heap));
161 assert (cost >= MIN_COST);
163 /* determine whether we need to grow the heap */
164 if (heap->size + 1 >= heap->max)
166 heap->max *= 2;
167 if (heap->max == 0)
168 heap->max = 256; /* default initial heap size */
169 heap->element =
170 realloc (heap->element, heap->max * sizeof (*heap->element));
172 heap->size++;
173 assert (heap->size < heap->max);
174 heap->element[heap->size].cost = cost;
175 heap->element[heap->size].data = data;
176 __upheap (heap, heap->size); /* fix heap condition violation */
177 assert (__heap_is_good (heap));
178 return;
181 /* this procedure moves down the heap, exchanging the node at position
182 * k with the smaller of its two children as necessary and stopping when
183 * the node at k is smaller than both children or the bottom is reached.
185 static void
186 __downheap (heap_t * heap, int k)
188 struct heap_element v;
190 assert (heap && heap->size < heap->max);
191 assert (k <= heap->size);
193 v = heap->element[k];
194 while (k <= heap->size / 2)
196 int j = k + k;
197 if (j < heap->size && heap->element[j].cost > heap->element[j + 1].cost)
198 j++;
199 if (v.cost < heap->element[j].cost)
200 break;
201 heap->element[k] = heap->element[j];
202 k = j;
204 heap->element[k] = v;
207 void *
208 heap_remove_smallest (heap_t * heap)
210 struct heap_element v;
211 assert (heap && __heap_is_good (heap));
212 assert (heap->size > 0);
213 assert (heap->max > 1);
215 v = heap->element[1];
216 heap->element[1] = heap->element[heap->size--];
217 if (heap->size > 0)
218 __downheap (heap, 1);
220 assert (__heap_is_good (heap));
221 return v.data;
224 void *
225 heap_replace (heap_t * heap, cost_t cost, void *data)
227 assert (heap && __heap_is_good (heap));
229 if (heap_is_empty (heap))
230 return data;
232 assert (heap->size > 0);
233 assert (heap->max > 1);
235 heap->element[0].cost = cost;
236 heap->element[0].data = data;
237 __downheap (heap, 0); /* ooh, tricky! */
239 assert (__heap_is_good (heap));
240 return heap->element[0].data;
243 /* -- interrogation -- */
245 heap_is_empty (heap_t * heap)
247 assert (__heap_is_good (heap));
248 return heap->size == 0;