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 "core/HTMLNames.h"
  35 #include "core/dom/Element.h"
  36 #include "core/dom/ElementTraversal.h"
  37 #include "core/dom/TreeScope.h"
  38 #include "core/html/HTMLMapElement.h"
  39
  40 namespace blink {
  41
  42 using namespace HTMLNames;
  43
  44 inline bool keyMatchesId(const AtomicString& key, const Element& element)
  45 {
  46     return element.getIdAttribute() == key;
  47 }
  48
  49 inline bool keyMatchesMapName(const AtomicString& key, const Element& element)
  50 {
  51     return isHTMLMapElement(element) && toHTMLMapElement(element).getName() == key;
  52 }
  53
  54 inline bool keyMatchesLowercasedMapName(const AtomicString& key, const Element& element)
  55 {
  56     return isHTMLMapElement(element) && toHTMLMapElement(element).getName().lower() == key;
  57 }
  58
  59 inline bool keyMatchesLabelForAttribute(const AtomicString& key, const Element& element)
  60 {
  61     return isHTMLLabelElement(element) && element.getAttribute(forAttr) == key;
  62 }
  63
  64 PassOwnPtrWillBeRawPtr<DocumentOrderedMap> DocumentOrderedMap::create()
  65 {
  66     return adoptPtrWillBeNoop(new DocumentOrderedMap());
  67 }
  68
  69 void DocumentOrderedMap::add(const AtomicString& key, Element* element)
  70 {
  71     ASSERT(key);
  72     ASSERT(element);
  73
  74     Map::AddResult addResult = m_map.add(key, adoptPtrWillBeNoop(new MapEntry(element)));
  75     if (addResult.isNewEntry)
  76         return;
  77
  78     OwnPtrWillBeMember<MapEntry>& entry = addResult.storedValue->value;
  79     ASSERT(entry->count);
  80     entry->element = nullptr;
  81     entry->count++;
  82     entry->orderedList.clear();
  83 }
  84
  85 void DocumentOrderedMap::remove(const AtomicString& key, Element* element)
  86 {
  87     ASSERT(key);
  88     ASSERT(element);
  89
  90     Map::iterator it = m_map.find(key);
  91     if (it == m_map.end())
  92         return;
  93
  94     OwnPtrWillBeMember<MapEntry>& entry = it->value;
  95     ASSERT(entry->count);
  96     if (entry->count == 1) {
  97         ASSERT(!entry->element || entry->element == element);
  98         m_map.remove(it);
  99     } else {
 100         if (entry->element == element) {
 101             ASSERT(entry->orderedList.isEmpty() || entry->orderedList.first() == element);
 102             entry->element = entry->orderedList.size() > 1 ? entry->orderedList[1] : nullptr;
 103         }
 104         entry->count--;
 105         entry->orderedList.clear();
 106     }
 107 }
 108
 109 template<bool keyMatches(const AtomicString&, const Element&)>
 110 inline Element* DocumentOrderedMap::get(const AtomicString& key, const TreeScope* scope) const
 111 {
 112     ASSERT(key);
 113     ASSERT(scope);
 114
 115     MapEntry* entry = m_map.get(key);
 116     if (!entry)
 117         return 0;
 118
 119     ASSERT(entry->count);
 120     if (entry->element)
 121         return entry->element;
 122
 123     // We know there's at least one node that matches; iterate to find the first one.
 124     for (Element& element : ElementTraversal::startsAfter(scope->rootNode())) {
 125         if (!keyMatches(key, element))
 126             continue;
 127         entry->element = &element;
 128         return &element;
 129     }
 130     ASSERT_NOT_REACHED();
 131     return 0;
 132 }
 133
 134 Element* DocumentOrderedMap::getElementById(const AtomicString& key, const TreeScope* scope) const
 135 {
 136     return get<keyMatchesId>(key, scope);
 137 }
 138
 139 const WillBeHeapVector<RawPtrWillBeMember<Element>>& DocumentOrderedMap::getAllElementsById(const AtomicString& key, const TreeScope* scope) const
 140 {
 141     ASSERT(key);
 142     ASSERT(scope);
 143     DEFINE_STATIC_LOCAL(OwnPtrWillBePersistent<WillBeHeapVector<RawPtrWillBeMember<Element>>>, emptyVector, (adoptPtrWillBeNoop(new WillBeHeapVector<RawPtrWillBeMember<Element>>())));
 144
 145     Map::iterator it = m_map.find(key);
 146     if (it == m_map.end())
 147         return *emptyVector;
 148
 149     OwnPtrWillBeMember<MapEntry>& entry = it->value;
 150     ASSERT(entry->count);
 151
 152     if (entry->orderedList.isEmpty()) {
 153         entry->orderedList.reserveCapacity(entry->count);
 154         for (Element* element = entry->element ? entry->element.get() : ElementTraversal::firstWithin(scope->rootNode()); entry->orderedList.size() < entry->count; element = ElementTraversal::next(*element)) {
 155             ASSERT(element);
 156             if (!keyMatchesId(key, *element))
 157                 continue;
 158             entry->orderedList.uncheckedAppend(element);
 159         }
 160         if (!entry->element)
 161             entry->element = entry->orderedList.first();
 162     }
 163
 164     return entry->orderedList;
 165 }
 166
 167 Element* DocumentOrderedMap::getElementByMapName(const AtomicString& key, const TreeScope* scope) const
 168 {
 169     return get<keyMatchesMapName>(key, scope);
 170 }
 171
 172 Element* DocumentOrderedMap::getElementByLowercasedMapName(const AtomicString& key, const TreeScope* scope) const
 173 {
 174     return get<keyMatchesLowercasedMapName>(key, scope);
 175 }
 176
 177 Element* DocumentOrderedMap::getElementByLabelForAttribute(const AtomicString& key, const TreeScope* scope) const
 178 {
 179     return get<keyMatchesLabelForAttribute>(key, scope);
 180 }
 181
 182 DEFINE_TRACE(DocumentOrderedMap)
 183 {
 184 #if ENABLE(OILPAN)
 185     visitor->trace(m_map);
 186 #endif
 187 }
 188
 189 DEFINE_TRACE(DocumentOrderedMap::MapEntry)
 190 {
 191     visitor->trace(element);
 192 #if ENABLE(OILPAN)
 193     visitor->trace(orderedList);
 194 #endif
 195 }
 196
 197 } // namespace blink