home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / warphead.zip / H / STRHSHTB.H < prev    next >
C/C++ Source or Header  |  1997-02-28  |  8KB  |  240 lines
  1. //====START_GENERATED_PROLOG======================================
  2. //
  3. //
  4. //   COMPONENT_NAME: odutils
  5. //
  6. //   CLASSES:   StringHashTable
  7. //        StringHashTableIterator
  8. //
  9. //   ORIGINS: 82,27
  10. //
  11. //
  12. //   (C) COPYRIGHT International Business Machines Corp. 1995,1996
  13. //   All Rights Reserved
  14. //   Licensed Materials - Property of IBM
  15. //   US Government Users Restricted Rights - Use, duplication or
  16. //   disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
  17. //       
  18. //   IBM DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  19. //   ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  20. //   PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  21. //   CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
  22. //   USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  23. //   OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
  24. //   OR PERFORMANCE OF THIS SOFTWARE.
  25. //
  26. //====END_GENERATED_PROLOG========================================
  27. //
  28. // @(#) 1.3 com/src/utils/include/StrHshTb.h, odutils, od96os2, odos29646d 7/15/96 18:02:03 [ 11/15/96 15:29:35 ]
  29. /*
  30.     File:        StrHshTb.h
  31.  
  32.     Contains:    Interface to StringHashTable class.
  33.  
  34.     Owned by:    Nick Pilch
  35.  
  36.     Copyright:    ⌐ 1993 - 1995 by Apple Computer, Inc., all rights reserved.
  37.  
  38.     
  39.     In Progress:
  40. */
  41.  
  42. #ifndef _STRHSHTB_
  43. #define _STRHSHTB_
  44.  
  45. #ifndef _ODTYPES_
  46. #include "ODTypes.h"
  47. #endif
  48.  
  49. #ifndef _PLFMDEF_
  50. #include "PlfmDef.h"
  51. #endif
  52.  
  53. #ifndef _ODMEMORY_
  54. #include "ODMemory.h"
  55. #endif
  56.  
  57. #ifndef __STDIO__
  58. #include <stdio.h>
  59. #endif
  60.  
  61. //==============================================================================
  62. // Theory of Operation
  63. //==============================================================================
  64.  
  65. /*
  66.     A simple hash table for keys of variable length. Value is 8 bytes. First
  67.     four bytes are a pointer to the storage for the value, the next four bytes
  68.     are the length of that storage. The caller must allocate the storage.
  69.     Implemented with chaining. Keys are bytes streams. Embedded NULLs are
  70.     allowed. However, keys of zero length are not allowed.
  71. */
  72.  
  73. //==============================================================================
  74. // Scalar Types
  75. //==============================================================================
  76.  
  77. typedef ODULong (*StringHashTableFunc)(ODUByte* string,
  78.                                             ODULong stringLength,
  79.                                             ODULong& hashValueLowerBounds,
  80.                                             ODULong& hashValueUpperBounds);
  81.  
  82.     // this is the hash function prototype.
  83.  
  84. //==============================================================================
  85. // Classes defined in this interface
  86. //==============================================================================
  87.  
  88. class    StringHashTable;
  89. class    StringHashTableIterator;
  90.  
  91. //==============================================================================
  92. // Classes used by this interface
  93. //==============================================================================
  94.  
  95. class    LinkedNodesIterator;
  96. struct    HashEntryRec;
  97. struct    EntryNode;
  98.  
  99. //==============================================================================
  100. // StringHashTable
  101. //==============================================================================
  102.  
  103. class StringHashTable
  104. {
  105.     
  106.     friend class LinkedNodesIterator;
  107.     friend class StringHashTableIterator;
  108.  
  109.   public:
  110.  
  111.     StringHashTable(ODULong numEntries);
  112.         // numEntries should be the expected number of table entries. The table
  113.         //    will not grow or shrink. If zero is passed, the table is initialized
  114.         //    with 1 entry. (not very interesting).
  115.  
  116.     ODVMethod void Initialize(ODMemoryHeapID heapID);
  117.         // kODErrOutOfMemory will be thrown if the table could not be created.
  118.  
  119.     virtual ~StringHashTable();
  120.  
  121.  
  122.     ODVMethod void            Insert(ODUByte* string, ODULong stringLength,
  123.                                         ODPtr value, ODULong valueLength);
  124.         // If this key already exists, that value is replaced by the new value.
  125.         //     kODErrOutOfMemory will be thrown if the entry could not be inserted.
  126.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  127.         //    The key is copied into the table, the value is not.
  128.         //    If an exception is 
  129.  
  130.     ODVMethod void            Remove(ODUByte* string, ODULong stringLength);
  131.         // No exception is thrown if the key does not exist.
  132.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  133.  
  134.     ODVMethod ODBoolean         Find(ODUByte* string, ODULong stringLength,
  135.                                         ODPtr* value, ODULong* valueLength);    
  136.         // kODTrue is returned if the value is found, kODFalse otherwise.
  137.         //    If the entry is not found. *value and *valueLength are not
  138.         //    guaranteed to contain any useful information.
  139.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  140.  
  141.     ODVMethod ODBoolean         Exists(ODUByte* string, ODULong stringLength);    
  142.         // kODTrue is returned if the value is found, kODFalse otherwise.
  143.         //    kODErrInvalidKey will be thrown if stringLength is zero.
  144.  
  145.     ODVMethod ODULong         GetNumEntries();    
  146.         // Return the number of entries.
  147.  
  148.     ODVMethod void        PrintTable(FILE* outfile);
  149.     ODVMethod void        PrintDistribution(FILE* outfile);
  150.     
  151.         // for debugging / testing
  152.  
  153.     StringHashTableFunc    GetHashFunc();
  154.     void                    SetHashFunc(StringHashTableFunc func);
  155.  
  156.         // get and set the hash function.
  157.  
  158.   protected:
  159.       ODMemoryHeapID         fHeapID;
  160.  
  161.     HashEntryRec*    fTable; // pointer to start of table,
  162.                             //    fNumSlots * sizeof(HashEntry) long. Initialized to
  163.                             //    all zeroes.
  164.  
  165.     ODULong        fNumSlots; // Number of slots in the table, not number of
  166.                                 //    entries.
  167.  
  168.     ODULong        fNumEntries;    // Actual number of entries.
  169.  
  170.     StringHashTableFunc    fHashFunc;
  171.     
  172.     ODVMethod HashEntryRec*    GetTable();
  173.     ODVMethod ODULong            GetNumSlots();
  174.  
  175.     static ODULong        StdHash(ODUByte* string, ODULong stringLength,
  176.                                             ODULong& hashValueLowerBounds,
  177.                                             ODULong& hashValueUpperBounds);
  178.  
  179.     ODVMethod ODULong    MapToTableIndex(ODULong hash,
  180.                                             ODULong hashValueLowerBounds,
  181.                                             ODULong hashValueUpperBounds);
  182.  
  183.     ODVMethod ODULong    HashAndMap(ODUByte* string, ODULong stringLength);
  184.     ODVMethod void        InsertAtIndex(ODULong index, ODUByte* string,
  185.                                                 ODULong stringLength,
  186.                                                 ODPtr value,
  187.                                                 ODULong valueLength);
  188.     ODVMethod void        RemoveAtIndex(ODULong index, ODUByte* string,
  189.                                                 ODULong stringLength);
  190.     EntryNode*            MakeNewNode(ODUByte* string, ODULong stringLength,
  191.                                         ODPtr value, ODULong valueLength);
  192.     ODUByte*            MakeStringFromBytes(ODUByte* string,
  193.                                                     ODULong stringLength);
  194. };
  195.  
  196. //==============================================================================
  197. // StringHashTableIterator
  198. //
  199. //    This iterator is only meant to be used in the the context of a for loop,
  200. //    e.g.:
  201. //
  202. //    StringHashTableIterator iter;
  203. //    for (iter.First(string, len, value, valueLen);
  204. //            iter.IsNotComplete();
  205. //            iter.Next(string, len, value, valueLen))
  206. //    {
  207. //        ...
  208. //    }
  209. //
  210. //==============================================================================
  211.  
  212. class StringHashTableIterator
  213. {
  214.   public:
  215.     StringHashTableIterator(StringHashTable* tb);
  216.     ~StringHashTableIterator();
  217.     void        First(ODUByte** string, ODULong* len, ODPtr* value,
  218.                           ODULong* valueLen);
  219.         // A pointer to the private copy of the string is returned. The user
  220.         //    must copy the storage if he or she desires to change it.
  221.         //    If there are no entries in the table, *string will be set to
  222.         //    kODNULL and *len set to 0.
  223.     void        Next(ODUByte** string, ODULong* len, ODPtr* value,
  224.                         ODULong* valueLen);
  225.         // A pointer to the private copy of the string is returned. The user
  226.         //    must copy the storage if he or she desires to change it.
  227.         //    If there are no more entries in the table, *string will be set to
  228.         //    kODNULL and *len set to 0.
  229.     ODBoolean    IsNotComplete();
  230.   private:
  231.     ODBoolean    GetNext(ODUByte** string, ODULong* len,
  232.                         ODPtr* value, ODULong* valueLen);
  233.     StringHashTable*    fTable;
  234.     ODULong            fTableIndex;
  235.     EntryNode*            fCurNode;
  236.     ODBoolean            fDone;
  237. };
  238.  
  239. #endif // _STRHSHTB_
  240.