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