RefHashTableOf.hpp
上传用户:zhuqijet
上传日期:2013-06-25
资源大小:10074k
文件大小:13k
源码类别:

词法分析

开发平台:

Visual C++

  1. /*
  2.  * The Apache Software License, Version 1.1
  3.  *
  4.  * Copyright (c) 1999-2003 The Apache Software Foundation.  All rights
  5.  * reserved.
  6.  *
  7.  * Redistribution and use in source and binary forms, with or without
  8.  * modification, are permitted provided that the following conditions
  9.  * are met:
  10.  *
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  *
  14.  * 2. Redistributions in binary form must reproduce the above copyright
  15.  *    notice, this list of conditions and the following disclaimer in
  16.  *    the documentation and/or other materials provided with the
  17.  *    distribution.
  18.  *
  19.  * 3. The end-user documentation included with the redistribution,
  20.  *    if any, must include the following acknowledgment:
  21.  *       "This product includes software developed by the
  22.  *        Apache Software Foundation (http://www.apache.org/)."
  23.  *    Alternately, this acknowledgment may appear in the software itself,
  24.  *    if and wherever such third-party acknowledgments normally appear.
  25.  *
  26.  * 4. The names "Xerces" and "Apache Software Foundation" must
  27.  *    not be used to endorse or promote products derived from this
  28.  *    software without prior written permission. For written
  29.  *    permission, please contact apache@apache.org.
  30.  *
  31.  * 5. Products derived from this software may not be called "Apache",
  32.  *    nor may "Apache" appear in their name, without prior written
  33.  *    permission of the Apache Software Foundation.
  34.  *
  35.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  36.  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  37.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  38.  * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  39.  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  40.  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  41.  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  42.  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  43.  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  44.  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  45.  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  46.  * SUCH DAMAGE.
  47.  * ====================================================================
  48.  *
  49.  * This software consists of voluntary contributions made by many
  50.  * individuals on behalf of the Apache Software Foundation, and was
  51.  * originally based on software copyright (c) 1999, International
  52.  * Business Machines, Inc., http://www.ibm.com .  For more information
  53.  * on the Apache Software Foundation, please see
  54.  * <http://www.apache.org/>.
  55.  */
  56. /*
  57.  * $Log: RefHashTableOf.hpp,v $
  58.  * Revision 1.10  2003/05/18 14:02:05  knoaman
  59.  * Memory manager implementation: pass per instance manager.
  60.  *
  61.  * Revision 1.9  2003/05/16 21:36:59  knoaman
  62.  * Memory manager implementation: Modify constructors to pass in the memory manager.
  63.  *
  64.  * Revision 1.8  2003/05/15 19:04:35  knoaman
  65.  * Partial implementation of the configurable memory manager.
  66.  *
  67.  * Revision 1.7  2003/05/15 10:37:08  gareth
  68.  * Optimization. We now resize the hash when appropriate. Patch by Nathan Codding.
  69.  *
  70.  * Revision 1.6  2002/11/04 15:22:04  tng
  71.  * C++ Namespace Support.
  72.  *
  73.  * Revision 1.5  2002/08/21 17:45:00  tng
  74.  * [Bug 7087] compiler warnings when using gcc.
  75.  *
  76.  * Revision 1.4  2002/07/11 18:49:53  knoaman
  77.  * Add setAdoptElements method.
  78.  * Rename removeBucketElemSafe to orphanKey.
  79.  *
  80.  * Revision 1.3  2002/07/04 15:24:57  tng
  81.  * DOM L3: add transferElement and removeBucketElemSafe for use in DOMDocument::renameNode.
  82.  *
  83.  * Revision 1.2  2002/06/12 17:14:03  tng
  84.  * Add function cleanup, reinitialize and nextElementKey for ease of use.
  85.  *
  86.  * Revision 1.1.1.1  2002/02/01 22:22:12  peiyongz
  87.  * sane_include
  88.  *
  89.  * Revision 1.9  2001/06/04 13:45:04  tng
  90.  * The "hash" argument clashes with STL hash.  Fixed by Pei Yong Zhang.
  91.  *
  92.  * Revision 1.8  2000/07/07 22:16:51  jpolast
  93.  * remove old put(value) function.  use put(key,value) instead.
  94.  *
  95.  * Revision 1.7  2000/06/29 18:27:09  jpolast
  96.  * bug fix for passing hasher class references to constructor
  97.  *
  98.  * Revision 1.6  2000/06/27 22:11:12  jpolast
  99.  * added more general functionality to hashtables.
  100.  * able to specify which hasher to use.
  101.  * default: HashXMLCh [hashes XMLCh* strings]
  102.  *
  103.  * future todo: make hasher class references static so only
  104.  * one instance of a hasher is ever created.
  105.  *
  106.  * Revision 1.5  2000/03/02 19:54:44  roddey
  107.  * This checkin includes many changes done while waiting for the
  108.  * 1.1.0 code to be finished. I can't list them all here, but a list is
  109.  * available elsewhere.
  110.  *
  111.  * Revision 1.4  2000/02/24 20:05:25  abagchi
  112.  * Swat for removing Log from API docs
  113.  *
  114.  * Revision 1.3  2000/02/06 07:48:03  rahulj
  115.  * Year 2K copyright swat.
  116.  *
  117.  * Revision 1.2  1999/12/18 00:18:10  roddey
  118.  * More changes to support the new, completely orthagonal support for
  119.  * intrinsic encodings.
  120.  *
  121.  * Revision 1.1.1.1  1999/11/09 01:05:01  twl
  122.  * Initial checkin
  123.  *
  124.  * Revision 1.2  1999/11/08 20:45:12  rahul
  125.  * Swat for adding in Product name and CVS comment log variable.
  126.  *
  127.  */
  128. #if !defined(REFHASHTABLEOF_HPP)
  129. #define REFHASHTABLEOF_HPP
  130. #include <xercesc/util/HashBase.hpp>
  131. #include <xercesc/util/IllegalArgumentException.hpp>
  132. #include <xercesc/util/NoSuchElementException.hpp>
  133. #include <xercesc/util/RuntimeException.hpp>
  134. #include <xercesc/util/XMLString.hpp>
  135. #include <xercesc/util/HashXMLCh.hpp>
  136. #include <xercesc/util/PlatformUtils.hpp>
  137. #include <xercesc/framework/MemoryManager.hpp>
  138. XERCES_CPP_NAMESPACE_BEGIN
  139. //
  140. //  Forward declare the enumerator so he can be our friend. Can you say
  141. //  friend? Sure...
  142. //
  143. template <class TVal> class RefHashTableOfEnumerator;
  144. template <class TVal> struct RefHashTableBucketElem;
  145. //
  146. //  This should really be a nested class, but some of the compilers we
  147. //  have to support cannot deal with that!
  148. //
  149. template <class TVal> struct RefHashTableBucketElem : public XMemory
  150. {
  151.     RefHashTableBucketElem(void* key, TVal* const value, RefHashTableBucketElem<TVal>* next)
  152. : fData(value), fNext(next), fKey(key)
  153.         {
  154.         }
  155.     TVal*                           fData;
  156.     RefHashTableBucketElem<TVal>*   fNext;
  157. void* fKey;
  158. };
  159. template <class TVal> class RefHashTableOf : public XMemory
  160. {
  161. public:
  162.     // -----------------------------------------------------------------------
  163.     //  Constructors and Destructor
  164.     // -----------------------------------------------------------------------
  165. // backwards compatability - default hasher is HashXMLCh
  166.     RefHashTableOf
  167.     (
  168.         const unsigned int modulus
  169.         , MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager
  170.     );
  171. // backwards compatability - default hasher is HashXMLCh
  172.     RefHashTableOf
  173.     (
  174.         const unsigned int modulus
  175.         , const bool adoptElems
  176.         , MemoryManager* const manager =  XMLPlatformUtils::fgMemoryManager
  177.     );
  178. // if a hash function is passed in, it will be deleted when the hashtable is deleted.
  179. // use a new instance of the hasher class for each hashtable, otherwise one hashtable
  180. // may delete the hasher of a different hashtable if both use the same hasher.
  181.     RefHashTableOf
  182.     (
  183.         const unsigned int modulus
  184.         , const bool adoptElems
  185.         , HashBase* hashBase
  186.         , MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager
  187.     );
  188.     ~RefHashTableOf();
  189.     // -----------------------------------------------------------------------
  190.     //  Element management
  191.     // -----------------------------------------------------------------------
  192.     bool isEmpty() const;
  193.     bool containsKey(const void* const key) const;
  194.     void removeKey(const void* const key);
  195.     void removeAll();
  196.     void cleanup();
  197.     void reinitialize(HashBase* hashBase);
  198.     void transferElement(const void* const key1, void* key2);
  199.     TVal* orphanKey(const void* const key);
  200.     // -----------------------------------------------------------------------
  201.     //  Getters
  202.     // -----------------------------------------------------------------------
  203.     TVal* get(const void* const key);
  204.     const TVal* get(const void* const key) const;
  205.     MemoryManager* getMemoryManager() const;
  206.     // -----------------------------------------------------------------------
  207.     //  Setters
  208.     // -----------------------------------------------------------------------
  209.     void setAdoptElements(const bool aValue);
  210.     // -----------------------------------------------------------------------
  211.     //  Putters
  212.     // -----------------------------------------------------------------------
  213. void put(void* key, TVal* const valueToAdopt);
  214. private :
  215.     // -----------------------------------------------------------------------
  216.     //  Declare our friends
  217.     // -----------------------------------------------------------------------
  218.     friend class RefHashTableOfEnumerator<TVal>;
  219. private:
  220.     // -----------------------------------------------------------------------
  221.     //  Private methods
  222.     // -----------------------------------------------------------------------
  223.     RefHashTableBucketElem<TVal>* findBucketElem(const void* const key, unsigned int& hashVal);
  224.     const RefHashTableBucketElem<TVal>* findBucketElem(const void* const key, unsigned int& hashVal) const;
  225.     void removeBucketElem(const void* const key, unsigned int& hashVal);
  226.     void initialize(const unsigned int modulus);
  227.     void rehash();
  228.     // -----------------------------------------------------------------------
  229.     //  Data members
  230.     //
  231.     //  fAdoptedElems
  232.     //      Indicates whether the values added are adopted or just referenced.
  233.     //      If adopted, then they are deleted when they are removed from the
  234.     //      hash table.
  235.     //
  236.     //  fBucketList
  237.     //      This is the array that contains the heads of all of the list
  238.     //      buckets, one for each possible hash value.
  239.     //
  240.     //  fHashModulus
  241.     //      The modulus used for this hash table, to hash the keys. This is
  242.     //      also the number of elements in the bucket list.
  243. //
  244. //  fHash
  245. //      The hasher for the key data type.
  246.     // -----------------------------------------------------------------------
  247.     MemoryManager*                 fMemoryManager;
  248.     bool                           fAdoptedElems;
  249.     RefHashTableBucketElem<TVal>** fBucketList;
  250.     unsigned int                   fHashModulus;
  251.     unsigned int                   fInitialModulus;
  252.     unsigned int                   fCount;
  253.     HashBase*                      fHash;
  254. };
  255. //
  256. //  An enumerator for a value array. It derives from the basic enumerator
  257. //  class, so that value vectors can be generically enumerated.
  258. //
  259. template <class TVal> class RefHashTableOfEnumerator : public XMLEnumerator<TVal>
  260. {
  261. public :
  262.     // -----------------------------------------------------------------------
  263.     //  Constructors and Destructor
  264.     // -----------------------------------------------------------------------
  265.     RefHashTableOfEnumerator(RefHashTableOf<TVal>* const toEnum, const bool adopt = false);
  266.     virtual ~RefHashTableOfEnumerator();
  267.     // -----------------------------------------------------------------------
  268.     //  Enum interface
  269.     // -----------------------------------------------------------------------
  270.     bool hasMoreElements() const;
  271.     TVal& nextElement();
  272.     void Reset();
  273.     // -----------------------------------------------------------------------
  274.     //  New interface specific for key used in RefHashable
  275.     // -----------------------------------------------------------------------
  276.     void* nextElementKey();
  277. private :
  278.     // -----------------------------------------------------------------------
  279.     //  Private methods
  280.     // -----------------------------------------------------------------------
  281.     void findNext();
  282.     // -----------------------------------------------------------------------
  283.     //  Data Members
  284.     //
  285.     //  fAdopted
  286.     //      Indicates whether we have adopted the passed vector. If so then
  287.     //      we delete the vector when we are destroyed.
  288.     //
  289.     //  fCurElem
  290.     //      This is the current bucket bucket element that we are on.
  291.     //
  292.     //  fCurHash
  293.     //      The is the current hash buck that we are working on. Once we hit
  294.     //      the end of the bucket that fCurElem is in, then we have to start
  295.     //      working this one up to the next non-empty bucket.
  296.     //
  297.     //  fToEnum
  298.     //      The value array being enumerated.
  299.     // -----------------------------------------------------------------------
  300.     bool                                  fAdopted;
  301.     RefHashTableBucketElem<TVal>*         fCurElem;
  302.     unsigned int                          fCurHash;
  303.     RefHashTableOf<TVal>*                 fToEnum;
  304. };
  305. XERCES_CPP_NAMESPACE_END
  306. #if !defined(XERCES_TMPLSINC)
  307. #include <xercesc/util/RefHashTableOf.c>
  308. #endif
  309. #endif