|
1 /* $Id$ */ |
|
2 |
|
3 #ifndef QUEUE_H |
|
4 #define QUEUE_H |
|
5 |
|
6 //#define NOFREE |
|
7 //#define QUEUE_DEBUG |
|
8 //#define HASH_DEBUG |
|
9 //#define HASH_STATS |
|
10 |
|
11 |
|
12 typedef struct Queue Queue; |
|
13 typedef bool Queue_PushProc(Queue* q, void* item, int priority); |
|
14 typedef void* Queue_PopProc(Queue* q); |
|
15 typedef bool Queue_DeleteProc(Queue* q, void* item, int priority); |
|
16 typedef void Queue_ClearProc(Queue* q, bool free_values); |
|
17 typedef void Queue_FreeProc(Queue* q, bool free_values); |
|
18 |
|
19 typedef struct InsSortNode InsSortNode; |
|
20 struct InsSortNode { |
|
21 void* item; |
|
22 int priority; |
|
23 InsSortNode* next; |
|
24 }; |
|
25 |
|
26 typedef struct BinaryHeapNode BinaryHeapNode; |
|
27 struct BinaryHeapNode { |
|
28 void* item; |
|
29 int priority; |
|
30 }; |
|
31 |
|
32 |
|
33 struct Queue{ |
|
34 /* |
|
35 * Pushes an element into the queue, at the appropriate place for the queue. |
|
36 * Requires the queue pointer to be of an appropriate type, of course. |
|
37 */ |
|
38 Queue_PushProc* push; |
|
39 /* |
|
40 * Pops the first element from the queue. What exactly is the first element, |
|
41 * is defined by the exact type of queue. |
|
42 */ |
|
43 Queue_PopProc* pop; |
|
44 /* |
|
45 * Deletes the item from the queue. priority should be specified if |
|
46 * known, which speeds up the deleting for some queue's. Should be -1 |
|
47 * if not known. |
|
48 */ |
|
49 Queue_DeleteProc* del; |
|
50 |
|
51 /* Clears the queue, by removing all values from it. It's state is |
|
52 * effectively reset. If free_items is true, each of the items cleared |
|
53 * in this way are free()'d. |
|
54 */ |
|
55 Queue_ClearProc* clear; |
|
56 /* Frees the queue, by reclaiming all memory allocated by it. After |
|
57 * this it is no longer usable. If free_items is true, any remaining |
|
58 * items are free()'d too. |
|
59 */ |
|
60 Queue_FreeProc* free; |
|
61 |
|
62 union { |
|
63 struct { |
|
64 uint max_size; |
|
65 uint size; |
|
66 void** elements; |
|
67 } stack; |
|
68 struct { |
|
69 uint max_size; |
|
70 uint head; /* The index where the last element should be inserted */ |
|
71 uint tail; /* The index where the next element should be read */ |
|
72 void** elements; |
|
73 } fifo; |
|
74 struct { |
|
75 InsSortNode* first; |
|
76 } inssort; |
|
77 struct { |
|
78 uint max_size; |
|
79 uint size; |
|
80 uint blocks; /* The amount of blocks for which space is reserved in elements */ |
|
81 BinaryHeapNode** elements; |
|
82 } binaryheap; |
|
83 } data; |
|
84 |
|
85 /* If true, this struct will be free'd when the |
|
86 * Queue is deleted. */ |
|
87 bool freeq; |
|
88 }; |
|
89 |
|
90 /* Initializes a stack and allocates internal memory. */ |
|
91 void init_Stack(Queue* q, uint max_size); |
|
92 |
|
93 /* Allocate a new stack with a maximum of max_size elements. */ |
|
94 Queue* new_Stack(uint max_size); |
|
95 |
|
96 /* |
|
97 * Fifo |
|
98 */ |
|
99 |
|
100 /* Initializes a fifo and allocates internal memory for maximum of max_size |
|
101 * elements */ |
|
102 void init_Fifo(Queue* q, uint max_size); |
|
103 |
|
104 /* Allocate a new fifo and initializes it with a maximum of max_size elements. */ |
|
105 Queue* new_Fifo(uint max_size); |
|
106 |
|
107 Queue* new_Fifo_in_buffer(uint max_size, void* buffer); |
|
108 |
|
109 int build_Fifo(void* buffer, uint size); |
|
110 |
|
111 /* |
|
112 * Insertion Sorter |
|
113 */ |
|
114 |
|
115 /* Initializes a inssort and allocates internal memory. There is no maximum |
|
116 * size */ |
|
117 void init_InsSort(Queue* q); |
|
118 |
|
119 /* Allocate a new fifo and initializes it. There is no maximum size */ |
|
120 Queue* new_InsSort(void); |
|
121 |
|
122 /* |
|
123 * Binary Heap |
|
124 * For information, see: |
|
125 * http://www.policyalmanac.org/games/binaryHeaps.htm |
|
126 */ |
|
127 |
|
128 /* The amount of elements that will be malloc'd at a time */ |
|
129 #define BINARY_HEAP_BLOCKSIZE_BITS 10 |
|
130 |
|
131 /* Initializes a binary heap and allocates internal memory for maximum of |
|
132 * max_size elements */ |
|
133 void init_BinaryHeap(Queue* q, uint max_size); |
|
134 |
|
135 /* Allocate a new binary heap and initializes it with a maximum of max_size |
|
136 * elements. */ |
|
137 Queue* new_BinaryHeap(uint max_size); |
|
138 |
|
139 /* |
|
140 * Hash |
|
141 */ |
|
142 typedef struct HashNode HashNode; |
|
143 struct HashNode { |
|
144 uint key1; |
|
145 uint key2; |
|
146 void* value; |
|
147 HashNode* next; |
|
148 }; |
|
149 /** |
|
150 * Generates a hash code from the given key pair. You should make sure that |
|
151 * the resulting range is clearly defined. |
|
152 */ |
|
153 typedef uint Hash_HashProc(uint key1, uint key2); |
|
154 typedef struct Hash { |
|
155 /* The hash function used */ |
|
156 Hash_HashProc* hash; |
|
157 /* The amount of items in the hash */ |
|
158 uint size; |
|
159 /* The number of buckets allocated */ |
|
160 uint num_buckets; |
|
161 /* A pointer to an array of num_buckets buckets. */ |
|
162 HashNode* buckets; |
|
163 /* A pointer to an array of numbuckets booleans, which will be true if |
|
164 * there are any Nodes in the bucket */ |
|
165 bool* buckets_in_use; |
|
166 /* If true, buckets will be freed in delete_hash */ |
|
167 bool freeb; |
|
168 /* If true, the pointer to this struct will be freed in delete_hash */ |
|
169 bool freeh; |
|
170 } Hash; |
|
171 |
|
172 /* Call these function to manipulate a hash */ |
|
173 |
|
174 /* Deletes the value with the specified key pair from the hash and returns |
|
175 * that value. Returns NULL when the value was not present. The value returned |
|
176 * is _not_ free()'d! */ |
|
177 void* Hash_Delete(Hash* h, uint key1, uint key2); |
|
178 /* Sets the value associated with the given key pair to the given value. |
|
179 * Returns the old value if the value was replaced, NULL when it was not yet present. */ |
|
180 void* Hash_Set(Hash* h, uint key1, uint key2, void* value); |
|
181 /* Gets the value associated with the given key pair, or NULL when it is not |
|
182 * present. */ |
|
183 void* Hash_Get(const Hash* h, uint key1, uint key2); |
|
184 |
|
185 /* Call these function to create/destroy a hash */ |
|
186 |
|
187 /* Builds a new hash, with num_buckets buckets. Make sure that hash() always |
|
188 * returns a hash less than num_buckets! Call delete_hash after use */ |
|
189 Hash* new_Hash(Hash_HashProc* hash, int num_buckets); |
|
190 /* Builds a new hash in an existing struct. Make sure that hash() always |
|
191 * returns a hash less than num_buckets! Call delete_hash after use */ |
|
192 void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets); |
|
193 /* |
|
194 * Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash |
|
195 * & friends. If free is true, it will call free() on all the values that |
|
196 * are left in the hash. |
|
197 */ |
|
198 void delete_Hash(Hash* h, bool free_values); |
|
199 /* |
|
200 * Cleans the hash, but keeps the memory allocated |
|
201 */ |
|
202 void clear_Hash(Hash* h, bool free_values); |
|
203 /* |
|
204 * Gets the current size of the Hash |
|
205 */ |
|
206 uint Hash_Size(const Hash* h); |
|
207 |
|
208 #endif /* QUEUE_H */ |