source: icGREP/icgrep-devel/cudd-2.5.1/nanotrav/ntrHeap.c @ 6132

Last change on this file since 6132 was 4597, checked in by nmedfort, 4 years ago

Upload of the CUDD library.

File size: 10.8 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [ntrHeap.c]
4
5  PackageName [ntr]
6
7  Synopsis    [Functions for heap-based priority queue.]
8
9  Description [The functions in this file manage a priority queue implemented
10  as a heap. The first element of the heap is the one with the smallest key.
11  Refer to Chapter 7 of Cormen, Leiserson, and Rivest for the theory.]
12
13  SeeAlso     []
14
15  Author      [Fabio Somenzi]
16
17  Copyright   [Copyright (c) 1995-2012, 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
49******************************************************************************/
50
51#include "ntr.h"
52
53/*---------------------------------------------------------------------------*/
54/* Constant declarations                                                     */
55/*---------------------------------------------------------------------------*/
56
57
58/*---------------------------------------------------------------------------*/
59/* Stucture declarations                                                     */
60/*---------------------------------------------------------------------------*/
61
62/*---------------------------------------------------------------------------*/
63/* Type declarations                                                         */
64/*---------------------------------------------------------------------------*/
65
66/*---------------------------------------------------------------------------*/
67/* Variable declarations                                                     */
68/*---------------------------------------------------------------------------*/
69
70#ifndef lint
71static char rcsid[] UTIL_UNUSED = "$Id: ntrHeap.c,v 1.6 2012/02/05 01:53:01 fabio Exp fabio $";
72#endif
73
74/*---------------------------------------------------------------------------*/
75/* Macro declarations                                                        */
76/*---------------------------------------------------------------------------*/
77
78#define PARENT(i)       (((i)-1)>>1)
79#define RIGHT(i)        (((i)+1)<<1)
80#define LEFT(i)         (((i)<<1)|1)
81#define ITEM(p,i)       ((p)[i].item)
82#define KEY(p,i)        ((p)[i].key)
83
84/**AutomaticStart*************************************************************/
85
86/*---------------------------------------------------------------------------*/
87/* Static function prototypes                                                */
88/*---------------------------------------------------------------------------*/
89
90static void ntrHeapify (NtrHeap *heap, int i);
91static int ntrHeapResize (NtrHeap *heap);
92
93/**AutomaticEnd***************************************************************/
94
95/*---------------------------------------------------------------------------*/
96/* Definition of exported functions                                          */
97/*---------------------------------------------------------------------------*/
98
99
100/**Function********************************************************************
101
102  Synopsis    [Initializes a priority queue.]
103
104  Description [Initializes a priority queue. Returns a pointer to the heap
105  if successful; NULL otherwise.]
106
107  SideEffects [None]
108
109  SeeAlso     [Ntr_FreeHeap]
110
111******************************************************************************/
112NtrHeap *
113Ntr_InitHeap(
114  int size)
115{
116    NtrHeap *heap;
117
118    heap = ALLOC(NtrHeap,1);
119    if (heap == NULL) return(NULL);
120    heap->size = size;
121    heap->nslots = 0;
122    heap->slots = ALLOC(NtrHeapSlot,size);
123    if (heap->slots == NULL) {
124        FREE(heap);
125        return(NULL);
126    }
127    return(heap);
128
129} /* end of Ntr_InitHeap */
130
131
132/**Function********************************************************************
133
134  Synopsis    [Frees a priority queue.]
135
136  Description []
137
138  SideEffects [None]
139
140  SeeAlso     [Ntr_InitHeap]
141
142******************************************************************************/
143void
144Ntr_FreeHeap(
145  NtrHeap *heap)
146{
147    FREE(heap->slots);
148    FREE(heap);
149    return;
150
151} /* end of Ntr_FreeHeap */
152
153
154/**Function********************************************************************
155
156  Synopsis    [Inserts an item in a priority queue.]
157
158  Description [Inserts an item in a priority queue. Returns 1 if successful;
159  0 otherwise.]
160
161  SideEffects [None]
162
163  SeeAlso     [Ntr_HeapExtractMin]
164
165******************************************************************************/
166int
167Ntr_HeapInsert(
168  NtrHeap *heap,
169  void *item,
170  int key)
171{
172    NtrHeapSlot *slots;
173    int i = heap->nslots;
174
175    if (i == heap->size && !ntrHeapResize(heap)) return(0);
176    slots = heap->slots;
177    heap->nslots++;
178    while (i > 0 && KEY(slots,PARENT(i)) > key) {
179        ITEM(slots,i) = ITEM(slots,PARENT(i));
180        KEY(slots,i) = KEY(slots,PARENT(i));
181        i = PARENT(i);
182    }
183    ITEM(slots,i) = item;
184    KEY(slots,i) = key;
185    return(1);
186
187} /* end of Ntr_HeapInsert */
188
189
190/**Function********************************************************************
191
192  Synopsis    [Extracts the element with the minimum key from a priority
193  queue.]
194
195  Description [Extracts the element with the minimum key from a priority
196  queue. Returns 1 if successful; 0 otherwise.]
197
198  SideEffects [The minimum key and the associated item are returned as
199  side effects.]
200
201  SeeAlso     [Ntr_HeapInsert]
202
203******************************************************************************/
204int
205Ntr_HeapExtractMin(
206  NtrHeap *heap,
207  void *item,
208  int *key)
209{
210    NtrHeapSlot *slots = heap->slots;
211
212    if (heap->nslots == 0) return(0);
213    *(void **)item = ITEM(slots,0);
214    *key = KEY(slots,0);
215    heap->nslots--;
216    ITEM(slots,0) = ITEM(slots,heap->nslots);
217    KEY(slots,0) = KEY(slots,heap->nslots);
218    ntrHeapify(heap,0);
219
220    return(1);
221
222} /* end of Ntr_HeapExtractMin */
223
224
225/**Function********************************************************************
226
227  Synopsis    [Returns the number of items in a priority queue.]
228
229  Description []
230
231  SideEffects [None]
232
233  SeeAlso     []
234
235******************************************************************************/
236int
237Ntr_HeapCount(
238  NtrHeap *heap)
239{
240    return(heap->nslots);
241
242} /* end of Ntr_HeapCount */
243
244
245/**Function********************************************************************
246
247  Synopsis    [Clones a priority queue.]
248
249  Description []
250
251  SideEffects [None]
252
253  SeeAlso     [Ntr_InitHeap]
254
255******************************************************************************/
256NtrHeap *
257Ntr_HeapClone(
258  NtrHeap *source)
259{
260    NtrHeap *dest;
261    int i;
262    int nslots = source->nslots;
263    NtrHeapSlot *sslots = source->slots;
264    NtrHeapSlot *dslots;
265
266    dest = Ntr_InitHeap(source->size);
267    if (dest == NULL) return(NULL);
268    dest->nslots = nslots;
269    dslots = dest->slots;
270    for (i = 0; i < nslots; i++) {
271        KEY(dslots,i) = KEY(sslots,i);
272        ITEM(dslots,i) = ITEM(sslots,i);
273    }
274    return(dest);
275
276} /* end of Ntr_HeapClone */
277
278
279/**Function********************************************************************
280
281  Synopsis    [Tests the heap property of a priority queue.]
282
283  Description [Tests the heap property of a priority queue. Returns 1 if
284  Successful; 0 otherwise.]
285
286  SideEffects [None]
287
288  SeeAlso     []
289
290******************************************************************************/
291int
292Ntr_TestHeap(
293  NtrHeap *heap,
294  int i)
295{
296    NtrHeapSlot *slots = heap->slots;
297    int nslots = heap->nslots;
298
299    if (i > 0 && KEY(slots,i) < KEY(slots,PARENT(i)))
300        return(0);
301    if (LEFT(i) < nslots) {
302        if (!Ntr_TestHeap(heap,LEFT(i)))
303            return(0);
304    }
305    if (RIGHT(i) < nslots) {
306        if (!Ntr_TestHeap(heap,RIGHT(i)))
307            return(0);
308    }
309    return(1);
310
311} /* end of Ntr_TestHeap */
312
313
314/*---------------------------------------------------------------------------*/
315/* Definition of static functions                                            */
316/*---------------------------------------------------------------------------*/
317
318
319/**Function********************************************************************
320
321  Synopsis    [Maintains the heap property of a priority queue.]
322
323  Description []
324
325  SideEffects [None]
326
327  SeeAlso     [Ntr_HeapExtractMin]
328
329******************************************************************************/
330static void
331ntrHeapify(
332  NtrHeap *heap,
333  int i)
334{
335    int smallest;
336    int left = LEFT(i);
337    int right = RIGHT(i);
338    int nslots = heap->nslots;
339    NtrHeapSlot *slots = heap->slots;
340    int key = KEY(slots,i);
341
342    if (left < nslots && KEY(slots,left) < key) {
343        smallest = left;
344    } else {
345        smallest = i;
346    }
347    if (right < nslots && KEY(slots,right) < KEY(slots,smallest)) {
348        smallest = right;
349    }
350    if (smallest != i) {
351        void *item = ITEM(slots,i);
352        KEY(slots,i) = KEY(slots,smallest);
353        ITEM(slots,i) = ITEM(slots,smallest);
354        KEY(slots,smallest) = key;
355        ITEM(slots,smallest) = item;
356        ntrHeapify(heap,smallest);
357    }
358
359    return;
360
361} /* end of ntrHeapify */
362
363
364/**Function********************************************************************
365
366  Synopsis    [Resizes a priority queue.]
367
368  Description [Resizes a priority queue by doubling the number of
369  available slots.  Returns 1 if successful; 0 otherwise.]
370
371  SideEffects [None]
372
373  SeeAlso     [Ntr_HeapInsert]
374
375******************************************************************************/
376static int
377ntrHeapResize(
378  NtrHeap *heap)
379{
380  int oldlength = heap->size;
381  int newlength = 2 * oldlength;
382  NtrHeapSlot *oldslots = heap->slots;
383  NtrHeapSlot *newslots = REALLOC(NtrHeapSlot, oldslots, newlength);
384  if (newslots == NULL) return 0;
385  heap->size = newlength;
386  heap->slots = newslots;
387  assert(Ntr_TestHeap(heap, 0));
388  return 1;
389
390} /* end of ntrHeapResize */
Note: See TracBrowser for help on using the repository browser.