home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / warphead.zip / H / OPENHASH.H < prev    next >
C/C++ Source or Header  |  1997-02-28  |  24KB  |  529 lines
  1. //====START_GENERATED_PROLOG======================================
  2. //
  3. //
  4. //   COMPONENT_NAME: odutils
  5. //
  6. //   CLASSES:   OpenHashTable
  7. //        OpenHashTableIterator
  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/OpenHash.h, odutils, od96os2, odos29646d 7/15/96 18:01:24 [ 11/15/96 15:29:01 ]
  29. /*
  30.     File:        OpenHash.h
  31.  
  32.     Contains:    OpenHashTable, a hash table with "open" hashing
  33.  
  34.     Owned by:    David McCusker
  35.  
  36.     Copyright:    ⌐ 1995 by Apple Computer, Inc., all rights reserved.
  37.  
  38.     
  39. */
  40.  
  41. #ifndef _OPENHASH_
  42. #define _OPENHASH_ 1
  43.  
  44. #ifndef _ODTYPES_
  45. #include "ODTypes.h"
  46. #endif
  47.  
  48. #ifndef _ODMEMORY_
  49. #include "ODMemory.h"
  50. #endif
  51.  
  52. //==============================================================================
  53. // Constants
  54. //==============================================================================
  55.  
  56. //==============================================================================
  57. // Scalar Types
  58. //==============================================================================
  59.  
  60. typedef ODBoolean (*OpenHashKeyEqual)(const void* key, const void* testKey);
  61. typedef ODULong (*OpenHashKeyHash)(const void* key);
  62.  
  63. typedef unsigned int OpenHashSize; // must be unsigned, (similar to size_t)
  64.  
  65. typedef ODBoolean (*OpenHashAction)(void* key, void* value, ODULong slot, void* ref);
  66.     /* OpenHashAction supports walking hash tables.  Returning true causes
  67.      * a walk to terminate early (false continues the walk).  This allows
  68.      * a walk to be invoked just to see if it finds something interesting.
  69.      */
  70.  
  71. //==============================================================================
  72. // Classes defined in this interface
  73. //==============================================================================
  74.  
  75. class OpenHashTable;
  76. class OpenHashTableIterator;
  77.  
  78. //==============================================================================
  79. // Classes used by this interface
  80. //==============================================================================
  81.  
  82. class OpenHashEntry; // private to the implementation
  83. class OpenHashVectors; // private to the implementation
  84.  
  85.  
  86. //==============================================================================
  87. // OpenHashTable: theory of operation
  88. //==============================================================================
  89.  
  90. /*
  91.     OpenHashTable is a hash table that implements "open" hashing (such that
  92.     collisions are handled by chaining together the members of a bucket). This
  93.     permits efficient removal of hash table associations (as opposed to closed
  94.     hashing, which might require a non-trivial amount of entry movement after
  95.     a removal).  In particular, this implementation of open hashing supports
  96.     removal during iterations.
  97.     
  98.     A table is logically a set of <key, value> pairs, where no key is equal to
  99.     another. This defines a mapping that associates keys with values.
  100.     OpenHashTable manages the space for both keys and values; keys and values
  101.     are copied into and out of the hash table through the interface.  The
  102.     amount of space required for each key and value is specified when the hash
  103.     table is initialized.  Values may be specified as zero-sized, causing the
  104.     the table to allocate space for keys only.  Users might want to do this
  105.     when a key contains all the information of interest, and a value would
  106.     be redundant. (Note that keys may *not* be zero-sized.)  If users want
  107.     to manage the memory for their own keys and values, it is simple to use
  108.     pointers for the keys and values, and specify the size as sizeof(void*).
  109.     
  110.     The only requirements for keys are that they have appropriate
  111.     OpenHashKeyEqual and OpenHashKeyHash functions, which are related to 
  112.     each other by the following invariant:
  113.         (*equal)(key1, key2) implies (*hash)(key1) == (*hash)(key2)
  114.     
  115.     Assuming a full table, the storage overhead for this implementation is
  116.     two longwords per <key, value> association.  (If OPENHASH_CACHE_HASH is
  117.     defined, another longword of overhead is added to cache the hash of keys,
  118.     and the speed of lookup operations and changes in table size will be
  119.     significantly increased.)
  120.     
  121.     This implementation uses mod (%) to calculate buckets from hashes.  If
  122.     masking (&) had been used, the table would have been constrained to sizes
  123.     that are powers of two.  Masking might be slightly faster, but causes
  124.     poor distribution if the low bits of hashes are not very pseudo-random.
  125. */
  126.  
  127.  
  128. class OpenHashTable {    
  129. public:
  130.         
  131.     //=============================
  132.     // Hashing
  133.     
  134.     static ODULong StdHash(const void* key);
  135.         // A standard hash function useable when keys are pointers or ints.
  136.         // Hash is defined as the pointer cast to an integer.  Note that since
  137.         // a pointer to the key is passed, the argument type is actually
  138.         // pointer to a pointer.
  139.         // returns *(ODULong*) key;
  140.  
  141.     static ODULong Random(ODULong seed);
  142.         // Pseudo-random number generator with period 2**31-1 (i.e. all
  143.         // values in 1..2**31-1 are visted before repetition). Useful
  144.         // for hashing one or more longwords. Derived from published
  145.         // literature on good random number generators (the names
  146.         // Park and Miller come to mind).
  147.     
  148.     static ODULong HashString(const ODUByte* key, ODULong keyLength);
  149.         // This is a generic hashing utility that might sometimes be used to
  150.         // implement a hash function passed to the OpenHashTable constructor;
  151.         // the keyLength arg must be curried because only key is passed
  152.         // to a hash function.  HashString() is conceptually derived
  153.         // from P.J.Weinberger (from the "dragon" book).
  154.     
  155.     static ODULong RandomOneLong(const void* key);
  156.         // A standard hash function for a 4-byte key, based on Random().
  157.         // returns Random( *(ODULong*) key );
  158.     
  159.     static ODULong RandomTwoLongs(const void* key);
  160.         // A standard hash function for an 8-byte key, based on Random().
  161.         // returns Random( ((ODULong*) key)[0] ^ ((ODULong*) key)[1] );
  162.     
  163.     static ODULong HashTwoLongs(const void* key);
  164.         // A standard hash function for an 8-byte key, where the longwords
  165.         // in the keys are likely already largish values (like pointers).
  166.         // returns ( ((ODULong*) key)[0] ^ ((ODULong*) key)[1] );
  167.         
  168.     //=============================
  169.     // Equality
  170.  
  171.     static ODBoolean StdEqual(const void* key, const void* testKey);
  172.         // A standard equal function useable when keys are pointers or ints.
  173.         // Equality is defined as pointer equality.  Note that since
  174.         // a pointer to the key is passed, the argument type is actually
  175.         // pointer to a pointer.
  176.         // returns ( *(void**) key == *(void**) testKey);
  177.         
  178.     static ODBoolean EqualTwoLongs(const void* key, const void* testKey);
  179.         // A standard equal function for an 8-byte key. Compares the
  180.         // first two longwords of each keys as unsigned longs.
  181.  
  182.     //=============================
  183.     // Making and Breaking
  184.         
  185.     OpenHashTable(OpenHashKeyEqual equal = StdEqual, 
  186.                   OpenHashKeyHash hash = StdHash,
  187.                   ODMemoryHeapID heap=kDefaultHeapID);
  188.         // Compare keys with equal, and hash them with hash.
  189.         // All memory is allocated from the specified heap.
  190.             
  191.     OpenHashTable(const OpenHashTable& otherTable); 
  192.         // Use the same equal, hash, and heap as otherTable.
  193.         // (Does *not* copy otherTable; use InitializeAndCopy() 
  194.         // to actually copy the contents of otherTable.)
  195.  
  196.     void SetHeap(ODMemoryHeapID heap=kDefaultHeapID);
  197.         // All memory is allocated from the specified heap.
  198.         // This method does nothing after Initialize() has been called.
  199.         // Generally this function is only called by hash tables delegating
  200.         // to this one, which specify the heap in Initialize() functions
  201.         // instead of in the constructor.
  202.     
  203.     ODBoolean Initialize(ODULong sizeHint=5, 
  204.                          OpenHashSize keySize=sizeof(void*),
  205.                          OpenHashSize valueSize=sizeof(void*), 
  206.                          ODBoolean throwErrors=kODTrue);
  207.         // Initialize the table with sizeHint slots.  Keys will occupy keySize
  208.         // bytes of space, and this amount of space will copied in/out of
  209.         // functions.  Values will occupy valueSize bytes of space, and this
  210.         // amount of space will copied in/out of functions.   valueSize can
  211.         // be zero, causing values to be ignored.  The value of throwErrors
  212.         // controls whether exceptions will be thrown when errors occur.
  213.         // Note that if either keys or values have alignment requirements,
  214.         // then keySize and valueSize must be such that keyPtr + keySize and
  215.         // valuePtr + valueSize point to appropriately aligned structures.
  216.         // Returns false only if memory could not be allocated. (If
  217.         // throwErrors, throws kODErrOutOfMemory instead of returning false.) 
  218.         // You can alternatively use InitAndCopyFrom() to copy another table.
  219.         
  220.     ODBoolean InitAndCopyFrom(const OpenHashTable& otherTable);
  221.         // Initialize this table so that it uses the same parameters
  222.         // as otherTable; sizeHint is taken as otherTable.Count().
  223.         // Then we call this->CopyTable(otherTable) to copy the contents.
  224.         // Returns false only if memory could not be allocated. (If
  225.         // throwErrors, throws kODErrOutOfMemory instead of returning false.) 
  226.         
  227.     ODBoolean CopyTable(const OpenHashTable& otherTable);
  228.         // Copy all of otherTable's entries into this table such that the
  229.         // result is the union of the previous contents of this table and
  230.         // otherTable.  If this table was empty, the result is a simple copy.
  231.         // If this table contains entries that are also in otherTable, they
  232.         // are replaced with otherTable's entries (beware losing pointers
  233.         // and creating garbage this way). Othertable should have the same
  234.         // equal and hash functions, as well as the same key and value sizes.  
  235.         // Returns false only if memory could not be allocated. (If
  236.         // throwErrors, throws kODErrOutOfMemory instead of returning false.)
  237.         // The implementation is just an optimized way of iterating over
  238.         // entries in otherTable and calling this->ReplaceEntry() for each. 
  239.  
  240.     ~OpenHashTable();
  241.         
  242.     //=============================
  243.     // Association operations
  244.  
  245.     ODBoolean        ReplaceEntry(void* keyPtr, void* valuePtr);
  246.         // Replace and/or add an entry that associates key with value. keyPtr 
  247.         // must be a POINTER to a key, and valuePtr must be a POINTER to a value
  248.         // (e.g. if a key is struct Foo, then keyPtr must be type struct Foo*).
  249.         // <key-size> bytes from keyPtr will be copied into the table, and 
  250.         // <value-size> bytes from valuePtr will be be copied into the
  251.         // table (if <value-size> is zero, valuePtr is ignored).
  252.         // (Note that if you need a copy of the old contents of the key or
  253.         // value from a previous association, you should copy them first using
  254.         // one of GetKey(), GetValue(), or GetKeyAndValue().)
  255.         // If the addition of this entry makes the table's entry count exceed
  256.         // the current capacity of the table, then the table grows by some
  257.         // percentage (say 50%), leaving some empty slots for future additions.
  258.         // False is returned only if memory could not be allocated. (If
  259.         // throwErrors, throws kODErrOutOfMemory instead of returning false.) 
  260.  
  261.     void             RemoveEntry(void* keyPtr);
  262.         // Remove the association with the specified key.  keyPtr must be
  263.         // a POINTER to a key (e.g. if a key is struct Foo, then keyPtr must
  264.         // be type struct Foo*). Nothing happens if there was no such
  265.         // association.  This operation is fast and cheap because an old entry
  266.         // is simply "unlinked" and set aside for reuse.  (Consider using 
  267.         // ShrinkToFit() to reclaim space after numerous removals.)
  268.         // (Note that if you need a copy of the old contents of the key or
  269.         // value from a previous association, you should copy them first using
  270.         // one of GetKey(), GetValue(), or GetKeyAndValue().)
  271.  
  272.     ODBoolean        GetValue(void* keyPtr, void* valuePtr) const;
  273.         // Find and return the value associated with key in (*valuePtr);
  274.         // returns false only if there was no association with the given key,
  275.         // or if <value-size> is zero.  keyPtr must be a POINTER to a key, and
  276.         // valuePtr must be a POINTER to a value (e.g. if a key is struct
  277.         // Foo, then keyPtr must be type struct Foo*).
  278.         // If the association is found, and if <value-size> is nonzero, then
  279.         // <value-size> bytes are copied to the address indicated by valuePtr;
  280.         // otherwise valuePtr is ignored.
  281.  
  282.     ODBoolean        GetKey(void* keyInPtr, void* keyOutPtr) const;
  283.         // Find the key in the table equal to (*keyInPtr) and return it in
  284.         // (*keyOutPtr); returns false only if there was no association with
  285.         // the given key.   keyInPtr and keyOutPtr must be POINTERs to keys
  286.         // (e.g. if a key is struct Foo, then keyPtr must be type struct Foo*).
  287.         // If the association is found, then <key-size> bytes are copied to the
  288.         // address indicated by keyOutPtr; it is safe to use the same pointer
  289.         // for keyInPtr and keyOutPtr because keyInPtr is not read again after
  290.         // keyOutPtr is written.
  291.  
  292.     ODBoolean        GetKeyAndValue(void* key, void* keyPtr, void* valuePtr) const;
  293.         // Roughly equivalent to GetKey(key, keyPtr), GetValue(key, valuePtr),
  294.         // but faster.  Either keyPtr or valuePtr can be set to zero to
  295.         // suppress copying that part of the association.
  296.     
  297.     ODBoolean        Exists(void* keyPtr) const;
  298.         // Return whether there is an association with a key equal to (*keyPtr).
  299.         // keyPtr must be a POINTER to a key (e.g. if a key is struct
  300.         // Foo, then keyPtr must be type struct Foo*).
  301.         
  302.     //=============================
  303.     // Table parameters
  304.  
  305.     ODULong          Count() const; // number of associations
  306.     ODULong          Capacity() const; // current number of slots
  307.     ODULong          Seed() const; // changes whenever table is modified
  308.  
  309.     OpenHashSize     KeySize() const; // size of keys: <key-size>
  310.     OpenHashSize     ValueSize() const; // size of values: <value-size>
  311.  
  312.     ODBoolean        ThrowErrors() const;
  313.     void             SetThrowErrors(ODBoolean b);
  314.     
  315.     ODBoolean        ShrinkToFit(OpenHashSize extraSlots=3);
  316.         // Change the capacity of the table to Count() + extraSlots.  This is
  317.         // the principal means of recovering storage after numerous removals.
  318.         // Presumably an application watches the relationship between Count()
  319.         // and Capacity(), and shrinks the table when count falls below some
  320.         // threshold. Returns false only if memory could not be allocated. (If
  321.         // throwErrors, throws kODErrOutOfMemory instead of returning false.)
  322.     
  323.     //=============================
  324.     // comparing hash tables:
  325.     ODBoolean        Intersect(OpenHashTable* ht, OpenHashAction action, void* ref);
  326.         // Walk this table and compare with table ht, calling action (with ref
  327.         // as one argument) once for every association in this table which has
  328.         // a key equal to a key in ht.  (Note: the value of slot passed to
  329.         // action is meaningless.) If action ever returns true, Intersect()
  330.         // returns immediately without examining any more associations. 
  331.         // Intersect() returns true only if action returns true (thus, for
  332.         // example, if either table is empty then action is never called and
  333.         // Intersect() returns false). If the caller wishes to build a data
  334.         // structure (e.g. a list) that represents the intersection, this can
  335.         // be maintained in ref.  Or, if the caller wants a boolean yes or no
  336.         // (is the intersection non-empty?) then action merely needs to always
  337.         // return true (use TrueAction()).  Table ht must have the
  338.         // same hash and equal functions as in this table. You cannot add or
  339.         // remove associations in this table during the intersection, but you
  340.         // can in ht. 
  341.  
  342.     static ODBoolean TrueAction(void* k, void* v, ODULong s, void* r);
  343.         // This function ignores its arguments and always returns true.
  344.         // It is meant to be passed as an action argument to Intersect().
  345.  
  346.     //=============================
  347.     // testing & debugging:
  348.     ODBoolean        Walk(OpenHashAction action, void* ref) const;
  349.         // Call action once for every association in the hash table, passing 
  350.         // through ref each time, as well as the slot in the table containing
  351.         // the association.  If action ever returns true, the walk is terminated
  352.         // immediately, rather than visiting every association. Walk() only
  353.         // returns true if action returns true (thus, an empty table never calls
  354.         // action and returns false). This function is useful for printing the
  355.         // distribution of keys in a table to evaluate the quality of hashing.
  356.         // (It's not appropriate to expose slots in the table with an iterator.)
  357.         // You cannot add or remove associations during the walk.
  358.     
  359. protected:
  360.     OpenHashEntry**  fTable;       // hash buckets (numbering fSlots)
  361.     OpenHashEntry*   fEntries;     // block of fSlots entries
  362.     char*            fKeys;        // block of fSlots keys
  363.     char*            fValues;      // block of fSlots values
  364.     OpenHashEntry*   fFreeList;    // free list of entries
  365.     OpenHashKeyEqual fEqual;       // used to compare keys
  366.     OpenHashKeyHash  fHash;        // used to hash keys
  367.     ODMemoryHeapID   fHeap;        // used to allocate memory
  368.     OpenHashSize     fSlots;       // current size (capacity) of table
  369.     ODULong          fCount;       // number of entries in table
  370.     ODULong          fSeed;        // used to validate iterators
  371.     OpenHashSize     fKeySize;     // size of keys
  372.     OpenHashSize     fValSize;     // size of values
  373.     ODBoolean        fThrowErrors; // throw exception on errors
  374.  
  375.     OpenHashEntry**  Find(void* key, ODULong hash) const;
  376.     ODBoolean        Grow();
  377.     
  378.     void             Clear();
  379.     OpenHashEntry**  NewTable(OpenHashSize slots) const;
  380.     OpenHashEntry*   NewEntries(OpenHashSize slots) const;
  381.     char*            NewKeys(OpenHashSize slots) const;
  382.     char*            NewValues(OpenHashSize slots) const;
  383.  
  384.     ODBoolean        NewVectors(OpenHashVectors* old, OpenHashSize slots);
  385.     
  386.     OpenHashEntry*   PopFreeEntry();
  387.     void             PushFreeEntry(OpenHashEntry* e);
  388.     
  389.     void             CopyTo(void* key, void* value, ODULong i) const;
  390. private:                  
  391.     friend class OpenHashTableIterator;
  392.     friend class OpenHashVectors;
  393. };
  394.  
  395. inline ODULong OpenHashTable::Capacity() const
  396. {
  397.     return fSlots;
  398. }
  399.  
  400. inline ODULong OpenHashTable::Count() const
  401. {
  402.     return fCount;
  403. }
  404.  
  405. inline ODULong OpenHashTable::Seed() const
  406. {
  407.     return fSeed;
  408. }
  409.  
  410. inline OpenHashSize OpenHashTable::KeySize() const
  411. {
  412.     return fKeySize;
  413. }
  414.  
  415. inline OpenHashSize OpenHashTable::ValueSize() const
  416. {
  417.     return fValSize;
  418. }
  419.  
  420. inline ODBoolean OpenHashTable::ThrowErrors() const
  421. {
  422.     return fThrowErrors;
  423. }
  424.  
  425. inline void OpenHashTable::SetThrowErrors(ODBoolean b)
  426. {
  427.     fThrowErrors = b;
  428. }
  429.  
  430.  
  431. //==============================================================================
  432. // OpenHashTableIterator
  433. //
  434. //    This iterator is only meant to be used in the the context of a for loop,
  435. //    e.g.:
  436. //
  437. //  struct MyKey key;
  438. //  struct MyValue value;
  439. //    OpenHashTableIterator i(table);
  440. //    for (i.First(&key, &value); i.IsNotComplete(); i.Next(&key, &value))
  441. //    {
  442. //        ...
  443. //    }
  444. //
  445. //==============================================================================
  446.  
  447. class OpenHashTableIterator
  448. {
  449.   public:
  450.     OpenHashTableIterator(OpenHashTable* table);
  451.     ~OpenHashTableIterator();    
  452.  
  453.     void              First(void* keyPtr, void* valuePtr);
  454.         // Resets the iteration and copies the "first" <key, value> pair 
  455.         // in the hash table.  Either keyPtr or valuePtr can be set to 
  456.         // zero to suppress copying that part of the assocation.  valuePtr
  457.         // will also be ignored if <value-size> is zero.  keyPtr must 
  458.         // be a POINTER to a key, and valuePtr must be a POINTER to a value
  459.         // (e.g. if a key is struct Foo, then keyPtr must be type struct Foo*).
  460.         // keyPtr or valuePtr are ignored if there are no more associations
  461.         // (use IsNotComplete() to check).  The iterator and the table are
  462.         // always in sync after First().
  463.     
  464.     void              Next(void* keyPtr, void* valuePtr);
  465.         // Continues the iteration and copies the "next" <key, value> 
  466.         // pair in the hash table.  Either keyPtr or valuePtr can be set to 
  467.         // zero to suppress copying that part of the assocation.  valuePtr
  468.         // will also be ignored if <value-size> is zero.  keyPtr must 
  469.         // be a POINTER to a key, and valuePtr must be a POINTER to a value
  470.         // (e.g. if a key is struct Foo, then keyPtr must be type struct Foo*).
  471.         // keyPtr or valuePtr are ignored if there are no more associations
  472.         // (use IsNotComplete() to check).  If the table is out of sync with
  473.         // the iterator (has been modified since First() other than by
  474.         // RemoveCurrent()), then exception kODErrIteratorOutOfSync is thrown.
  475.     
  476.     ODBoolean         Current(void* keyPtr, void* valuePtr);
  477.         // Copies the same <key, value> pair as the last call to either
  478.         // First() or Next().  Either keyPtr or valuePtr can be set to 
  479.         // zero to suppress copying that part of the assocation.  valuePtr
  480.         // will also be ignored if <value-size> is zero.  keyPtr must 
  481.         // be a POINTER to a key, and valuePtr must be a POINTER to a value
  482.         // (e.g. if a key is struct Foo, then keyPtr must be type struct Foo*).
  483.         // keyPtr or valuePtr are ignored if there are no more associations
  484.         // (use IsNotComplete() to check).  If the table is out of sync with
  485.         // the iterator (has been modified since First() other than by
  486.         // RemoveCurrent()), then exception kODErrIteratorOutOfSync is thrown.
  487.  
  488.     void              RemoveCurrent();
  489.         // Efficiently removes the current <key, value> pair from the table.
  490.         // This method works the same whether you are iterating with
  491.         // associations or with pointers.  If the table is out of sync with
  492.         // the iterator (has been modified since First() other than by
  493.         // RemoveCurrent()), then exception kODErrIteratorOutOfSync is thrown.
  494.  
  495.     ODBoolean          IsNotComplete() const;
  496.         // Returns true if the last call to First(), Next() or Current()
  497.         // accessed an association in the table.
  498.  
  499.     ODBoolean          IsOutOfSync() const;
  500.         // Returns whether the iterator is out of sync with the table.
  501.         // Users who do not want an kODErrIteratorOutOfSync exception to be
  502.         // thrown from Next(), Current(), or RemoveCurrent() should avoid
  503.         // calling those functions when IsOutOfSync() returns true.
  504.         // (The iterator becomes out of sync when the table is modified other
  505.         // than by RemoveCurrent() since the last call to First().)
  506.  
  507.   private:
  508.     OpenHashTable*   fTable;    // the table we are iterating over
  509.     ODULong          fSeed;     // should match table's seed
  510.     OpenHashEntry**  fBucket;   // current bucket in the table
  511.     OpenHashEntry**  fRef;      // normally (*fRef == fCurrent), for removal
  512.     OpenHashEntry*   fCurrent;  // the current entry
  513.     OpenHashEntry*   fAfter;    // normally fCurrent->fLink
  514. };
  515.  
  516. inline ODBoolean OpenHashTableIterator::IsNotComplete() const
  517. {
  518.     return (fCurrent != 0);
  519. }
  520.  
  521. inline ODBoolean OpenHashTableIterator::IsOutOfSync() const
  522. {
  523.     return (fSeed != fTable->Seed());
  524. }
  525.  
  526.  
  527. #endif
  528. // _OPENHASH_
  529.