From 0c6505a26a537dc911b6566f82d759521e527c08 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 30 Jan 2008 20:01:00 -0800 Subject: Version abc80130_2 --- src/misc/hash/hash.h | 65 +++++++++ src/misc/hash/hashFlt.h | 330 +++++++++++++++++++++++++++++++++++++++++++++ src/misc/hash/hashInt.h | 293 ++++++++++++++++++++++++++++++++++++++++ src/misc/hash/hashPtr.h | 331 ++++++++++++++++++++++++++++++++++++++++++++++ src/misc/hash/module.make | 1 + 5 files changed, 1020 insertions(+) create mode 100644 src/misc/hash/hash.h create mode 100644 src/misc/hash/hashFlt.h create mode 100644 src/misc/hash/hashInt.h create mode 100644 src/misc/hash/hashPtr.h create mode 100644 src/misc/hash/module.make (limited to 'src/misc/hash') diff --git a/src/misc/hash/hash.h b/src/misc/hash/hash.h new file mode 100644 index 00000000..90e72868 --- /dev/null +++ b/src/misc/hash/hash.h @@ -0,0 +1,65 @@ +/**CFile**************************************************************** + + FileName [hash.h] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Hash map.] + + Synopsis [External declarations.] + + Author [Aaron P. Hurst] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - May 16, 2005.] + + Revision [$Id: vec.h,v 1.00 2005/06/20 00:00:00 ahurst Exp $] + +***********************************************************************/ + +#ifndef __HASH_H__ +#define __HASH_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#ifdef _WIN32 +#define inline __inline // compatible with MS VS 6.0 +#endif + +#include "hashInt.h" +#include "hashFlt.h" +#include "hashPtr.h" + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// BASIC TYPES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +#ifndef ABS +#define ABS(a) ((a) < 0 ? -(a) : (a)) +#endif + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +int Hash_DefaultHashFunc(int key, int nBins) { + return ABS( ( (key+11)*(key)*7+3 ) % nBins ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + +#endif + diff --git a/src/misc/hash/hashFlt.h b/src/misc/hash/hashFlt.h new file mode 100644 index 00000000..da20ee28 --- /dev/null +++ b/src/misc/hash/hashFlt.h @@ -0,0 +1,330 @@ +/**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_FLT_H__ +#define __HASH_FLT_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#include +#include "extra.h" + +extern int Hash_DefaultHashFunc(int key, int nBins); + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// BASIC TYPES /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Hash_Flt_t_ Hash_Flt_t; +typedef struct Hash_Flt_Entry_t_ Hash_Flt_Entry_t; + +struct Hash_Flt_Entry_t_ +{ + int key; + float data; + struct Hash_Flt_Entry_t_ * pNext; +}; + +struct Hash_Flt_t_ +{ + int nSize; + int nBins; + int (* fHash)(int key, int nBins); + Hash_Flt_Entry_t ** pArray; +}; + + + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +#define Hash_FltForEachEntry( 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_Flt_t * Hash_FltAlloc( int nBins ) +{ + Hash_Flt_t * p; + int i; + assert(nBins > 0); + p = ALLOC( Hash_Flt_t, 1); + p->nBins = nBins; + p->fHash = Hash_DefaultHashFunc; + p->nSize = 0; + p->pArray = ALLOC( Hash_Flt_Entry_t *, nBins ); + for(i=0; ipArray[i] = NULL; + + return p; +} + +/**Function************************************************************* + + Synopsis [Returns 1 if a key already exists.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Hash_FltExists( Hash_Flt_t *p, int key ) +{ + int bin; + Hash_Flt_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_FltWriteEntry( Hash_Flt_t *p, int key, float data ) +{ + int bin; + Hash_Flt_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_Flt_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 new entries should be created.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline float Hash_FltEntry( Hash_Flt_t *p, int key, int fCreate ) +{ + int bin; + Hash_Flt_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_Flt_Entry_t, 1 ); + pEntry->pNext = NULL; + pEntry->key = key; + pEntry->data = 0.0; + return pEntry->data; + } + + return 0.0; +} + + +/**Function************************************************************* + + Synopsis [Finds or creates an entry with a key and returns the pointer to it.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline float* Hash_FltEntryPtr( Hash_Flt_t *p, int key ) +{ + int bin; + Hash_Flt_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_Flt_Entry_t, 1 ); + pEntry->pNext = NULL; + pEntry->key = key; + pEntry->data = 0.0; + + return &(pEntry->data); +} + +/**Function************************************************************* + + Synopsis [Deletes an entry.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Hash_FltRemove( Hash_Flt_t *p, int key ) +{ + int bin; + Hash_Flt_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--; + *pLast = pEntry->pNext; + FREE( pEntry ); + return; + } + pLast = &(pEntry->pNext); + pEntry = pEntry->pNext; + } + + // could not find key + return; +} + +/**Function************************************************************* + + Synopsis [Frees the hash.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Hash_FltFree( Hash_Flt_t *p ) { + int bin; + Hash_Flt_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 diff --git a/src/misc/hash/hashInt.h b/src/misc/hash/hashInt.h new file mode 100644 index 00000000..3b91f5df --- /dev/null +++ b/src/misc/hash/hashInt.h @@ -0,0 +1,293 @@ +/**CFile**************************************************************** + + FileName [hashInt.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_INT_H__ +#define __HASH_INT_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#include +#include "extra.h" + +extern int Hash_DefaultHashFunc(int key, int nBins); + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// BASIC TYPES /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Hash_Int_t_ Hash_Int_t; +typedef struct Hash_Int_Entry_t_ Hash_Int_Entry_t; + +struct Hash_Int_Entry_t_ +{ + int key; + int data; + struct Hash_Int_Entry_t_ * pNext; +}; + +struct Hash_Int_t_ +{ + int nSize; + int nBins; + int (* fHash)(int key, int nBins); + Hash_Int_Entry_t ** pArray; +}; + + + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +#define Hash_IntForEachEntry( 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_Int_t * Hash_IntAlloc( int nBins ) +{ + Hash_Int_t * p; + int i; + assert(nBins > 0); + p = ALLOC( Hash_Int_t, 1); + p->nBins = nBins; + p->fHash = Hash_DefaultHashFunc; + p->nSize = 0; + p->pArray = ALLOC( Hash_Int_Entry_t *, nBins ); + for(i=0; ipArray[i] = NULL; + + return p; +} + +/**Function************************************************************* + + Synopsis [Returns 1 if a key already exists.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Hash_IntExists( Hash_Int_t *p, int key) +{ + int bin; + Hash_Int_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_IntWriteEntry( Hash_Int_t *p, int key, int data ) +{ + int bin; + Hash_Int_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_Int_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 new entries will be created.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Hash_IntEntry( Hash_Int_t *p, int key, int fCreate ) +{ + int bin; + Hash_Int_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_Int_Entry_t, 1 ); + pEntry->pNext = NULL; + pEntry->key = key; + pEntry->data = 0; + return pEntry->data; + } + + return 0; +} + + +/**Function************************************************************* + + Synopsis [Finds or creates an entry with a key and returns the pointer to it.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int* Hash_IntEntryPtr( Hash_Int_t *p, int key ) +{ + int bin; + Hash_Int_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_Int_Entry_t, 1 ); + pEntry->pNext = NULL; + pEntry->key = key; + pEntry->data = 0; + + return &(pEntry->data); +} + +/**Function************************************************************* + + Synopsis [Frees the hash.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Hash_IntFree( Hash_Int_t *p ) { + int bin; + Hash_Int_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 diff --git a/src/misc/hash/hashPtr.h b/src/misc/hash/hashPtr.h new file mode 100644 index 00000000..15398a8a --- /dev/null +++ b/src/misc/hash/hashPtr.h @@ -0,0 +1,331 @@ +/**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 +#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; ipArray[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 diff --git a/src/misc/hash/module.make b/src/misc/hash/module.make new file mode 100644 index 00000000..d6d908e7 --- /dev/null +++ b/src/misc/hash/module.make @@ -0,0 +1 @@ +SRC += -- cgit v1.2.3