1 /****************************************************************************** 2 ** Filename: heap.h 3 ** Purpose: Definition of heap access routines. 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 #ifndef HEAP_H 19 #define HEAP_H 20 21 /**---------------------------------------------------------------------------- 22 Include Files and Type Defines 23 ----------------------------------------------------------------------------**/ 24 #include "general.h" 25 #include "cutil.h" 26 27 #define HEAPFULL 3000 28 29 #define OK 0 30 #define EMPTY -1 31 32 typedef struct 33 { 34 FLOAT32 Key; 35 void *Data; 36 } 37 38 39 HEAPENTRY; 40 41 typedef struct 42 { 43 inT32 Size; 44 inT32 FirstFree; 45 HEAPENTRY Entry[1]; 46 } 47 48 49 HEAP; 50 51 /**---------------------------------------------------------------------------- 52 Macros 53 ----------------------------------------------------------------------------**/ 54 #define FreeHeap(H) memfree(H) 55 #define MaxSizeOfHeap(H) (H->Size) 56 #define SizeOfHeap(H) (H->FirstFree - 1) 57 #define InitHeap(H) (H->FirstFree = 1) 58 #define HeapFull(H) ((H)->FirstFree > (H)->Size) 59 #define HeapEmpty(H) ((H)->FirstFree <= 1) 60 61 /* macros for accessing elements in heap by index. The indicies vary from 62 0 to SizeOfHeap-1. No bounds checking is done. Elements accessed in 63 this manner are in random order relative to the Key values. These 64 macros should never be used as the LHS of an assignment statement as this 65 will corrupt the heap.*/ 66 #define HeapKeyFor(H,E) ((H)->Entry[(E)+1].Key) 67 #define HeapDataFor(H,E) ((H)->Entry[(E)+1].Data) 68 69 /**---------------------------------------------------------------------------- 70 Public Function Prototypes 71 ----------------------------------------------------------------------------**/ 72 HEAP *MakeHeap(int Size); 73 74 int HeapPop(HEAP *Heap, FLOAT32 *Key, void *out_ptr); 75 76 int HeapPopWorst(HEAP *Heap, FLOAT32 *Key, void *out_ptr); 77 78 void HeapPush(HEAP *Heap, FLOAT32 Key, void *Data); 79 80 void HeapStore(HEAP *Heap, HEAPENTRY *Entry); 81 82 int GetTopOfHeap(HEAP *Heap, HEAPENTRY *Entry); 83 84 void FreeHeapData(HEAP *Heap, void_dest destructor); 85 86 /* 87 #if defined(__STDC__) || defined(__cplusplus) 88 # define _ARGS(s) s 89 #else 90 # define _ARGS(s) () 91 #endif*/ 92 93 /* heap.c 94 HEAP *MakeHeap 95 _ARGS((int Size)); 96 97 int HeapPop 98 _ARGS((HEAP *Heap, 99 FLOAT32 *Key, 100 char **Data)); 101 102 int HeapPopWorst 103 _ARGS((HEAP *Heap, 104 FLOAT32 *Key, 105 char **Data)); 106 107 void HeapPush 108 _ARGS((HEAP *Heap, 109 FLOAT32 Key, 110 char *Data)); 111 112 void HeapStore 113 _ARGS((HEAP *Heap, 114 HEAPENTRY *Entry)); 115 116 int GetTopOfHeap 117 _ARGS((HEAP *Heap, 118 HEAPENTRY *Entry)); 119 120 void FreeHeapData 121 _ARGS((HEAP *Heap, 122 void (*Deallocator )())); 123 124 #undef _ARGS 125 */ 126 #endif 127