Refactor HTMLCollection to be as fast as CachedLiveNodeList
[WebKit-https.git] / Source / WebCore / html / HTMLCollection.h
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2011, 2012, 2013, 2014 Apple Inc. All rights reserved.
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Library General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Library General Public License for more details.
15  *
16  * You should have received a copy of the GNU Library General Public License
17  * along with this library; see the file COPYING.LIB.  If not, write to
18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19  * Boston, MA 02110-1301, USA.
20  *
21  */
22
23 #ifndef HTMLCollection_h
24 #define HTMLCollection_h
25
26 #include "CollectionIndexCache.h"
27 #include "HTMLNames.h"
28 #include "LiveNodeList.h"
29 #include "ScriptWrappable.h"
30 #include <wtf/HashMap.h>
31
32 namespace WebCore {
33
34 class Element;
35
36 class CollectionNamedElementCache {
37 public:
38     const Vector<Element*>* findElementsWithId(const AtomicString& id) const;
39     const Vector<Element*>* findElementsWithName(const AtomicString& name) const;
40
41     void appendToIdCache(const AtomicString& id, Element&);
42     void appendToNameCache(const AtomicString& name, Element&);
43     void didPopulate();
44
45     size_t memoryCost() const;
46
47 private:
48     typedef HashMap<AtomicStringImpl*, Vector<Element*>> StringToElementsMap;
49
50     const Vector<Element*>* find(const StringToElementsMap&, const AtomicString& key) const;
51     static void append(StringToElementsMap&, const AtomicString& key, Element&);
52
53     StringToElementsMap m_idMap;
54     StringToElementsMap m_nameMap;
55
56 #if !ASSERT_DISABLED
57     bool m_didPopulate { false };
58 #endif
59 };
60
61 class HTMLCollection : public ScriptWrappable, public RefCounted<HTMLCollection> {
62 public:
63     virtual ~HTMLCollection();
64
65     // DOM API
66     virtual unsigned length() const = 0;
67     virtual Element* item(unsigned offset) const = 0;
68     virtual Element* namedItem(const AtomicString& name) const = 0;
69     PassRefPtr<NodeList> tags(const String&);
70
71     // Non-DOM API
72     bool hasNamedItem(const AtomicString& name) const;
73     Vector<Ref<Element>> namedItems(const AtomicString& name) const;
74     virtual size_t memoryCost() const;
75
76     bool isRootedAtDocument() const;
77     NodeListInvalidationType invalidationType() const;
78     CollectionType type() const;
79     ContainerNode& ownerNode() const;
80     ContainerNode& rootNode() const;
81     void invalidateCache(const QualifiedName* attributeName);
82     virtual void invalidateCache(Document&);
83
84     bool hasNamedElementCache() const;
85
86 protected:
87     HTMLCollection(ContainerNode& base, CollectionType);
88
89     virtual void updateNamedElementCache() const;
90     Element* namedItemSlow(const AtomicString& name) const;
91
92     void setNamedItemCache(std::unique_ptr<CollectionNamedElementCache>) const;
93     const CollectionNamedElementCache& namedItemCaches() const;
94
95     Document& document() const;
96
97     void invalidateNamedElementCache(Document&) const;
98
99     enum RootType { IsRootedAtNode, IsRootedAtDocument };
100     static RootType rootTypeFromCollectionType(CollectionType);
101
102     Ref<ContainerNode> m_ownerNode;
103
104     mutable std::unique_ptr<CollectionNamedElementCache> m_namedElementCache;
105
106     const unsigned m_collectionType : 5;
107     const unsigned m_invalidationType : 4;
108     const unsigned m_rootType : 1;
109 };
110
111 inline ContainerNode& HTMLCollection::rootNode() const
112 {
113     if (isRootedAtDocument() && ownerNode().inDocument())
114         return ownerNode().document();
115
116     return ownerNode();
117 }
118
119 inline const Vector<Element*>* CollectionNamedElementCache::findElementsWithId(const AtomicString& id) const
120 {
121     return find(m_idMap, id);
122 }
123
124 inline const Vector<Element*>* CollectionNamedElementCache::findElementsWithName(const AtomicString& name) const
125 {
126     return find(m_nameMap, name);
127 }
128
129 inline void CollectionNamedElementCache::appendToIdCache(const AtomicString& id, Element& element)
130 {
131     return append(m_idMap, id, element);
132 }
133
134 inline void CollectionNamedElementCache::appendToNameCache(const AtomicString& name, Element& element)
135 {
136     return append(m_nameMap, name, element);
137 }
138
139 inline size_t CollectionNamedElementCache::memoryCost() const
140 {
141     return (m_idMap.size() + m_nameMap.size()) * sizeof(Element*);
142 }
143
144 inline void CollectionNamedElementCache::didPopulate()
145 {
146 #if !ASSERT_DISABLED
147     m_didPopulate = true;
148 #endif
149     if (size_t cost = memoryCost())
150         reportExtraMemoryAllocatedForCollectionIndexCache(cost);
151 }
152
153 inline const Vector<Element*>* CollectionNamedElementCache::find(const StringToElementsMap& map, const AtomicString& key) const
154 {
155     ASSERT(m_didPopulate);
156     auto it = map.find(key.impl());
157     return it != map.end() ? &it->value : nullptr;
158 }
159
160 inline void CollectionNamedElementCache::append(StringToElementsMap& map, const AtomicString& key, Element& element)
161 {
162     map.add(key.impl(), Vector<Element*>()).iterator->value.append(&element);
163 }
164
165 inline size_t HTMLCollection::memoryCost() const
166 {
167     return m_namedElementCache ? m_namedElementCache->memoryCost() : 0;
168 }
169
170 inline bool HTMLCollection::isRootedAtDocument() const
171 {
172     return m_rootType == IsRootedAtDocument;
173 }
174
175 inline NodeListInvalidationType HTMLCollection::invalidationType() const
176 {
177     return static_cast<NodeListInvalidationType>(m_invalidationType);
178 }
179
180 inline CollectionType HTMLCollection::type() const
181 {
182     return static_cast<CollectionType>(m_collectionType);
183 }
184
185 inline ContainerNode& HTMLCollection::ownerNode() const
186 {
187     return const_cast<ContainerNode&>(m_ownerNode.get());
188 }
189
190 inline Document& HTMLCollection::document() const
191 {
192     return m_ownerNode->document();
193 }
194
195 inline void HTMLCollection::invalidateCache(const QualifiedName* attributeName)
196 {
197     if (!attributeName || shouldInvalidateTypeOnAttributeChange(invalidationType(), *attributeName))
198         invalidateCache(document());
199     else if (hasNamedElementCache() && (*attributeName == HTMLNames::idAttr || *attributeName == HTMLNames::nameAttr))
200         invalidateNamedElementCache(document());
201 }
202
203 inline bool HTMLCollection::hasNamedElementCache() const
204 {
205     return !!m_namedElementCache;
206 }
207
208 inline void HTMLCollection::setNamedItemCache(std::unique_ptr<CollectionNamedElementCache> cache) const
209 {
210     ASSERT(cache);
211     ASSERT(!m_namedElementCache);
212     cache->didPopulate();
213     m_namedElementCache = WTF::move(cache);
214     document().collectionCachedIdNameMap(*this);
215 }
216
217 inline const CollectionNamedElementCache& HTMLCollection::namedItemCaches() const
218 {
219     ASSERT(!!m_namedElementCache);
220     return *m_namedElementCache;
221 }
222
223 } // namespace WebCore
224
225 #define SPECIALIZE_TYPE_TRAITS_HTMLCOLLECTION(ClassName, Type) \
226 SPECIALIZE_TYPE_TRAITS_BEGIN(WebCore::ClassName) \
227     static bool isType(const WebCore::HTMLCollection& collection) { return collection.type() == WebCore::Type; } \
228 SPECIALIZE_TYPE_TRAITS_END()
229
230 #endif // HTMLCollection_h