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