abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
nmTable.c File Reference
#include "nmInt.h"

Go to the source code of this file.

Functions

static
ABC_NAMESPACE_IMPL_START
unsigned 		Nm_HashNumber (int Num, int TableSize)
 DECLARATIONS ///. More...
 
static unsigned Nm_HashString (char *pName, int TableSize)
 
static void Nm_ManResize (Nm_Man_t *p)
 
int Nm_ManTableAdd (Nm_Man_t *p, Nm_Entry_t *pEntry)
 FUNCTION DEFINITIONS ///. More...
 
int Nm_ManTableDelete (Nm_Man_t *p, int ObjId)
 
Nm_Entry_t * Nm_ManTableLookupId (Nm_Man_t *p, int ObjId)
 
Nm_Entry_t * Nm_ManTableLookupName (Nm_Man_t *p, char *pName, int Type)
 
void Nm_ManProfile (Nm_Man_t *p)
 

Function Documentation

static ABC_NAMESPACE_IMPL_START unsigned Nm_HashNumber ( int  Num,
int  TableSize 
)
static

DECLARATIONS ///.

CFile****************************************************************

FileName [nmTable.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Name manager.]

Synopsis [Hash table for the name manager.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:
nmTable.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Definition at line 31 of file nmTable.c.

32 {
33  unsigned Key = 0;
34  Key ^= ( Num & 0xFF) * 7937;
35  Key ^= ((Num >> 8) & 0xFF) * 2971;
36  Key ^= ((Num >> 16) & 0xFF) * 911;
37  Key ^= ((Num >> 24) & 0xFF) * 353;
38  return Key % TableSize;
39 }
static unsigned Nm_HashString ( char *  pName,
int  TableSize 
)
static

Definition at line 42 of file nmTable.c.

43 {
44  static int s_Primes[10] = {
45  1291, 1699, 2357, 4177, 5147,
46  5647, 6343, 7103, 7873, 8147
47  };
48  unsigned i, Key = 0;
49  for ( i = 0; pName[i] != '\0'; i++ )
50  Key ^= s_Primes[i%10]*pName[i]*pName[i];
51  return Key % TableSize;
52 }
s_Primes
static int s_Primes[MAX_PRIMES]
Definition: fxuPair.c:30
void Nm_ManProfile ( Nm_Man_t *  p)

Function*************************************************************

Synopsis [Profiles hash tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 221 of file nmTable.c.

222 {
223  Nm_Entry_t * pEntry;
224  int Counter, e;
225  printf( "I2N table: " );
226  for ( e = 0; e < p->nBins; e++ )
227  {
228  Counter = 0;
229  for ( pEntry = p->pBinsI2N[e]; pEntry; pEntry = pEntry->pNextI2N )
230  Counter++;
231  printf( "%d ", Counter );
232  }
233  printf( "\n" );
234  printf( "N2I table: " );
235  for ( e = 0; e < p->nBins; e++ )
236  {
237  Counter = 0;
238  for ( pEntry = p->pBinsN2I[e]; pEntry; pEntry = pEntry->pNextN2I )
239  Counter++;
240  printf( "%d ", Counter );
241  }
242  printf( "\n" );
243 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Nm_Entry_t
typedefABC_NAMESPACE_HEADER_START struct Nm_Entry_t_ Nm_Entry_t
INCLUDES ///.
Definition: nmInt.h:46
Counter
static int Counter
Definition: extraBddMisc.c:1877
void Nm_ManResize ( Nm_Man_t *  p)
static

Function*************************************************************

Synopsis [Resizes the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 256 of file nmTable.c.

257 {
258  Nm_Entry_t ** pBinsNewI2N, ** pBinsNewN2I, * pEntry, * pEntry2, ** ppSpot;
259  int nBinsNew, Counter, e;
260  abctime clk;
261 
262 clk = Abc_Clock();
263  // get the new table size
264  nBinsNew = Abc_PrimeCudd( p->nGrowthFactor * p->nBins );
265  // allocate a new array
266  pBinsNewI2N = ABC_ALLOC( Nm_Entry_t *, nBinsNew );
267  pBinsNewN2I = ABC_ALLOC( Nm_Entry_t *, nBinsNew );
268  memset( pBinsNewI2N, 0, sizeof(Nm_Entry_t *) * nBinsNew );
269  memset( pBinsNewN2I, 0, sizeof(Nm_Entry_t *) * nBinsNew );
270  // rehash entries in Id->Name table
271  Counter = 0;
272  for ( e = 0; e < p->nBins; e++ )
273  for ( pEntry = p->pBinsI2N[e], pEntry2 = pEntry? pEntry->pNextI2N : NULL;
274  pEntry; pEntry = pEntry2, pEntry2 = pEntry? pEntry->pNextI2N : NULL )
275  {
276  ppSpot = pBinsNewI2N + Nm_HashNumber(pEntry->ObjId, nBinsNew);
277  pEntry->pNextI2N = *ppSpot;
278  *ppSpot = pEntry;
279  Counter++;
280  }
281  // rehash entries in Name->Id table
282  for ( e = 0; e < p->nBins; e++ )
283  for ( pEntry = p->pBinsN2I[e], pEntry2 = pEntry? pEntry->pNextN2I : NULL;
284  pEntry; pEntry = pEntry2, pEntry2 = pEntry? pEntry->pNextN2I : NULL )
285  {
286  ppSpot = pBinsNewN2I + Nm_HashString(pEntry->Name, nBinsNew);
287  pEntry->pNextN2I = *ppSpot;
288  *ppSpot = pEntry;
289  }
290  assert( Counter == p->nEntries );
291 // printf( "Increasing the structural table size from %6d to %6d. ", p->nBins, nBinsNew );
292 // ABC_PRT( "Time", Abc_Clock() - clk );
293  // replace the table and the parameters
294  ABC_FREE( p->pBinsI2N );
295  ABC_FREE( p->pBinsN2I );
296  p->pBinsI2N = pBinsNewI2N;
297  p->pBinsN2I = pBinsNewN2I;
298  p->nBins = nBinsNew;
299 // Nm_ManProfile( p );
300 }
memset
char * memset()
Abc_PrimeCudd
static int Abc_PrimeCudd(unsigned int p)
Definition: abc_global.h:383
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Nm_Entry_t
typedefABC_NAMESPACE_HEADER_START struct Nm_Entry_t_ Nm_Entry_t
INCLUDES ///.
Definition: nmInt.h:46
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Counter
static int Counter
Definition: extraBddMisc.c:1877
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Nm_HashString
static unsigned Nm_HashString(char *pName, int TableSize)
Definition: nmTable.c:42
assert
#define assert(ex)
Definition: util_old.h:213
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
Nm_HashNumber
static ABC_NAMESPACE_IMPL_START unsigned Nm_HashNumber(int Num, int TableSize)
DECLARATIONS ///.
Definition: nmTable.c:31
int Nm_ManTableAdd ( Nm_Man_t *  p,
Nm_Entry_t *  pEntry 
)

FUNCTION DEFINITIONS ///.

MACRO DEFINITIONS ///.

Function*************************************************************

Synopsis [Adds an entry to two hash tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 71 of file nmTable.c.

72 {
73  Nm_Entry_t ** ppSpot, * pOther;
74  // resize the tables if needed
75  if ( p->nEntries > p->nBins * p->nSizeFactor )
76  Nm_ManResize( p );
77  // add the entry to the table Id->Name
78  assert( Nm_ManTableLookupId(p, pEntry->ObjId) == NULL );
79  ppSpot = p->pBinsI2N + Nm_HashNumber(pEntry->ObjId, p->nBins);
80  pEntry->pNextI2N = *ppSpot;
81  *ppSpot = pEntry;
82  // check if an entry with the same name already exists
83  if ( (pOther = Nm_ManTableLookupName(p, pEntry->Name, -1)) )
84  {
85  // entry with the same name already exists - add it to the ring
86  pEntry->pNameSake = pOther->pNameSake? pOther->pNameSake : pOther;
87  pOther->pNameSake = pEntry;
88  }
89  else
90  {
91  // entry with the same name does not exist - add it to the table
92  ppSpot = p->pBinsN2I + Nm_HashString(pEntry->Name, p->nBins);
93  pEntry->pNextN2I = *ppSpot;
94  *ppSpot = pEntry;
95  }
96  // report successfully added entry
97  p->nEntries++;
98  return 1;
99 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Nm_ManTableLookupName
Nm_Entry_t * Nm_ManTableLookupName(Nm_Man_t *p, char *pName, int Type)
Definition: nmTable.c:191
Nm_Entry_t
typedefABC_NAMESPACE_HEADER_START struct Nm_Entry_t_ Nm_Entry_t
INCLUDES ///.
Definition: nmInt.h:46
Nm_ManTableLookupId
Nm_Entry_t * Nm_ManTableLookupId(Nm_Man_t *p, int ObjId)
Definition: nmTable.c:171
Nm_ManResize
static void Nm_ManResize(Nm_Man_t *p)
Definition: nmTable.c:256
Nm_HashString
static unsigned Nm_HashString(char *pName, int TableSize)
Definition: nmTable.c:42
assert
#define assert(ex)
Definition: util_old.h:213
Nm_HashNumber
static ABC_NAMESPACE_IMPL_START unsigned Nm_HashNumber(int Num, int TableSize)
DECLARATIONS ///.
Definition: nmTable.c:31
int Nm_ManTableDelete ( Nm_Man_t *  p,
int  ObjId 
)

Function*************************************************************

Synopsis [Deletes the entry from two hash tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 112 of file nmTable.c.

113 {
114  Nm_Entry_t ** ppSpot, * pEntry, * pPrev;
115  int fRemoved;
116  p->nEntries--;
117  // remove the entry from the table Id->Name
118  assert( Nm_ManTableLookupId(p, ObjId) != NULL );
119  ppSpot = p->pBinsI2N + Nm_HashNumber(ObjId, p->nBins);
120  while ( (*ppSpot)->ObjId != (unsigned)ObjId )
121  ppSpot = &(*ppSpot)->pNextI2N;
122  pEntry = *ppSpot;
123  *ppSpot = (*ppSpot)->pNextI2N;
124  // remove the entry from the table Name->Id
125  ppSpot = p->pBinsN2I + Nm_HashString(pEntry->Name, p->nBins);
126  while ( *ppSpot && *ppSpot != pEntry )
127  ppSpot = &(*ppSpot)->pNextN2I;
128  // remember if we found this one in the list
129  fRemoved = (*ppSpot != NULL);
130  if ( *ppSpot )
131  {
132  assert( *ppSpot == pEntry );
133  *ppSpot = (*ppSpot)->pNextN2I;
134  }
135  // quit if this entry has no namesakes
136  if ( pEntry->pNameSake == NULL )
137  {
138  assert( fRemoved );
139  return 1;
140  }
141  // remove entry from the ring of namesakes
142  assert( pEntry->pNameSake != pEntry );
143  for ( pPrev = pEntry; pPrev->pNameSake != pEntry; pPrev = pPrev->pNameSake );
144  assert( !strcmp(pPrev->Name, pEntry->Name) );
145  assert( pPrev->pNameSake == pEntry );
146  if ( pEntry->pNameSake == pPrev ) // two entries in the ring
147  pPrev->pNameSake = NULL;
148  else
149  pPrev->pNameSake = pEntry->pNameSake;
150  // reinsert the ring back if we removed its connection with the list in the table
151  if ( fRemoved )
152  {
153  assert( pPrev->pNextN2I == NULL );
154  pPrev->pNextN2I = *ppSpot;
155  *ppSpot = pPrev;
156  }
157  return 1;
158 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Nm_Entry_t
typedefABC_NAMESPACE_HEADER_START struct Nm_Entry_t_ Nm_Entry_t
INCLUDES ///.
Definition: nmInt.h:46
Nm_ManTableLookupId
Nm_Entry_t * Nm_ManTableLookupId(Nm_Man_t *p, int ObjId)
Definition: nmTable.c:171
strcmp
int strcmp()
Nm_HashString
static unsigned Nm_HashString(char *pName, int TableSize)
Definition: nmTable.c:42
assert
#define assert(ex)
Definition: util_old.h:213
Nm_HashNumber
static ABC_NAMESPACE_IMPL_START unsigned Nm_HashNumber(int Num, int TableSize)
DECLARATIONS ///.
Definition: nmTable.c:31
Nm_Entry_t* Nm_ManTableLookupId ( Nm_Man_t *  p,
int  ObjId 
)

Function*************************************************************

Synopsis [Looks up the entry by ID.]

Description []

SideEffects []

SeeAlso []

Definition at line 171 of file nmTable.c.

172 {
173  Nm_Entry_t * pEntry;
174  for ( pEntry = p->pBinsI2N[ Nm_HashNumber(ObjId, p->nBins) ]; pEntry; pEntry = pEntry->pNextI2N )
175  if ( pEntry->ObjId == (unsigned)ObjId )
176  return pEntry;
177  return NULL;
178 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Nm_Entry_t
typedefABC_NAMESPACE_HEADER_START struct Nm_Entry_t_ Nm_Entry_t
INCLUDES ///.
Definition: nmInt.h:46
Nm_HashNumber
static ABC_NAMESPACE_IMPL_START unsigned Nm_HashNumber(int Num, int TableSize)
DECLARATIONS ///.
Definition: nmTable.c:31
Nm_Entry_t* Nm_ManTableLookupName ( Nm_Man_t *  p,
char *  pName,
int  Type 
)

Function*************************************************************

Synopsis [Looks up the entry by name and type.]

Description []

SideEffects []

SeeAlso []

Definition at line 191 of file nmTable.c.

192 {
193  Nm_Entry_t * pEntry, * pTemp;
194  for ( pEntry = p->pBinsN2I[ Nm_HashString(pName, p->nBins) ]; pEntry; pEntry = pEntry->pNextN2I )
195  {
196  // check the entry itself
197  if ( !strcmp(pEntry->Name, pName) && (Type == -1 || pEntry->Type == (unsigned)Type) )
198  return pEntry;
199  // if there is no namesakes, continue
200  if ( pEntry->pNameSake == NULL )
201  continue;
202  // check the list of namesakes
203  for ( pTemp = pEntry->pNameSake; pTemp != pEntry; pTemp = pTemp->pNameSake )
204  if ( !strcmp(pTemp->Name, pName) && (Type == -1 || pTemp->Type == (unsigned)Type) )
205  return pTemp;
206  }
207  return NULL;
208 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Nm_Entry_t
typedefABC_NAMESPACE_HEADER_START struct Nm_Entry_t_ Nm_Entry_t
INCLUDES ///.
Definition: nmInt.h:46
strcmp
int strcmp()
Nm_HashString
static unsigned Nm_HashString(char *pName, int TableSize)
Definition: nmTable.c:42