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

词法分析

开发平台:

Visual C++

  1. /*
  2.  * The Apache Software License, Version 1.1
  3.  *
  4.  * Copyright (c) 2001-2002 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) 2001, 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.  * $Id: DOMNodeIDMap.cpp,v 1.4 2002/11/04 15:07:34 tng Exp $
  58.  */
  59. #include "DOMAttrImpl.hpp"
  60. #include "DOMDocumentImpl.hpp"
  61. #include "DOMNodeIDMap.hpp"
  62. #include <xercesc/util/XMLString.hpp>
  63. #include <xercesc/util/RuntimeException.hpp>
  64. #include <stdio.h>
  65. XERCES_CPP_NAMESPACE_BEGIN
  66. static const int gPrimes[] = {997, 9973, 99991, 999983, 0 };  // To do - add a few more.
  67. static const float gMaxFill = 0.8f;   // The maximum fraction of the total
  68.                                     // table entries to consume before exanding.
  69. DOMNodeIDMap::DOMNodeIDMap(int initialSize, DOMDocument *doc)
  70. {
  71.     fDoc = doc;
  72.     for (fSizeIndex = 0; gPrimes[fSizeIndex] < initialSize; fSizeIndex++)
  73.     {
  74.         if (gPrimes[fSizeIndex] == 0)
  75.         {
  76.             // We need a bigger size than the largest available one.
  77.             //   Big trouble.
  78.             fSizeIndex--;
  79.             ThrowXML(RuntimeException, XMLExcepts::NodeIDMap_GrowErr);
  80.         }
  81.     }
  82.     fSize = gPrimes[fSizeIndex];
  83.     fNumEntries = 0;
  84.     fMaxEntries = (XMLSize_t)(float(fSize) * gMaxFill);
  85.     //fTable = new (fDoc) DOMAttr*[fSize];
  86.     fTable = (DOMAttr**) ((DOMDocumentImpl *)fDoc)->allocate(sizeof(DOMAttr*) * fSize);
  87.     XMLSize_t i;
  88.     for (i=0; i<fSize; i++)
  89.         fTable[i] = 0;
  90. };
  91. DOMNodeIDMap::~DOMNodeIDMap()
  92. {
  93.     // don't delete - the document owns the storage.
  94.     fTable = 0;
  95. };
  96. void DOMNodeIDMap::add(DOMAttr *attr)
  97. {
  98. //
  99. //  If the table is getting too full, grow it.  We arbitrarily limit
  100. //   the table to 80 full, which should limit the average number of
  101. //   rehashes to a reasonable value.
  102. //
  103. if (fNumEntries >= fMaxEntries)
  104. growTable();
  105.     fNumEntries++;
  106. //
  107. // Hash the value string from the ID attribute being added to the table
  108. //      0 < Initial hash value < table size.
  109. //      An initial hash of zero would cause the rehash to fail.
  110. //
  111. const XMLCh *id=attr->getValue();
  112.     XMLSize_t initalHash = XMLString::hash(id, fSize-1);
  113. initalHash++;
  114. XMLSize_t currentHash = initalHash;
  115. //
  116. // Loop looking for an empty slot for this ID.
  117. //   Don't even bother checking to see if the ID is already there -
  118. //   the table is only filled by the parser from valid documents, which
  119. //   can not have duplicates.  Behavior of invalid docs is not defined.
  120. //
  121.     while (true)
  122. {
  123. DOMAttr *tableSlot = fTable[currentHash];
  124. if (tableSlot == 0 ||
  125. tableSlot == (DOMAttr *)-1)
  126. break;
  127. currentHash += initalHash;  // rehash
  128.         if (currentHash >= fSize)
  129.             currentHash = currentHash % fSize;
  130.     }
  131.     //
  132.     // We've found our slot.  Stick the pointer to the attr into it.
  133.     //
  134.     fTable[currentHash] = attr;
  135. };
  136. void DOMNodeIDMap::remove(DOMAttr *attr)
  137. {
  138.     //
  139. // Hash the value string from the ID attribute being added to the table
  140. //      0 < Initial hash value < table size.
  141. //      An initial hash of zero would cause the rehash to fail.
  142. //
  143. const XMLCh *id=attr->getValue();
  144.     XMLSize_t initalHash = XMLString::hash(id, fSize-1);
  145. initalHash++;
  146. XMLSize_t currentHash = initalHash;
  147. //
  148. // Loop looking for a slot pointing to an attr with this id.
  149.     //
  150.     while (true)
  151. {
  152. DOMAttr *tableSlot = fTable[currentHash];
  153. if (tableSlot == 0)
  154.         {
  155.             // There is no matching entry in the table
  156.             return;
  157.         }
  158.         if (tableSlot == attr)
  159.         {
  160.             //  Found the attribute.  Set the slot to -1 to indicate
  161.             //   that it was once used, meaning that lookups, while never
  162.             //   matching here, can not stop either, but must rehash again
  163.             //   and continue searching.
  164.             fTable[currentHash] = (DOMAttr *)-1;
  165.             return;
  166.         }
  167.         currentHash += initalHash;  // rehash.
  168.         if (currentHash >= fSize)
  169.             currentHash = currentHash % fSize;
  170.     }
  171. };
  172. DOMAttr *DOMNodeIDMap::find(const XMLCh *id)
  173. {
  174.     //
  175.     //  Get the hashcode for the supplied string.
  176.     //
  177. XMLSize_t initalHash = XMLString::hash(id, fSize-1);
  178. initalHash++;
  179. XMLSize_t currentHash = initalHash;
  180. //
  181. // Loop looking for a slot pointing to an attr with this id.
  182.     //
  183.     while (true)
  184. {
  185. DOMAttr *tableSlot = fTable[currentHash];
  186. if (tableSlot == 0)
  187.         {
  188.             // There is no matching entry in the table
  189.             return 0;
  190.         }
  191.         if ((tableSlot != (DOMAttr *)-1) && XMLString::equals(tableSlot->getValue(), id))
  192.             return tableSlot;
  193.         currentHash += initalHash;  // rehash
  194.         if (currentHash >= fSize)
  195.             currentHash = currentHash % fSize;
  196.     }
  197.     return 0;  // Never gets here, but keeps some compilers happy.
  198. };
  199. //
  200. //  Grow the table to the next larger size.
  201. //      It has gotten too full for efficient operation.
  202. //     (We never fill it all the way)
  203. //
  204. void DOMNodeIDMap::growTable()
  205. {
  206.     DOMAttr     **oldTable = fTable;
  207.     XMLSize_t oldSize  = fSize;
  208.     //
  209.     //  Figure the new table size.
  210.     //
  211. #if defined(XERCES_DEBUG)
  212.     fprintf(stderr, "growing...n");
  213. #endif
  214.     fSizeIndex++;
  215.     fSize = gPrimes[fSizeIndex];
  216.     if (fSize == 0)
  217.     {
  218.         // We need to grow bigger than the largest available size.
  219.         //   Big trouble.
  220.         fSizeIndex--;
  221.         ThrowXML(RuntimeException, XMLExcepts::NodeIDMap_GrowErr);
  222.     }
  223.     //
  224.     //  Allocate the new table.
  225.     //
  226.     //fTable = new (fDoc) DOMAttr *[fSize];
  227.     fTable = (DOMAttr**) ((DOMDocumentImpl *)fDoc)->allocate(sizeof(DOMAttr*) * fSize);
  228.     XMLSize_t i;
  229.     for (i=0; i<fSize; i++)
  230.         fTable[i] = 0;
  231.     fMaxEntries = (XMLSize_t)(float(fSize) * gMaxFill);
  232.     //
  233.     // Move entries over from the old table to the new one.
  234.     //
  235.     for (i=0; i<oldSize; i++)
  236.     {
  237.         if ((oldTable[i] != 0)  &&  (oldTable[i] != (DOMAttr *)-1))
  238.             add(oldTable[i]);
  239.     }
  240.     // delete [] oldTable;   (The document owns the storage.  The old table will just
  241.     //                        need to leak until until the document is discarded.)
  242. };
  243. XERCES_CPP_NAMESPACE_END