WebCore:
[WebKit-https.git] / WebCore / dom / DynamicNodeList.cpp
1 /**
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  *           (C) 2001 Dirk Mueller (mueller@kde.org)
5  * Copyright (C) 2004, 2006, 2007 Apple Inc. All rights reserved.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB.  If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  * Boston, MA 02110-1301, USA.
21  */
22
23 #include "config.h"
24 #include "DynamicNodeList.h"
25
26 #include "Document.h"
27 #include "Element.h"
28
29 namespace WebCore {
30
31 DynamicNodeList::DynamicNodeList(PassRefPtr<Node> rootNode, bool needsNotifications)
32     : m_rootNode(rootNode)
33     , m_caches(new Caches)
34     , m_ownsCaches(true)
35     , m_needsNotifications(needsNotifications)
36 {
37     m_rootNode->registerDynamicNodeList(this);
38 }    
39
40 DynamicNodeList::DynamicNodeList(PassRefPtr<Node> rootNode, DynamicNodeList::Caches* info, bool needsNotifications)
41     : m_rootNode(rootNode)
42     , m_caches(info)
43     , m_ownsCaches(false)
44     , m_needsNotifications(needsNotifications)
45 {
46     m_rootNode->registerDynamicNodeList(this);
47 }    
48
49 DynamicNodeList::~DynamicNodeList()
50 {
51     m_rootNode->unregisterDynamicNodeList(this);
52     if (m_ownsCaches)
53         delete m_caches;
54 }
55
56 unsigned DynamicNodeList::recursiveLength(Node* start) const
57 {
58     if (!start)
59         start = m_rootNode.get();
60
61     if (m_caches->isLengthCacheValid && start == m_rootNode)
62         return m_caches->cachedLength;
63
64     unsigned len = 0;
65
66     for (Node* n = start->firstChild(); n; n = n->nextSibling())
67         if (n->isElementNode()) {
68             if (nodeMatches(n))
69                 len++;
70             len += recursiveLength(n);
71         }
72
73     if (start == m_rootNode) {
74         m_caches->cachedLength = len;
75         m_caches->isLengthCacheValid = true;
76     }
77
78     return len;
79 }
80
81 Node* DynamicNodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const
82 {
83     ASSERT(remainingOffset >= 0);
84
85     for (Node *n = start; n; n = n->traverseNextNode(m_rootNode.get())) {
86         if (n->isElementNode()) {
87             if (nodeMatches(n)) {
88                 if (!remainingOffset) {
89                     m_caches->lastItem = n;
90                     m_caches->lastItemOffset = offset;
91                     m_caches->isItemCacheValid = true;
92                     return n;
93                 }
94                 remainingOffset--;
95             }
96         }
97     }
98
99     return 0; // no matching node in this subtree
100 }
101
102 Node* DynamicNodeList::itemBackwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const
103 {
104     ASSERT(remainingOffset < 0);
105     for (Node *n = start; n; n = n->traversePreviousNode(m_rootNode.get())) {
106         if (n->isElementNode()) {
107             if (nodeMatches(n)) {
108                 if (!remainingOffset) {
109                     m_caches->lastItem = n;
110                     m_caches->lastItemOffset = offset;
111                     m_caches->isItemCacheValid = true;
112                     return n;
113                 }
114                 remainingOffset++;
115             }
116         }
117     }
118
119     return 0; // no matching node in this subtree
120 }
121
122 Node* DynamicNodeList::recursiveItem(unsigned offset, Node* start) const
123 {
124     int remainingOffset = offset;
125     if (!start) {
126         start = m_rootNode->firstChild();
127         if (m_caches->isItemCacheValid) {
128             if (offset == m_caches->lastItemOffset) {
129                 return m_caches->lastItem;
130             } else if (offset > m_caches->lastItemOffset || m_caches->lastItemOffset - offset < offset) {
131                 start = m_caches->lastItem;
132                 remainingOffset -= m_caches->lastItemOffset;
133             }
134         }
135     }
136
137     if (remainingOffset < 0)
138         return itemBackwardsFromCurrent(start, offset, remainingOffset);
139     else
140         return itemForwardsFromCurrent(start, offset, remainingOffset);
141 }
142
143 Node* DynamicNodeList::itemWithName(const AtomicString& elementId) const
144 {
145     if (m_rootNode->isDocumentNode() || m_rootNode->inDocument()) {
146         Node* node = m_rootNode->document()->getElementById(elementId);
147
148         if (!node || !nodeMatches(node))
149             return 0;
150
151         for (Node* p = node->parentNode(); p; p = p->parentNode())
152             if (p == m_rootNode)
153                 return node;
154
155         return 0;
156     }
157
158     unsigned l = length();
159     for (unsigned i = 0; i < l; i++) {
160         Node* node = item(i);
161         if (node->isElementNode() && static_cast<Element*>(node)->getIDAttribute() == elementId)
162             return node;
163     }
164
165     return 0;
166 }
167
168 void DynamicNodeList::rootNodeChildrenChanged()
169 {
170     m_caches->reset();
171 }
172
173
174 DynamicNodeList::Caches::Caches()
175     : lastItem(0)
176     , isLengthCacheValid(false)
177     , isItemCacheValid(false)
178 {
179 }
180
181 void DynamicNodeList::Caches::reset()
182 {
183     lastItem = 0;
184     isLengthCacheValid = false;
185     isItemCacheValid = false;     
186 }
187
188 }