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
40namespace blink {
41
42using namespace HTMLNames;
43
44inline bool keyMatchesId(const AtomicString& key, const Element& element)
45{
46    return element.getIdAttribute() == key;
47}
48
49inline bool keyMatchesMapName(const AtomicString& key, const Element& element)
50{
51    return isHTMLMapElement(element) && toHTMLMapElement(element).getName() == key;
52}
53
54inline bool keyMatchesLowercasedMapName(const AtomicString& key, const Element& element)
55{
56    return isHTMLMapElement(element) && toHTMLMapElement(element).getName().lower() == key;
57}
58
59inline bool keyMatchesLabelForAttribute(const AtomicString& key, const Element& element)
60{
61    return isHTMLLabelElement(element) && element.getAttribute(forAttr) == key;
62}
63
64PassOwnPtrWillBeRawPtr<DocumentOrderedMap> DocumentOrderedMap::create()
65{
66    return adoptPtrWillBeNoop(new DocumentOrderedMap());
67}
68
69void 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
85void 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
109template<bool keyMatches(const AtomicString&, const Element&)>
110inline 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
134Element* DocumentOrderedMap::getElementById(const AtomicString& key, const TreeScope* scope) const
135{
136    return get<keyMatchesId>(key, scope);
137}
138
139const 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
167Element* DocumentOrderedMap::getElementByMapName(const AtomicString& key, const TreeScope* scope) const
168{
169    return get<keyMatchesMapName>(key, scope);
170}
171
172Element* DocumentOrderedMap::getElementByLowercasedMapName(const AtomicString& key, const TreeScope* scope) const
173{
174    return get<keyMatchesLowercasedMapName>(key, scope);
175}
176
177Element* DocumentOrderedMap::getElementByLabelForAttribute(const AtomicString& key, const TreeScope* scope) const
178{
179    return get<keyMatchesLabelForAttribute>(key, scope);
180}
181
182void DocumentOrderedMap::trace(Visitor* visitor)
183{
184#if ENABLE(OILPAN)
185    visitor->trace(m_map);
186#endif
187}
188
189void 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