diff options
Diffstat (limited to 'src/misc/hash')
-rw-r--r-- | src/misc/hash/hashGen.h | 365 |
1 files changed, 365 insertions, 0 deletions
diff --git a/src/misc/hash/hashGen.h b/src/misc/hash/hashGen.h new file mode 100644 index 00000000..33359e89 --- /dev/null +++ b/src/misc/hash/hashGen.h @@ -0,0 +1,365 @@ +/**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 $] + +***********************************************************************/ + +#ifndef __HASH_GEN_H__ +#define __HASH_GEN_H__ + + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#include <stdio.h> +#include "extra.h" + +ABC_NAMESPACE_HEADER_START + + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// BASIC TYPES /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Hash_Gen_t_ Hash_Gen_t; +typedef struct Hash_Gen_Entry_t_ Hash_Gen_Entry_t; + +struct Hash_Gen_Entry_t_ +{ + char * key; + void * data; + struct Hash_Gen_Entry_t_ * pNext; +}; + +struct Hash_Gen_t_ +{ + int nSize; + int nBins; + int (* fHash)(void *key, int nBins); + int (* fComp)(void *key, void *data); + int fFreeKey; + Hash_Gen_Entry_t ** pArray; +}; + + + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +#define Hash_GenForEachEntry( pHash, pEntry, bin ) \ + for(bin=-1, pEntry=NULL; bin < pHash->nBins; (!pEntry)?(pEntry=pHash->pArray[++bin]):(pEntry=pEntry->pNext)) \ + if (pEntry) + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Default hash function for strings.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static int Hash_DefaultHashFuncStr( void * key, int nBins ) +{ + char* p = (const char*)key; + int h=0; + + for( ; *p ; ++p ) + h += h*5 + *p; + + return (unsigned)h % nBins; +} + +static int Hash_DefaultCmpFuncStr( void * key1, void * key2 ) +{ + return strcmp((const char*)key1, (const char*) key2); +} + +/**Function************************************************************* + + Synopsis [Default hash function for (long) integers.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static int Hash_DefaultHashFuncInt( void * key, int nBins ) +{ + return (long)key % nBins; +} + +/**Function************************************************************* + + Synopsis [Default comparison function for (long) integers.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static int Hash_DefaultCmpFuncInt( void * key1, void* key2 ) +{ + return (long)key1 - (long)key2; +} + +/**Function************************************************************* + + Synopsis [Allocates a hash map with the given number of bins.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Hash_Gen_t * Hash_GenAlloc( + int nBins, + int (*Hash_FuncHash)(void *, int), + int (*Hash_FuncComp)(void *, void *), + int fFreeKey) +{ + Hash_Gen_t * p; + int i; + assert(nBins > 0); + p = ABC_CALLOC( Hash_Gen_t, 1 ); + p->nBins = nBins; + p->fHash = Hash_FuncHash? Hash_FuncHash : (int (*)(void *, int))Hash_DefaultHashFuncStr; + p->fComp = Hash_FuncComp? Hash_FuncComp : (int (*)(void *, void *))Hash_DefaultCmpFuncStr; + p->fFreeKey = fFreeKey; + p->nSize = 0; + p->pArray = ABC_CALLOC( Hash_Gen_Entry_t *, nBins ); + return p; +} + +/**Function************************************************************* + + Synopsis [Returns 1 if a key already exists.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Hash_GenExists( Hash_Gen_t *p, void * key ) +{ + int bin; + Hash_Gen_Entry_t *pEntry; + + // find the bin where this key would live + bin = (*(p->fHash))(key, p->nBins); + + // search for key + pEntry = p->pArray[bin]; + while(pEntry) { + if ( !p->fComp(pEntry->key,key) ) { + return 1; + } + pEntry = pEntry->pNext; + } + + return 0; +} + +/**Function************************************************************* + + Synopsis [Finds or creates an entry with a key and writes value.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Hash_GenWriteEntry( Hash_Gen_t *p, void * key, void * data ) +{ + int bin; + Hash_Gen_Entry_t *pEntry, **pLast; + + // find the bin where this key would live + bin = (*(p->fHash))(key, p->nBins); + + // search for key + pLast = &(p->pArray[bin]); + pEntry = p->pArray[bin]; + while(pEntry) { + if ( !p->fComp(pEntry->key,key) ) { + pEntry->data = data; + return; + } + pLast = &(pEntry->pNext); + pEntry = pEntry->pNext; + } + + // this key does not currently exist + // create a new entry and add to bin + p->nSize++; + (*pLast) = pEntry = ABC_ALLOC( Hash_Gen_Entry_t, 1 ); + pEntry->pNext = NULL; + pEntry->key = key; + pEntry->data = data; + + return; +} + + +/**Function************************************************************* + + Synopsis [Finds or creates an entry with a key.] + + Description [fCreate specifies whether a new entry should be created.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Hash_Gen_Entry_t * Hash_GenEntry( Hash_Gen_t *p, void * key, int fCreate ) +{ + int bin; + Hash_Gen_Entry_t *pEntry, **pLast; + + // find the bin where this key would live + bin = (*(p->fHash))(key, p->nBins); + + // search for key + pLast = &(p->pArray[bin]); + pEntry = p->pArray[bin]; + while(pEntry) { + if ( !p->fComp(pEntry->key,key) ) + return pEntry; + pLast = &(pEntry->pNext); + pEntry = pEntry->pNext; + } + + // this key does not currently exist + if (fCreate) { + // create a new entry and add to bin + p->nSize++; + (*pLast) = pEntry = ABC_ALLOC( Hash_Gen_Entry_t, 1 ); + pEntry->pNext = NULL; + pEntry->key = key; + pEntry->data = NULL; + return pEntry; + } + + return NULL; +} + +/**Function************************************************************* + + Synopsis [Deletes an entry.] + + Description [Returns data, if there was any.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void* Hash_GenRemove( Hash_Gen_t *p, void * key ) +{ + int bin; + void * data; + Hash_Gen_Entry_t *pEntry, **pLast; + + // find the bin where this key would live + bin = (*(p->fHash))(key, p->nBins); + + // search for key + pLast = &(p->pArray[bin]); + pEntry = p->pArray[bin]; + while(pEntry) { + if ( !p->fComp(pEntry->key,key) ) { + p->nSize--; + data = pEntry->data; + *pLast = pEntry->pNext; + if (p->fFreeKey) + ABC_FREE(pEntry->key); + ABC_FREE(pEntry); + return data; + } + pLast = &(pEntry->pNext); + pEntry = pEntry->pNext; + } + + // could not find key + return NULL; +} + +/**Function************************************************************* + + Synopsis [Frees the hash.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Hash_GenFree( Hash_Gen_t *p ) +{ + int bin; + Hash_Gen_Entry_t *pEntry, *pTemp; + + // free bins + for(bin = 0; bin < p->nBins; bin++) { + pEntry = p->pArray[bin]; + while(pEntry) { + pTemp = pEntry; + if( p->fFreeKey ) + ABC_FREE(pTemp->key); + pEntry = pEntry->pNext; + ABC_FREE( pTemp ); + } + } + + // free hash + ABC_FREE( p->pArray ); + ABC_FREE( p ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + + +ABC_NAMESPACE_HEADER_END + +#endif |