summaryrefslogtreecommitdiffstats
path: root/src/bdd/cudd/cuddLevelQ.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/bdd/cudd/cuddLevelQ.c')
-rw-r--r--src/bdd/cudd/cuddLevelQ.c195
1 files changed, 113 insertions, 82 deletions
diff --git a/src/bdd/cudd/cuddLevelQ.c b/src/bdd/cudd/cuddLevelQ.c
index 1a09820a..43e730d6 100644
--- a/src/bdd/cudd/cuddLevelQ.c
+++ b/src/bdd/cudd/cuddLevelQ.c
@@ -25,28 +25,55 @@
Internal procedures provided by this module:
<ul>
- <li> cuddLevelQueueInit()
- <li> cuddLevelQueueQuit()
- <li> cuddLevelQueueEnqueue()
- <li> cuddLevelQueueDequeue()
- </ul>
+ <li> cuddLevelQueueInit()
+ <li> cuddLevelQueueQuit()
+ <li> cuddLevelQueueEnqueue()
+ <li> cuddLevelQueueDequeue()
+ </ul>
Static procedures included in this module:
- <ul>
- <li> hashLookup()
- <li> hashInsert()
- <li> hashDelete()
- <li> hashResize()
- </ul>
- ]
+ <ul>
+ <li> hashLookup()
+ <li> hashInsert()
+ <li> hashDelete()
+ <li> hashResize()
+ </ul>
+ ]
SeeAlso []
Author [Fabio Somenzi]
- Copyright [This file was created at the University of Colorado at
- Boulder. The University of Colorado at Boulder makes no
- warranty about the suitability of this software for any
- purpose. It is presented on an AS IS basis.]
+ Copyright [Copyright (c) 1995-2004, Regents of the University of Colorado
+
+ All rights reserved.
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions
+ are met:
+
+ Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+
+ Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in the
+ documentation and/or other materials provided with the distribution.
+
+ Neither the name of the University of Colorado nor the names of its
+ contributors may be used to endorse or promote products derived from
+ this software without specific prior written permission.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ POSSIBILITY OF SUCH DAMAGE.]
******************************************************************************/
@@ -56,6 +83,7 @@
ABC_NAMESPACE_IMPL_START
+
/*---------------------------------------------------------------------------*/
/* Constant declarations */
/*---------------------------------------------------------------------------*/
@@ -74,7 +102,7 @@ ABC_NAMESPACE_IMPL_START
/*---------------------------------------------------------------------------*/
#ifndef lint
-static char rcsid[] DD_UNUSED = "$Id: cuddLevelQ.c,v 1.1.1.1 2003/02/24 22:23:52 wjiang Exp $";
+static char rcsid[] DD_UNUSED = "$Id: cuddLevelQ.c,v 1.13 2009/03/08 02:49:02 fabio Exp $";
#endif
/*---------------------------------------------------------------------------*/
@@ -95,7 +123,7 @@ static char rcsid[] DD_UNUSED = "$Id: cuddLevelQ.c,v 1.1.1.1 2003/02/24 22:23:52
******************************************************************************/
#if SIZEOF_VOID_P == 8 && SIZEOF_INT == 4
#define lqHash(key,shift) \
-(((unsigned)(unsigned long)(key) * DD_P1) >> (shift))
+(((unsigned)(ptruint)(key) * DD_P1) >> (shift))
#else
#define lqHash(key,shift) \
(((unsigned)(key) * DD_P1) >> (shift))
@@ -108,10 +136,10 @@ static char rcsid[] DD_UNUSED = "$Id: cuddLevelQ.c,v 1.1.1.1 2003/02/24 22:23:52
/* Static function prototypes */
/*---------------------------------------------------------------------------*/
-static DdQueueItem * hashLookup ARGS((DdLevelQueue *queue, void *key));
-static int hashInsert ARGS((DdLevelQueue *queue, DdQueueItem *item));
-static void hashDelete ARGS((DdLevelQueue *queue, DdQueueItem *item));
-static int hashResize ARGS((DdLevelQueue *queue));
+static DdQueueItem * hashLookup (DdLevelQueue *queue, void *key);
+static int hashInsert (DdLevelQueue *queue, DdQueueItem *item);
+static void hashDelete (DdLevelQueue *queue, DdQueueItem *item);
+static int hashResize (DdLevelQueue *queue);
/**AutomaticEnd***************************************************************/
@@ -148,7 +176,7 @@ cuddLevelQueueInit(
queue = ABC_ALLOC(DdLevelQueue,1);
if (queue == NULL)
- return(NULL);
+ return(NULL);
#ifdef __osf__
#pragma pointer_size save
#pragma pointer_size short
@@ -159,8 +187,8 @@ cuddLevelQueueInit(
#pragma pointer_size restore
#endif
if (queue->last == NULL) {
- ABC_FREE(queue);
- return(NULL);
+ ABC_FREE(queue);
+ return(NULL);
}
/* Use a hash table to test for uniqueness. */
if (numBuckets < 2) numBuckets = 2;
@@ -176,9 +204,9 @@ cuddLevelQueueInit(
#pragma pointer_size restore
#endif
if (queue->buckets == NULL) {
- ABC_FREE(queue->last);
- ABC_FREE(queue);
- return(NULL);
+ ABC_FREE(queue->last);
+ ABC_FREE(queue);
+ return(NULL);
}
#ifdef __osf__
#pragma pointer_size save
@@ -219,14 +247,14 @@ cuddLevelQueueQuit(
DdQueueItem *item;
while (queue->freelist != NULL) {
- item = queue->freelist;
- queue->freelist = item->next;
- ABC_FREE(item);
+ item = queue->freelist;
+ queue->freelist = item->next;
+ ABC_FREE(item);
}
while (queue->first != NULL) {
- item = (DdQueueItem *) queue->first;
- queue->first = item->next;
- ABC_FREE(item);
+ item = (DdQueueItem *) queue->first;
+ queue->first = item->next;
+ ABC_FREE(item);
}
ABC_FREE(queue->buckets);
ABC_FREE(queue->last);
@@ -268,12 +296,12 @@ cuddLevelQueueEnqueue(
/* Get a free item from either the free list or the memory manager. */
if (queue->freelist == NULL) {
- item = (DdQueueItem *) ABC_ALLOC(char, queue->itemsize);
- if (item == NULL)
- return(NULL);
+ item = (DdQueueItem *) ABC_ALLOC(char, queue->itemsize);
+ if (item == NULL)
+ return(NULL);
} else {
- item = queue->freelist;
- queue->freelist = item->next;
+ item = queue->freelist;
+ queue->freelist = item->next;
}
/* Initialize. */
memset(item, 0, queue->itemsize);
@@ -282,29 +310,29 @@ cuddLevelQueueEnqueue(
queue->size++;
if (queue->last[level]) {
- /* There are already items for this level in the queue. */
- item->next = queue->last[level]->next;
- queue->last[level]->next = item;
- } else {
- /* There are no items at the current level. Look for the first
- ** non-empty level preceeding this one. */
- plevel = level;
- while (plevel != 0 && queue->last[plevel] == NULL)
- plevel--;
- if (queue->last[plevel] == NULL) {
- /* No element precedes this one in the queue. */
- item->next = (DdQueueItem *) queue->first;
- queue->first = item;
+ /* There are already items for this level in the queue. */
+ item->next = queue->last[level]->next;
+ queue->last[level]->next = item;
} else {
- item->next = queue->last[plevel]->next;
- queue->last[plevel]->next = item;
- }
+ /* There are no items at the current level. Look for the first
+ ** non-empty level preceeding this one. */
+ plevel = level;
+ while (plevel != 0 && queue->last[plevel] == NULL)
+ plevel--;
+ if (queue->last[plevel] == NULL) {
+ /* No element precedes this one in the queue. */
+ item->next = (DdQueueItem *) queue->first;
+ queue->first = item;
+ } else {
+ item->next = queue->last[plevel]->next;
+ queue->last[plevel]->next = item;
+ }
}
queue->last[level] = item;
/* Insert entry for the key in the hash table. */
if (hashInsert(queue,item) == 0) {
- return(NULL);
+ return(NULL);
}
return(item);
@@ -335,7 +363,7 @@ cuddLevelQueueDequeue(
/* Since we delete from the front, if this is the last item for
** its level, there are no other items for the same level. */
if (queue->last[level] == item)
- queue->last[level] = NULL;
+ queue->last[level] = NULL;
queue->first = item->next;
/* Put item on the free list. */
@@ -378,10 +406,10 @@ hashLookup(
item = queue->buckets[posn];
while (item != NULL) {
- if (item->key == key) {
- return(item);
- }
- item = item->cnext;
+ if (item->key == key) {
+ return(item);
+ }
+ item = item->cnext;
}
return(NULL);
@@ -410,8 +438,8 @@ hashInsert(
int posn;
if (queue->size > queue->maxsize) {
- result = hashResize(queue);
- if (result == 0) return(0);
+ result = hashResize(queue);
+ if (result == 0) return(0);
}
posn = lqHash(item->key,queue->shift);
@@ -448,16 +476,16 @@ hashDelete(
if (prevItem == NULL) return;
if (prevItem == item) {
- queue->buckets[posn] = prevItem->cnext;
- return;
+ queue->buckets[posn] = prevItem->cnext;
+ return;
}
while (prevItem->cnext != NULL) {
- if (prevItem->cnext == item) {
- prevItem->cnext = item->cnext;
- return;
- }
- prevItem = prevItem->cnext;
+ if (prevItem->cnext == item) {
+ prevItem->cnext = item->cnext;
+ return;
+ }
+ prevItem = prevItem->cnext;
}
return;
@@ -496,8 +524,8 @@ hashResize(
#endif
int shift;
int oldNumBuckets = queue->numBuckets;
-// extern void (*MMoutOfMemory)(long);
- void (*saveHandler)(long);
+ extern DD_OOMFP MMoutOfMemory;
+ DD_OOMFP saveHandler;
/* Compute the new size of the subtable. */
numBuckets = oldNumBuckets << 1;
@@ -508,9 +536,10 @@ hashResize(
#pragma pointer_size short
#endif
buckets = queue->buckets = ABC_ALLOC(DdQueueItem *, numBuckets);
+ MMoutOfMemory = saveHandler;
if (buckets == NULL) {
- queue->maxsize <<= 1;
- return(1);
+ queue->maxsize <<= 1;
+ return(1);
}
queue->numBuckets = numBuckets;
@@ -521,18 +550,20 @@ hashResize(
#pragma pointer_size restore
#endif
for (j = 0; j < oldNumBuckets; j++) {
- item = oldBuckets[j];
- while (item != NULL) {
- next = item->cnext;
- posn = lqHash(item->key, shift);
- item->cnext = buckets[posn];
- buckets[posn] = item;
- item = next;
- }
+ item = oldBuckets[j];
+ while (item != NULL) {
+ next = item->cnext;
+ posn = lqHash(item->key, shift);
+ item->cnext = buckets[posn];
+ buckets[posn] = item;
+ item = next;
+ }
}
ABC_FREE(oldBuckets);
return(1);
} /* end of hashResize */
+
+
ABC_NAMESPACE_IMPL_END
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-18 09:08:01 +0000