---

dsHashTable.h

Go to the documentation of this file.

/*
 * $Id: dsHashTable.h,v 1.10 2004/06/03 12:11:47 dsamersoff Exp $
 */

#ifndef dsHashTable_H
#define dsHashTable_H

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif


#ifdef WITH_HASH_STAT
#include <stdio.h>
#endif

#include <dsSmartException.h>
#include <dsDataAccessor.h>

#define HASH_INCREMENT 1024
#define HASH_MAXSIZE 32576


DECLARE_EXCEPTION2(dsHash, dsDataAccessor);



class dsHashTableItem : public dsDataAccessorItem 
{
public:
   dsHashTableItem():
      dsDataAccessorItem(){}

   dsHashTableItem(void *xval):
      dsDataAccessorItem(xval){ }
}; 

typedef dsHashTableItem *dsHashTableItemPtr;

class dsHashTableGeneric : public dsDataAccessor
{ 
     dsHashTableItem **_Table;  // Pointer to table 
     int  _HSize;          // The size of the hash table 

     int GrowUp(void);

     dsHashTableItem* _hi_seek(void *a, int *HIndex );

protected:
   virtual int cf(void * a, void *b)          = 0;  
   virtual int primary_hash_func( void *a)    = 0;
   virtual int secondary_hash_func( void *a)  = 0; 

public:
    dsHashTableGeneric(int numEntries, DACleanupMode purge = cmPURGE);
    virtual ~dsHashTableGeneric();

/* Implementation of dsDataAccessor interfaces 
 */
     virtual void *insert(void *a, bool replace = false );
     virtual void *remove(void *a);
     virtual void *seek(void *a); 

     void clear();
     void *walk(int i);

     int HSize(void); 

     int NumEntries(void);


#ifdef WITH_HASH_STAT
     long n_computation;
     long n_cmps;
     long n_grows;
     long n_repeats;

     void print_stat()
      {
        printf("Table size:         %ld\n",HSize());
        printf("Table entries:      %ld\n",NumEntries() );
        printf("\nWarning! All Library should be compiled with -DWITH_HASH_STAT\n");
        printf("Hash computation:   %ld\n",n_computation);
        printf("String comparisons: %ld\n",n_cmps);
        printf("String repeats:     %ld\n",n_repeats);
        printf("Table resizing:     %ld\n",n_grows);
      }
#endif

}; 

inline int dsHashTableGeneric::HSize(void) 
{
        return _HSize; 
}
     
inline void *dsHashTableGeneric::walk(int i)
{
  if (i > _HSize)
       throw dsHashException("Index out of bounds");

  return (_Table[i]) ? _Table[i]->body : 0;
}

inline int dsHashTableGeneric::NumEntries(void) 
{ 
   int total=0; 

   for (int i=0; i < _HSize; i++) 
   {
           if (_Table[i]) total++; 
   }

   return total; 
} 




class dsHashTable : public dsHashTableGeneric
{

  int HFuncAddition( const char *key ); // Hash function using Addition method 
  int HFuncHorner( const char *key );   // Hash function using horner's method 
  const char *key(void *a)                  { return ((dsDataPair *)a)->key;  }
 
protected:
   virtual int cf(void * a, void *b)         { return strcmp(key(a), key(b));  }
   virtual int primary_hash_func( void *a)   { return HFuncAddition( key(a) ); }
   virtual int secondary_hash_func( void *a) { return HFuncHorner( key(a) );   }

public:
   dsHashTable(int numEntries, DACleanupMode purge = cmPURGE):
       dsHashTableGeneric(numEntries,purge){}

   /* convenience interfaces */
   char *      seek(const char *key, char *defval = 0);

   dsDataPair *seek(dsDataPair *dp);

   void *insert(const char *key, void *value, bool replace = false);
   void *insert(const char *key, const void *value, size_t size, bool replace = false);

   char *insert(const char *key, const char * value, bool replace = false);
   long  insert(const char *key, long value, bool replace = false);

   dsDataPair *insert(dsDataPair *dp, bool replace = false);
};  

/* convenience interfaces */

inline  dsDataPair * dsHashTable::seek(dsDataPair *dp)
{ 
    return (dsDataPair *) dsHashTableGeneric::seek((void *)dp); 
}

inline dsDataPair *dsHashTable::insert(dsDataPair *dp, bool replace)
{ 
    return (dsDataPair *) dsHashTableGeneric::insert((void *)dp, replace);
}

inline  char * dsHashTable::seek(const char *xkey, char *defval)
{
    dsDataPair dp(xkey); 
    dsDataPair *tmp = seek(&dp); 
    return (tmp) ? (char *) (tmp->val) : defval; 
}


inline void *dsHashTable::insert(const char *key, void *value, bool replace)
{
   dsDataPair *hi  = new dsDataPair(key, value);
   dsDataPair *tmp = insert(hi, replace);
   if (tmp)
   { if (!replace)
            delete hi;
      return tmp->val;
   }

   return 0;
}

inline void *dsHashTable::insert(const char *key, const void *value, size_t size, bool replace)
{
   dsDataPair *hi  = new dsDataPair(key, value, size);
   dsDataPair *tmp = insert(hi, replace);
   if (tmp)
   { if (!replace)
            delete hi;
      return tmp->val;
   }

   return 0;
}


inline char *dsHashTable::insert(const char *key, const char * value, bool replace)
{
   dsDataPair *hi  = new dsDataPair(key, value);
   dsDataPair *tmp = insert(hi, replace);
   if (tmp)
   { if (!replace)
            delete hi;
      return (char *)tmp->val;
   }

   return 0;
}

inline long dsHashTable::insert(const char *key, long value, bool replace)
{
   dsDataPair *hi  = new dsDataPair(key, &value, sizeof(value) );
   dsDataPair *tmp = insert(hi, replace);
   if (tmp)
   { if (!replace)
            delete hi;
      return *((long *)(tmp->val));
   }

   return 0;
}



#endif 

---