kwqmapimpl.cpp

khtml在gtk上的移植版本

/*
 * Copyright (C) 2003 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 "KWQMapImpl.h"

#include "KWQDef.h"

KWQMapNodeImpl::KWQMapNodeImpl() :
    prev(NULL),
    next(NULL),
    prevIsChild(true),
    nextIsChild(true),
    color(Red)
{
}

KWQMapNodeImpl *KWQMapNodeImpl::left()
{
    return prevIsChild ? prev : NULL;
}

const KWQMapNodeImpl *KWQMapNodeImpl::left() const
{
    return prevIsChild ? prev : NULL;
}

KWQMapNodeImpl *KWQMapNodeImpl::right()
{
    return nextIsChild ? next : NULL;
}

const KWQMapNodeImpl *KWQMapNodeImpl::right() const
{
    return nextIsChild ? next : NULL;
}

KWQMapNodeImpl *KWQMapNodeImpl::predecessor()
{
    if (!prevIsChild || prev == NULL) {
	return prev;
    }
    KWQMapNodeImpl *pred = left();
    while (pred->right() != NULL) {
	pred = pred->right();
    }
    return pred;
}

const KWQMapNodeImpl *KWQMapNodeImpl::predecessor() const
{
    if (!prevIsChild || prev == NULL) {
	return prev;
    }
    const KWQMapNodeImpl *pred = left();
    while (pred->right() != NULL) {
	pred = pred->right();
    }
    return pred;
}

KWQMapNodeImpl *KWQMapNodeImpl::successor()
{
    if (!nextIsChild || next == NULL) {
	return next;
    }
    KWQMapNodeImpl *succ = right();
    while (succ->left() != NULL) {
	succ = succ->left();
    }
    return succ;
}

const KWQMapNodeImpl *KWQMapNodeImpl::successor() const
{
    if (!nextIsChild || next == NULL) {
	return next;
    }
    const KWQMapNodeImpl *succ = right();
    while (succ->left() != NULL) {
	succ = succ->left();
    }
    return succ;
}


KWQMapIteratorImpl::KWQMapIteratorImpl() : node(NULL)
{
}

void KWQMapIteratorImpl::incrementInternal()
{
    node = node->successor();
}


// KWQMapImplPrivate

class KWQMapImpl::KWQMapPrivate
{
public:
    KWQMapPrivate(KWQMapNodeImpl *node,
		  uint count,
		  void (*deleteFunc)(KWQMapNodeImpl *));

    ~KWQMapPrivate();

    KWQMapNodeImpl *guard;
    uint numNodes;
    int refCount;
    void (*deleteNode)(KWQMapNodeImpl *);
    friend class KWQRefPtr<KWQMapImpl::KWQMapPrivate>;
};

KWQMapImpl::KWQMapPrivate::KWQMapPrivate(KWQMapNodeImpl *node,
					 uint count,
					 void (*deleteFunc)(KWQMapNodeImpl *)) :
    guard(node),
    numNodes(count),
    refCount(0),
    deleteNode(deleteFunc)
{
}

KWQMapImpl::KWQMapPrivate::~KWQMapPrivate()
{
    deleteNode(guard);
}

// KWQMapImpl

KWQMapImpl::KWQMapImpl(KWQMapNodeImpl *guard, void (*deleteNode)(KWQMapNodeImpl *)) :
    d(new KWQMapPrivate(guard, 0, deleteNode))
{
}

KWQMapImpl::KWQMapImpl(const KWQMapImpl &impl) :
    d(impl.d)
{
}

KWQMapImpl::~KWQMapImpl()
{
}

void KWQMapImpl::copyOnWrite()
{
    if (d->refCount > 1) {
	d = KWQRefPtr<KWQMapPrivate>(new KWQMapPrivate(copyTree(d->guard, NULL, NULL), d->numNodes, d->deleteNode));
    }
}

KWQMapNodeImpl *KWQMapImpl::copyTree(const KWQMapNodeImpl *node, 
				     KWQMapNodeImpl *subtreePredecessor, 
				     KWQMapNodeImpl *subtreeSuccessor) const
{
    if (node == NULL) {
	return NULL;
    }
    
    // FIXME: not exception-safe - use auto_ptr?
    KWQMapNodeImpl *copy = duplicateNode(node);
    copy->color = node->color;
    
    if (node->prevIsChild) {
	copy->prevIsChild = true;
	copy->prev = copyTree(node->prev, subtreePredecessor, copy);
    } else {
	copy->prevIsChild = false;
	copy->prev = subtreePredecessor;
    }
    
    if (node->nextIsChild) {
	copy->nextIsChild = true;
	copy->next = copyTree(node->next, copy, subtreeSuccessor);
    } else {
	copy->nextIsChild = false;
	copy->next = subtreeSuccessor;
    }
    
    return copy;
}

void KWQMapImpl::rotateRight(KWQMapNodeImpl *node, KWQMapNodeImpl *parent, bool leftParent)
{
    KWQMapNodeImpl *rotationChild = node->left();

	if (leftParent) {
	    parent->prev = rotationChild;
	} else {
	    parent->next = rotationChild;
	}
	
	node->prev = rotationChild->next;
	node->prevIsChild = rotationChild->nextIsChild;
	
	rotationChild->next = node;
	rotationChild->nextIsChild = true;

	// fixup threads
	if (!node->prevIsChild) {
	    node->prev = rotationChild;
	}
    }
    
void KWQMapImpl::rotateLeft(KWQMapNodeImpl *node, KWQMapNodeImpl *parent, bool leftParent)
{
    KWQMapNodeImpl *rotationChild = node->right();
    
    if (leftParent) {
	parent->prev = rotationChild;
    } else {
	parent->next = rotationChild;
    }
    
    node->next = rotationChild->prev;
    node->nextIsChild = rotationChild->prevIsChild;
    
    rotationChild->prev = node;
    rotationChild->prevIsChild = true;
    
    // fixup threads
    if (!node->nextIsChild) {
	node->next = rotationChild;
    }
}

void KWQMapImpl::rebalanceAfterInsert(KWQMapNodeImpl **nodes, bool *wentLeft, int height)
{
    nodes[height]->color = KWQMapNodeImpl::Red;
    
    while (nodes[height] != d->guard->prev && nodes[height-1]->color == KWQMapNodeImpl::Red) {
	if (wentLeft[height-2]) {
	    KWQMapNodeImpl *uncle = nodes[height-2]->right();
	    if (uncle != NULL && uncle->color == KWQMapNodeImpl::Red) {
		nodes[height-1]->color = KWQMapNodeImpl::Black;
		uncle->color = KWQMapNodeImpl::Black;
		nodes[height-2]->color = KWQMapNodeImpl::Red;
		
		// go up two levels
		height = height - 2;
	    } else {
		KWQMapNodeImpl *parent;
		if (!wentLeft[height-1]) {
		    parent = nodes[height-1]->right();
		    rotateLeft(nodes[height-1], nodes[height-2], wentLeft[height-2]);
		} else {
		    parent = nodes[height-1];
		}
		parent->color = KWQMapNodeImpl::Black;
		nodes[height-2]->color = KWQMapNodeImpl::Red;
		rotateRight(nodes[height-2], nodes[height-3], wentLeft[height-3]);
		break;
	    }
	} else {
	    // same as the other branch, but with left and right swapped
	    
	    KWQMapNodeImpl *uncle = nodes[height-2]->left();
	    
	    if (uncle != NULL && uncle->color == KWQMapNodeImpl::Red) {
		nodes[height-1]->color = KWQMapNodeImpl::Black;
		uncle->color = KWQMapNodeImpl::Black;
		nodes[height-2]->color = KWQMapNodeImpl::Red;
		
		// go up two levels
		height = height - 2;
	    } else {
		KWQMapNodeImpl *parent;
		if (wentLeft[height-1]) {
		    parent = nodes[height-1]->left();
		    rotateRight(nodes[height-1], nodes[height-2], wentLeft[height-2]);
		} else {
		    parent = nodes[height-1];
		}
		parent->color = KWQMapNodeImpl::Black;
		nodes[height-2]->color = KWQMapNodeImpl::Red;
		rotateLeft(nodes[height-2], nodes[height-3], wentLeft[height-3]);
		break;
	    }
	}
    }
    
    d->guard->prev->color = KWQMapNodeImpl::Black;
}

void KWQMapImpl::rebalanceAfterRemove(KWQMapNodeImpl *nodeToRemove, KWQMapNodeImpl **nodes, bool *wentLeft, int height) 
{
    if (nodeToRemove->color == KWQMapNodeImpl::Black) {
	while (nodes[height] != d->guard->prev && (nodes[height]==NULL || nodes[height]->color==KWQMapNodeImpl::Black)) {
	    if (wentLeft[height-1]) {
		KWQMapNodeImpl *sibling = nodes[height-1]->right();
		if (sibling != NULL && sibling->color == KWQMapNodeImpl::Red) {
		    sibling->color = KWQMapNodeImpl::Black;
		    nodes[height-1]->color = KWQMapNodeImpl::Red;
		    rotateLeft(nodes[height-1], nodes[height-2], wentLeft[height-2]);
		    
		    nodes[height] = nodes[height-1];
		    wentLeft[height] = true;
		    nodes[height-1] = sibling;
		    height = height + 1;
		    
		    sibling = nodes[height-1]->right();
		}
		if ((sibling->left() == NULL || sibling->left()->color == KWQMapNodeImpl::Black) &&