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
keyMatchesId(AtomicStringImpl * key,Element * element)43 inline bool keyMatchesId(AtomicStringImpl* key, Element* element)
44 {
45 return element->hasID() && element->getIdAttribute().impl() == key;
46 }
47
keyMatchesMapName(AtomicStringImpl * key,Element * element)48 inline bool keyMatchesMapName(AtomicStringImpl* key, Element* element)
49 {
50 return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().impl() == key;
51 }
52
keyMatchesLowercasedMapName(AtomicStringImpl * key,Element * element)53 inline bool keyMatchesLowercasedMapName(AtomicStringImpl* key, Element* element)
54 {
55 return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().lower().impl() == key;
56 }
57
clear()58 void DocumentOrderedMap::clear()
59 {
60 m_map.clear();
61 m_duplicateCounts.clear();
62 }
63
add(AtomicStringImpl * key,Element * element)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
remove(AtomicStringImpl * key,Element * element)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*)>
get(AtomicStringImpl * key,const TreeScope * scope) const108 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
getElementById(AtomicStringImpl * key,const TreeScope * scope) const136 Element* DocumentOrderedMap::getElementById(AtomicStringImpl* key, const TreeScope* scope) const
137 {
138 return get<keyMatchesId>(key, scope);
139 }
140
getElementByMapName(AtomicStringImpl * key,const TreeScope * scope) const141 Element* DocumentOrderedMap::getElementByMapName(AtomicStringImpl* key, const TreeScope* scope) const
142 {
143 return get<keyMatchesMapName>(key, scope);
144 }
145
getElementByLowercasedMapName(AtomicStringImpl * key,const TreeScope * scope) const146 Element* DocumentOrderedMap::getElementByLowercasedMapName(AtomicStringImpl* key, const TreeScope* scope) const
147 {
148 return get<keyMatchesLowercasedMapName>(key, scope);
149 }
150
151 } // namespace WebCore
152
153