source: vis_dev/glu-2.3/src/calBdd/calHashTableOne.c@ 26

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

library glu 2.3
File size: 9.8 KB
Line 
1/**CFile***********************************************************************
2
3 FileName [calHashTableOne.c]
4
5 PackageName [cal]
6
7 Synopsis [Routines for managing hash table with Bdd is a key and
8 int, long, or double as a value]
9
10 Description [ ]
11
12 SeeAlso [optional]
13
14 Author [Jagesh Sanghavi (sanghavi@eecs.berkeley.edu)
15 Rajeev Ranjan (rajeev@eecs.berkeley.edu)
16 ]
17
18 Copyright [Copyright (c) 1994-1996 The Regents of the Univ. of California.
19 All rights reserved.
20
21 Permission is hereby granted, without written agreement and without license
22 or royalty fees, to use, copy, modify, and distribute this software and its
23 documentation for any purpose, provided that the above copyright notice and
24 the following two paragraphs appear in all copies of this software.
25
26 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
27 DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
28 OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
29 CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
32 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
33 FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN
34 "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
35 MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
36
37 Revision [$Id: calHashTableOne.c,v 1.1.1.3 1998/05/04 00:58:57 hsv Exp $]
38
39******************************************************************************/
40#include "calInt.h"
41
42/*---------------------------------------------------------------------------*/
43/* Constant declarations */
44/*---------------------------------------------------------------------------*/
45
46/*---------------------------------------------------------------------------*/
47/* Type declarations */
48/*---------------------------------------------------------------------------*/
49
50/*---------------------------------------------------------------------------*/
51/* Stucture declarations */
52/*---------------------------------------------------------------------------*/
53
54/*---------------------------------------------------------------------------*/
55/* Variable declarations */
56/*---------------------------------------------------------------------------*/
57
58/*---------------------------------------------------------------------------*/
59/* Macro declarations */
60/*---------------------------------------------------------------------------*/
61#ifdef USE_POWER_OF_2
62# define HashTableOneDoHash(hashTable, keyBdd) \
63 (((CalAddress_t)(CalBddGetBddNode(keyBdd)) / NODE_SIZE) & ((hashTable)->numBins - 1))
64#else
65# define HashTableOneDoHash(hashTable, keyBdd) \
66 (((CalAddress_t)(CalBddGetBddNode(keyBdd)) / NODE_SIZE) % hashTable->numBins)
67#endif
68
69/**AutomaticStart*************************************************************/
70
71/*---------------------------------------------------------------------------*/
72/* Static function prototypes */
73/*---------------------------------------------------------------------------*/
74
75static void HashTableOneRehash(CalHashTable_t * hashTable, int grow);
76
77/**AutomaticEnd***************************************************************/
78
79/*---------------------------------------------------------------------------*/
80/* Definition of exported functions */
81/*---------------------------------------------------------------------------*/
82/*---------------------------------------------------------------------------*/
83/* Definition of internal functions */
84/*---------------------------------------------------------------------------*/
85
86/**Function********************************************************************
87
88 Synopsis [Initialize a hash table using default parameters.]
89
90 Description [optional]
91
92 SideEffects [required]
93
94 SeeAlso [optional]
95
96******************************************************************************/
97CalHashTable_t *
98CalHashTableOneInit(Cal_BddManager_t * bddManager, int itemSize)
99{
100 int i;
101 CalHashTable_t *hashTable;
102
103 hashTable = Cal_MemAlloc(CalHashTable_t, 1);
104 if(hashTable == Cal_Nil(CalHashTable_t)){
105 CalBddFatalMessage("out of memory");
106 }
107 hashTable->sizeIndex = HASH_TABLE_DEFAULT_SIZE_INDEX;
108 hashTable->numBins = TABLE_SIZE(hashTable->sizeIndex);
109 hashTable->maxCapacity = hashTable->numBins*HASH_TABLE_DEFAULT_MAX_DENSITY;
110 hashTable->bins = Cal_MemAlloc(CalBddNode_t *, hashTable->numBins);
111 if(hashTable->bins == Cal_Nil(CalBddNode_t *)){
112 CalBddFatalMessage("out of memory");
113 }
114 for(i = 0; i < hashTable->numBins; i++){
115 hashTable->bins[i] = Cal_Nil(CalBddNode_t);
116 }
117 hashTable->numEntries = 0;
118 hashTable->bddId = (Cal_BddId_t)itemSize;
119 if(itemSize > NODE_SIZE){
120 CalBddFatalMessage("CalHashTableOneInit: itemSize exceeds NODE_SIZE");
121 }
122 hashTable->nodeManager = bddManager->nodeManagerArray[0];
123 hashTable->requestNodeList = Cal_Nil(CalRequestNode_t);
124 return hashTable;
125}
126
127
128/**Function********************************************************************
129
130 Synopsis [Free a hash table along with the associated storage.]
131
132 Description [optional]
133
134 SideEffects [required]
135
136 SeeAlso [optional]
137
138******************************************************************************/
139void
140CalHashTableOneQuit(
141 CalHashTable_t * hashTable)
142{
143 CalBddNode_t *ptr, *next, *node;
144 int i;
145 if(hashTable == Cal_Nil(CalHashTable_t))return;
146 for(i = 0; i < hashTable->numBins; i++){
147 ptr = hashTable->bins[i];
148 while(ptr != Cal_Nil(CalBddNode_t)){
149 next = CalBddNodeGetNextBddNode(ptr);
150 node = CalBddNodeGetElseBddNode(ptr);
151 CalNodeManagerFreeNode(hashTable->nodeManager, node);
152 CalNodeManagerFreeNode(hashTable->nodeManager, ptr);
153 ptr = next;
154 }
155 }
156 Cal_MemFree(hashTable->bins);
157 Cal_MemFree(hashTable);
158}
159
160
161/**Function********************************************************************
162
163 Synopsis [Directly insert a BDD node in the hash table.]
164
165 Description [optional]
166
167 SideEffects [required]
168
169 SeeAlso [optional]
170
171******************************************************************************/
172void
173CalHashTableOneInsert(CalHashTable_t * hashTable, Cal_Bdd_t keyBdd,
174 char * valuePtr)
175{
176 int hashValue;
177 CalBddNode_t *bddNode, *dataPtr;
178
179 hashValue = HashTableOneDoHash(hashTable, keyBdd);
180 hashTable->numEntries++;
181 if(hashTable->numEntries >= hashTable->maxCapacity){
182 HashTableOneRehash(hashTable, 1);
183 hashValue = HashTableOneDoHash(hashTable, keyBdd);
184 }
185 CalNodeManagerAllocNode(hashTable->nodeManager, dataPtr);
186 memcpy(dataPtr, valuePtr, (size_t)hashTable->bddId);
187 CalNodeManagerAllocNode(hashTable->nodeManager, bddNode);
188 CalBddNodePutThenBdd(bddNode, keyBdd);
189 CalBddNodePutElseBddNode(bddNode, dataPtr);
190 CalBddNodePutNextBddNode(bddNode, hashTable->bins[hashValue]);
191 hashTable->bins[hashValue] = bddNode;
192}
193
194/**Function********************************************************************
195
196 Synopsis [required]
197
198 Description [optional]
199
200 SideEffects [required]
201
202 SeeAlso [optional]
203
204******************************************************************************/
205int
206CalHashTableOneLookup(CalHashTable_t * hashTable, Cal_Bdd_t keyBdd,
207 char ** valuePtrPtr)
208{
209 CalBddNode_t *ptr;
210 Cal_Bdd_t tmpBdd;
211 int hashValue;
212
213 hashValue = HashTableOneDoHash(hashTable, keyBdd);
214 ptr = hashTable->bins[hashValue];
215 while(ptr != Cal_Nil(CalBddNode_t)){
216 CalBddNodeGetThenBdd(ptr, tmpBdd);
217 if(CalBddIsEqual(keyBdd, tmpBdd)){
218 if(valuePtrPtr){
219 *valuePtrPtr = (char *)CalBddNodeGetElseBddNode(ptr);
220 }
221 return 1;
222 }
223 ptr = CalBddNodeGetNextBddNode(ptr);
224 }
225 if(valuePtrPtr){
226 *valuePtrPtr = Cal_Nil(char);
227 }
228 return 0;
229}
230/*---------------------------------------------------------------------------*/
231/* Definition of static functions */
232/*---------------------------------------------------------------------------*/
233
234/**Function********************************************************************
235
236 Synopsis [required]
237
238 Description [optional]
239
240 SideEffects [required]
241
242 SeeAlso [optional]
243
244******************************************************************************/
245static void
246HashTableOneRehash(
247 CalHashTable_t * hashTable,
248 int grow)
249{
250 CalBddNode_t *ptr, *next;
251 CalBddNode_t **oldBins = hashTable->bins;
252 int i, hashValue;
253 int oldNumBins = hashTable->numBins;
254 Cal_Bdd_t keyBdd;
255
256 if(grow){
257 hashTable->sizeIndex++;
258 }
259 else{
260 if (hashTable->sizeIndex <= HASH_TABLE_DEFAULT_SIZE_INDEX){/* No need to rehash */
261 return;
262 }
263 hashTable->sizeIndex--;
264 }
265
266 hashTable->numBins = TABLE_SIZE(hashTable->sizeIndex);
267 hashTable->maxCapacity = hashTable->numBins * HASH_TABLE_DEFAULT_MAX_DENSITY;
268 hashTable->bins = Cal_MemAlloc(CalBddNode_t *, hashTable->numBins);
269 if(hashTable->bins == Cal_Nil(CalBddNode_t *)){
270 CalBddFatalMessage("out of memory");
271 }
272 for(i = 0; i < hashTable->numBins; i++){
273 hashTable->bins[i] = Cal_Nil(CalBddNode_t);
274 }
275
276 for(i = 0; i < oldNumBins; i++){
277 ptr = oldBins[i];
278 while(ptr != Cal_Nil(CalBddNode_t)){
279 next = CalBddNodeGetNextBddNode(ptr);
280 CalBddNodeGetThenBdd(ptr, keyBdd);
281 hashValue = HashTableOneDoHash(hashTable, keyBdd);
282 CalBddNodePutNextBddNode(ptr, hashTable->bins[hashValue]);
283 hashTable->bins[hashValue] = ptr;
284 ptr = next;
285 }
286 }
287 Cal_MemFree(oldBins);
288}
289
290
291
292
293
294
295
296
297
298
Note: See TracBrowser for help on using the repository browser.