kwqmapimpl.cpp

khtml在gtk上的移植版本

		    (sibling->right() == NULL || sibling->right()->color == KWQMapNodeImpl::Black)) {
		    sibling->color = KWQMapNodeImpl::Red;
		    height = height - 1;
		} else {
		    if (sibling->right() == NULL || sibling->right()->color == KWQMapNodeImpl::Black) {
			sibling->left()->color = KWQMapNodeImpl::Black;
			sibling->color = KWQMapNodeImpl::Red;
			rotateRight(sibling, nodes[height-1], !wentLeft[height-1]);
			sibling = nodes[height-1]->right();
		    }
		    
		    sibling->color = nodes[height-1]->color;
		    nodes[height-1]->color = KWQMapNodeImpl::Black;
		    sibling->right()->color = KWQMapNodeImpl::Black;
		    rotateLeft(nodes[height-1], nodes[height-2], wentLeft[height-2]);
		    
		    nodes[height] = d->guard->prev;
		}
	    } else {
		// same as the other branch, but with left and right swapped
		
		KWQMapNodeImpl *sibling = nodes[height-1]->left();
		if (sibling != NULL && sibling->color == KWQMapNodeImpl::Red) {
		    sibling->color = KWQMapNodeImpl::Black;
		    nodes[height-1]->color = KWQMapNodeImpl::Red;
		    rotateRight(nodes[height-1], nodes[height-2], wentLeft[height-2]);
		    
		    nodes[height] = nodes[height-1];
		    wentLeft[height] = false;
		    nodes[height-1] = sibling;
		    height = height + 1;
		    
		    sibling = nodes[height-1]->left();
		}
		if ((sibling->right() == NULL || sibling->right()->color == KWQMapNodeImpl::Black) &&
		    (sibling->left() == NULL || sibling->left()->color == KWQMapNodeImpl::Black)) {
		    sibling->color = KWQMapNodeImpl::Red;
		    height = height - 1;
		} else {
		    if (sibling->left() == NULL || sibling->left()->color == KWQMapNodeImpl::Black) {
			sibling->right()->color = KWQMapNodeImpl::Black;
			sibling->color = KWQMapNodeImpl::Red;
			rotateLeft(sibling, nodes[height-1], !wentLeft[height-1]);
			sibling = nodes[height-1]->left();
		    }
		    
		    sibling->color = nodes[height-1]->color;
		    nodes[height-1]->color = KWQMapNodeImpl::Black;
		    sibling->left()->color = KWQMapNodeImpl::Black;
		    rotateRight(nodes[height-1], nodes[height-2], wentLeft[height-2]);
		    
		    nodes[height] = d->guard->prev;
		}
	    }
	}
	
	if (nodes[height] != NULL) {
	    nodes[height]->color = KWQMapNodeImpl::Black;
	}
    }
}

KWQMapNodeImpl *KWQMapImpl::findInternal(KWQMapNodeImpl *target) const
{
    KWQMapNodeImpl *node = d->guard->left();
    
    while (node != NULL) {
	CompareResult compare = compareNodes(target,node);
	
	if (compare == Equal) {
	    break;
	} else if (compare == Less) {
	    node = node->left();
	} else if (compare == Greater) {
	    node = node->right();
	}
    }
    
    return node;
}

KWQMapNodeImpl *KWQMapImpl::insertInternal(KWQMapNodeImpl *nodeToInsert, bool replaceExisting)
{
    KWQMapNodeImpl *nodeStack[MAX_STACK];
    bool wentLeftStack[MAX_STACK];
    int height = 0;
    
    copyOnWrite();

    nodeStack[height] = d->guard;
    wentLeftStack[height] = true;
    height++;
    
    KWQMapNodeImpl *node = d->guard->left();
    
    while (node != NULL) {
	CompareResult compare = compareNodes(nodeToInsert, node);
	if (compare == Equal) {
	    break;
	} else if (compare == Less) {
	    nodeStack[height] = node;
	    wentLeftStack[height] = true;
	    height++;
	    node = node->left();
	} else {
	    nodeStack[height] = node;
	    wentLeftStack[height] = false;
	    height++;
	    node = node->right();
	}
    }
    
    if (node != NULL) {
	if (replaceExisting) {
	    copyNode(nodeToInsert, node);
	}
	return node;
    }
    
    node = duplicateNode(nodeToInsert);
    
    nodeStack[height] = node;
    
    if (wentLeftStack[height-1]) {
	// arrange for threading
	node->prev = nodeStack[height-1]->prev;
	node->prevIsChild = false;
	node->next = nodeStack[height-1];
	node->nextIsChild = false;
	
	// make it the child
	nodeStack[height-1]->prev = node;
	nodeStack[height-1]->prevIsChild = true;
    } else {
	// arrange for threading
	node->next = nodeStack[height-1]->next;
	node->nextIsChild = false;
	node->prev = nodeStack[height-1];
	node->prevIsChild = false;
	
	// make it the child
	nodeStack[height-1]->next = node;
	nodeStack[height-1]->nextIsChild = true;
    }
    
    rebalanceAfterInsert(nodeStack, wentLeftStack, height);
    d->numNodes++;

    return node;
}

void KWQMapImpl::removeEqualInternal(KWQMapNodeImpl *nodeToDelete, bool samePointer)
{
    KWQMapNodeImpl *nodeStack[MAX_STACK];
    bool wentLeftStack[MAX_STACK];
    int height = 0;
    
    copyOnWrite();

    nodeStack[height] = d->guard;
    wentLeftStack[height] = true;
    height++;
    
    KWQMapNodeImpl *node = d->guard->left();
    
    while (node != NULL) {
	CompareResult compare = compareNodes(nodeToDelete, node);
	if (compare == Equal) {
	    break;
	} else if (compare == Less) {
	    nodeStack[height] = node;
	    wentLeftStack[height] = true;
	    height++;
	    node = node->left();
	} else {
	    nodeStack[height] = node;
	    wentLeftStack[height] = false;
	    height++;
	    node = node->right();
	}
    }

    if (node == NULL || samePointer && node != nodeToDelete) {
	return;
    }
	
    KWQMapNodeImpl *removalParent;
    KWQMapNodeImpl *nodeToRemove;
    bool removalWentLeft;

    if (node->left() == NULL || node->right() == NULL) {
	// If this node has at most one subtree, we can remove it directly
	nodeToRemove = node;
	removalParent = nodeStack[height-1];
	removalWentLeft = wentLeftStack[height-1];
    } else {
	// Otherwise we find the immediate successor (leftmost
	// node in the right subtree), which must have at most one
	// subtree, swap it's contents with the node we found, and
	// remove it.
	nodeToRemove = node->right();
	wentLeftStack[height] = false;
	nodeStack[height] = node;
	height++;
	
	removalParent = node;
	removalWentLeft = false;
	
	while (nodeToRemove->left() != NULL) {
	    wentLeftStack[height] = true;
	    nodeStack[height] = nodeToRemove;
	    removalParent = nodeToRemove;
	    nodeToRemove = nodeToRemove->left();
	    removalWentLeft = true;
	    height++;
	}

	swapNodes(node,nodeToRemove);
    }


    // find replacement node
    KWQMapNodeImpl *removalReplacement;

    if (nodeToRemove->left() != NULL) {
	removalReplacement = nodeToRemove->left();
	// fixup threading
	nodeToRemove->predecessor()->next = nodeToRemove->next; 
    } else if (nodeToRemove->right() != NULL) {
	removalReplacement = nodeToRemove->right();
	// fixup threading
	nodeToRemove->successor()->prev = nodeToRemove->prev;
    } else {
	removalReplacement = NULL;
    }
    
    nodeStack[height] = removalReplacement;
    
    // detach removal node
    if (removalWentLeft) {
	if (removalReplacement == NULL) {
	    removalParent->prev = nodeToRemove->prev;
	    removalParent->prevIsChild = nodeToRemove->prevIsChild;
	} else {
	    removalParent->prev = removalReplacement;
	}
    } else {
	if (removalReplacement == NULL) {
	    removalParent->next = nodeToRemove->next;
	    removalParent->nextIsChild = nodeToRemove->nextIsChild;
	} else {
	    removalParent->next = removalReplacement;
	}
    }
    
    // do red-black rebalancing
    rebalanceAfterRemove(nodeToRemove, nodeStack, wentLeftStack, height);
    
    // detach removal node's children
    nodeToRemove->next = NULL;
    nodeToRemove->prev = NULL;
    
    d->numNodes--;
    d->deleteNode(nodeToRemove);
}

void KWQMapImpl::swap(KWQMapImpl &map)
{
    KWQRefPtr<KWQMapPrivate> tmp = d;
    d = map.d;
    map.d = tmp; // KWIQ: Possible bugfix: Orig: map.d = d;
}

uint KWQMapImpl::countInternal() const
{
    return d->numNodes;
}

void KWQMapImpl::clearInternal()
{
    copyOnWrite();

    d->deleteNode(d->guard->prev);
    d->guard->prev = NULL;
    d->numNodes = 0;
}

const KWQMapNodeImpl *KWQMapImpl::beginInternal() const
{
    KWQMapNodeImpl *node;
    
    node = d->guard;
    while (node->left() != NULL) {
	node = node->left();
    }
    
    return node;
}

const KWQMapNodeImpl *KWQMapImpl::endInternal() const
{
    return d->guard;
}

KWQMapNodeImpl *KWQMapImpl::beginInternal()
{
    KWQMapNodeImpl *node;
    
    copyOnWrite();

    node = d->guard;
    while (node->left() != NULL) {
	node = node->left();
    }
    
    return node;
}

KWQMapNodeImpl *KWQMapImpl::endInternal()
{
    copyOnWrite();
    return d->guard;
}