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