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 40namespace blink { 41 42using namespace HTMLNames; 43 44inline bool keyMatchesId(const AtomicString& key, const Element& element) 45{ 46 return element.getIdAttribute() == key; 47} 48 49inline bool keyMatchesMapName(const AtomicString& key, const Element& element) 50{ 51 return isHTMLMapElement(element) && toHTMLMapElement(element).getName() == key; 52} 53 54inline bool keyMatchesLowercasedMapName(const AtomicString& key, const Element& element) 55{ 56 return isHTMLMapElement(element) && toHTMLMapElement(element).getName().lower() == key; 57} 58 59inline bool keyMatchesLabelForAttribute(const AtomicString& key, const Element& element) 60{ 61 return isHTMLLabelElement(element) && element.getAttribute(forAttr) == key; 62} 63 64PassOwnPtrWillBeRawPtr<DocumentOrderedMap> DocumentOrderedMap::create() 65{ 66 return adoptPtrWillBeNoop(new DocumentOrderedMap()); 67} 68 69void 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 85void 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 109template<bool keyMatches(const AtomicString&, const Element&)> 110inline 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::firstWithin(scope->rootNode()); element; element = ElementTraversal::next(*element)) { 125 if (!keyMatches(key, *element)) 126 continue; 127 entry->element = element; 128 return element; 129 } 130 ASSERT_NOT_REACHED(); 131 return 0; 132} 133 134Element* DocumentOrderedMap::getElementById(const AtomicString& key, const TreeScope* scope) const 135{ 136 return get<keyMatchesId>(key, scope); 137} 138 139const 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 167Element* DocumentOrderedMap::getElementByMapName(const AtomicString& key, const TreeScope* scope) const 168{ 169 return get<keyMatchesMapName>(key, scope); 170} 171 172Element* DocumentOrderedMap::getElementByLowercasedMapName(const AtomicString& key, const TreeScope* scope) const 173{ 174 return get<keyMatchesLowercasedMapName>(key, scope); 175} 176 177Element* DocumentOrderedMap::getElementByLabelForAttribute(const AtomicString& key, const TreeScope* scope) const 178{ 179 return get<keyMatchesLabelForAttribute>(key, scope); 180} 181 182void DocumentOrderedMap::trace(Visitor* visitor) 183{ 184#if ENABLE(OILPAN) 185 visitor->trace(m_map); 186#endif 187} 188 189void DocumentOrderedMap::MapEntry::trace(Visitor* visitor) 190{ 191 visitor->trace(element); 192#if ENABLE(OILPAN) 193 visitor->trace(orderedList); 194#endif 195} 196 197} // namespace blink 198