source: vis_dev/glu-2.1/src/calBdd/calHashTableThree.c @ 13

Last change on this file since 13 was 8, checked in by cecile, 13 years ago

src glu
File size: 7.9 KB
RevLine 
[8]1/**CFile***********************************************************************
2
3  FileName    [calHashTableThree.c]
4
5  PackageName [cal]
6
7  Synopsis    [Functions to manage the hash tables that are a part of
8                  ITE operation]
9
10  Description [CalHashTableThreeFindOrAdd]
11
12  SeeAlso     [optional]
13
14  Author      [Jagesh Sanghavi (sanghavi@eecs.berkeley.edu)
15                Rajeev Ranjan   (rajeev@eecs.berkeley.edu)]
16
17  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
18  All rights reserved.
19
20  Permission is hereby granted, without written agreement and without license
21  or royalty fees, to use, copy, modify, and distribute this software and its
22  documentation for any purpose, provided that the above copyright notice and
23  the following two paragraphs appear in all copies of this software.
24
25  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
26  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
27  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
28  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
31  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
32  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
33  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
34  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
35
36  Revision    [$Id: calHashTableThree.c,v 1.1.1.3 1998/05/04 00:58:58 hsv Exp $]
37
38******************************************************************************/
39
40#include "calInt.h"
41
42
43/*---------------------------------------------------------------------------*/
44/* Constant declarations                                                     */
45/*---------------------------------------------------------------------------*/
46
47/*---------------------------------------------------------------------------*/
48/* Type declarations                                                         */
49/*---------------------------------------------------------------------------*/
50
51
52/*---------------------------------------------------------------------------*/
53/* Stucture declarations                                                     */
54/*---------------------------------------------------------------------------*/
55
56
57/*---------------------------------------------------------------------------*/
58/* Variable declarations                                                     */
59/*---------------------------------------------------------------------------*/
60
61/*---------------------------------------------------------------------------*/
62/* Macro declarations                                                        */
63/*---------------------------------------------------------------------------*/
64#ifdef USE_POWER_OF_2
65#define CalDoHash3(fBddNode, gBddNode, hBddNode,table) \
66((((CalAddress_t)fBddNode + \
67   (CalAddress_t)gBddNode + \
68   (CalAddress_t) hBddNode) \
69  / NODE_SIZE) & ((table)->numBins-1))
70#else
71#define CalDoHash3(fBddNode, gBddNode, hBddNode,table) \
72  ((((CalAddress_t)fBddNode + \
73  (CalAddress_t)gBddNode + \
74  (CalAddress_t) hBddNode) \
75  / NODE_SIZE)% table->numBins)
76#endif
77/**AutomaticStart*************************************************************/
78
79/*---------------------------------------------------------------------------*/
80/* Static function prototypes                                                */
81/*---------------------------------------------------------------------------*/
82
83static void CalHashTableThreeRehash(CalHashTable_t *hashTable, int grow);
84
85/**AutomaticEnd***************************************************************/
86
87
88/*---------------------------------------------------------------------------*/
89/* Definition of exported functions                                          */
90/*---------------------------------------------------------------------------*/
91
92
93/*---------------------------------------------------------------------------*/
94/* Definition of internal functions                                          */
95/*---------------------------------------------------------------------------*/
96/**Function********************************************************************
97
98  Synopsis    [required]
99
100  Description [optional]
101
102  SideEffects [required]
103
104  SeeAlso     [optional]
105
106******************************************************************************/
107int
108CalHashTableThreeFindOrAdd(CalHashTable_t * hashTable,
109                           Cal_Bdd_t  f,
110                           Cal_Bdd_t  g,
111                           Cal_Bdd_t  h,
112                           Cal_Bdd_t * bddPtr)
113{
114  CalBddNode_t *ptr, *ptrIndirect;
115  Cal_Bdd_t tmpBdd;
116  int hashValue;
117 
118  hashValue = CalDoHash3(CalBddGetBddNode(f), 
119      CalBddGetBddNode(g), CalBddGetBddNode(h), hashTable);
120  ptr = hashTable->bins[hashValue];
121  while(ptr != Cal_Nil(CalBddNode_t)){
122    CalBddNodeGetThenBdd(ptr, tmpBdd);
123    if(CalBddIsEqual(f, tmpBdd)){
124      ptrIndirect = CalBddNodeGetElseBddNode(ptr);
125      CalBddNodeGetThenBdd(ptrIndirect, tmpBdd);
126      if(CalBddIsEqual(g, tmpBdd)){
127        CalBddNodeGetElseBdd(ptrIndirect, tmpBdd);
128        if(CalBddIsEqual(h, tmpBdd)){
129          CalBddPutBddId(*bddPtr, hashTable->bddId);
130          CalBddPutBddNode(*bddPtr, ptr);
131          return 1;
132        }
133      }
134    }
135    ptr = CalBddNodeGetNextBddNode(ptr);
136  }
137  hashTable->numEntries++;
138  if(hashTable->numEntries > hashTable->maxCapacity){
139    CalHashTableThreeRehash(hashTable,1);
140    hashValue = CalDoHash3(CalBddGetBddNode(f),
141        CalBddGetBddNode(g), CalBddGetBddNode(h), hashTable);
142  }
143  CalNodeManagerAllocNode(hashTable->nodeManager, ptr);
144  CalNodeManagerAllocNode(hashTable->nodeManager, ptrIndirect);
145  CalBddNodePutThenBdd(ptr, f);
146  CalBddNodePutThenBdd(ptrIndirect, g);
147  CalBddNodePutElseBdd(ptrIndirect, h);
148  CalBddNodePutElseBddNode(ptr, ptrIndirect);
149  CalBddNodePutNextBddNode(ptr, hashTable->bins[hashValue]);
150  hashTable->bins[hashValue] = ptr;
151  CalBddPutBddId(*bddPtr, hashTable->bddId);
152  CalBddPutBddNode(*bddPtr, ptr);
153  return 0;
154}
155
156/*---------------------------------------------------------------------------*/
157/* Definition of static functions                                            */
158/*---------------------------------------------------------------------------*/
159/**Function********************************************************************
160
161  Synopsis    [required]
162
163  Description [optional]
164
165  SideEffects [required]
166
167  SeeAlso     [optional]
168
169******************************************************************************/
170static void
171CalHashTableThreeRehash(CalHashTable_t *hashTable, int grow)
172{
173  CalBddNode_t *ptr, *ptrIndirect, *next;
174  CalBddNode_t **oldBins = hashTable->bins;
175  int i, hashValue;
176  int oldNumBins = hashTable->numBins;
177
178  if(grow){
179    hashTable->sizeIndex++;
180  }
181  else{
182    if (hashTable->sizeIndex <= HASH_TABLE_DEFAULT_SIZE_INDEX){/* No need to rehash */
183      return;
184    }
185    hashTable->sizeIndex--;
186  }
187
188  hashTable->numBins = TABLE_SIZE(hashTable->sizeIndex);
189  hashTable->numBins = hashTable->numBins;
190  hashTable->maxCapacity = hashTable->numBins * HASH_TABLE_DEFAULT_MAX_DENSITY;
191  hashTable->bins = Cal_MemAlloc(CalBddNode_t *, hashTable->numBins);
192  if(hashTable->bins == Cal_Nil(CalBddNode_t *)){
193    CalBddFatalMessage("out of memory");
194  }
195  for(i = 0; i < hashTable->numBins; i++){
196    hashTable->bins[i] = Cal_Nil(CalBddNode_t);
197  }
198
199  for(i = 0; i < oldNumBins; i++){
200    ptr = oldBins[i];
201    while(ptr != Cal_Nil(CalBddNode_t)){
202      next = CalBddNodeGetNextBddNode(ptr);
203      ptrIndirect = CalBddNodeGetElseBddNode(ptr);
204      hashValue = CalDoHash3(CalBddNodeGetThenBddNode(ptr),
205          CalBddNodeGetThenBddNode(ptrIndirect),
206          CalBddNodeGetElseBddNode(ptrIndirect), hashTable);
207      CalBddNodePutNextBddNode(ptr, hashTable->bins[hashValue]);
208      hashTable->bins[hashValue] = ptr;
209      ptr = next;
210    }
211  }
212  Cal_MemFree(oldBins);
213}
214
215
216
217
218
219
220
221
Note: See TracBrowser for help on using the repository browser.