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, 2008 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
DynamicNodeList(PassRefPtr<Node> rootNode)31 DynamicNodeList::DynamicNodeList(PassRefPtr<Node> rootNode)
32 : m_rootNode(rootNode)
33 , m_caches(Caches::create())
34 , m_ownsCaches(true)
35 {
36 m_rootNode->registerDynamicNodeList(this);
37 }
38
DynamicNodeList(PassRefPtr<Node> rootNode,DynamicNodeList::Caches * caches)39 DynamicNodeList::DynamicNodeList(PassRefPtr<Node> rootNode, DynamicNodeList::Caches* caches)
40 : m_rootNode(rootNode)
41 , m_caches(caches)
42 , m_ownsCaches(false)
43 {
44 m_rootNode->registerDynamicNodeList(this);
45 }
46
~DynamicNodeList()47 DynamicNodeList::~DynamicNodeList()
48 {
49 m_rootNode->unregisterDynamicNodeList(this);
50 }
51
length() const52 unsigned DynamicNodeList::length() const
53 {
54 if (m_caches->isLengthCacheValid)
55 return m_caches->cachedLength;
56
57 unsigned length = 0;
58
59 for (Node* n = m_rootNode->firstChild(); n; n = n->traverseNextNode(m_rootNode.get()))
60 length += n->isElementNode() && nodeMatches(static_cast<Element*>(n));
61
62 m_caches->cachedLength = length;
63 m_caches->isLengthCacheValid = true;
64
65 return length;
66 }
67
itemForwardsFromCurrent(Node * start,unsigned offset,int remainingOffset) const68 Node* DynamicNodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const
69 {
70 ASSERT(remainingOffset >= 0);
71 for (Node* n = start; n; n = n->traverseNextNode(m_rootNode.get())) {
72 if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
73 if (!remainingOffset) {
74 m_caches->lastItem = n;
75 m_caches->lastItemOffset = offset;
76 m_caches->isItemCacheValid = true;
77 return n;
78 }
79 --remainingOffset;
80 }
81 }
82
83 return 0; // no matching node in this subtree
84 }
85
itemBackwardsFromCurrent(Node * start,unsigned offset,int remainingOffset) const86 Node* DynamicNodeList::itemBackwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const
87 {
88 ASSERT(remainingOffset < 0);
89 for (Node* n = start; n; n = n->traversePreviousNode(m_rootNode.get())) {
90 if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
91 if (!remainingOffset) {
92 m_caches->lastItem = n;
93 m_caches->lastItemOffset = offset;
94 m_caches->isItemCacheValid = true;
95 return n;
96 }
97 ++remainingOffset;
98 }
99 }
100
101 return 0; // no matching node in this subtree
102 }
103
item(unsigned offset) const104 Node* DynamicNodeList::item(unsigned offset) const
105 {
106 int remainingOffset = offset;
107 Node* start = m_rootNode->firstChild();
108 if (m_caches->isItemCacheValid) {
109 if (offset == m_caches->lastItemOffset)
110 return m_caches->lastItem;
111 else if (offset > m_caches->lastItemOffset || m_caches->lastItemOffset - offset < offset) {
112 start = m_caches->lastItem;
113 remainingOffset -= m_caches->lastItemOffset;
114 }
115 }
116
117 if (remainingOffset < 0)
118 return itemBackwardsFromCurrent(start, offset, remainingOffset);
119 return itemForwardsFromCurrent(start, offset, remainingOffset);
120 }
121
itemWithName(const AtomicString & elementId) const122 Node* DynamicNodeList::itemWithName(const AtomicString& elementId) const
123 {
124 if (m_rootNode->isDocumentNode() || m_rootNode->inDocument()) {
125 Element* node = m_rootNode->document()->getElementById(elementId);
126 if (node && nodeMatches(node)) {
127 for (Node* p = node->parentNode(); p; p = p->parentNode()) {
128 if (p == m_rootNode)
129 return node;
130 }
131 }
132 if (!node)
133 return 0;
134 // In the case of multiple nodes with the same name, just fall through.
135 }
136
137 unsigned length = this->length();
138 for (unsigned i = 0; i < length; i++) {
139 Node* node = item(i);
140 if (node->isElementNode() && static_cast<Element*>(node)->getIDAttribute() == elementId)
141 return node;
142 }
143
144 return 0;
145 }
146
invalidateCache()147 void DynamicNodeList::invalidateCache()
148 {
149 // This should only be called for node lists that own their own caches.
150 ASSERT(m_ownsCaches);
151 m_caches->reset();
152 }
153
Caches()154 DynamicNodeList::Caches::Caches()
155 : lastItem(0)
156 , isLengthCacheValid(false)
157 , isItemCacheValid(false)
158 {
159 }
160
create()161 PassRefPtr<DynamicNodeList::Caches> DynamicNodeList::Caches::create()
162 {
163 return adoptRef(new Caches());
164 }
165
reset()166 void DynamicNodeList::Caches::reset()
167 {
168 lastItem = 0;
169 isLengthCacheValid = false;
170 isItemCacheValid = false;
171 }
172
173 } // namespace WebCore
174