home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / grafik / cgazv5n3 / dynhash.hpp < prev    next >
Encoding:
C/C++ Source or Header  |  1991-02-28  |  3.3 KB  |  67 lines
  1. /********* Listing 3 *************************** DYNHASH.HPP ******
  2. *  Copyright (C) 1990 by Tom Provenzano
  3. * 
  4. *  Implements a dynamic hashing scheme called linear hashing and
  5. *  is based on the article "Dynamic Hash Tables" by Per-Ake Larson,
  6. *  Communications of the ACM, v31 n4, April 1988, pp. 446-457.
  7. *******************************************************************/
  8.  
  9. #include <generic.hpp>  // Zortech's equivalent of generic.h
  10. #include <slist.hpp>    // use's Zortech Tools singly-linked lists & iterators
  11. #include "dynarray.hpp" // will inherit dynamic array class
  12.  
  13. // status parameters
  14.  
  15. const int OK             =  0;    // successful operation
  16. const int NOT_FOUND      = -100;  // item not found
  17. const int NO_MEMORY      = -101;  // memory allocation failure
  18. const int NOT_INSERTED   = -102;  // item not put in hashtable
  19. const int NOT_REMOVED    = -103;  // item not removed from hashtable
  20. const int EXPAND_ERROR   = -104;  // error during hashtable expansion
  21. const int CONTRACT_ERROR = -105;  // error during hashtable contraction
  22.  
  23. #define gdynhash(type) name2(type,gdynhash)
  24. #define gdynhashdeclare(type)                                           \
  25. struct gdynhash(type) : dynhash                                         \
  26. {                                                                       \
  27.   gdynhash(type)() : (sizeof(type)) {}                                  \
  28.   int   insert(type* p)   { return dynhash::insert(p); }                \
  29.   int   remove(type* p)   { return dynhash::remove(p); }                \
  30.   type* lookup(type* p)   { return (type* )dynhash::lookup(p);  }       \
  31.   type* get_next( void )  { return (type* )dynhash::get_next(); }   \
  32. };
  33.  
  34. typedef zSList* pzSList;  // because 'declare' won't accept pointer syntax
  35. declare(gdynarray,pzSList);
  36.  
  37. class dynhash
  38. {
  39. private:
  40.   int N;                        // minimum size of hash table
  41.   int splitp;                   // pointer to next bucket to split
  42.   int maxp;                     // upper bound on p during this expansion
  43.   int CurrentSize;              // current size (num records in table)
  44.   int MinLoadFactor;            // lower bound on load factor
  45.   int MaxLoadFactor;            // upper bound on load factor
  46.   int Threshold;                // load factor threshold reached (Y/N)
  47.   int recsize;                  // size of a table record (bytes)
  48.   int err;                      // class's error flag
  49.  
  50.   int hash( char * );           // compute hash function
  51.   int ExpandTable();            // expand hash table
  52.   int ContractTable();          // contract hash table
  53.   int ConvertKey( char * );     // convert key to integer value
  54.   int insert_rec( void * );     // insert record in hash table
  55.   int remove_rec( void * );     // remove record from hash table
  56.   gdynarray(pzSList) hashtable; // declare hash table dynarray of pzSList*'s
  57.  
  58. public:
  59.   dynhash( int );               // constructor
  60.   ~dynhash();                   // destructor
  61.   int insert( void * );         // insert entry in hash table
  62.   int remove( void * );         // remove entry from hash table
  63.   void *get_next( void );       // get next entry in hash table
  64.   void *lookup( void * );       // look up entry in hash table
  65.   int size() { return CurrentSize; } // report number of records in table
  66.   int error() { int x = err; err = 0; return x; } // error handler
  67. };