rvtree.c

h.248协议源码

/******************************************************************************
Filename:    rvtree.c
Description: balanced binary tree class
*******************************************************************************
                Copyright (c) 2000 RADVision Inc.
*******************************************************************************
NOTICE:
This document contains information that is proprietary to RADVision LTD.
No part of this publication may be reproduced in any form whatsoever 
without written prior approval by RADVision LTD..

RADVision LTD. reserves the right to revise this publication and make 
changes without obligation to notify any person of such revisions or 
changes.
******************************************************************************/

#include "rvtree.h"

typedef struct RvTreeNode
{
	struct RvTreeNode *left, *right, *mommy;
	int height;
} RvNode;

static void *rvNodeGetKey(RvNode *node)
{
	return (char *)node + sizeof(RvNode);
}

static void *rvNodeGetValue(RvNode *node, const RvTreeInfo *info)
{
	return (char *)node + sizeof(RvNode) + info->keySize;
}

static int getLeftHeight(const RvNode *node)
{
	return node->left == NULL ? -1 : node->left->height;
}

static int getRightHeight(const RvNode *node)
{
	return node->right == NULL ? -1 : node->right->height;
}

static void rvNodeFixHeight(RvNode *node)
{
	int lh = getLeftHeight(node);
	int rh = getRightHeight(node);
	node->height = (lh > rh) ? (lh + 1) : (rh + 1);
}

static void rvNodeRotateLeft(RvNode **x)
{
	RvNode * saveRight = (*x)->right;
	(*x)->right = saveRight->left;
	if((*x)->right != NULL) 
		(*x)->right->mommy = *x;
	saveRight->left = *x;
	saveRight->mommy = (*x)->mommy;
	(*x)->mommy = saveRight;
	*x = saveRight;
	rvNodeFixHeight((*x)->left);
	rvNodeFixHeight(*x);
}

static void rvNodeRotateRight(RvNode **x)
{
	RvNode * saveLeft = (*x)->left;
	(*x)->left = saveLeft->right;
	if((*x)->left != NULL) 
		(*x)->left->mommy = *x;
	saveLeft->right = *x;
	saveLeft->mommy = (*x)->mommy;
	(*x)->mommy = saveLeft;
	*x = saveLeft;
	rvNodeFixHeight((*x)->right);
	rvNodeFixHeight(*x);
}

static void rvNodeBalanceLeft(RvNode **x)
{
	rvNodeFixHeight(*x);
	if(getRightHeight(*x) - getLeftHeight(*x) > 1)
	{
		if(getLeftHeight((*x)->right) > getRightHeight((*x)->right))
		{
			rvNodeRotateRight(&(*x)->right);
		}
		rvNodeRotateLeft(x);
	}
}

static void rvNodeBalanceRight(RvNode **x)
{
	rvNodeFixHeight(*x);
	if(getLeftHeight(*x) - getRightHeight(*x) > 1)
	{
		if(getRightHeight((*x)->left) > getLeftHeight((*x)->left))
		{
			rvNodeRotateLeft(&(*x)->left);
		}
		rvNodeRotateRight(x);
	}
}

static void rvNodeAdd(RvNode **x, const void *key, const void *value, RvTree *tree, RvNode *parent)
{
	const RvTreeInfo *info = tree->info;
	if(*x == NULL)
	{
		*x = (RvNode *)rvAllocAllocate(tree->allocator, sizeof(RvNode) + info->keySize + info->valueSize);
		(*x)->left = (*x)->right = 0;
		(*x)->mommy = parent;
		(*x)->height = 0;
		info->keyConstructCopy(rvNodeGetKey(*x), key, tree->allocator);
		info->valueConstructCopy(rvNodeGetValue(*x, info), value, tree->allocator);
		tree->count++;
	}
	else if(info->keyEqual(key, rvNodeGetKey(*x)))
	{
		info->valueDestruct(rvNodeGetValue(*x, info));
		info->valueConstructCopy(rvNodeGetValue(*x, info), value, tree->allocator);
	}
	else if(info->keyLess(key, rvNodeGetKey(*x)))
	{
		rvNodeAdd(&(*x)->left, key, value, tree, *x);
		rvNodeBalanceRight(x);
	}
	else
	{
		rvNodeAdd(&(*x)->right, key, value, tree, *x);
		rvNodeBalanceLeft(x);
	}
}

static RvNode *rvNodeRemoveLargest(RvNode **x)
{
	RvNode *retVal;
	if((*x)->right == NULL)
	{
		RvNode *largest = *x;
		*x = largest->left;
		if(*x != NULL)
			(*x)->mommy = largest->mommy;
		return largest;
	}
	retVal = rvNodeRemoveLargest(&(*x)->right);
	rvNodeBalanceRight(x);
	return retVal;
}

static RvNode *rvNodeRemoveSmallest(RvNode **x)
{
	RvNode *retVal;
	if((*x)->left == NULL)
	{
		RvNode *smallest = *x;
		*x = smallest->right;
		if(*x != NULL)
			(*x)->mommy = smallest->mommy;
		return smallest;
	}
	retVal = rvNodeRemoveSmallest(&(*x)->left);
	rvNodeBalanceLeft(x);
	return retVal;
}

static void rvNodeRemove(RvNode **x, const void *key, RvTree *tree)
{
	const RvTreeInfo *info = tree->info;
	if(*x == NULL)
		return;
	if(info->keyEqual(key, rvNodeGetKey(*x)))
	{
		info->keyDestruct(rvNodeGetKey(*x));
		info->valueDestruct(rvNodeGetValue(*x, info));
		if((*x)->left != NULL)
		{
			RvNode *largest = rvNodeRemoveLargest(&(*x)->left);
			info->keyConstructCopy(rvNodeGetKey(*x), rvNodeGetKey(largest), tree->allocator);
			info->valueConstructCopy(rvNodeGetValue(*x, info), rvNodeGetValue(largest, info), tree->allocator);
			rvAllocDeallocate(tree->allocator, sizeof(RvNode) + info->keySize + info->valueSize, largest);
			rvNodeBalanceLeft(x);
		}
		else if((*x)->right != NULL)
		{
			RvNode *smallest = rvNodeRemoveSmallest(&(*x)->right);
			info->keyConstructCopy(rvNodeGetKey(*x), rvNodeGetKey(smallest), tree->allocator);
			info->valueConstructCopy(rvNodeGetValue(*x, info), rvNodeGetValue(smallest, info), tree->allocator);
			rvAllocDeallocate(tree->allocator, sizeof(RvNode) + info->keySize + info->valueSize, smallest);
			rvNodeBalanceRight(x);
		}
		else
		{
			rvAllocDeallocate(tree->allocator, sizeof(RvNode) + info->keySize + info->valueSize, *x);
			*x = NULL;
		}
		tree->count--;
	}
	else if(info->keyLess(key, rvNodeGetKey(*x)))
	{
		rvNodeRemove(&(*x)->left, key, tree);
		rvNodeBalanceLeft(x);
	}
	else
	{
		rvNodeRemove(&(*x)->right, key, tree);
		rvNodeBalanceRight(x);
	}
}

static void *rvNodeFind(RvNode * const *x, const void *key, const RvTreeInfo *info)
{
	if(*x == NULL)
		return NULL;
	if(info->keyEqual(key, rvNodeGetKey(*x)))
		return rvNodeGetValue(*x, info);
	if(info->keyLess(key, rvNodeGetKey(*x)))
		return rvNodeFind(&(*x)->left, key, info);
	return rvNodeFind(&(*x)->right, key, info);
}

static void rvNodeClear(RvNode **x, RvTree *tree)
{
	const RvTreeInfo *info = tree->info;
	if(*x == NULL)
		return;
	rvNodeClear(&(*x)->left, tree);
	rvNodeClear(&(*x)->right, tree);
	info->keyDestruct(rvNodeGetKey(*x));
	info->valueDestruct(rvNodeGetValue(*x, info));
	rvAllocDeallocate(tree->allocator, sizeof(RvNode) + info->keySize + info->valueSize, *x);
}

static RvTreeIter rvTreeSmallest(RvTreeIter t)
{
	while(t->left != NULL)
		t = t->left;
	return t;
}

static RvTreeIter rvTreeLargest(RvTreeIter t)
{
	while(t->right != NULL)
		t = t->right;
	return t;
}


/******************** interface ********************/

RvTree *rvTreeConstruct(RvTree *t, RvAlloc *allocator, const RvTreeInfo *info)
{
	t->tree = NULL;
	t->allocator = allocator;
	t->info = info;
	t->count = 0;
	return t;
}

void rvTreeDestruct(RvTree *t)
{
	rvTreeClear(t);
}

RvTree *rvTreeConstructCopy(RvTree *d, const RvTree *s, RvAlloc *a)
{
	RvTreeIter iter;
	d->tree = NULL;
	d->allocator = s->allocator;
	d->info = s->info;
	d->count = 0;
	for(iter=rvTreeBegin(s); iter!=rvTreeEnd(s); iter=rvTreeIterNext(iter))
		rvTreeSetValue(d, rvTreeIterGetKey(iter), rvTreeIterGetValue(iter, s->info));
	return d;
}

RvTree *rvTreeCopy(RvTree *d, const RvTree *s)
{
	RvTreeIter iter;
	rvTreeClear(d);
	for(iter=rvTreeBegin(s); iter!=rvTreeEnd(s); iter=rvTreeIterNext(iter))
		rvTreeSetValue(d, rvTreeIterGetKey(iter), rvTreeIterGetValue(iter, s->info));
	return d;
}

void rvTreeSetValue(RvTree *t, const void *key, const void *value)
{
	rvNodeAdd(&t->tree, key, value, t, NULL);
}

const void *rvTreeGetValue(const RvTree *t, const void *key)
{
	return rvNodeFind(&t->tree, key, t->info);
}

void *rvTreeFindValue(const RvTree *t, const void *key)
{
	return rvNodeFind(&t->tree, key, t->info);
}

void rvTreeRemove(RvTree *t, const void *key)
{
	rvNodeRemove(&t->tree, key, t);
}

size_t rvTreeSize(const RvTree *t)
{
	return t->count;
}

void rvTreeClear(RvTree *t)
{
	rvNodeClear(&t->tree, t);
	t->tree = NULL;
	t->count = 0;
}

RvAlloc* rvTreeGetAllocator(const RvTree *t)
{
	return t->allocator;
}

RvTreeIter rvTreeBegin(const RvTree *t)
{
	return (t->tree == NULL) ? NULL : rvTreeSmallest(t->tree);
}

RvTreeIter rvTreeEnd(const RvTree *t)
{
	return NULL;
}

RvTreeRevIter rvTreeRevBegin(const RvTree *t)
{
	return (t->tree == NULL) ? NULL : rvTreeLargest(t->tree);
}

RvTreeRevIter rvTreeRevEnd(const RvTree *t)
{
	return NULL;
}

RvTreeIter rvTreeIterNext(RvTreeIter iter)
{
	if(iter->right != NULL)
		return rvTreeSmallest(iter->right);
	while(iter->mommy != NULL)
	{
		if(iter->mommy->left == iter)
			return iter->mommy;
		iter = iter->mommy;
	}
	return NULL;
}

RvTreeIter rvTreeIterPrev(RvTreeIter iter)
{
	if(iter->left != NULL)
		return rvTreeLargest(iter->left);
	while(iter->mommy != NULL)
	{
		if(iter->mommy->right == iter)
			return iter->mommy;
		iter = iter->mommy;
	}
	return NULL;
}

RvTreeRevIter rvTreeRevIterNext(RvTreeRevIter iter)
{
	return rvTreeIterPrev(iter);
}

RvTreeRevIter rvTreeRevIterPrev(RvTreeRevIter iter)
{
	return rvTreeIterNext(iter);
}

const void *rvTreeIterGetKey(RvTreeIter iter)
{
	return rvNodeGetKey(iter);
}

void *rvTreeIterGetValue(RvTreeIter iter, const RvTreeInfo *info)
{
	return rvNodeGetValue(iter, info);
}

const void *rvTreeRevIterGetKey(RvTreeRevIter iter)
{
	return rvNodeGetKey(iter);
}

void *rvTreeRevIterGetValue(RvTreeRevIter iter, const RvTreeInfo *info)
{
	return rvNodeGetValue(iter, info);
}