abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Data Structures | Macros | Typedefs | Functions
hashGen.h File Reference
#include <stdio.h>
#include "misc/extra/extra.h"

Go to the source code of this file.

Data Structures

struct  Hash_Gen_Entry_t_
 
struct  Hash_Gen_t_
 

Macros

#define Hash_GenForEachEntry(pHash, pEntry, bin)
 MACRO DEFINITIONS ///. More...
 

Typedefs

typedef
typedefABC_NAMESPACE_HEADER_START
struct Hash_Gen_t_ 		Hash_Gen_t
 INCLUDES ///. More...
 
typedef struct Hash_Gen_Entry_t_ Hash_Gen_Entry_t
 
typedef int(* Hash_GenHashFunction_t )(void *key, int nBins)
 
typedef int(* Hash_GenCompFunction_t )(void *key, void *data)
 

Functions

static int Hash_DefaultHashFuncStr (void *key, int nBins)
 FUNCTION DEFINITIONS ///. More...
 
static int Hash_DefaultCmpFuncStr (void *key1, void *key2)
 
static int Hash_DefaultHashFuncInt (void *key, int nBins)
 
static int Hash_DefaultCmpFuncInt (void *key1, void *key2)
 
static Hash_Gen_t * Hash_GenAlloc (int nBins, int(*Hash_FuncHash)(void *, int), int(*Hash_FuncComp)(void *, void *), int fFreeKey)
 
static int Hash_GenExists (Hash_Gen_t *p, void *key)
 
static void Hash_GenWriteEntry (Hash_Gen_t *p, void *key, void *data)
 
static Hash_Gen_Entry_t * Hash_GenEntry (Hash_Gen_t *p, void *key, int fCreate)
 
static void * Hash_GenRemove (Hash_Gen_t *p, void *key)
 
static void Hash_GenFree (Hash_Gen_t *p)
 

Macro Definition Documentation

#define Hash_GenForEachEntry (   pHash,
  pEntry,
  bin 
)
Value:
for(bin=-1, pEntry=NULL; bin < pHash->nBins; (!pEntry)?(pEntry=pHash->pArray[++bin]):(pEntry=pEntry->pNext)) \
if (pEntry)
if
if(last==0)
Definition: sparse_int.h:34

MACRO DEFINITIONS ///.

Definition at line 72 of file hashGen.h.

Typedef Documentation

typedef struct Hash_Gen_Entry_t_ Hash_Gen_Entry_t

Definition at line 44 of file hashGen.h.

typedef typedefABC_NAMESPACE_HEADER_START struct Hash_Gen_t_ Hash_Gen_t

INCLUDES ///.

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

FileName [vecGen.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Hash maps.]

Synopsis [Hash maps.]

Author [Aaron P. Hurst, Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - Jan 26, 2011.]

Revision [

Id:
vecGen.h,v 1.00 2005/06/20 00:00:00 ahurst Exp

]PARAMETERS ///BASIC TYPES ///

Definition at line 43 of file hashGen.h.

typedef int(* Hash_GenCompFunction_t)(void *key, void *data)

Definition at line 54 of file hashGen.h.

typedef int(* Hash_GenHashFunction_t)(void *key, int nBins)

Definition at line 53 of file hashGen.h.

Function Documentation

static int Hash_DefaultCmpFuncInt ( void *  key1,
void *  key2 
)
static

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

Synopsis [Default comparison function for (long) integers.]

Description []

SideEffects []

SeeAlso []

Definition at line 134 of file hashGen.h.

135 {
136  return (long)key1 - (long)key2;
137 }
static int Hash_DefaultCmpFuncStr ( void *  key1,
void *  key2 
)
static

Definition at line 102 of file hashGen.h.

103 {
104  return strcmp((const char*)key1, (const char*) key2);
105 }
strcmp
int strcmp()
static int Hash_DefaultHashFuncInt ( void *  key,
int  nBins 
)
static

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

Synopsis [Default hash function for (long) integers.]

Description []

SideEffects []

SeeAlso []

Definition at line 118 of file hashGen.h.

119 {
120  return (long)key % nBins;
121 }
key
enum keys key
Definition: misc/espresso/main.h:25
static int Hash_DefaultHashFuncStr ( void *  key,
int  nBins 
)
static

FUNCTION DEFINITIONS ///.

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

Synopsis [Default hash function for strings.]

Description []

SideEffects []

SeeAlso []

Definition at line 91 of file hashGen.h.

92 {
93  const char* p = (const char*)key;
94  int h=0;
95 
96  for( ; *p ; ++p )
97  h += h*5 + *p;
98 
99  return (unsigned)h % nBins;
100 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
key
enum keys key
Definition: misc/espresso/main.h:25
static Hash_Gen_t* Hash_GenAlloc ( int  nBins,
int(*)(void *, int)  Hash_FuncHash,
int(*)(void *, void *)  Hash_FuncComp,
int  fFreeKey 
)
inlinestatic

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

Synopsis [Allocates a hash map with the given number of bins.]

Description []

SideEffects []

SeeAlso []

Definition at line 150 of file hashGen.h.

155 {
156  Hash_Gen_t * p;
157  assert(nBins > 0);
158  p = ABC_CALLOC( Hash_Gen_t, 1 );
159  p->nBins = nBins;
160  p->fHash = Hash_FuncHash? Hash_FuncHash : (int (*)(void *, int))Hash_DefaultHashFuncStr;
161  p->fComp = Hash_FuncComp? Hash_FuncComp : (int (*)(void *, void *))Hash_DefaultCmpFuncStr;
162  p->fFreeKey = fFreeKey;
163  p->nSize = 0;
164  p->pArray = ABC_CALLOC( Hash_Gen_Entry_t *, nBins );
165  return p;
166 }
Hash_DefaultHashFuncStr
static int Hash_DefaultHashFuncStr(void *key, int nBins)
FUNCTION DEFINITIONS ///.
Definition: hashGen.h:91
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Hash_DefaultCmpFuncStr
static int Hash_DefaultCmpFuncStr(void *key1, void *key2)
Definition: hashGen.h:102
Hash_Gen_t
typedefABC_NAMESPACE_HEADER_START struct Hash_Gen_t_ Hash_Gen_t
INCLUDES ///.
Definition: hashGen.h:43
ABC_CALLOC
#define ABC_CALLOC(type, num)
Definition: abc_global.h:230
assert
#define assert(ex)
Definition: util_old.h:213
Hash_Gen_Entry_t_
Definition: hashGen.h:46
static Hash_Gen_Entry_t* Hash_GenEntry ( Hash_Gen_t *  p,
void *  key,
int  fCreate 
)
inlinestatic

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

Synopsis [Finds or creates an entry with a key.]

Description [fCreate specifies whether a new entry should be created.]

SideEffects []

SeeAlso []

Definition at line 253 of file hashGen.h.

254 {
255  int bin;
256  Hash_Gen_Entry_t *pEntry, **pLast;
257 
258  // find the bin where this key would live
259  bin = (*(p->fHash))(key, p->nBins);
260 
261  // search for key
262  pLast = &(p->pArray[bin]);
263  pEntry = p->pArray[bin];
264  while(pEntry) {
265  if ( !p->fComp(pEntry->key,key) )
266  return pEntry;
267  pLast = &(pEntry->pNext);
268  pEntry = pEntry->pNext;
269  }
270 
271  // this key does not currently exist
272  if (fCreate) {
273  // create a new entry and add to bin
274  p->nSize++;
275  (*pLast) = pEntry = ABC_ALLOC( Hash_Gen_Entry_t, 1 );
276  pEntry->pNext = NULL;
277  pEntry->key = (char *)key;
278  pEntry->data = NULL;
279  return pEntry;
280  }
281 
282  return NULL;
283 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Hash_Gen_Entry_t_::key
char * key
Definition: hashGen.h:48
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Hash_Gen_Entry_t_::data
void * data
Definition: hashGen.h:49
key
enum keys key
Definition: misc/espresso/main.h:25
Hash_Gen_Entry_t_
Definition: hashGen.h:46
Hash_Gen_Entry_t_::pNext
struct Hash_Gen_Entry_t_ * pNext
Definition: hashGen.h:50
static int Hash_GenExists ( Hash_Gen_t *  p,
void *  key 
)
inlinestatic

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

Synopsis [Returns 1 if a key already exists.]

Description []

SideEffects []

SeeAlso []

Definition at line 179 of file hashGen.h.

180 {
181  int bin;
182  Hash_Gen_Entry_t *pEntry;
183 
184  // find the bin where this key would live
185  bin = (*(p->fHash))(key, p->nBins);
186 
187  // search for key
188  pEntry = p->pArray[bin];
189  while(pEntry) {
190  if ( !p->fComp(pEntry->key,key) ) {
191  return 1;
192  }
193  pEntry = pEntry->pNext;
194  }
195 
196  return 0;
197 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Hash_Gen_Entry_t_::key
char * key
Definition: hashGen.h:48
key
enum keys key
Definition: misc/espresso/main.h:25
Hash_Gen_Entry_t_
Definition: hashGen.h:46
Hash_Gen_Entry_t_::pNext
struct Hash_Gen_Entry_t_ * pNext
Definition: hashGen.h:50
static void Hash_GenFree ( Hash_Gen_t *  p)
inlinestatic

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

Synopsis [Frees the hash.]

Description []

SideEffects []

SeeAlso []

Definition at line 337 of file hashGen.h.

338 {
339  int bin;
340  Hash_Gen_Entry_t *pEntry, *pTemp;
341 
342  // free bins
343  for(bin = 0; bin < p->nBins; bin++) {
344  pEntry = p->pArray[bin];
345  while(pEntry) {
346  pTemp = pEntry;
347  if( p->fFreeKey )
348  ABC_FREE(pTemp->key);
349  pEntry = pEntry->pNext;
350  ABC_FREE( pTemp );
351  }
352  }
353 
354  // free hash
355  ABC_FREE( p->pArray );
356  ABC_FREE( p );
357 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Hash_Gen_Entry_t_::key
char * key
Definition: hashGen.h:48
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Hash_Gen_Entry_t_
Definition: hashGen.h:46
Hash_Gen_Entry_t_::pNext
struct Hash_Gen_Entry_t_ * pNext
Definition: hashGen.h:50
static void* Hash_GenRemove ( Hash_Gen_t *  p,
void *  key 
)
inlinestatic

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

Synopsis [Deletes an entry.]

Description [Returns data, if there was any.]

SideEffects []

SeeAlso []

Definition at line 296 of file hashGen.h.

297 {
298  int bin;
299  void * data;
300  Hash_Gen_Entry_t *pEntry, **pLast;
301 
302  // find the bin where this key would live
303  bin = (*(p->fHash))(key, p->nBins);
304 
305  // search for key
306  pLast = &(p->pArray[bin]);
307  pEntry = p->pArray[bin];
308  while(pEntry) {
309  if ( !p->fComp(pEntry->key,key) ) {
310  p->nSize--;
311  data = pEntry->data;
312  *pLast = pEntry->pNext;
313  if (p->fFreeKey)
314  ABC_FREE(pEntry->key);
315  ABC_FREE(pEntry);
316  return data;
317  }
318  pLast = &(pEntry->pNext);
319  pEntry = pEntry->pNext;
320  }
321 
322  // could not find key
323  return NULL;
324 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Hash_Gen_Entry_t_::key
char * key
Definition: hashGen.h:48
Hash_Gen_Entry_t_::data
void * data
Definition: hashGen.h:49
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
key
enum keys key
Definition: misc/espresso/main.h:25
Hash_Gen_Entry_t_
Definition: hashGen.h:46
Hash_Gen_Entry_t_::pNext
struct Hash_Gen_Entry_t_ * pNext
Definition: hashGen.h:50
static void Hash_GenWriteEntry ( Hash_Gen_t *  p,
void *  key,
void *  data 
)
inlinestatic

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

Synopsis [Finds or creates an entry with a key and writes value.]

Description []

SideEffects []

SeeAlso []

Definition at line 210 of file hashGen.h.

211 {
212  int bin;
213  Hash_Gen_Entry_t *pEntry, **pLast;
214 
215  // find the bin where this key would live
216  bin = (*(p->fHash))(key, p->nBins);
217 
218  // search for key
219  pLast = &(p->pArray[bin]);
220  pEntry = p->pArray[bin];
221  while(pEntry) {
222  if ( !p->fComp(pEntry->key,key) ) {
223  pEntry->data = data;
224  return;
225  }
226  pLast = &(pEntry->pNext);
227  pEntry = pEntry->pNext;
228  }
229 
230  // this key does not currently exist
231  // create a new entry and add to bin
232  p->nSize++;
233  (*pLast) = pEntry = ABC_ALLOC( Hash_Gen_Entry_t, 1 );
234  pEntry->pNext = NULL;
235  pEntry->key = (char *)key;
236  pEntry->data = data;
237 
238  return;
239 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Hash_Gen_Entry_t_::key
char * key
Definition: hashGen.h:48
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Hash_Gen_Entry_t_::data
void * data
Definition: hashGen.h:49
key
enum keys key
Definition: misc/espresso/main.h:25
Hash_Gen_Entry_t_
Definition: hashGen.h:46
Hash_Gen_Entry_t_::pNext
struct Hash_Gen_Entry_t_ * pNext
Definition: hashGen.h:50