--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/WebCore/dom/ContainerNodeAlgorithms.h	Fri Sep 17 09:02:29 2010 +0300
@@ -0,0 +1,149 @@
+/*
+ * Copyright (C) 2007 Apple Inc. All rights reserved.
+ *           (C) 2008 Nikolas Zimmermann <zimmermann@kde.org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ *
+ */
+
+#ifndef ContainerNodeAlgorithms_h
+#define ContainerNodeAlgorithms_h
+
+#include <wtf/Assertions.h>
+
+namespace WebCore {
+
+class Node;
+
+namespace Private {
+
+    template<class GenericNode, class GenericNodeContainer>
+    void addChildNodesToDeletionQueue(GenericNode*& head, GenericNode*& tail, GenericNodeContainer* container);
+
+};
+
+// Helper functions for TreeShared-derived classes, which have a 'Node' style interface
+// This applies to 'ContainerNode' and 'SVGElementInstance'
+template<class GenericNode, class GenericNodeContainer>
+void removeAllChildrenInContainer(GenericNodeContainer* container)
+{
+    // List of nodes to be deleted.
+    GenericNode* head = 0;
+    GenericNode* tail = 0;
+
+    Private::addChildNodesToDeletionQueue<GenericNode, GenericNodeContainer>(head, tail, container);
+
+    GenericNode* n;
+    GenericNode* next;
+    while ((n = head) != 0) {
+        ASSERT(n->m_deletionHasBegun);
+
+        next = n->nextSibling();
+        n->setNextSibling(0);
+
+        head = next;
+        if (next == 0)
+            tail = 0;
+
+        if (n->hasChildNodes())
+            Private::addChildNodesToDeletionQueue<GenericNode, GenericNodeContainer>(head, tail, static_cast<GenericNodeContainer*>(n));
+
+        delete n;
+    }
+}
+
+template<class GenericNode, class GenericNodeContainer>
+void appendChildToContainer(GenericNode* child, GenericNodeContainer* container)
+{
+    child->setParent(container);
+
+    GenericNode* lastChild = container->lastChild();
+    if (lastChild) {
+        child->setPreviousSibling(lastChild);
+        lastChild->setNextSibling(child);
+    } else
+        container->setFirstChild(child);
+
+    container->setLastChild(child);
+}
+
+// Helper methods for removeAllChildrenInContainer, hidden from WebCore namespace
+namespace Private {
+
+    template<class GenericNode, bool dispatchRemovalNotification>
+    struct NodeRemovalDispatcher {
+        static void dispatch(GenericNode*)
+        {
+            // no-op, by default
+        }
+    };
+
+    template<class GenericNode>
+    struct NodeRemovalDispatcher<GenericNode, true> {
+        static void dispatch(GenericNode* node)
+        {
+            if (node->inDocument())
+                node->removedFromDocument();
+        }
+    };
+
+    template<class GenericNode>
+    struct ShouldDispatchRemovalNotification {
+        static const bool value = false;
+    };
+
+    template<>
+    struct ShouldDispatchRemovalNotification<Node> {
+        static const bool value = true;
+    };
+
+    template<class GenericNode, class GenericNodeContainer>
+    void addChildNodesToDeletionQueue(GenericNode*& head, GenericNode*& tail, GenericNodeContainer* container)
+    {
+        // We have to tell all children that their parent has died.
+        GenericNode* next = 0;
+        for (GenericNode* n = container->firstChild(); n != 0; n = next) {
+            ASSERT(!n->m_deletionHasBegun);
+
+            next = n->nextSibling();
+            n->setPreviousSibling(0);
+            n->setNextSibling(0);
+            n->setParent(0);
+
+            if (!n->refCount()) {
+#ifndef NDEBUG
+                n->m_deletionHasBegun = true;
+#endif
+                // Add the node to the list of nodes to be deleted.
+                // Reuse the nextSibling pointer for this purpose.
+                if (tail)
+                    tail->setNextSibling(n);
+                else
+                    head = n;
+
+                tail = n;
+            } else
+                NodeRemovalDispatcher<GenericNode, ShouldDispatchRemovalNotification<GenericNode>::value>::dispatch(n);
+        }
+
+        container->setFirstChild(0);
+        container->setLastChild(0);
+    }
+};
+
+} // namespace WebCore
+
+#endif // ContainerNodeAlgorithms_h