kwqlistimpl.cpp

手机浏览器源码程序,功能强大

/*
 * Copyright (C) 2003 Apple Computer, Inc.  All rights reserved.
 * Portions Copyright (c) 2005 Nokia Corporation, 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 "KWQListImpl.h"

#include <e32std.h>
#include <algorithm>
#include "KWQAssertions.h"

// Adapter classes in order to use Symbian's sorting algorithm
typedef void* VoidPtr;
typedef int (*KWQCompareFunction)(void *a, void *b, void *data);

class KWQLinearOrder : public TLinearOrder<VoidPtr>
	{
	public:
		KWQLinearOrder( KWQCompareFunction aFunction, VoidPtr aData ) : TLinearOrder<VoidPtr>(SortCompareFunction)
			{
			iFunction = aFunction;
			iData = aData;
			}

		static TInt SortCompareFunction( const VoidPtr& a, const VoidPtr& b )
			{
			return iFunction( const_cast<VoidPtr&>(a), const_cast<VoidPtr&>(b), iData );
			}

	private:
		static void* iData;
		static KWQCompareFunction iFunction;
	};

void* KWQLinearOrder::iData = 0;
KWQCompareFunction KWQLinearOrder::iFunction = 0;

class KWQListNode
OOM_MODIFIED
{
public:
    KWQListNode(void *d) : data(d), next(NULL), prev(NULL) { }

    void *data;
    KWQListNode *next;
    KWQListNode *prev;
};

static KWQListNode *copyList(KWQListNode *l, KWQListNode *&tail)
{
    KWQListNode *node = l;
    KWQListNode *copyHead = NULL;
    KWQListNode *last = NULL;

    while (node != NULL) {
	KWQListNode *copy = new KWQListNode(node->data);
	if (last != NULL) {
	    last->next = copy;
	} else {
	    copyHead = copy;
	}

	copy->prev = last;

	last = copy;
	node = node->next;
    }

    tail = last;
    return copyHead;
}


KWQListImpl::KWQListImpl(void (*deleteFunc)(void *)) :
    head(NULL),
    tail(NULL),
    cur(NULL),
    nodeCount(0),
    deleteItem(deleteFunc),
    iterators(NULL)
{
}

KWQListImpl::KWQListImpl(const KWQListImpl &impl) :
    cur(NULL),
    nodeCount(impl.nodeCount),
    deleteItem(impl.deleteItem),
    iterators(NULL)
{
    this->head = copyList(impl.head, tail);
}

KWQListImpl::~KWQListImpl()
{
    clear(false);

    KWQListIteratorImpl *next;
    for (KWQListIteratorImpl *it = iterators; it != NULL; it = next) {
        next = it->next;
        it->list = NULL;
        ASSERT(it->node == NULL);
        it->next = NULL;
        it->prev = NULL;
    }
}

void KWQListImpl::clear(bool deleteItems)
{
    KWQListNode *next;

    for (KWQListNode *node = this->head; node != NULL; node = next) {
        next = node->next;
        if (deleteItems) {
            deleteItem(node->data);
        }
        delete node;
    }

    this->head = NULL;
    tail = NULL;
    cur = NULL;
    nodeCount = 0;

    for (KWQListIteratorImpl *it = iterators; it != NULL; it = it->next) {
	it->node = NULL;
    }
}

void KWQListImpl::sort(int (*compareFunc)(void *a, void *b, void *data), void *data)
{
    // no sorting for 0 or 1-element lists
    if (nodeCount <= 1) {
        return;
    }

    // special case for 2-element lists
    if (nodeCount == 2) {
        void *a = this->head->data;
        void *b = this->head->next->data;
        if (compareFunc(a, b, data) <= 0) {
            return;
        }
        this->head->next->data = a;
        this->head->data = b;
        return;
    }

    // insertion sort for most common sizes
    const uint cutoff = 32;
    if (nodeCount <= cutoff) {
        // Straight out of Sedgewick's Algorithms in C++.

        // put all the elements into an array
#ifndef __OOM__
        VoidPtr* a = new VoidPtr[cutoff];
#else
        VoidPtr* a = (VoidPtr*)MemoryManager::Calloc( cutoff, sizeof(VoidPtr) );
#endif
        if( !a ) return;

        uint i = 0;
        for (KWQListNode *node = this->head; node != NULL; node = node->next) {
            a[i++] = node->data;
        }

        // move the smallest element to the start to serve as a sentinel
        for (i = nodeCount - 1; i > 0; i--) {
            if (compareFunc(a[i-1], a[i], data) > 0) {
                void *t = a[i-1];
                a[i-1] = a[i];
                a[i] = t;
            }
        }

        // move other items to the right and put a[i] into position
        for (i = 2; i < nodeCount; i++) {
            void *v = a[i];
            uint j = i;
            while (compareFunc(v, a[j-1], data) < 0) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = v;
        }

        // finally, put everything back into the list
        i = 0;
        for (KWQListNode *node = this->head; node != NULL; node = node->next) {
            node->data = a[i++];
        }
#ifndef __OOM__
        delete [] a;
#else
		MemoryManager::Free(a);
#endif
        return;
    }

    KWQLinearOrder order( compareFunc, data );
    RArray<VoidPtr> array;

    // populate the array and sort
    for (KWQListNode *node = this->head; node != NULL; node = node->next) {
		User::LeaveIfError( array.Append( node->data ) );
    }
    array.Sort( order );

    // copy data back to the list
    int i = 0;
    for (KWQListNode *node = this->head; node != NULL; node = node->next) {
		node->data = const_cast<void *>( array[i++] );
    }
}

void *KWQListImpl::at(uint n)
{
    KWQListNode *node;
    if (n >= nodeCount - 1) {
        node = tail;
    } else {
        node = this->head;
        for (uint i = 0; i < n && node != NULL; i++) {
            node = node->next;
        }
    }

    cur = node;
    return node ? node->data : 0;
}

bool KWQListImpl::insert(uint n, const void *item)
{
    if (n > nodeCount) {
	return false;
    }

    KWQListNode *node = new KWQListNode((void *)item);

    if (n == 0) {
	// inserting at this->head
	node->next = this->head;
	if (this->head != NULL) {
	    this->head->prev = node;
	}
	this->head = node;
        if (tail == NULL) {
            tail = node;
        }
    } else if (n == nodeCount) {
        // inserting at tail
        node->prev = tail;
        if (tail != NULL) {
            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
	KWQListNode *prevNode = this->head;

	for (uint i = 0; i < n - 1; i++) {
	    prevNode = prevNode->next;
	}
	node->prev = prevNode;
	node->next = prevNode->next;
	if (node->next != NULL) {
	    node->next->prev = node;
	}
	prevNode->next = node;
    }

    nodeCount++;
    cur = node;
    return true;
}

bool KWQListImpl::remove(bool shouldDeleteItem)
{
    KWQListNode *node = cur;
    if (node == NULL) {
	return false;
    }

    if (node->prev == NULL) {
	this->head = node->next;
    } else {
	node->prev->next = node->next;
    }

    if (node->next == NULL) {
        tail = node->prev;
    } else {
	node->next->prev = node->prev;
    }

    if (node->next != NULL) {
	cur = node->next;
    } else {
	cur = node->prev;
    }

    for (KWQListIteratorImpl *it = iterators; it != NULL; it = it->next) {
	if (it->node == node) {
	    it->node = cur;
	}
    }

    if (shouldDeleteItem) {
	deleteItem(node->data);
    }
    delete node;

    nodeCount--;

    return true;
}

bool KWQListImpl::remove(uint n, bool deleteItem)
{
    if (n >= nodeCount) {
	return false;
    }

    at(n);
    return remove(deleteItem);
}

bool KWQListImpl::removeFirst(bool deleteItem)
{
    return remove(0, deleteItem);
}

bool KWQListImpl::removeLast(bool deleteItem)
{
    return remove(nodeCount - 1, deleteItem);
}

bool KWQListImpl::remove(const void *item, bool deleteItem, int (*compareFunc)(void *a, void *b, void *data), void *data)
{
    KWQListNode *node;

    node = this->head;

    while (node != NULL && compareFunc((void *)item, node->data, data) != 0) {
	node = node->next;
    }

    if (node == NULL) {
	return false;
    }

    cur = node;

    return remove(deleteItem);
}

bool KWQListImpl::removeRef(const void *item, bool deleteItem)
{
    KWQListNode *node;

    node = this->head;

    while (node != NULL && item != node->data) {
	node = node->next;
    }

    if (node == NULL) {
	return false;
    }

    cur = node;

    return remove(deleteItem);
}

void *KWQListImpl::getFirst() const
{
    return this->head ? this->head->data : 0;
}

void *KWQListImpl::getLast() const
{
    return tail ? tail->data : 0;
}

void *KWQListImpl::getNext() const
{
    return cur && cur->next ? cur->next->data : 0;
}

void *KWQListImpl::getPrev() const
{
    return cur && cur->prev ? cur->prev->data : 0;
}

void *KWQListImpl::current() const
{
    if (cur != NULL) {
	return cur->data;
    } else {
	return NULL;
    }
}

void *KWQListImpl::first()
{
    cur = this->head;
    return current();
}

void *KWQListImpl::last()
{
    cur = tail;
    return current();
}

void *KWQListImpl::next()
{
    if (cur != NULL) {
	cur = cur->next;
    }
    return current();
}

void *KWQListImpl::prev()
{
    if (cur != NULL) {
	cur = cur->prev;
    }
    return current();
}

void *KWQListImpl::take(uint n)
{
    void *retval = at(n);
    remove(false);
    return retval;
}

void *KWQListImpl::take()
{
    void *retval = current();
    remove(false);
    return retval;
}

void KWQListImpl::append(const void *item)
{
    insert(nodeCount, item);
}

void KWQListImpl::prepend(const void *item)
{
    insert(0, item);
}

uint KWQListImpl::containsRef(const void *item) const
{
    uint count = 0;

    for (KWQListNode *node = this->head; node != NULL; node = node->next) {
        if (item == node->data) {
            ++count;
        }
    }

    return count;
}

KWQListImpl &KWQListImpl::assign(const KWQListImpl &impl, bool deleteItems)
{
    clear(deleteItems);
    KWQListImpl(impl).swap(*this);
    return *this;
}

void KWQListImpl::addIterator(KWQListIteratorImpl *iter) const
{
    iter->next = iterators;
    iter->prev = NULL;

    if (iterators != NULL) {
        iterators->prev = iter;
    }
    iterators = iter;
}

void KWQListImpl::removeIterator(KWQListIteratorImpl *iter) const
{
    if (iter->prev == NULL) {
        iterators = iter->next;
    } else {
        iter->prev->next = iter->next;
    }

    if (iter->next != NULL) {
        iter->next->prev = iter->prev;
    }
}

void KWQListImpl::swap(KWQListImpl &other)
{
    using std::swap;

    ASSERT(iterators == NULL);
    ASSERT(other.iterators == NULL);

    swap(this->head, other.head);
    swap(this->tail, other.tail);
    swap(this->cur, other.cur);
    swap(this->nodeCount, other.nodeCount);
    swap(this->deleteItem, other.deleteItem);
}


KWQListIteratorImpl::KWQListIteratorImpl() :
    list(NULL),
    node(NULL)
{
}

KWQListIteratorImpl::KWQListIteratorImpl(const KWQListImpl &impl)  :
    list(&impl),
    node(impl.head)
{
    impl.addIterator(this);
}

KWQListIteratorImpl::~KWQListIteratorImpl()
{
    if (list != NULL) {
	list->removeIterator(this);
    }
}

KWQListIteratorImpl::KWQListIteratorImpl(const KWQListIteratorImpl &impl) :
    list(impl.list),
    node(impl.node)
{
    if (list != NULL) {
        list->addIterator(this);
    }
}

uint KWQListIteratorImpl::count() const
{
    return list == NULL ? 0 : list->count();
}

void *KWQListIteratorImpl::toFirst()
{
    if (list != NULL) {
        node = list->head;
    }
    return current();
}

void *KWQListIteratorImpl::toLast()
{
    if (list != NULL) {
        node = list->tail;
    }
    return current();
}

void *KWQListIteratorImpl::current() const
{
    return node == NULL ? NULL : node->data;
}

void *KWQListIteratorImpl::operator--()
{
    if (node != NULL) {
	node = node->prev;
    }
    return current();
}

void *KWQListIteratorImpl::operator++()
{
    if (node != NULL) {
	node = node->next;
    }
    return current();
}

KWQListIteratorImpl &KWQListIteratorImpl::operator=(const KWQListIteratorImpl &impl)
{
    if (list != NULL) {
	list->removeIterator(this);
    }

    list = impl.list;
    node = impl.node;

    if (list != NULL) {
	list->addIterator(this);
    }

    return *this;
}