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::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 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 void DocumentOrderedMap::trace(Visitor* visitor) 183 { 184 #if ENABLE(OILPAN) 185 visitor->trace(m_map); 186 #endif 187 } 188 189 void 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
