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