• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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