diff options
Diffstat (limited to 'src/3rdparty/webkit/WebCore/platform/DeprecatedPtrListImpl.cpp')
-rw-r--r-- | src/3rdparty/webkit/WebCore/platform/DeprecatedPtrListImpl.cpp | 514 |
1 files changed, 514 insertions, 0 deletions
diff --git a/src/3rdparty/webkit/WebCore/platform/DeprecatedPtrListImpl.cpp b/src/3rdparty/webkit/WebCore/platform/DeprecatedPtrListImpl.cpp new file mode 100644 index 0000000..b3badc2 --- /dev/null +++ b/src/3rdparty/webkit/WebCore/platform/DeprecatedPtrListImpl.cpp @@ -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; +} + +} |