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 }