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
keyMatchesId(const AtomicString & key,const Element & element)44 inline bool keyMatchesId(const AtomicString& key, const Element& element)
45 {
46 return element.getIdAttribute() == key;
47 }
48
keyMatchesMapName(const AtomicString & key,const Element & element)49 inline bool keyMatchesMapName(const AtomicString& key, const Element& element)
50 {
51 return isHTMLMapElement(element) && toHTMLMapElement(element).getName() == key;
52 }
53
keyMatchesLowercasedMapName(const AtomicString & key,const Element & element)54 inline bool keyMatchesLowercasedMapName(const AtomicString& key, const Element& element)
55 {
56 return isHTMLMapElement(element) && toHTMLMapElement(element).getName().lower() == key;
57 }
58
keyMatchesLabelForAttribute(const AtomicString & key,const Element & element)59 inline bool keyMatchesLabelForAttribute(const AtomicString& key, const Element& element)
60 {
61 return isHTMLLabelElement(element) && element.getAttribute(forAttr) == key;
62 }
63
create()64 PassOwnPtrWillBeRawPtr<DocumentOrderedMap> DocumentOrderedMap::create()
65 {
66 return adoptPtrWillBeNoop(new DocumentOrderedMap());
67 }
68
add(const AtomicString & key,Element * element)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
remove(const AtomicString & key,Element * element)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&)>
get(const AtomicString & key,const TreeScope * scope) const110 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
getElementById(const AtomicString & key,const TreeScope * scope) const134 Element* DocumentOrderedMap::getElementById(const AtomicString& key, const TreeScope* scope) const
135 {
136 return get<keyMatchesId>(key, scope);
137 }
138
getAllElementsById(const AtomicString & key,const TreeScope * scope) const139 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
getElementByMapName(const AtomicString & key,const TreeScope * scope) const167 Element* DocumentOrderedMap::getElementByMapName(const AtomicString& key, const TreeScope* scope) const
168 {
169 return get<keyMatchesMapName>(key, scope);
170 }
171
getElementByLowercasedMapName(const AtomicString & key,const TreeScope * scope) const172 Element* DocumentOrderedMap::getElementByLowercasedMapName(const AtomicString& key, const TreeScope* scope) const
173 {
174 return get<keyMatchesLowercasedMapName>(key, scope);
175 }
176
getElementByLabelForAttribute(const AtomicString & key,const TreeScope * scope) const177 Element* DocumentOrderedMap::getElementByLabelForAttribute(const AtomicString& key, const TreeScope* scope) const
178 {
179 return get<keyMatchesLabelForAttribute>(key, scope);
180 }
181
trace(Visitor * visitor)182 void DocumentOrderedMap::trace(Visitor* visitor)
183 {
184 #if ENABLE(OILPAN)
185 visitor->trace(m_map);
186 #endif
187 }
188
trace(Visitor * visitor)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