home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 October: Mac OS SDK / Dev.CD Oct 96 SDK / Dev.CD Oct 96 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc Source Code / Utilities / Interfaces / StrHshTb.h < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-22  |  6.6 KB  |  211 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        StrHshTb.h
  3.  
  4.     Contains:    Interface to StringHashTable class.
  5.  
  6.     Owned by:    Nick Pilch
  7.  
  8.     Copyright:    © 1993 - 1995 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     
  11.     In Progress:
  12. */
  13.  
  14. #ifndef _STRHSHTB_
  15. #define _STRHSHTB_
  16.  
  17. #ifndef _ODTYPES_
  18. #include "ODTypes.h"
  19. #endif
  20.  
  21. #ifndef _PLFMDEF_
  22. #include "PlfmDef.h"
  23. #endif
  24.  
  25. #ifndef _ODMEMORY_
  26. #include "ODMemory.h"
  27. #endif
  28.  
  29. #ifndef __STDIO__
  30. #include <stdio.h>
  31. #endif
  32.  
  33. //==============================================================================
  34. // Theory of Operation
  35. //==============================================================================
  36.  
  37. /*
  38.     A simple hash table for keys of variable length. Value is 8 bytes. First
  39.     four bytes are a pointer to the storage for the value, the next four bytes
  40.     are the length of that storage. The caller must allocate the storage.
  41.     Implemented with chaining. Keys are bytes streams. Embedded NULLs are
  42.     allowed. However, keys of zero length are not allowed.
  43. */
  44.  
  45. //==============================================================================
  46. // Scalar Types
  47. //==============================================================================
  48.  
  49. typedef ODULong (*StringHashTableFunc)(ODUByte* string,
  50.                                             ODULong stringLength,
  51.                                             ODULong& hashValueLowerBounds,
  52.                                             ODULong& hashValueUpperBounds);
  53.  
  54.     // this is the hash function prototype.
  55.  
  56. //==============================================================================
  57. // Classes defined in this interface
  58. //==============================================================================
  59.  
  60. class    StringHashTable;
  61. class    StringHashTableIterator;
  62.  
  63. //==============================================================================
  64. // Classes used by this interface
  65. //==============================================================================
  66.  
  67. class    LinkedNodesIterator;
  68. struct    HashEntryRec;
  69. struct    EntryNode;
  70.  
  71. //==============================================================================
  72. // StringHashTable
  73. //==============================================================================
  74.  
  75. class StringHashTable
  76. {
  77.     
  78.     friend class LinkedNodesIterator;
  79.     friend class StringHashTableIterator;
  80.  
  81.   public:
  82.  
  83.     StringHashTable(ODULong numEntries);
  84.         // numEntries should be the expected number of table entries. The table
  85.         //    will not grow or shrink. If zero is passed, the table is initialized
  86.         //    with 1 entry. (not very interesting).
  87.  
  88.     ODVMethod void Initialize(ODMemoryHeapID heapID);
  89.         // kODErrOutOfMemory will be thrown if the table could not be created.
  90.  
  91.     virtual ~StringHashTable();
  92.  
  93.  
  94.     ODVMethod void            Insert(ODUByte* string, ODULong stringLength,
  95.                                         ODPtr value, ODULong valueLength);
  96.         // If this key already exists, that value is replaced by the new value.
  97.         //     kODErrOutOfMemory will be thrown if the entry could not be inserted.
  98.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  99.         //    The key is copied into the table, the value is not.
  100.         //    If an exception is 
  101.  
  102.     ODVMethod void            Remove(ODUByte* string, ODULong stringLength);
  103.         // No exception is thrown if the key does not exist.
  104.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  105.  
  106.     ODVMethod ODBoolean         Find(ODUByte* string, ODULong stringLength,
  107.                                         ODPtr* value, ODULong* valueLength);    
  108.         // kODTrue is returned if the value is found, kODFalse otherwise.
  109.         //    If the entry is not found. *value and *valueLength are not
  110.         //    guaranteed to contain any useful information.
  111.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  112.  
  113.     ODVMethod ODBoolean         Exists(ODUByte* string, ODULong stringLength);    
  114.         // kODTrue is returned if the value is found, kODFalse otherwise.
  115.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  116.  
  117.     ODVMethod ODULong         GetNumEntries();    
  118.         // Return the number of entries.
  119.  
  120.     ODVMethod void        PrintTable(FILE* outfile);
  121.     ODVMethod void        PrintDistribution(FILE* outfile);
  122.     
  123.         // for debugging / testing
  124.  
  125.     StringHashTableFunc    GetHashFunc();
  126.     void                    SetHashFunc(StringHashTableFunc func);
  127.  
  128.         // get and set the hash function.
  129.  
  130.   protected:
  131.       ODMemoryHeapID         fHeapID;
  132.  
  133.     HashEntryRec*    fTable; // pointer to start of table,
  134.                             //    fNumSlots * sizeof(HashEntry) long. Initialized to
  135.                             //    all zeroes.
  136.  
  137.     ODULong        fNumSlots; // Number of slots in the table, not number of
  138.                                 //    entries.
  139.  
  140.     ODULong        fNumEntries;    // Actual number of entries.
  141.  
  142.     StringHashTableFunc    fHashFunc;
  143.     
  144.     ODVMethod HashEntryRec*    GetTable();
  145.     ODVMethod ODULong            GetNumSlots();
  146.  
  147.     static ODULong        StdHash(ODUByte* string, ODULong stringLength,
  148.                                             ODULong& hashValueLowerBounds,
  149.                                             ODULong& hashValueUpperBounds);
  150.  
  151.     ODVMethod ODULong    MapToTableIndex(ODULong hash,
  152.                                             ODULong hashValueLowerBounds,
  153.                                             ODULong hashValueUpperBounds);
  154.  
  155.     ODVMethod ODULong    HashAndMap(ODUByte* string, ODULong stringLength);
  156.     ODVMethod void        InsertAtIndex(ODULong index, ODUByte* string,
  157.                                                 ODULong stringLength,
  158.                                                 ODPtr value,
  159.                                                 ODULong valueLength);
  160.     ODVMethod void        RemoveAtIndex(ODULong index, ODUByte* string,
  161.                                                 ODULong stringLength);
  162.     EntryNode*            MakeNewNode(ODUByte* string, ODULong stringLength,
  163.                                         ODPtr value, ODULong valueLength);
  164.     ODUByte*            MakeStringFromBytes(ODUByte* string,
  165.                                                     ODULong stringLength);
  166. };
  167.  
  168. //==============================================================================
  169. // StringHashTableIterator
  170. //
  171. //    This iterator is only meant to be used in the the context of a for loop,
  172. //    e.g.:
  173. //
  174. //    StringHashTableIterator iter;
  175. //    for (iter.First(string, len, value, valueLen);
  176. //            iter.IsNotComplete();
  177. //            iter.Next(string, len, value, valueLen))
  178. //    {
  179. //        ...
  180. //    }
  181. //
  182. //==============================================================================
  183.  
  184. class StringHashTableIterator
  185. {
  186.   public:
  187.     StringHashTableIterator(StringHashTable* tb);
  188.     ~StringHashTableIterator();
  189.     void        First(ODUByte** string, ODULong* len, ODPtr* value,
  190.                           ODULong* valueLen);
  191.         // A pointer to the private copy of the string is returned. The user
  192.         //    must copy the storage if he or she desires to change it.
  193.         //    If there are no entries in the table, *string will be set to
  194.         //    kODNULL and *len set to 0.
  195.     void        Next(ODUByte** string, ODULong* len, ODPtr* value,
  196.                         ODULong* valueLen);
  197.         // A pointer to the private copy of the string is returned. The user
  198.         //    must copy the storage if he or she desires to change it.
  199.         //    If there are no more entries in the table, *string will be set to
  200.         //    kODNULL and *len set to 0.
  201.     ODBoolean    IsNotComplete();
  202.   private:
  203.     ODBoolean    GetNext(ODUByte** string, ODULong* len,
  204.                         ODPtr* value, ODULong* valueLen);
  205.     StringHashTable*    fTable;
  206.     ODULong            fTableIndex;
  207.     EntryNode*            fCurNode;
  208.     ODBoolean            fDone;
  209. };
  210.  
  211. #endif // _STRHSHTB_