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

词法分析

开发平台:

Visual C++

  1. /*
  2.  * The Apache Software License, Version 1.1
  3.  *
  4.  * Copyright (c) 1999-2000 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: NameIdPool.hpp,v $
  58.  * Revision 1.6  2003/05/16 06:01:52  knoaman
  59.  * Partial implementation of the configurable memory manager.
  60.  *
  61.  * Revision 1.5  2003/05/15 19:04:35  knoaman
  62.  * Partial implementation of the configurable memory manager.
  63.  *
  64.  * Revision 1.4  2003/03/07 18:11:54  tng
  65.  * Return a reference instead of void for operator=
  66.  *
  67.  * Revision 1.3  2002/12/04 02:32:43  knoaman
  68.  * #include cleanup.
  69.  *
  70.  * Revision 1.2  2002/11/04 15:22:04  tng
  71.  * C++ Namespace Support.
  72.  *
  73.  * Revision 1.1.1.1  2002/02/01 22:22:11  peiyongz
  74.  * sane_include
  75.  *
  76.  * Revision 1.6  2000/09/09 00:11:48  andyh
  77.  * Virtual Destructor Patch, submitted by Kirk Wylie
  78.  *
  79.  * Revision 1.5  2000/07/19 18:47:26  andyh
  80.  * More Macintosh port tweaks, submitted by James Berry.
  81.  *
  82.  * Revision 1.4  2000/03/02 19:54:42  roddey
  83.  * This checkin includes many changes done while waiting for the
  84.  * 1.1.0 code to be finished. I can't list them all here, but a list is
  85.  * available elsewhere.
  86.  *
  87.  * Revision 1.3  2000/02/24 20:05:24  abagchi
  88.  * Swat for removing Log from API docs
  89.  *
  90.  * Revision 1.2  2000/02/06 07:48:02  rahulj
  91.  * Year 2K copyright swat.
  92.  *
  93.  * Revision 1.1.1.1  1999/11/09 01:04:48  twl
  94.  * Initial checkin
  95.  *
  96.  * Revision 1.3  1999/11/08 20:45:10  rahul
  97.  * Swat for adding in Product name and CVS comment log variable.
  98.  *
  99.  */
  100. #if !defined(NAMEIDPOOL_HPP)
  101. #define NAMEIDPOOL_HPP
  102. #include <xercesc/util/XMemory.hpp>
  103. #include <xercesc/util/XMLString.hpp>
  104. #include <xercesc/util/PlatformUtils.hpp>
  105. XERCES_CPP_NAMESPACE_BEGIN
  106. //
  107. //  Forward declare the enumerator so he can be our friend. Can you say
  108. //  friend? Sure...
  109. //
  110. template <class TElem> class NameIdPoolEnumerator;
  111. //
  112. //  This class is provided to serve as the basis of many of the pools that
  113. //  are used by the scanner and validators. They often need to be able to
  114. //  store objects in such a way that they can be quickly accessed by the
  115. //  name field of the object, and such that each element added is assigned
  116. //  a unique id via which it can be accessed almost instantly.
  117. //
  118. //  Object names are enforced as being unique, since that's what all these
  119. //  pools require. So its effectively a hash table in conjunction with an
  120. //  array of references into the hash table by id. Ids are assigned such that
  121. //  id N can be used to get the Nth element from the array of references.
  122. //  This provides very fast access by id.
  123. //
  124. //  The way these pools are used, elements are never removed except when the
  125. //  whole thing is flushed. This makes it very easy to maintain the two
  126. //  access methods in sync.
  127. //
  128. //  For efficiency reasons, the id refererence array is never flushed until
  129. //  the dtor. This way, it does not have to be regrown every time its reused.
  130. //
  131. //  All elements are assumed to be owned by the pool!
  132. //
  133. //  We have to have a bucket element structure to use to maintain the linked
  134. //  lists for each bucket. Because some of the compilers we have to support
  135. //  are totally brain dead, it cannot be a nested class as it should be.
  136. //
  137. template <class TElem> struct NameIdPoolBucketElem : public XMemory
  138. {
  139. public :
  140.     NameIdPoolBucketElem
  141.     (
  142.         TElem* const                            value
  143.         , NameIdPoolBucketElem<TElem>* const    next
  144.     );
  145.     ~NameIdPoolBucketElem();
  146.     TElem*                          fData;
  147.     NameIdPoolBucketElem<TElem>*    fNext;
  148. };
  149. template <class TElem> class NameIdPool : public XMemory
  150. {
  151. public :
  152.     // -----------------------------------------------------------------------
  153.     //  Contructors and Destructor
  154.     // -----------------------------------------------------------------------
  155.     NameIdPool
  156.     (
  157.         const   unsigned int    hashModulus
  158.         , const unsigned int    initSize = 128
  159.         , MemoryManager* const  manager = XMLPlatformUtils::fgMemoryManager
  160.     );
  161.     ~NameIdPool();
  162.     // -----------------------------------------------------------------------
  163.     //  Element management
  164.     // -----------------------------------------------------------------------
  165.     bool containsKey(const XMLCh* const key) const;
  166.     void removeAll();
  167.     // -----------------------------------------------------------------------
  168.     //  Getters
  169.     // -----------------------------------------------------------------------
  170.     TElem* getByKey(const XMLCh* const key);
  171.     const TElem* getByKey(const XMLCh* const key) const;
  172.     TElem* getById(const unsigned elemId);
  173.     const TElem* getById(const unsigned elemId) const;
  174.     // -----------------------------------------------------------------------
  175.     //  Putters
  176.     //
  177.     //  Dups are not allowed and cause an IllegalArgumentException. The id
  178.     //  of the new element is returned.
  179.     // -----------------------------------------------------------------------
  180.     unsigned int put(TElem* const valueToAdopt);
  181. protected :
  182.     // -----------------------------------------------------------------------
  183.     //  Declare the enumerator our friend so he can see our members
  184.     // -----------------------------------------------------------------------
  185.     friend class NameIdPoolEnumerator<TElem>;
  186. private :
  187.     // -----------------------------------------------------------------------
  188.     //  Unused constructors and operators
  189.     // -----------------------------------------------------------------------
  190.     NameIdPool(const NameIdPool<TElem>&);
  191.     NameIdPool<TElem>& operator=(const NameIdPool<TElem>&);
  192.     // -----------------------------------------------------------------------
  193.     //  Private helper methods
  194.     // -----------------------------------------------------------------------
  195.     NameIdPoolBucketElem<TElem>* findBucketElem
  196.     (
  197.         const XMLCh* const      key
  198.         ,     unsigned int&     hashVal
  199.     );
  200.     const NameIdPoolBucketElem<TElem>* findBucketElem
  201.     (
  202.         const   XMLCh* const    key
  203.         ,       unsigned int&   hashVal
  204.     )   const;
  205.     // -----------------------------------------------------------------------
  206.     //  Data members
  207.     //
  208.     //  fBucketList
  209.     //      This is the array that contains the heads of all of the list
  210.     //      buckets, one for each possible hash value.
  211.     //
  212.     //  fIdPtrs
  213.     //  fIdPtrsCount
  214.     //      This is the array of pointers to the bucket elements in order of
  215.     //      their assigned ids. So taking id N and referencing this array
  216.     //      gives you the element with that id. The count field indicates
  217.     //      the current size of this list. When fIdCounter+1 reaches this
  218.     //      value the list must be expanded.
  219.     //
  220.     //  fIdCounter
  221.     //      This is used to give out unique ids to added elements. It starts
  222.     //      at zero (which means empty), and is bumped up for each newly added
  223.     //      element. So the first element is 1, the next is 2, etc... This
  224.     //      means that this value is set to the top index of the fIdPtrs array.
  225.     //
  226.     //  fHashModulus
  227.     //      This is the modulus to use in this pool. The fBucketList array
  228.     //      is of this size. It should be a prime number.
  229.     // -----------------------------------------------------------------------
  230.     MemoryManager*                  fMemoryManager;
  231.     NameIdPoolBucketElem<TElem>**   fBucketList;
  232.     TElem**                         fIdPtrs;
  233.     unsigned int                    fIdPtrsCount;
  234.     unsigned int                    fIdCounter;
  235.     unsigned int                    fHashModulus;
  236. };
  237. //
  238. //  An enumerator for a name id pool. It derives from the basic enumerator
  239. //  class, so that pools can be generically enumerated.
  240. //
  241. template <class TElem> class NameIdPoolEnumerator : public XMLEnumerator<TElem>
  242. {
  243. public :
  244.     // -----------------------------------------------------------------------
  245.     //  Constructors and Destructor
  246.     // -----------------------------------------------------------------------
  247.     NameIdPoolEnumerator
  248.     (
  249.                 NameIdPool<TElem>* const    toEnum
  250.     );
  251.     NameIdPoolEnumerator
  252.     (
  253.         const   NameIdPoolEnumerator<TElem>& toCopy
  254.     );
  255.     virtual ~NameIdPoolEnumerator();
  256.     // -----------------------------------------------------------------------
  257.     //  Public operators
  258.     // -----------------------------------------------------------------------
  259.     NameIdPoolEnumerator<TElem>& operator=
  260.     (
  261.         const   NameIdPoolEnumerator<TElem>& toAssign
  262.     );
  263.     // -----------------------------------------------------------------------
  264.     //  Enum interface
  265.     // -----------------------------------------------------------------------
  266.     bool hasMoreElements() const;
  267.     TElem& nextElement();
  268.     void Reset();
  269. private :
  270.     // -----------------------------------------------------------------------
  271.     //  Data Members
  272.     //
  273.     //  fCurIndex
  274.     //      This is the current index into the pool's id mapping array. This
  275.     //      is now we enumerate it.
  276.     //
  277.     //  fToEnum
  278.     //      The name id pool that is being enumerated.
  279.     // -----------------------------------------------------------------------
  280.     unsigned int        fCurIndex;
  281.     NameIdPool<TElem>*  fToEnum;
  282. };
  283. XERCES_CPP_NAMESPACE_END
  284. #if !defined(XERCES_TMPLSINC)
  285. #include <xercesc/util/NameIdPool.c>
  286. #endif
  287. #endif