dict.h

mgcp协议源代码。支持多种编码：g711

/*
 * 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.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 __GNUC__
#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   /// Ordinal index value to use as a key.
    );
  //@}

  /**@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;
  //@}

  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:
        PObject * key;
        PObject * data;
        Element * next;
        Element * prev;
    };

    PDECLARE_BASEARRAY(Table, Element *)
#ifdef DOC_PLUS_PLUS
    {
#endif
      public:
        virtual ~Table() { Destruct(); }
        virtual void DestroyContents();

        PINDEX AppendElement(PObject * key, PObject * data);
        PObject * RemoveElement(const PObject & key);
        BOOL SetLastElementAt(PINDEX index);
        Element * GetElementAt(const PObject & key);
        PINDEX GetElementsIndex(const PObject*obj,BOOL byVal,BOOL keys) const;

        PINDEX    lastIndex;
        PINDEX    lastBucket;
        Element * lastElement;

        BOOL deleteKeys;

      friend class PHashTable;
      friend class PAbstractSet;
    };
    friend class Table;


    Table * hashTable;
};


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

/** Abstract set of PObjects.
 */
class PAbstractSet : public PHashTable
{
  PCONTAINERINFO(PAbstractSet, PHashTable);
  public:
  /**@name Construction */
  //@{
    /**Create a new, empty, set.

       Note that by default, objects placed into the list will be deleted when
       removed or when all references to the list are destroyed.
     */
    PINLINE PAbstractSet();
  //@}

  /**@name Overrides from class PCollection */
  //@{
    /**Add a new object to the collection. If the objects value is already in
       the set then the object is {\bf not} included. If the
       #AllowDeleteObjects# option is set then the #obj# parameter
       is also deleted.

       @return
       hash function value of the newly added object.
     */
    virtual PINDEX Append(
      PObject * obj   /// New object to place into the collection.
    );

    /**Add a new object to the collection. If the objects value is already in
       the set then the object is {\bf not} included. If the
       AllowDeleteObjects option is set then the #obj# parameter is
       also deleted.
       
       The object is always placed in the an ordinal position dependent on its
       hash function. It is not placed at the specified position. The
       #before# parameter is ignored.

       @return
       hash function value of the newly added object.
     */
    virtual PINDEX Insert(
      const PObject & before,   /// Object value to insert before.
      PObject * obj             /// New object to place into the collection.
    );

    /**Add a new object to the collection. If the objects value is already in
       the set then the object is {\bf not} included. If the
       AllowDeleteObjects option is set then the #obj# parameter is
       also deleted.
       
       The object is always placed in the an ordinal position dependent on its
       hash function. It is not placed at the specified position. The
       #index# parameter is ignored.

       @return
       hash function value of the newly added object.
     */
    virtual PINDEX InsertAt(
      PINDEX index,   /// Index position in collection to place the object.
      PObject * obj   /// New object to place into the collection.
    );

    /**Remove the object from the collection. If the AllowDeleteObjects option
       is set then the object is also deleted.

       Note that the comparison for searching for the object in collection is
       made by pointer, not by value. Thus the parameter must point to the
       same instance of the object that is in the collection.

       @return
       TRUE if the object was in the collection.
     */
    virtual BOOL Remove(
      const PObject * obj   /// Existing object to remove from the collection.
    );

    /**This function is the same as PHashTable::AbstractGetKeyAt().

       @return
       Always NULL.
     */
    virtual PObject * GetAt(
      PINDEX index  /// Index position in the collection of the object.
    ) const;

    /**Add a new object to the collection. If the objects value is already in
       the set then the object is {\bf not} included. If the
       AllowDeleteObjects option is set then the #obj# parameter is
       also deleted.

       The object is always placed in the an ordinal position dependent on its
       hash function. It is not placed at the specified position. The
       #index# parameter is ignored.

       @return
       TRUE if the object was successfully added.
     */
    virtual BOOL SetAt(
      PINDEX index,   /// Index position in collection to set.
      PObject * val   /// New value to place into the collection.
    );

    /**Search the collection for the specific instance of the object. The
       object pointers are compared, not the values. The hash table is used
       to locate the entry.

       Note that that will require value comparisons to be made to find the
       equivalent entry and then a final check is made with the pointers to
       see if they are the same instance.

       @return
       ordinal index position of the object, or P_MAX_INDEX.
     */
    virtual PINDEX GetObjectsIndex(
      const PObject * obj   /// Object to find.
    ) const;

    /**Search the collection for the specified value of the object. The object
       values are compared, not the pointers.  So the objects in the