1 /******************************************************************************
2 ** Filename: heap.c
3 ** Purpose: Routines for managing heaps (smallest at root)
4 ** Author: Dan Johnson
5 ** History: 3/13/89, DSJ, Created.
6 **
7 ** (c) Copyright Hewlett-Packard Company, 1988.
8 ** Licensed under the Apache License, Version 2.0 (the "License");
9 ** you may not use this file except in compliance with the License.
10 ** You may obtain a copy of the License at
11 ** http://www.apache.org/licenses/LICENSE-2.0
12 ** Unless required by applicable law or agreed to in writing, software
13 ** distributed under the License is distributed on an "AS IS" BASIS,
14 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 ** See the License for the specific language governing permissions and
16 ** limitations under the License.
17 ******************************************************************************/
18 /**----------------------------------------------------------------------------
19 Include Files and Type Defines
20 ----------------------------------------------------------------------------**/
21 #include "oldheap.h"
22 #include "freelist.h"
23 #include "danerror.h"
24 #include "emalloc.h"
25 #include <stdio.h>
26
27 #define FATHER(N) ((N)>>1)
28 #define LEFTSON(N) ((N)<<1)
29 #define RIGHTSON(N) ((N)<<1 + 1)
30
31 /**----------------------------------------------------------------------------
32 Public Code
33 ----------------------------------------------------------------------------**/
34 /*---------------------------------------------------------------------------*/
MakeHeap(int Size)35 HEAP *MakeHeap(int Size) {
36 /*
37 ** Parameters:
38 ** Size maximum number of entries in the heap
39 ** Globals:
40 ** None
41 ** Operation:
42 ** This routine creates and initializes a new heap data
43 ** structure containing Size elements. In actuality, Size + 1
44 ** elements are allocated. The first element, element 0, is
45 ** unused, this makes the index arithmetic easier.
46 ** Return:
47 ** Pointer to the new heap.
48 ** Exceptions:
49 ** None
50 ** History:
51 ** 3/13/89, DSJ, Created.
52 */
53 HEAP *NewHeap;
54
55 NewHeap = (HEAP *) Emalloc (sizeof (HEAP) + Size * sizeof (HEAPENTRY));
56
57 NewHeap->Size = Size;
58 NewHeap->FirstFree = 1;
59 return (NewHeap);
60 } /* MakeHeap */
61
62
63 /*---------------------------------------------------------------------------*/
HeapPop(HEAP * Heap,FLOAT32 * Key,void * out_ptr)64 int HeapPop(HEAP *Heap, FLOAT32 *Key, void *out_ptr) {
65 /*
66 ** Parameters:
67 ** Heap ptr to heap whose top is to be removed and returned
68 ** Key place to put key of top heap item
69 ** Data place to put data of top heap item
70 ** Globals:
71 ** None
72 ** Operation:
73 ** This routine removes the top item on the heap and places
74 ** its contents into Key and Data.
75 ** Return:
76 ** OK if top entry returned, EMPTY if heap is empty
77 ** Exceptions:
78 ** None
79 ** History:
80 ** 5/10/91, DSJ, Created (Modified from GetTopOfHeap).
81 */
82 inT32 Hole;
83 FLOAT32 HoleKey;
84 inT32 Son;
85 void **Data = (void **) out_ptr;
86
87 if (Heap->FirstFree <= 1)
88 return (EMPTY);
89
90 *Key = Heap->Entry[1].Key;
91 *Data = Heap->Entry[1].Data;
92
93 Heap->FirstFree--;
94
95 /* imagine the hole at the root is filled with the last entry in the heap */
96 HoleKey = Heap->Entry[Heap->FirstFree].Key;
97 Hole = 1;
98
99 /* while hole has 2 sons */
100 while ((Son = LEFTSON (Hole)) < Heap->FirstFree) {
101 /* find the son with the smallest key */
102 if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key)
103 Son++;
104
105 /* if key for hole is greater than key for son, sift hole down */
106 if (HoleKey > Heap->Entry[Son].Key) {
107 Heap->Entry[Hole].Key = Heap->Entry[Son].Key;
108 Heap->Entry[Hole].Data = Heap->Entry[Son].Data;
109 Hole = Son;
110 }
111 else
112 break;
113 }
114 Heap->Entry[Hole].Key = HoleKey;
115 Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data;
116 return (OK);
117 } /* HeapPop */
118
119
120 /**********************************************************************
121 * HeapPopWorst
122 *
123 * Remove the largest item from the heap.
124 **********************************************************************/
HeapPopWorst(HEAP * Heap,FLOAT32 * Key,void * out_ptr)125 int HeapPopWorst(HEAP *Heap, FLOAT32 *Key, void *out_ptr) {
126 /*
127 ** Parameters:
128 ** Heap ptr to heap whose top is to be removed and returned
129 ** Key place to put key of top heap item
130 ** Data place to put data of top heap item
131 */
132 inT32 Index; /*current index */
133 inT32 Hole;
134 FLOAT32 HoleKey;
135 inT32 Father;
136 void *HoleData;
137 void **Data = (void **) out_ptr;
138
139 if (Heap->FirstFree <= 1)
140 return (EMPTY);
141
142 HoleKey = Heap->Entry[1].Key;
143 Hole = 1;
144 Heap->FirstFree--;
145 for (Index = Heap->FirstFree, Father = FATHER (Index); Index > Father;
146 Index--)
147 if (Heap->Entry[Index].Key > HoleKey) {
148 /*find biggest */
149 HoleKey = Heap->Entry[Index].Key;
150 Hole = Index;
151 }
152 *Key = HoleKey;
153 *Data = Heap->Entry[Hole].Data;
154
155 HoleKey = Heap->Entry[Heap->FirstFree].Key;
156 Heap->Entry[Hole].Key = HoleKey;
157 HoleData = Heap->Entry[Heap->FirstFree].Data;
158 Heap->Entry[Hole].Data = HoleData;
159
160 /* now sift last entry to its rightful place */
161 Father = FATHER (Hole); /*father of hole */
162 while (Hole > 1 && Heap->Entry[Father].Key > HoleKey) {
163 /*swap entries */
164 Heap->Entry[Hole].Key = Heap->Entry[Father].Key;
165 Heap->Entry[Hole].Data = Heap->Entry[Father].Data;
166 Heap->Entry[Father].Data = HoleData;
167 Heap->Entry[Father].Key = HoleKey;
168 Hole = Father;
169 Father = FATHER (Hole);
170 }
171 return (OK);
172 } /* HeapPop */
173
174
175 /*---------------------------------------------------------------------------*/
HeapPush(HEAP * Heap,FLOAT32 Key,void * Data)176 void HeapPush(HEAP *Heap, FLOAT32 Key, void *Data) {
177 /*
178 ** Parameters:
179 ** Heap ptr to heap to store new item in
180 ** Key numeric key associated with new item
181 ** Data ptr to data contents of new item
182 ** Globals:
183 ** None
184 ** Operation:
185 ** This routine stores Data into Heap and associates it
186 ** with Key. The heap is
187 ** maintained in such a way that the item with the lowest key
188 ** is always at the top of the heap.
189 ** Return:
190 ** None
191 ** Exceptions:
192 ** HEAPFULL error if heap size is exceeded
193 ** History:
194 ** 5/10/91, DSJ, Created (Modified version of HeapStore).
195 */
196 inT32 Item;
197 inT32 Father;
198
199 if (Heap->FirstFree > Heap->Size)
200 DoError (HEAPFULL, "Heap size exceeded");
201
202 Item = Heap->FirstFree;
203 Heap->FirstFree++;
204 while (Item != 1) {
205 Father = FATHER (Item);
206 if (Heap->Entry[Father].Key > Key) {
207 Heap->Entry[Item].Key = Heap->Entry[Father].Key;
208 Heap->Entry[Item].Data = Heap->Entry[Father].Data;
209 Item = Father;
210 }
211 else
212 break;
213 }
214 Heap->Entry[Item].Key = Key;
215 Heap->Entry[Item].Data = Data;
216 } /* HeapPush */
217
218
219 /*---------------------------------------------------------------------------*/
HeapStore(HEAP * Heap,HEAPENTRY * Entry)220 void HeapStore(HEAP *Heap, HEAPENTRY *Entry) {
221 /*
222 ** Parameters:
223 ** Heap ptr to heap to store new item in
224 ** Entry ptr to item to be stored in Heap
225 ** Globals:
226 ** None
227 ** Operation:
228 ** This routine stores Entry into Heap. The heap is
229 ** maintained in such a way that the item with the lowest key
230 ** is always at the top of the heap.
231 ** Return:
232 ** None
233 ** Exceptions:
234 ** HEAPFULL error if heap size is exceeded
235 ** History:
236 ** 3/13/89, DSJ, Created.
237 */
238 inT32 Item;
239 inT32 Father;
240
241 if (Heap->FirstFree > Heap->Size)
242 DoError (HEAPFULL, "Heap size exceeded");
243
244 Item = Heap->FirstFree;
245 Heap->FirstFree++;
246 while (Item != 1) {
247 Father = FATHER (Item);
248 if (Heap->Entry[Father].Key > Entry->Key) {
249 Heap->Entry[Item].Key = Heap->Entry[Father].Key;
250 Heap->Entry[Item].Data = Heap->Entry[Father].Data;
251 Item = Father;
252 }
253 else
254 break;
255 }
256 Heap->Entry[Item].Key = Entry->Key;
257 Heap->Entry[Item].Data = Entry->Data;
258 } /* HeapStore */
259
260
261 /*---------------------------------------------------------------------------*/
GetTopOfHeap(HEAP * Heap,HEAPENTRY * Entry)262 int GetTopOfHeap(HEAP *Heap, HEAPENTRY *Entry) {
263 /*
264 ** Parameters:
265 ** Heap ptr to heap whose top is to be removed and returned
266 ** Entry ptr to heap entry to be filled with top entry on Heap
267 ** Globals:
268 ** None
269 ** Operation:
270 ** This routine removes the top item on the heap and copies its
271 ** contents into Entry.
272 ** Return:
273 ** OK if top entry returned, EMPTY if heap is empty
274 ** Exceptions:
275 ** None
276 ** History:
277 ** 3/13/89, DSJ, Created.
278 */
279 inT32 Hole;
280 FLOAT32 HoleKey;
281 inT32 Son;
282
283 if (Heap->FirstFree <= 1)
284 return (EMPTY);
285
286 Entry->Key = Heap->Entry[1].Key;
287 Entry->Data = Heap->Entry[1].Data;
288
289 Heap->FirstFree--;
290
291 /* imagine the hole at the root is filled with the last entry in the heap */
292 HoleKey = Heap->Entry[Heap->FirstFree].Key;
293 Hole = 1;
294
295 /* while hole has 2 sons */
296 while ((Son = LEFTSON (Hole)) < Heap->FirstFree) {
297 /* find the son with the smallest key */
298 if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key)
299 Son++;
300
301 /* if key for hole is greater than key for son, sift hole down */
302 if (HoleKey > Heap->Entry[Son].Key) {
303 Heap->Entry[Hole].Key = Heap->Entry[Son].Key;
304 Heap->Entry[Hole].Data = Heap->Entry[Son].Data;
305 Hole = Son;
306 }
307 else
308 break;
309 }
310 Heap->Entry[Hole].Key = HoleKey;
311 Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data;
312 return (OK);
313 } /* GetTopOfHeap */
314
315
316 /*---------------------------------------------------------------------------*/
FreeHeapData(HEAP * Heap,void_dest destructor)317 void FreeHeapData(HEAP *Heap, void_dest destructor) {
318 /*
319 ** Parameters:
320 ** Heap heap whose data is to be freed
321 ** Deallocator function to be used to deallocate data
322 ** Globals: none
323 ** Operation: This routine is similar to FreeHeap in that it
324 ** deallocates the memory consumed by the heap. However, it
325 ** also calls Deallocator for each item in the heap so that
326 ** this data is also deallocated.
327 ** Return: none
328 ** Exceptions: none
329 ** History: Tue May 15 08:52:04 1990, DSJ, Created.
330 */
331 HEAPENTRY Entry;
332
333 while (GetTopOfHeap (Heap, &Entry) != EMPTY)
334 destructor (Entry.Data);
335
336 FreeHeap(Heap);
337 } /* FreeHeapData */
338