1/*
2 * Copyright (C) 2008, 2010 Apple Inc. All rights reserved.
3 * Copyright (C) 2008 David Smith <catfish.man@gmail.com>
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB.  If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 *
20 */
21
22#ifndef NodeRareData_h
23#define NodeRareData_h
24
25#include "core/dom/ChildNodeList.h"
26#include "core/dom/LiveNodeList.h"
27#include "core/dom/MutationObserverRegistration.h"
28#include "core/dom/QualifiedName.h"
29#include "core/dom/TagNodeList.h"
30#include "core/page/Page.h"
31#include "wtf/HashSet.h"
32#include "wtf/OwnPtr.h"
33#include "wtf/PassOwnPtr.h"
34#include "wtf/text/AtomicString.h"
35#include "wtf/text/StringHash.h"
36
37namespace WebCore {
38
39class LabelsNodeList;
40class RadioNodeList;
41class TreeScope;
42
43class NodeListsNodeData {
44    WTF_MAKE_NONCOPYABLE(NodeListsNodeData); WTF_MAKE_FAST_ALLOCATED;
45public:
46    void clearChildNodeListCache()
47    {
48        if (m_childNodeList)
49            m_childNodeList->invalidateCache();
50    }
51
52    PassRefPtr<ChildNodeList> ensureChildNodeList(Node* node)
53    {
54        if (m_childNodeList)
55            return m_childNodeList;
56        RefPtr<ChildNodeList> list = ChildNodeList::create(node);
57        m_childNodeList = list.get();
58        return list.release();
59    }
60
61    void removeChildNodeList(ChildNodeList* list)
62    {
63        ASSERT(m_childNodeList = list);
64        if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode()))
65            return;
66        m_childNodeList = 0;
67    }
68
69    template <typename StringType>
70    struct NodeListCacheMapEntryHash {
71        static unsigned hash(const std::pair<unsigned char, StringType>& entry)
72        {
73            return DefaultHash<StringType>::Hash::hash(entry.second) + entry.first;
74        }
75        static bool equal(const std::pair<unsigned char, StringType>& a, const std::pair<unsigned char, StringType>& b) { return a == b; }
76        static const bool safeToCompareToEmptyOrDeleted = DefaultHash<StringType>::Hash::safeToCompareToEmptyOrDeleted;
77    };
78
79    typedef HashMap<std::pair<unsigned char, AtomicString>, LiveNodeListBase*, NodeListCacheMapEntryHash<AtomicString> > NodeListAtomicNameCacheMap;
80    typedef HashMap<std::pair<unsigned char, String>, LiveNodeListBase*, NodeListCacheMapEntryHash<String> > NodeListNameCacheMap;
81    typedef HashMap<QualifiedName, TagNodeList*> TagNodeListCacheNS;
82
83    template<typename T>
84    PassRefPtr<T> addCacheWithAtomicName(Node* node, CollectionType collectionType, const AtomicString& name)
85    {
86        NodeListAtomicNameCacheMap::AddResult result = m_atomicNameCaches.add(namedNodeListKey(collectionType, name), 0);
87        if (!result.isNewEntry)
88            return static_cast<T*>(result.iterator->value);
89
90        RefPtr<T> list = T::create(node, collectionType, name);
91        result.iterator->value = list.get();
92        return list.release();
93    }
94
95    // FIXME: This function should be renamed since it doesn't have an atomic name.
96    template<typename T>
97    PassRefPtr<T> addCacheWithAtomicName(Node* node, CollectionType collectionType)
98    {
99        NodeListAtomicNameCacheMap::AddResult result = m_atomicNameCaches.add(namedNodeListKey(collectionType, starAtom), 0);
100        if (!result.isNewEntry)
101            return static_cast<T*>(result.iterator->value);
102
103        RefPtr<T> list = T::create(node, collectionType);
104        result.iterator->value = list.get();
105        return list.release();
106    }
107
108    template<typename T>
109    T* cacheWithAtomicName(CollectionType collectionType)
110    {
111        return static_cast<T*>(m_atomicNameCaches.get(namedNodeListKey(collectionType, starAtom)));
112    }
113
114    template<typename T>
115    PassRefPtr<T> addCacheWithName(Node* node, CollectionType collectionType, const String& name)
116    {
117        NodeListNameCacheMap::AddResult result = m_nameCaches.add(namedNodeListKey(collectionType, name), 0);
118        if (!result.isNewEntry)
119            return static_cast<T*>(result.iterator->value);
120
121        RefPtr<T> list = T::create(node, name);
122        result.iterator->value = list.get();
123        return list.release();
124    }
125
126    PassRefPtr<TagNodeList> addCacheWithQualifiedName(Node* node, const AtomicString& namespaceURI, const AtomicString& localName)
127    {
128        QualifiedName name(nullAtom, localName, namespaceURI);
129        TagNodeListCacheNS::AddResult result = m_tagNodeListCacheNS.add(name, 0);
130        if (!result.isNewEntry)
131            return result.iterator->value;
132
133        RefPtr<TagNodeList> list = TagNodeList::create(node, namespaceURI, localName);
134        result.iterator->value = list.get();
135        return list.release();
136    }
137
138    void removeCacheWithAtomicName(LiveNodeListBase* list, CollectionType collectionType, const AtomicString& name = starAtom)
139    {
140        ASSERT(list == m_atomicNameCaches.get(namedNodeListKey(collectionType, name)));
141        if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode()))
142            return;
143        m_atomicNameCaches.remove(namedNodeListKey(collectionType, name));
144    }
145
146    void removeCacheWithName(LiveNodeListBase* list, CollectionType collectionType, const String& name)
147    {
148        ASSERT(list == m_nameCaches.get(namedNodeListKey(collectionType, name)));
149        if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode()))
150            return;
151        m_nameCaches.remove(namedNodeListKey(collectionType, name));
152    }
153
154    void removeCacheWithQualifiedName(LiveNodeList* list, const AtomicString& namespaceURI, const AtomicString& localName)
155    {
156        QualifiedName name(nullAtom, localName, namespaceURI);
157        ASSERT(list == m_tagNodeListCacheNS.get(name));
158        if (deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(list->ownerNode()))
159            return;
160        m_tagNodeListCacheNS.remove(name);
161    }
162
163    static PassOwnPtr<NodeListsNodeData> create()
164    {
165        return adoptPtr(new NodeListsNodeData);
166    }
167
168    void invalidateCaches(const QualifiedName* attrName = 0);
169    bool isEmpty() const
170    {
171        return m_atomicNameCaches.isEmpty() && m_nameCaches.isEmpty() && m_tagNodeListCacheNS.isEmpty();
172    }
173
174    void adoptTreeScope()
175    {
176        invalidateCaches();
177    }
178
179    void adoptDocument(Document* oldDocument, Document* newDocument)
180    {
181        invalidateCaches();
182
183        if (oldDocument != newDocument) {
184            NodeListAtomicNameCacheMap::const_iterator atomicNameCacheEnd = m_atomicNameCaches.end();
185            for (NodeListAtomicNameCacheMap::const_iterator it = m_atomicNameCaches.begin(); it != atomicNameCacheEnd; ++it) {
186                LiveNodeListBase* list = it->value;
187                oldDocument->unregisterNodeList(list);
188                newDocument->registerNodeList(list);
189            }
190
191            NodeListNameCacheMap::const_iterator nameCacheEnd = m_nameCaches.end();
192            for (NodeListNameCacheMap::const_iterator it = m_nameCaches.begin(); it != nameCacheEnd; ++it) {
193                LiveNodeListBase* list = it->value;
194                oldDocument->unregisterNodeList(list);
195                newDocument->registerNodeList(list);
196            }
197
198            TagNodeListCacheNS::const_iterator tagEnd = m_tagNodeListCacheNS.end();
199            for (TagNodeListCacheNS::const_iterator it = m_tagNodeListCacheNS.begin(); it != tagEnd; ++it) {
200                LiveNodeListBase* list = it->value;
201                ASSERT(!list->isRootedAtDocument());
202                oldDocument->unregisterNodeList(list);
203                newDocument->registerNodeList(list);
204            }
205        }
206    }
207
208private:
209    NodeListsNodeData()
210        : m_childNodeList(0)
211    { }
212
213    std::pair<unsigned char, AtomicString> namedNodeListKey(CollectionType type, const AtomicString& name)
214    {
215        return std::pair<unsigned char, AtomicString>(type, name);
216    }
217
218    std::pair<unsigned char, String> namedNodeListKey(CollectionType type, const String& name)
219    {
220        return std::pair<unsigned char, String>(type, name);
221    }
222
223    bool deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(Node*);
224
225    // FIXME: m_childNodeList should be merged into m_atomicNameCaches or at least be shared with HTMLCollection returned by Element::children
226    // but it's tricky because invalidateCaches shouldn't invalidate this cache and adoptTreeScope shouldn't call registerNodeList or unregisterNodeList.
227    ChildNodeList* m_childNodeList;
228    NodeListAtomicNameCacheMap m_atomicNameCaches;
229    NodeListNameCacheMap m_nameCaches;
230    TagNodeListCacheNS m_tagNodeListCacheNS;
231};
232
233class NodeMutationObserverData {
234    WTF_MAKE_NONCOPYABLE(NodeMutationObserverData); WTF_MAKE_FAST_ALLOCATED;
235public:
236    Vector<OwnPtr<MutationObserverRegistration> > registry;
237    HashSet<MutationObserverRegistration*> transientRegistry;
238
239    static PassOwnPtr<NodeMutationObserverData> create() { return adoptPtr(new NodeMutationObserverData); }
240
241private:
242    NodeMutationObserverData() { }
243};
244
245class NodeRareData : public NodeRareDataBase {
246    WTF_MAKE_NONCOPYABLE(NodeRareData); WTF_MAKE_FAST_ALLOCATED;
247public:
248    static PassOwnPtr<NodeRareData> create(RenderObject* renderer) { return adoptPtr(new NodeRareData(renderer)); }
249
250    void clearNodeLists() { m_nodeLists.clear(); }
251    NodeListsNodeData* nodeLists() const { return m_nodeLists.get(); }
252    NodeListsNodeData* ensureNodeLists()
253    {
254        if (!m_nodeLists)
255            m_nodeLists = NodeListsNodeData::create();
256        return m_nodeLists.get();
257    }
258
259    NodeMutationObserverData* mutationObserverData() { return m_mutationObserverData.get(); }
260    NodeMutationObserverData* ensureMutationObserverData()
261    {
262        if (!m_mutationObserverData)
263            m_mutationObserverData = NodeMutationObserverData::create();
264        return m_mutationObserverData.get();
265    }
266
267    unsigned connectedSubframeCount() const { return m_connectedFrameCount; }
268    void incrementConnectedSubframeCount(unsigned amount)
269    {
270        m_connectedFrameCount += amount;
271    }
272    void decrementConnectedSubframeCount(unsigned amount)
273    {
274        ASSERT(m_connectedFrameCount);
275        ASSERT(amount <= m_connectedFrameCount);
276        m_connectedFrameCount -= amount;
277    }
278
279protected:
280    NodeRareData(RenderObject* renderer)
281        : NodeRareDataBase(renderer)
282        , m_connectedFrameCount(0)
283    { }
284
285private:
286    unsigned m_connectedFrameCount : 10; // Must fit Page::maxNumberOfFrames.
287
288    OwnPtr<NodeListsNodeData> m_nodeLists;
289    OwnPtr<NodeMutationObserverData> m_mutationObserverData;
290};
291
292inline bool NodeListsNodeData::deleteThisAndUpdateNodeRareDataIfAboutToRemoveLastList(Node* ownerNode)
293{
294    ASSERT(ownerNode);
295    ASSERT(ownerNode->nodeLists() == this);
296    if ((m_childNodeList ? 1 : 0) + m_atomicNameCaches.size() + m_nameCaches.size() + m_tagNodeListCacheNS.size() != 1)
297        return false;
298    ownerNode->clearNodeLists();
299    return true;
300}
301
302// Ensure the 10 bits reserved for the m_connectedFrameCount cannot overflow
303COMPILE_ASSERT(Page::maxNumberOfFrames < 1024, Frame_limit_should_fit_in_rare_data_count);
304
305} // namespace WebCore
306
307#endif // NodeRareData_h
308