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

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

library glu 2.3
File size: 9.8 KB
RevLine 
[13]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.