1 /**
2 @file
3
4 @ingroup nanotrav
5
6 @brief Functions for heap-based priority queues.
7
8 @details The functions in this file manage a priority queue
9 implemented as a heap. The first element of the heap is the one with
10 the smallest key. The queue stores generic pointers, but the key
11 must be an int. Refer to Chapter 7 of Cormen, Leiserson, and Rivest
12 for the theory.
13
14 @author Fabio Somenzi
15
16 @copyright@parblock
17 Copyright (c) 1995-2015, Regents of the University of Colorado
18
19 All rights reserved.
20
21 Redistribution and use in source and binary forms, with or without
22 modification, are permitted provided that the following conditions
23 are met:
24
25 Redistributions of source code must retain the above copyright
26 notice, this list of conditions and the following disclaimer.
27
28 Redistributions in binary form must reproduce the above copyright
29 notice, this list of conditions and the following disclaimer in the
30 documentation and/or other materials provided with the distribution.
31
32 Neither the name of the University of Colorado nor the names of its
33 contributors may be used to endorse or promote products derived from
34 this software without specific prior written permission.
35
36 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
37 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
38 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
39 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
40 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
41 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
42 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
44 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
45 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
46 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
47 POSSIBILITY OF SUCH DAMAGE.
48 @endparblock
49
50 */
51
52 #include "ntr.h"
53
54 /*---------------------------------------------------------------------------*/
55 /* Constant declarations */
56 /*---------------------------------------------------------------------------*/
57
58
59 /*---------------------------------------------------------------------------*/
60 /* Stucture declarations */
61 /*---------------------------------------------------------------------------*/
62
63 /**
64 @brief Entry of NtrHeap.
65 */
66 struct NtrHeapSlot {
67 void *item;
68 int key;
69 };
70
71 /**
72 @brief Heap-based priority queue.
73 */
74 struct NtrHeap {
75 int size;
76 int nslots;
77 NtrHeapSlot *slots;
78 };
79
80 /*---------------------------------------------------------------------------*/
81 /* Type declarations */
82 /*---------------------------------------------------------------------------*/
83
84 /*---------------------------------------------------------------------------*/
85 /* Variable declarations */
86 /*---------------------------------------------------------------------------*/
87
88
89 /*---------------------------------------------------------------------------*/
90 /* Macro declarations */
91 /*---------------------------------------------------------------------------*/
92
93 #define PARENT(i) (((i)-1)>>1)
94 #define RIGHT(i) (((i)+1)<<1)
95 #define LEFT(i) (((i)<<1)|1)
96 #define ITEM(p,i) ((p)[i].item)
97 #define KEY(p,i) ((p)[i].key)
98
99 /** \cond */
100
101 /*---------------------------------------------------------------------------*/
102 /* Static function prototypes */
103 /*---------------------------------------------------------------------------*/
104
105 static void ntrHeapify (NtrHeap *heap, int i);
106 static int ntrHeapResize (NtrHeap *heap);
107
108 /** \endcond */
109
110
111 /*---------------------------------------------------------------------------*/
112 /* Definition of exported functions */
113 /*---------------------------------------------------------------------------*/
114
115
116 /**
117 @brief Initializes a priority queue.
118
119 @return a pointer to the heap if successful; NULL otherwise.
120
121 @sideeffect None
122
123 @see Ntr_FreeHeap
124
125 */
126 NtrHeap *
Ntr_InitHeap(int size)127 Ntr_InitHeap(
128 int size)
129 {
130 NtrHeap *heap;
131
132 heap = ALLOC(NtrHeap,1);
133 if (heap == NULL) return(NULL);
134 heap->size = size;
135 heap->nslots = 0;
136 heap->slots = ALLOC(NtrHeapSlot,size);
137 if (heap->slots == NULL) {
138 FREE(heap);
139 return(NULL);
140 }
141 return(heap);
142
143 } /* end of Ntr_InitHeap */
144
145
146 /**
147 @brief Frees a priority queue.
148
149 @sideeffect None
150
151 @see Ntr_InitHeap
152
153 */
154 void
Ntr_FreeHeap(NtrHeap * heap)155 Ntr_FreeHeap(
156 NtrHeap *heap)
157 {
158 FREE(heap->slots);
159 FREE(heap);
160 return;
161
162 } /* end of Ntr_FreeHeap */
163
164
165 /**
166 @brief Inserts an item in a priority queue.
167
168 @return 1 if successful; 0 otherwise.
169
170 @sideeffect None
171
172 @see Ntr_HeapExtractMin
173
174 */
175 int
Ntr_HeapInsert(NtrHeap * heap,void * item,int key)176 Ntr_HeapInsert(
177 NtrHeap *heap,
178 void *item,
179 int key)
180 {
181 NtrHeapSlot *slots;
182 int i = heap->nslots;
183
184 if (i == heap->size && !ntrHeapResize(heap)) return(0);
185 slots = heap->slots;
186 heap->nslots++;
187 while (i > 0 && KEY(slots,PARENT(i)) > key) {
188 ITEM(slots,i) = ITEM(slots,PARENT(i));
189 KEY(slots,i) = KEY(slots,PARENT(i));
190 i = PARENT(i);
191 }
192 ITEM(slots,i) = item;
193 KEY(slots,i) = key;
194 return(1);
195
196 } /* end of Ntr_HeapInsert */
197
198
199 /**
200 @brief Extracts the element with the minimum key from a priority
201 queue.
202
203 @return 1 if successful; 0 otherwise.
204
205 @sideeffect The minimum key and the associated item are returned as
206 side effects.
207
208 @see Ntr_HeapInsert
209
210 */
211 int
Ntr_HeapExtractMin(NtrHeap * heap,void * item,int * key)212 Ntr_HeapExtractMin(
213 NtrHeap *heap,
214 void *item,
215 int *key)
216 {
217 NtrHeapSlot *slots = heap->slots;
218
219 if (heap->nslots == 0) return(0);
220 *(void **)item = ITEM(slots,0);
221 *key = KEY(slots,0);
222 heap->nslots--;
223 ITEM(slots,0) = ITEM(slots,heap->nslots);
224 KEY(slots,0) = KEY(slots,heap->nslots);
225 ntrHeapify(heap,0);
226
227 return(1);
228
229 } /* end of Ntr_HeapExtractMin */
230
231
232 /**
233 @brief Returns the number of items in a priority queue.
234
235 @sideeffect None
236
237 */
238 int
Ntr_HeapCount(NtrHeap * heap)239 Ntr_HeapCount(
240 NtrHeap *heap)
241 {
242 return(heap->nslots);
243
244 } /* end of Ntr_HeapCount */
245
246
247 /**
248 @brief Clones a priority queue.
249
250 @sideeffect None
251
252 @see Ntr_InitHeap
253
254 */
255 NtrHeap *
Ntr_HeapClone(NtrHeap * source)256 Ntr_HeapClone(
257 NtrHeap *source)
258 {
259 NtrHeap *dest;
260 int i;
261 int nslots = source->nslots;
262 NtrHeapSlot *sslots = source->slots;
263 NtrHeapSlot *dslots;
264
265 dest = Ntr_InitHeap(source->size);
266 if (dest == NULL) return(NULL);
267 dest->nslots = nslots;
268 dslots = dest->slots;
269 for (i = 0; i < nslots; i++) {
270 KEY(dslots,i) = KEY(sslots,i);
271 ITEM(dslots,i) = ITEM(sslots,i);
272 }
273 return(dest);
274
275 } /* end of Ntr_HeapClone */
276
277
278 /**
279 @brief Calls a function on all items in a heap.
280 */
281 void
Ntr_HeapForeach(NtrHeap * heap,void (* f)(void * e,void * arg),void * arg)282 Ntr_HeapForeach(
283 NtrHeap *heap,
284 void (*f)(void * e, void * arg),
285 void * arg)
286 {
287 int i;
288
289 for (i = 0; i < heap->nslots; i++) {
290 f(heap->slots[i].item, arg);
291 }
292
293 } /* end of Ntr_HeapForeach */
294
295
296 /**
297 @brief Tests the heap property of a priority queue.
298
299 @return 1 if Successful; 0 otherwise.
300
301 @sideeffect None
302
303 */
304 int
Ntr_TestHeap(NtrHeap * heap,int i)305 Ntr_TestHeap(
306 NtrHeap *heap,
307 int i)
308 {
309 NtrHeapSlot *slots = heap->slots;
310 int nslots = heap->nslots;
311
312 if (i > 0 && KEY(slots,i) < KEY(slots,PARENT(i)))
313 return(0);
314 if (LEFT(i) < nslots) {
315 if (!Ntr_TestHeap(heap,LEFT(i)))
316 return(0);
317 }
318 if (RIGHT(i) < nslots) {
319 if (!Ntr_TestHeap(heap,RIGHT(i)))
320 return(0);
321 }
322 return(1);
323
324 } /* end of Ntr_TestHeap */
325
326
327 /*---------------------------------------------------------------------------*/
328 /* Definition of static functions */
329 /*---------------------------------------------------------------------------*/
330
331
332 /**
333 @brief Maintains the heap property of a priority queue.
334
335 @sideeffect None
336
337 @see Ntr_HeapExtractMin
338
339 */
340 static void
ntrHeapify(NtrHeap * heap,int i)341 ntrHeapify(
342 NtrHeap *heap,
343 int i)
344 {
345 int smallest;
346 int left = LEFT(i);
347 int right = RIGHT(i);
348 int nslots = heap->nslots;
349 NtrHeapSlot *slots = heap->slots;
350 int key = KEY(slots,i);
351
352 if (left < nslots && KEY(slots,left) < key) {
353 smallest = left;
354 } else {
355 smallest = i;
356 }
357 if (right < nslots && KEY(slots,right) < KEY(slots,smallest)) {
358 smallest = right;
359 }
360 if (smallest != i) {
361 void *item = ITEM(slots,i);
362 KEY(slots,i) = KEY(slots,smallest);
363 ITEM(slots,i) = ITEM(slots,smallest);
364 KEY(slots,smallest) = key;
365 ITEM(slots,smallest) = item;
366 ntrHeapify(heap,smallest);
367 }
368
369 return;
370
371 } /* end of ntrHeapify */
372
373
374 /**
375 @brief Resizes a priority queue.
376
377 @details Resizes a priority queue by doubling the number of
378 available slots.
379
380 @return 1 if successful; 0 otherwise.
381
382 @sideeffect None
383
384 @see Ntr_HeapInsert
385
386 */
387 static int
ntrHeapResize(NtrHeap * heap)388 ntrHeapResize(
389 NtrHeap *heap)
390 {
391 int oldlength = heap->size;
392 int newlength = 2 * oldlength;
393 NtrHeapSlot *oldslots = heap->slots;
394 NtrHeapSlot *newslots = REALLOC(NtrHeapSlot, oldslots, newlength);
395 if (newslots == NULL) return 0;
396 heap->size = newlength;
397 heap->slots = newslots;
398 assert(Ntr_TestHeap(heap, 0));
399 return 1;
400
401 } /* end of ntrHeapResize */
402