Version abc71001

5 files changed, 1020 insertions, 0 deletions

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 <stdio.h>
+#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; 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_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 <stdio.h>
+#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; 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_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 <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
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 +=