--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/webengine/osswebengine/WebCore/platform/DeprecatedPtrListImpl.cpp	Mon Mar 30 12:54:55 2009 +0300
@@ -0,0 +1,514 @@
+/*
+ * Copyright (C) 2003, 2006 Apple Computer, Inc.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "DeprecatedPtrListImpl.h"
+
+#include <cstddef>
+#include <algorithm>
+#include <wtf/Assertions.h>
+
+namespace WebCore {
+
+class DeprecatedListNode
+{
+public:
+    DeprecatedListNode(void *d) : data(d), next(0), prev(0) { }
+
+    void *data;
+    DeprecatedListNode *next;
+    DeprecatedListNode *prev;
+};
+
+
+static DeprecatedListNode *copyList(DeprecatedListNode *l, DeprecatedListNode *&tail)
+{
+    DeprecatedListNode *node = l;
+    DeprecatedListNode *copyHead = 0;
+    DeprecatedListNode *last = 0;
+
+    while (node != 0) {
+        DeprecatedListNode *copy = new DeprecatedListNode(node->data);
+        if (last != 0) {
+            last->next = copy;
+        } else {
+            copyHead = copy;
+        }
+
+        copy->prev = last;
+        
+        last = copy;
+        node = node->next;
+    }
+
+    tail = last;
+    return copyHead;
+}
+
+
+DeprecatedPtrListImpl::DeprecatedPtrListImpl(void (*deleteFunc)(void *)) :
+    head(0),
+    tail(0),
+    cur(0),
+    nodeCount(0),
+    deleteItem(deleteFunc),
+    iterators(0)
+{
+}
+
+DeprecatedPtrListImpl::DeprecatedPtrListImpl(const DeprecatedPtrListImpl &impl) :
+    cur(0),
+    nodeCount(impl.nodeCount),
+    deleteItem(impl.deleteItem),
+    iterators(0)
+{
+    head = copyList(impl.head, tail);
+}
+
+DeprecatedPtrListImpl::~DeprecatedPtrListImpl()
+{
+    clear(false);
+    
+    DeprecatedPtrListImplIterator *next;
+    for (DeprecatedPtrListImplIterator *it = iterators; it; it = next) {
+        next = it->next;
+        it->list = 0;
+        ASSERT(!it->node);
+        it->next = 0;
+        it->prev = 0;
+    }
+}
+     
+void DeprecatedPtrListImpl::clear(bool deleteItems)
+{
+    DeprecatedListNode *next;
+    
+    for (DeprecatedListNode *node = head; node; node = next) {
+        next = node->next;
+        if (deleteItems)
+            deleteItem(node->data);
+        delete node;
+    }
+
+    head = 0;
+    tail = 0;
+    cur = 0;
+    nodeCount = 0;
+
+    for (DeprecatedPtrListImplIterator *it = iterators; it; it = it->next)
+        it->node = 0;
+}
+
+void *DeprecatedPtrListImpl::at(unsigned n)
+{
+    DeprecatedListNode *node;
+    if (n >= nodeCount - 1) {
+        node = tail;
+    } else {
+        node = head;
+        for (unsigned i = 0; i < n && node; i++) {
+            node = node->next;
+        }
+    }
+
+    cur = node;
+    return node ? node->data : 0;
+}
+
+bool DeprecatedPtrListImpl::insert(unsigned n, const void *item)
+{
+    if (n > nodeCount) {
+        return false;
+    }
+
+    DeprecatedListNode *node = new DeprecatedListNode((void *)item);
+
+    if (n == 0) {
+        // inserting at head
+        node->next = head;
+        if (head) {
+            head->prev = node;
+        }
+        head = node;
+        if (tail == 0) {
+            tail = node;
+        }
+    } else if (n == nodeCount) {
+        // inserting at tail
+        node->prev = tail;
+        if (tail) {
+            tail->next = node;
+        }
+        tail = node;
+    } else {
+        // general insertion
+        
+        // iterate to one node before the insertion point, can't be null
+        // since we know n > 0 and n < nodeCount
+        DeprecatedListNode *prevNode = head;
+
+        for (unsigned i = 0; i < n - 1; i++) {
+            prevNode = prevNode->next;
+        }
+        node->prev = prevNode;
+        node->next = prevNode->next;
+        if (node->next) {
+            node->next->prev = node;
+        }
+        prevNode->next = node;
+    }
+
+    nodeCount++;
+    cur = node;
+    return true;
+}
+
+bool DeprecatedPtrListImpl::remove(bool shouldDeleteItem)
+{
+    DeprecatedListNode *node = cur;
+    if (node == 0) {
+        return false;
+    }
+
+    if (node->prev == 0) {
+        head = node->next;
+    } else {
+        node->prev->next = node->next;
+    }
+
+    if (node->next == 0) {
+        tail = node->prev;
+    } else {
+        node->next->prev = node->prev;
+    }
+
+    if (node->next) {
+        cur = node->next;
+    } else {
+        cur = node->prev;
+    }
+
+    for (DeprecatedPtrListImplIterator *it = iterators; it; it = it->next) {
+        if (it->node == node) {
+            it->node = cur;
+        }
+    }
+
+    if (shouldDeleteItem) {
+        deleteItem(node->data);
+    }
+    delete node;
+
+    nodeCount--;
+
+    return true;
+}
+
+bool DeprecatedPtrListImpl::remove(unsigned n, bool deleteItem)
+{
+    if (n >= nodeCount) {
+        return false;
+    }
+
+    at(n);
+    return remove(deleteItem);
+}
+
+bool DeprecatedPtrListImpl::removeFirst(bool deleteItem)
+{
+    return remove(0, deleteItem);
+}
+
+bool DeprecatedPtrListImpl::removeLast(bool deleteItem)
+{
+    return remove(nodeCount - 1, deleteItem);
+}
+
+bool DeprecatedPtrListImpl::removeRef(const void *item, bool deleteItem)
+{
+    DeprecatedListNode *node;
+
+    node = head;
+
+    while (node && item != node->data) {
+        node = node->next;
+    }
+    
+    if (node == 0) {
+        return false;
+    }
+
+    cur = node;
+
+    return remove(deleteItem);
+}
+
+void *DeprecatedPtrListImpl::getFirst() const
+{
+    return head ? head->data : 0;
+}
+
+void *DeprecatedPtrListImpl::getLast() const
+{
+    return tail ? tail->data : 0;
+}
+
+void *DeprecatedPtrListImpl::getNext() const
+{
+    return cur && cur->next ? cur->next->data : 0;
+}
+
+void *DeprecatedPtrListImpl::getPrev() const
+{
+    return cur && cur->prev ? cur->prev->data : 0;
+}
+
+void *DeprecatedPtrListImpl::current() const
+{
+    if (cur) {
+        return cur->data;
+    } else {
+        return 0;
+    }
+}
+
+void *DeprecatedPtrListImpl::first()
+{
+    cur = head;
+    return current();
+}
+
+void *DeprecatedPtrListImpl::last()
+{
+    cur = tail;
+    return current();
+}
+
+void *DeprecatedPtrListImpl::next()
+{
+    if (cur) {
+        cur = cur->next;
+    }
+    return current();
+}
+
+void *DeprecatedPtrListImpl::prev()
+{
+    if (cur) {
+        cur = cur->prev;
+    }
+    return current();
+}
+
+void *DeprecatedPtrListImpl::take(unsigned n)
+{
+    void *retval = at(n);
+    remove(false);
+    return retval;
+}
+
+void *DeprecatedPtrListImpl::take()
+{
+    void *retval = current();
+    remove(false);
+    return retval;
+}
+
+void DeprecatedPtrListImpl::append(const void *item)
+{
+    insert(nodeCount, item);
+}
+
+void DeprecatedPtrListImpl::prepend(const void *item)
+{
+    insert(0, item);
+}
+
+unsigned DeprecatedPtrListImpl::containsRef(const void *item) const
+{
+    unsigned count = 0;
+    
+    for (DeprecatedListNode *node = head; node; node = node->next) {
+        if (item == node->data) {
+            ++count;
+        }
+    }
+    
+    return count;
+}
+
+int DeprecatedPtrListImpl::findRef(const void *item)
+{
+    DeprecatedListNode *node = head;
+    int index = 0;
+    
+    while (node && item != node->data) {
+        node = node->next;
+        index++;
+    }
+    
+    cur = node;
+    
+    if (node == 0) {
+        return -1;
+    }
+    
+    return index;
+}
+
+DeprecatedPtrListImpl &DeprecatedPtrListImpl::assign(const DeprecatedPtrListImpl &impl, bool deleteItems)
+{
+    clear(deleteItems);
+    DeprecatedPtrListImpl(impl).swap(*this);
+    return *this;
+}
+
+void DeprecatedPtrListImpl::addIterator(DeprecatedPtrListImplIterator *iter) const
+{
+    iter->next = iterators;
+    iter->prev = 0;
+    
+    if (iterators) {
+        iterators->prev = iter;
+    }
+    iterators = iter;
+}
+
+void DeprecatedPtrListImpl::removeIterator(DeprecatedPtrListImplIterator *iter) const
+{
+    if (iter->prev == 0) {
+        iterators = iter->next;
+    } else {
+        iter->prev->next = iter->next;
+    }
+
+    if (iter->next) {
+        iter->next->prev = iter->prev;
+    }
+}
+
+void DeprecatedPtrListImpl::swap(DeprecatedPtrListImpl &other)
+{
+    using std::swap;
+    
+    ASSERT(iterators == 0);
+    ASSERT(other.iterators == 0);
+    
+    swap(head, other.head);
+    swap(tail, other.tail);
+    swap(cur, other.cur);
+    swap(nodeCount, other.nodeCount);
+    swap(deleteItem, other.deleteItem);
+}
+
+
+DeprecatedPtrListImplIterator::DeprecatedPtrListImplIterator() :
+    list(0),
+    node(0)
+{
+}
+
+DeprecatedPtrListImplIterator::DeprecatedPtrListImplIterator(const DeprecatedPtrListImpl &impl)  :
+    list(&impl),
+    node(impl.head)
+{
+    impl.addIterator(this);
+}
+
+DeprecatedPtrListImplIterator::~DeprecatedPtrListImplIterator()
+{
+    if (list) {
+        list->removeIterator(this);
+    }
+}
+
+DeprecatedPtrListImplIterator::DeprecatedPtrListImplIterator(const DeprecatedPtrListImplIterator &impl) :
+    list(impl.list),
+    node(impl.node)
+{
+    if (list) {
+        list->addIterator(this);
+    }
+}
+
+unsigned DeprecatedPtrListImplIterator::count() const
+{
+    return list == 0 ? 0 : list->count();
+}
+
+void *DeprecatedPtrListImplIterator::toFirst()
+{
+    if (list) {
+        node = list->head;
+    }
+    return current();
+}
+
+void *DeprecatedPtrListImplIterator::toLast()
+{
+    if (list) {
+        node = list->tail;
+    }
+    return current();
+}
+
+void *DeprecatedPtrListImplIterator::current() const
+{
+    return node == 0 ? 0 : node->data;
+}
+
+void *DeprecatedPtrListImplIterator::operator--()
+{
+    if (node) {
+        node = node->prev;
+    }
+    return current();
+}
+
+void *DeprecatedPtrListImplIterator::operator++()
+{
+    if (node) {
+        node = node->next;
+    }
+    return current();
+}
+
+DeprecatedPtrListImplIterator &DeprecatedPtrListImplIterator::operator=(const DeprecatedPtrListImplIterator &impl)
+{
+    if (list) {
+        list->removeIterator(this);
+    }
+    
+    list = impl.list;
+    node = impl.node;
+    
+    if (list) {
+        list->addIterator(this);
+    }
+
+    return *this;
+}
+
+}