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 "DocumentOrderedMap.h" 33 34#include "Element.h" 35#include "HTMLMapElement.h" 36#include "HTMLNameCollection.h" 37#include "HTMLNames.h" 38#include "NodeTraversal.h" 39#include "TreeScope.h" 40 41namespace WebCore { 42 43using namespace HTMLNames; 44 45inline bool keyMatchesId(AtomicStringImpl* key, Element* element) 46{ 47 return element->getIdAttribute().impl() == key; 48} 49 50inline bool keyMatchesName(AtomicStringImpl* key, Element* element) 51{ 52 return element->getNameAttribute().impl() == key; 53} 54 55inline bool keyMatchesMapName(AtomicStringImpl* key, Element* element) 56{ 57 return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().impl() == key; 58} 59 60inline bool keyMatchesLowercasedMapName(AtomicStringImpl* key, Element* element) 61{ 62 return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().lower().impl() == key; 63} 64 65inline bool keyMatchesLabelForAttribute(AtomicStringImpl* key, Element* element) 66{ 67 return element->hasTagName(labelTag) && element->getAttribute(forAttr).impl() == key; 68} 69 70inline bool keyMatchesWindowNamedItem(AtomicStringImpl* key, Element* element) 71{ 72 return WindowNameCollection::nodeMatches(element, key); 73} 74 75inline bool keyMatchesDocumentNamedItem(AtomicStringImpl* key, Element* element) 76{ 77 return DocumentNameCollection::nodeMatches(element, key); 78} 79 80void DocumentOrderedMap::clear() 81{ 82 m_map.clear(); 83} 84 85void DocumentOrderedMap::add(AtomicStringImpl* key, Element* element, const TreeScope* treeScope) 86{ 87 ASSERT_WITH_SECURITY_IMPLICATION(element->isInTreeScope()); 88 ASSERT_WITH_SECURITY_IMPLICATION(treeScope->rootNode()->containsIncludingShadowDOM(element)); 89 if (!element->isInTreeScope() || element->document() != treeScope->documentScope()) 90 return; 91 Map::AddResult addResult = m_map.add(key, MapEntry(element)); 92 if (addResult.isNewEntry) 93 return; 94 95 MapEntry& entry = addResult.iterator->value; 96 ASSERT_WITH_SECURITY_IMPLICATION(entry.count); 97 entry.element = 0; 98 entry.count++; 99 entry.orderedList.clear(); 100} 101 102void DocumentOrderedMap::remove(AtomicStringImpl* key, Element* element) 103{ 104 ASSERT(key); 105 ASSERT(element); 106 107 m_map.checkConsistency(); 108 Map::iterator it = m_map.find(key); 109 ASSERT_WITH_SECURITY_IMPLICATION(it != m_map.end()); 110 if (it == m_map.end()) 111 return; 112 MapEntry& entry = it->value; 113 114 ASSERT_WITH_SECURITY_IMPLICATION(entry.count); 115 if (entry.count == 1) { 116 ASSERT_WITH_SECURITY_IMPLICATION(!entry.element || entry.element == element); 117 m_map.remove(it); 118 } else { 119 if (entry.element == element) 120 entry.element = 0; 121 entry.count--; 122 entry.orderedList.clear(); // FIXME: Remove the element instead if there are only few items left. 123 } 124} 125 126template<bool keyMatches(AtomicStringImpl*, Element*)> 127inline Element* DocumentOrderedMap::get(AtomicStringImpl* key, const TreeScope* scope) const 128{ 129 ASSERT(key); 130 ASSERT(scope); 131 132 m_map.checkConsistency(); 133 134 Map::iterator it = m_map.find(key); 135 if (it == m_map.end()) 136 return 0; 137 138 MapEntry& entry = it->value; 139 ASSERT(entry.count); 140 if (entry.element) { 141 ASSERT_WITH_SECURITY_IMPLICATION(entry.element->isInTreeScope()); 142 ASSERT_WITH_SECURITY_IMPLICATION(entry.element->treeScope() == scope); 143 return entry.element; 144 } 145 146 // We know there's at least one node that matches; iterate to find the first one. 147 for (Element* element = ElementTraversal::firstWithin(scope->rootNode()); element; element = ElementTraversal::next(element)) { 148 if (!keyMatches(key, element)) 149 continue; 150 entry.element = element; 151 ASSERT_WITH_SECURITY_IMPLICATION(element->isInTreeScope()); 152 ASSERT_WITH_SECURITY_IMPLICATION(element->treeScope() == scope); 153 return element; 154 } 155 ASSERT_NOT_REACHED(); 156 return 0; 157} 158 159Element* DocumentOrderedMap::getElementById(AtomicStringImpl* key, const TreeScope* scope) const 160{ 161 return get<keyMatchesId>(key, scope); 162} 163 164Element* DocumentOrderedMap::getElementByName(AtomicStringImpl* key, const TreeScope* scope) const 165{ 166 return get<keyMatchesName>(key, scope); 167} 168 169Element* DocumentOrderedMap::getElementByMapName(AtomicStringImpl* key, const TreeScope* scope) const 170{ 171 return get<keyMatchesMapName>(key, scope); 172} 173 174Element* DocumentOrderedMap::getElementByLowercasedMapName(AtomicStringImpl* key, const TreeScope* scope) const 175{ 176 return get<keyMatchesLowercasedMapName>(key, scope); 177} 178 179Element* DocumentOrderedMap::getElementByLabelForAttribute(AtomicStringImpl* key, const TreeScope* scope) const 180{ 181 return get<keyMatchesLabelForAttribute>(key, scope); 182} 183 184Element* DocumentOrderedMap::getElementByWindowNamedItem(AtomicStringImpl* key, const TreeScope* scope) const 185{ 186 return get<keyMatchesWindowNamedItem>(key, scope); 187} 188 189Element* DocumentOrderedMap::getElementByDocumentNamedItem(AtomicStringImpl* key, const TreeScope* scope) const 190{ 191 return get<keyMatchesDocumentNamedItem>(key, scope); 192} 193 194const Vector<Element*>* DocumentOrderedMap::getAllElementsById(AtomicStringImpl* key, const TreeScope* scope) const 195{ 196 ASSERT(key); 197 ASSERT(scope); 198 199 m_map.checkConsistency(); 200 201 Map::iterator it = m_map.find(key); 202 if (it == m_map.end()) 203 return 0; 204 205 MapEntry& entry = it->value; 206 ASSERT_WITH_SECURITY_IMPLICATION(entry.count); 207 if (!entry.count) 208 return 0; 209 210 if (entry.orderedList.isEmpty()) { 211 entry.orderedList.reserveCapacity(entry.count); 212 for (Element* element = entry.element ? entry.element : ElementTraversal::firstWithin(scope->rootNode()); element; element = ElementTraversal::next(element)) { 213 if (!keyMatchesId(key, element)) 214 continue; 215 entry.orderedList.append(element); 216 } 217 ASSERT(entry.orderedList.size() == entry.count); 218 } 219 220 return &entry.orderedList; 221} 222 223} // namespace WebCore 224