dict.h

pwlib源码库

/*
 * dict.h
 *
 * Dictionary (hash table) Container classes.
 *
 * Portable Windows Library
 *
 * Copyright (c) 1993-1998 Equivalence Pty. Ltd.
 *
 * The contents of this file are subject to the Mozilla Public License
 * Version 1.0 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS"
 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
 * the License for the specific language governing rights and limitations
 * under the License.
 *
 * The Original Code is Portable Windows Library.
 *
 * The Initial Developer of the Original Code is Equivalence Pty. Ltd.
 *
 * Portions are Copyright (C) 1993 Free Software Foundation, Inc.
 * All Rights Reserved.
 *
 * Contributor(s): ______________________________________.
 *
 * $Log: dict.h,v $
 * Revision 1.34  2004/11/23 11:33:08  csoutheren
 * Fixed problem with RemoveAt returning invalid pointer in some cases,
 * and added extra documentation on this case.
 * Thanks to Diego Tartara for pointing out this potential problem
 *
 * Revision 1.33  2004/04/09 03:42:34  csoutheren
 * Removed all usages of "virtual inline" and "inline virtual"
 *
 * Revision 1.32  2004/04/03 23:53:09  csoutheren
 * Added various changes to improce compatibility with the Sun Forte compiler
 *   Thanks to Brian Cameron
 * Added detection of readdir_r version
 *
 * Revision 1.31  2003/09/17 01:18:02  csoutheren
 * Removed recursive include file system and removed all references
 * to deprecated coooperative threading support
 *
 * Revision 1.30  2003/03/31 01:23:56  robertj
 * Added ReadFrom functions for standard container classes such as
 *   PIntArray and PStringList etc
 *
 * Revision 1.29  2002/10/04 01:47:29  robertj
 * Added various increment and decrement operators to POrdinalKey.
 *
 * Revision 1.28  2002/09/16 01:08:59  robertj
 * Added #define so can select if #pragma interface/implementation is used on
 *   platform basis (eg MacOS) rather than compiler, thanks Robert Monaghan.
 *
 * Revision 1.27  2002/06/14 13:22:12  robertj
 * Fixed ability to remove elements from a PSet by value.
 * Added by value add and remove functions to a PSet.
 * Added a POrdinalSet class.
 * Fixed some documentation.
 *
 * Revision 1.26  2002/02/06 00:53:25  robertj
 * Fixed missing const on PSet::Contains and operator[], thanks Francisco Olarte Sanz
 *
 * Revision 1.25  1999/11/30 00:22:54  robertj
 * Updated documentation for doc++
 *
 * Revision 1.24  1999/08/22 12:13:43  robertj
 * Fixed warning when using inlines on older GNU compiler
 *
 * Revision 1.23  1999/03/09 02:59:49  robertj
 * Changed comments to doc++ compatible documentation.
 *
 * Revision 1.22  1999/02/16 08:07:11  robertj
 * MSVC 6.0 compatibility changes.
 *
 * Revision 1.21  1998/09/23 06:20:27  robertj
 * Added open source copyright license.
 *
 * Revision 1.20  1998/01/05 10:39:34  robertj
 * Fixed "typesafe" templates/macros for dictionaries, especially on GNU.
 *
 * Revision 1.19  1997/12/11 10:27:16  robertj
 * Added type correct Contains() function to dictionaries.
 *
 * Revision 1.18  1997/07/08 13:15:05  robertj
 * DLL support.
 *
 * Revision 1.17  1997/06/08 04:49:11  robertj
 * Fixed non-template class descendent order.
 *
 * Revision 1.16  1996/08/17 10:00:22  robertj
 * Changes for Windows DLL support.
 *
 * Revision 1.15  1996/03/31 08:44:10  robertj
 * Added RemoveAt() function to remove entries from dictionaries.
 *
 * Revision 1.14  1996/02/08 11:50:01  robertj
 * Moved Contains function from PSet to PHashTable so available for dictionaries.
 * Added print for dictionaries key=data\n.
 * Added GetAt(PINDEX) to template classes to make identical to macro.
 *
 * Revision 1.13  1996/02/03 11:00:28  robertj
 * Temporary removal of SetAt() and GetAt() functions in dictionary macro.
 *
 * Revision 1.12  1996/01/24 14:43:11  robertj
 * Added initialisers to string dictionaries.
 *
 * Revision 1.11  1996/01/23 13:11:12  robertj
 * Mac Metrowerks compiler support.
 *
 * Revision 1.10  1995/06/17 11:12:29  robertj
 * Documentation update.
 *
 * Revision 1.9  1995/06/04 08:45:57  robertj
 * Better C++ compatibility (with BC++)
 *
 * Revision 1.8  1995/03/14 12:41:19  robertj
 * Updated documentation to use HTML codes.
 *
 * Revision 1.7  1995/02/22  10:50:29  robertj
 * Changes required for compiling release (optimised) version.
 *
 * Revision 1.6  1995/02/11  04:10:35  robertj
 * Fixed dictionary MACRO for templates.
 *
 * Revision 1.5  1995/02/05  00:48:03  robertj
 * Fixed template version.
 *
 * Revision 1.4  1995/01/09  12:35:31  robertj
 * Removed unnecesary return value from I/O functions.
 * Changes due to Mac port.
 *
 * Revision 1.3  1994/12/21  11:52:51  robertj
 * Documentation and variable normalisation.
 *
 * Revision 1.2  1994/12/17  01:36:57  robertj
 * Fixed memory leak in PStringSet
 *
 * Revision 1.1  1994/12/12  09:59:32  robertj
 * Initial revision
 *
 */

#ifdef P_USE_PRAGMA
#pragma interface
#endif


///////////////////////////////////////////////////////////////////////////////
// PDictionary classes

/**This class is used when an ordinal index value is the key for #PSet#
   and #PDictionary# classes.
 */
class POrdinalKey : public PObject
{
  PCLASSINFO(POrdinalKey, PObject);

  public:
  /**@name Construction */
  //@{
    /** Create a new key for ordinal index values.
     */
    PINLINE POrdinalKey(
      PINDEX newKey = 0   /// Ordinal index value to use as a key.
    );

    /**Operator to assign the ordinal.
      */
    PINLINE POrdinalKey & operator=(PINDEX);
  //@}

  /**@name Overrides from class PObject */
  //@{
    /// Create a duplicate of the POrdinalKey.
    virtual PObject * Clone() const;

    /* Get the relative rank of the ordinal index. This is a simpel comparison
       of the objects PINDEX values.

       @return
       comparison of the two objects, #EqualTo# for same,
       #LessThan# for #obj# logically less than the
       object and #GreaterThan# for #obj# logically
       greater than the object.
     */
    virtual Comparison Compare(const PObject & obj) const;

    /**This function calculates a hash table index value for the implementation
       of #PSet# and #PDictionary# classes.

       @return
       hash table bucket number.
     */
    virtual PINDEX HashFunction() const;

    /**Output the ordinal index to the specified stream. This is identical to
       outputting the PINDEX, ie integer, value.

       @return
       stream that the index was output to.
     */
    virtual void PrintOn(ostream & strm) const;
  //@}

  /**@name New functions for class */
  //@{
    /** Operator so that a POrdinalKey can be used as a PINDEX value.
     */
    PINLINE operator PINDEX() const;

    /**Operator to pre-increment the ordinal.
      */
    PINLINE PINDEX operator++();

    /**Operator to post-increment the ordinal.
      */
    PINLINE PINDEX operator++(int);

    /**Operator to pre-decrement the ordinal.
      */
    PINLINE PINDEX operator--();

    /**Operator to post-decrement the ordinal.
      */
    PINLINE PINDEX operator--(int);

    /**Operator to add the ordinal.
      */
    PINLINE POrdinalKey & operator+=(PINDEX);

    /**Operator to subtract from the ordinal.
      */
    PINLINE POrdinalKey & operator-=(PINDEX );
  //@}

  private:
    PINDEX theKey;
};


//////////////////////////////////////////////////////////////////////////////

/**The hash table class is the basis for implementing the #PSet# and
   #PDictionary# classes.

   The hash table allows for very fast searches for an object based on a "hash
   function". This function yields an index into an array which is directly
   looked up to locate the object. When two key values have the same hash
   function value, then a linear search of a linked list is made to locate
   the object. Thus the efficiency of the hash table is highly dependent on the
   quality of the hash function for the data being used as keys.
 */
class PHashTable : public PCollection
{
  PCONTAINERINFO(PHashTable, PCollection);

  public:
  /**@name Construction */
  //@{
    /// Create a new, empty, hash table.
    PHashTable();
  //@}

  /**@name Overrides from class PObject */
  //@{
    /**Get the relative rank of the two hash tables. Actally ranking hash
       tables is really meaningless, so only equality is returned by the
       comparison. Equality is only achieved if the two instances reference the
       same hash table.

       @return
       comparison of the two objects, #EqualTo# if the same
       reference and #GreaterThan# if not.
     */
    virtual Comparison Compare(
      const PObject & obj   /// Other PHashTable to compare against.
    ) const;
  //@}


  protected:
  /**@name Overrides from class PContainer */
  //@{
    /**This function is meaningless for hash table. The size of the collection
       is determined by the addition and removal of objects. The size cannot be
       set in any other way.

       @return
       Always TRUE.
     */
    virtual BOOL SetSize(
      PINDEX newSize  /// New size for the hash table, this is ignored.
    );
  //@}


  /**@name New functions for class */
  //@{
    /**Determine if the value of the object is contained in the hash table. The
       object values are compared, not the pointers.  So the objects in the
       collection must correctly implement the #PObject::Compare()#
       function. The hash table is used to locate the entry.

       @return
       TRUE if the object value is in the set.
     */
    PINLINE BOOL AbstractContains(
      const PObject & key   /// Key to look for in the set.
    ) const;

    /**Get the key in the hash table at the ordinal index position.
    
       The ordinal position in the hash table is determined by the hash values
       of the keys and the order of insertion.

       The last key/data pair is remembered by the class so that subseqent
       access is very fast.

       This function is primarily used by the descendent template classes, or
       macro, with the appropriate type conversion.

       @return
       reference to key at the index position.
     */
    virtual const PObject & AbstractGetKeyAt(
      PINDEX index  /// Ordinal position in the hash table.
    ) const;

    /**Get the data in the hash table at the ordinal index position.
    
       The ordinal position in the hash table is determined by the hash values
       of the keys and the order of insertion.

       The last key/data pair is remembered by the class so that subseqent
       access is very fast.

       This function is primarily used by the descendent template classes, or
       macro, with the appropriate type conversion.

       @return
       reference to key at the index position.
     */
    virtual PObject & AbstractGetDataAt(
      PINDEX index  /// Ordinal position in the hash table.
    ) const;
  //@}


    // Member variables
    class Element {
      public:
        friend class Table;
        PObject * key;
        PObject * data;
        Element * next;
        Element * prev;