diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 08:01:00 -0800 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 08:01:00 -0800 |
commit | 4d30a1e4f1edecff86d5066ce4653a370e59e5e1 (patch) | |
tree | 366355938a4af0a92f848841ac65374f338d691b /src/misc/hash/hashPtr.h | |
parent | 6537f941887b06e588d3acfc97b5fdf48875cc4e (diff) | |
download | abc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.tar.gz abc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.tar.bz2 abc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.zip |
Version abc80130
Diffstat (limited to 'src/misc/hash/hashPtr.h')
-rw-r--r-- | src/misc/hash/hashPtr.h | 331 |
1 files changed, 0 insertions, 331 deletions
diff --git a/src/misc/hash/hashPtr.h b/src/misc/hash/hashPtr.h deleted file mode 100644 index 15398a8a..00000000 --- a/src/misc/hash/hashPtr.h +++ /dev/null @@ -1,331 +0,0 @@ -/**CFile**************************************************************** - - FileName [hashFlt.h] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Hash maps.] - - Synopsis [Hash maps.] - - Author [Aaron P. Hurst] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - May 16, 2006.] - - Revision [$Id: vecInt.h,v 1.00 2005/06/20 00:00:00 ahurst Exp $] - -***********************************************************************/ - -#ifndef __HASH_PTR_H__ -#define __HASH_PTR_H__ - -//////////////////////////////////////////////////////////////////////// -/// INCLUDES /// -//////////////////////////////////////////////////////////////////////// - -#include <stdio.h> -#include "extra.h" - -extern int Hash_DefaultHashFunc(int key, int nBins); - -//////////////////////////////////////////////////////////////////////// -/// PARAMETERS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// BASIC TYPES /// -//////////////////////////////////////////////////////////////////////// - -typedef struct Hash_Ptr_t_ Hash_Ptr_t; -typedef struct Hash_Ptr_Entry_t_ Hash_Ptr_Entry_t; - -struct Hash_Ptr_Entry_t_ -{ - int key; - void * data; - struct Hash_Ptr_Entry_t_ * pNext; -}; - -struct Hash_Ptr_t_ -{ - int nSize; - int nBins; - int (* fHash)(int key, int nBins); - Hash_Ptr_Entry_t ** pArray; -}; - - - -//////////////////////////////////////////////////////////////////////// -/// MACRO DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -#define Hash_PtrForEachEntry( 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 [Allocates a hash map with the given number of bins.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline Hash_Ptr_t * Hash_PtrAlloc( int nBins ) -{ - Hash_Ptr_t * p; - int i; - assert(nBins > 0); - p = ALLOC( Hash_Ptr_t, 1); - p->nBins = nBins; - p->fHash = Hash_DefaultHashFunc; - p->nSize = 0; - p->pArray = ALLOC( Hash_Ptr_Entry_t *, nBins ); - for(i=0; i<nBins; i++) - p->pArray[i] = NULL; - - return p; -} - -/**Function************************************************************* - - Synopsis [Returns 1 if a key already exists.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int Hash_PtrExists( Hash_Ptr_t *p, int key ) -{ - int bin; - Hash_Ptr_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 (pEntry->key == key) { - return 1; - } - pLast = &(pEntry->pNext); - 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_PtrWriteEntry( Hash_Ptr_t *p, int key, void * data ) -{ - int bin; - Hash_Ptr_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 (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 = ALLOC( Hash_Ptr_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 void * Hash_PtrEntry( Hash_Ptr_t *p, int key, int fCreate ) -{ - int bin; - Hash_Ptr_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 (pEntry->key == key) - return pEntry->data; - 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 = ALLOC( Hash_Ptr_Entry_t, 1 ); - pEntry->pNext = NULL; - pEntry->key = key; - pEntry->data = NULL; - return pEntry->data; - } - - return NULL; -} - - -/**Function************************************************************* - - Synopsis [Finds or creates an entry with a key and returns the pointer to it.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline void** Hash_PtrEntryPtr( Hash_Ptr_t *p, int key ) -{ - int bin; - Hash_Ptr_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 (pEntry->key == key) - return &(pEntry->data); - pLast = &(pEntry->pNext); - pEntry = pEntry->pNext; - } - - // this key does not currently exist - // create a new entry and add to bin - p->nSize++; - (*pLast) = pEntry = ALLOC( Hash_Ptr_Entry_t, 1 ); - pEntry->pNext = NULL; - pEntry->key = key; - pEntry->data = NULL; - - return &(pEntry->data); -} - -/**Function************************************************************* - - Synopsis [Deletes an entry.] - - Description [Returns data, if there was any.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline void* Hash_PtrRemove( Hash_Ptr_t *p, int key ) -{ - int bin; - void * data; - Hash_Ptr_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 (pEntry->key == key) { - p->nSize--; - data = pEntry->data; - *pLast = pEntry->pNext; - 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_PtrFree( Hash_Ptr_t *p ) { - int bin; - Hash_Ptr_Entry_t *pEntry; - - // free bins - for(bin = 0; bin < p->nBins; bin++) { - pEntry = p->pArray[bin]; - while(pEntry) { - pEntry = pEntry->pNext; - FREE( pEntry ); - } - } - - // free hash - FREE( p->pArray ); - FREE( p ); -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - -#endif |