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 "HTMLNames.h" 37 #include "TreeScope.h" 38 39 namespace WebCore { 40 41 using namespace HTMLNames; 42 43 inline bool keyMatchesId(AtomicStringImpl* key, Element* element) 44 { 45 return element->hasID() && element->getIdAttribute().impl() == key; 46 } 47 48 inline bool keyMatchesMapName(AtomicStringImpl* key, Element* element) 49 { 50 return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().impl() == key; 51 } 52 53 inline bool keyMatchesLowercasedMapName(AtomicStringImpl* key, Element* element) 54 { 55 return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().lower().impl() == key; 56 } 57 58 void DocumentOrderedMap::clear() 59 { 60 m_map.clear(); 61 m_duplicateCounts.clear(); 62 } 63 64 void DocumentOrderedMap::add(AtomicStringImpl* key, Element* element) 65 { 66 ASSERT(key); 67 ASSERT(element); 68 69 if (!m_duplicateCounts.contains(key)) { 70 // Fast path. The key is not already in m_duplicateCounts, so we assume that it's 71 // also not already in m_map and try to add it. If that add succeeds, we're done. 72 pair<Map::iterator, bool> addResult = m_map.add(key, element); 73 if (addResult.second) 74 return; 75 76 // The add failed, so this key was already cached in m_map. 77 // There are multiple elements with this key. Remove the m_map 78 // cache for this key so get searches for it next time it is called. 79 m_map.remove(addResult.first); 80 m_duplicateCounts.add(key); 81 } else { 82 // There are multiple elements with this key. Remove the m_map 83 // cache for this key so get will search for it next time it is called. 84 Map::iterator cachedItem = m_map.find(key); 85 if (cachedItem != m_map.end()) { 86 m_map.remove(cachedItem); 87 m_duplicateCounts.add(key); 88 } 89 } 90 91 m_duplicateCounts.add(key); 92 } 93 94 void DocumentOrderedMap::remove(AtomicStringImpl* key, Element* element) 95 { 96 ASSERT(key); 97 ASSERT(element); 98 99 m_map.checkConsistency(); 100 Map::iterator cachedItem = m_map.find(key); 101 if (cachedItem != m_map.end() && cachedItem->second == element) 102 m_map.remove(cachedItem); 103 else 104 m_duplicateCounts.remove(key); 105 } 106 107 template<bool keyMatches(AtomicStringImpl*, Element*)> 108 inline Element* DocumentOrderedMap::get(AtomicStringImpl* key, const TreeScope* scope) const 109 { 110 ASSERT(key); 111 112 m_map.checkConsistency(); 113 114 Element* element = m_map.get(key); 115 if (element) 116 return element; 117 118 if (m_duplicateCounts.contains(key)) { 119 // We know there's at least one node that matches; iterate to find the first one. 120 for (Node* node = scope->firstChild(); node; node = node->traverseNextNode()) { 121 if (!node->isElementNode()) 122 continue; 123 element = static_cast<Element*>(node); 124 if (!keyMatches(key, element)) 125 continue; 126 m_duplicateCounts.remove(key); 127 m_map.set(key, element); 128 return element; 129 } 130 ASSERT_NOT_REACHED(); 131 } 132 133 return 0; 134 } 135 136 Element* DocumentOrderedMap::getElementById(AtomicStringImpl* key, const TreeScope* scope) const 137 { 138 return get<keyMatchesId>(key, scope); 139 } 140 141 Element* DocumentOrderedMap::getElementByMapName(AtomicStringImpl* key, const TreeScope* scope) const 142 { 143 return get<keyMatchesMapName>(key, scope); 144 } 145 146 Element* DocumentOrderedMap::getElementByLowercasedMapName(AtomicStringImpl* key, const TreeScope* scope) const 147 { 148 return get<keyMatchesLowercasedMapName>(key, scope); 149 } 150 151 } // namespace WebCore 152 153
