kwqlistimpl.cpp

khtml在gtk上的移植版本

/*
 * Copyright (C) 2001, 2002 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 "KWQListImpl.h"

#include <cstddef>
#include <algorithm>
#if !KWIQ
#include <CoreFoundation/CFArray.h>
#endif
#include "KWQAssertions.h"

class KWQListNode
{
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)
{
    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 = head; node != NULL; node = next) {
        next = node->next;
        if (deleteItems) {
            deleteItem(node->data);
        }
        delete node;
    }

    head = NULL;
    tail = NULL;
    cur = NULL;
    nodeCount = 0;

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

/* FIXME: not re-entrant */
static void *_data = 0;
static int (*_cmpfunc)(void *a, void *b, void *data);
extern "C" {
static int _qsortCmpFunc(const void*a, const void*b){
    return _cmpfunc(const_cast<void*>(a), const_cast<void*>(b), _data);
}
}

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 = head->data;
        void *b = head->next->data;
        if (compareFunc(a, b, data) <= 0) {
            return;
        }
        head->next->data = a;
        head->data = b;
        return;
    }

    // insertion sort for most common sizes
    const uint cutoff = 2000;

    if (nodeCount <= cutoff) {
        // Straight out of Sedgewick's Algorithms in C++.

        // put all the elements into an array
		void *a[cutoff];
        uint i = 0;
		KWQListNode *node;
        for (node = 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 (node = head; node != NULL; node = node->next) {
            node->data = a[i++];
        }
        return;
    }
    /* use standard c lib qsort */
    void **arr = new void*[nodeCount];
    if (arr) {
	void *olddata = _data;
	int (*oldcmpfunc)(void *a, void *b, void *data) = _cmpfunc;
	_data = data;
	_cmpfunc = compareFunc;

	int i = 0;
	for (KWQListNode *node = head; node != NULL; node = node->next) {
	    arr[i++] = node->data;
	}
	qsort(arr, nodeCount, sizeof(void*), _qsortCmpFunc);

	i = 0;
	for (KWQListNode *node = head; node != NULL; node = node->next) {
	    node->data = const_cast<void *>(arr[i++]);
	}
	_data = olddata;
	_cmpfunc = oldcmpfunc;
	delete [] arr;
    }
}

void *KWQListImpl::at(uint n)
{
    KWQListNode *node;
    if (n >= nodeCount - 1) {
        node = tail;
    } else {
        node = 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 head
	node->next = head;
	if (head != NULL) {
	    head->prev = node;
	}
	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 = 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) {
	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 = 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 = 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 head ? head->data : 0;
}

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

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

void *KWQListImpl::first()
{
    cur = 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 = 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)
{
    ASSERT(iterators == NULL);
    ASSERT(other.iterators == NULL);
    
	std::swap(head, other.head);
	std::swap(tail, other.tail);
	std::swap(cur, other.cur);
	std::swap(nodeCount, other.nodeCount);
	std::swap(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;
}