src/third_party/WebKit/Source/core/dom/DocumentOrderedMap.cpp

   1 /*
   2  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #include "config.h"
  32 #include "core/dom/DocumentOrderedMap.h"
  33
  34 #include "HTMLNames.h"
  35 #include "core/dom/Element.h"
  36 #include "core/dom/ElementTraversal.h"
  37 #include "core/dom/TreeScope.h"
  38 #include "core/html/HTMLLabelElement.h"
  39 #include "core/html/HTMLMapElement.h"
  40
  41 namespace WebCore {
  42
  43 using namespace HTMLNames;
  44
  45 inline bool keyMatchesId(StringImpl* key, Element* element)
  46 {
  47     return element->getIdAttribute().impl() == key;
  48 }
  49
  50 inline bool keyMatchesMapName(StringImpl* key, Element* element)
  51 {
  52     return element->hasTagName(mapTag) && toHTMLMapElement(element)->getName().impl() == key;
  53 }
  54
  55 inline bool keyMatchesLowercasedMapName(StringImpl* key, Element* element)
  56 {
  57     return element->hasTagName(mapTag) && toHTMLMapElement(element)->getName().lower().impl() == key;
  58 }
  59
  60 inline bool keyMatchesLabelForAttribute(StringImpl* key, Element* element)
  61 {
  62     return isHTMLLabelElement(element) && element->getAttribute(forAttr).impl() == key;
  63 }
  64
  65 void DocumentOrderedMap::clear()
  66 {
  67     m_map.clear();
  68     m_duplicateCounts.clear();
  69 }
  70
  71 void DocumentOrderedMap::add(StringImpl* key, Element* element)
  72 {
  73     ASSERT(key);
  74     ASSERT(element);
  75
  76     if (!m_duplicateCounts.contains(key)) {
  77         // Fast path. The key is not already in m_duplicateCounts, so we assume that it's
  78         // also not already in m_map and try to add it. If that add succeeds, we're done.
  79         Map::AddResult addResult = m_map.add(key, element);
  80         if (addResult.isNewEntry)
  81             return;
  82
  83         // The add failed, so this key was already cached in m_map.
  84         // There are multiple elements with this key. Remove the m_map
  85         // cache for this key so get searches for it next time it is called.
  86         m_map.remove(addResult.iterator);
  87         m_duplicateCounts.add(key);
  88     } else {
  89         // There are multiple elements with this key. Remove the m_map
  90         // cache for this key so get will search for it next time it is called.
  91         Map::iterator cachedItem = m_map.find(key);
  92         if (cachedItem != m_map.end()) {
  93             m_map.remove(cachedItem);
  94             m_duplicateCounts.add(key);
  95         }
  96     }
  97
  98     m_duplicateCounts.add(key);
  99 }
 100
 101 void DocumentOrderedMap::remove(StringImpl* key, Element* element)
 102 {
 103     ASSERT(key);
 104     ASSERT(element);
 105
 106     Map::iterator cachedItem = m_map.find(key);
 107     if (cachedItem != m_map.end() && cachedItem->value == element)
 108         m_map.remove(cachedItem);
 109     else
 110         m_duplicateCounts.remove(key);
 111 }
 112
 113 template<bool keyMatches(StringImpl*, Element*)>
 114 inline Element* DocumentOrderedMap::get(StringImpl* key, const TreeScope* scope) const
 115 {
 116     ASSERT(key);
 117     ASSERT(scope);
 118
 119     Element* element = m_map.get(key);
 120     if (element)
 121         return element;
 122
 123     if (m_duplicateCounts.contains(key)) {
 124         // We know there's at least one node that matches; iterate to find the first one.
 125         for (element = ElementTraversal::firstWithin(scope->rootNode()); element; element = ElementTraversal::next(element)) {
 126             if (!keyMatches(key, element))
 127                 continue;
 128             m_duplicateCounts.remove(key);
 129             m_map.set(key, element);
 130             return element;
 131         }
 132         ASSERT_NOT_REACHED();
 133     }
 134
 135     return 0;
 136 }
 137
 138 Element* DocumentOrderedMap::getElementById(StringImpl* key, const TreeScope* scope) const
 139 {
 140     return get<keyMatchesId>(key, scope);
 141 }
 142
 143 Element* DocumentOrderedMap::getElementByMapName(StringImpl* key, const TreeScope* scope) const
 144 {
 145     return get<keyMatchesMapName>(key, scope);
 146 }
 147
 148 Element* DocumentOrderedMap::getElementByLowercasedMapName(StringImpl* key, const TreeScope* scope) const
 149 {
 150     return get<keyMatchesLowercasedMapName>(key, scope);
 151 }
 152
 153 Element* DocumentOrderedMap::getElementByLabelForAttribute(StringImpl* key, const TreeScope* scope) const
 154 {
 155     return get<keyMatchesLabelForAttribute>(key, scope);
 156 }
 157
 158 } // namespace WebCore