avl_tree.c

uClinux下用的数据库

/*      
** avl_tree.c	- AVL Tree Library
**
** Copyright (c) 1996  Hughes Technologies Pty Ltd
**
*************************************************************************
**
** This library implements a balanced tree capable of holding key/offset
** pairs.  The offset is assumed to be used as an offset into a data table.
** The library supports user defined key lengths on a per tree basis, and
** support for multiplte data types (i.e. int's, char strings and reals are
** inserted into the tree in the correct order, not just the order of the
** bytes that comprise the value).  This allows the btree to be used for
** range indexing.  Duplicate keys are supported.
**
** This library was written for Mini SQL.
**
** Mods for mSQL 2.1.x - Data stats are mainteined in the super block 
** including the total number of entries and the number of unique keys.
** The engine can use that info to determine index density when working
** on "union index" creation.
**
*/


/* #define AVL_DEBUG */

#include <stdio.h>
#include <fcntl.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <sys/stat.h>

#include <common/config.h>
#include <common/config_extras.h>
#include <common/portability.h>

#ifdef HAVE_STRINGS_H
#  include <strings.h>
#endif


#include <common/debug/debug.h>

#include "index.h"
#include "avl_tree.h"

#define	AVL_MAGIC 		0x01020304

#define	SBLK_SIZE		(sizeof(avl_sbk) + (8 - (sizeof(avl_sbk)% 8)))
#define DISK_NODE_SIZE(L)	(sizeof(avl_nod)+(L))
#define OFF_TO_NODE(t,o)	((o - SBLK_SIZE) / t->sblk->nodeLen + 1)
#define NODE_TO_OFF(t,n)	(((n - 1) * t->sblk->nodeLen) + SBLK_SIZE)
#define	REG			register


#define bcopy4(s,d) \
      ((((unsigned char *)d)[3] = ((unsigned char *)s)[3]), \
       (((unsigned char *)d)[2] = ((unsigned char *)s)[2]), \
       (((unsigned char *)d)[1] = ((unsigned char *)s)[1]), \
       (((unsigned char *)d)[0] = ((unsigned char *)s)[0]))

#define bcopy8(s,d) \
      ((((unsigned char *)d)[7] = ((unsigned char *)s)[7]), \
       (((unsigned char *)d)[6] = ((unsigned char *)s)[6]), \
       (((unsigned char *)d)[5] = ((unsigned char *)s)[5]), \
       (((unsigned char *)d)[4] = ((unsigned char *)s)[4]), \
       (((unsigned char *)d)[3] = ((unsigned char *)s)[3]), \
       (((unsigned char *)d)[2] = ((unsigned char *)s)[2]), \
       (((unsigned char *)d)[1] = ((unsigned char *)s)[1]), \
       (((unsigned char *)d)[0] = ((unsigned char *)s)[0]))


#define moveValue(src,srcnum,dst,dstnum,tree) \
	copyValue(src->keys[srcnum],dst->keys[dstnum],tree);	\
	dst->data[dstnum] = src->data[srcnum];			\
	dst->dups[dstnum] = src->dups[srcnum]


/*************************************************************************
**************************************************************************
**                                                                      **
**                         UTILITY ROUTINES                             **
**                                                                      **
**************************************************************************
*************************************************************************/

#define DISK_EXTEND_LENGTH		(1024 * 5)
#define MEM_EXTEND_LENGTH		256

static int extendTree(tree)
	avltree	*tree;
{
	int	nodeLen,
		count,
		extendLen;
	off_t	nodeOff,
		curOff;
	avl_nod	*cur;


	if (tree->memTree == NULL)
	{
		/*
		** Unmap the file, extend it and then re-map it
		*/
		extendLen = DISK_EXTEND_LENGTH;
		tree->oldRegion = tree->mapRegion;
		tree->oldLen = tree->mapLen;
		tree->remapped = 1;
		nodeLen = tree->sblk->nodeLen;
		munmap(tree->mapRegion, tree->mapLen);
		lseek(tree->fd, (extendLen * nodeLen) - 1, SEEK_END );
		if (write(tree->fd, "\0", 1) < 0)
		{
			perror("write failed");
			return(-1);
		}
		nodeOff = tree->mapLen;
		tree->mapLen += extendLen * nodeLen;
		tree->mapRegion = mmap(NULL, tree->mapLen, PROT_READ|PROT_WRITE,
			MAP_SHARED, tree->fd, (off_t)0);
		if (tree->mapRegion == (void*)-1)
		{
			char msg[160];
			sprintf(msg,"mmap of %u failed",tree->mapLen);
			perror(msg);
			return(-1);
		}
		tree->sblk = (avl_sbk *)tree->mapRegion;
		tree->sblk->fileLen = tree->mapLen;
	}
	else
	{
		extendLen = MEM_EXTEND_LENGTH;
		nodeOff = tree->memLen;
		tree->memTree = realloc(tree->memTree,tree->memLen +
			extendLen * tree->sblk->nodeLen);
		tree->sblk = (avl_sbk *)tree->memTree;
		tree->mapRegion = (char *)tree->memTree;
		tree->memLen += extendLen * tree->sblk->nodeLen;
	}
	
	/*
	** Setup the free list to wind through the new nodes
	*/
	curOff = nodeOff;
	for (count = 0; count < extendLen; count++)
	{
		cur = (avl_nod *)(tree->mapRegion + curOff);
		cur->parent = tree->sblk->freeList;
		tree->sblk->freeList = OFF_TO_NODE(tree, curOff);
		curOff += tree->sblk->nodeLen;
	}
	return(0);
}



static void checkTreeRemap(tree)
	avltree	*tree;
{
	off_t	oldLen,
		newLen;

	if (tree->sblk->fileLen > tree->mapLen)
	{
		oldLen = tree->mapLen;
		newLen = tree->sblk->fileLen;
		munmap(tree->mapRegion, oldLen);
		tree->mapRegion = mmap(NULL, newLen, PROT_READ|PROT_WRITE,
			MAP_SHARED, tree->fd, (off_t)0);
		tree->sblk = (avl_sbk *)tree->mapRegion;
		tree->mapLen = newLen;
	}
}
		


static avl_nod *getFreeNode(tree)
	avltree	*tree;
{
	int	freeNode = 0;
	avl_nod	*cur;


	checkTreeRemap(tree);
	if (tree->sblk->freeList == 0)
	{
		if (extendTree(tree) < 0)
			return(NULL);
	}
	freeNode = tree->sblk->freeList;
	cur = (avl_nod*)(tree->mapRegion + NODE_TO_OFF(tree,freeNode));
	tree->sblk->freeList = cur->parent;
	cur->left = cur->right = cur->parent = cur->height = cur->dup = 0;
	cur->key = (char *)((char *)cur)+sizeof(avl_nod);
	cur->nodeNum = freeNode;
	return(cur);
}



static void dropNode(tree,cur)
        avltree	*tree;
        avl_nod	*cur;
{
        cur->parent = tree->sblk->freeList;
        tree->sblk->freeList = cur->nodeNum;
}


avl_nod *avlGetNode(tree, num)
	avltree	*tree;
	int	num;
{
	avl_nod	*cur;

	if (num == 0)
		return(NULL);
	checkTreeRemap(tree);
	cur = (avl_nod *)(tree->mapRegion + NODE_TO_OFF(tree, num));
	cur->key = (char *)((char *)cur)+sizeof(avl_nod);
	return(cur);
}




void avlPrintElement(data,type)
	char	*data;
	int	type;
{
	switch(type)
	{
		case IDX_CHAR:
		case IDX_BYTE:
			printf("char '%s'",data);
			break;

		case IDX_INT:
			printf("int '%d'",(int)*(int*)data);
			break;

		case IDX_UINT:
			printf("uint '%u'",(u_int)*(u_int*)data);
			break;

		case IDX_REAL:
			printf("real '%f'",(double)*(double*)data);
			break;

		default:
			printf("Unknown Type!!!");
			break;
	}
}


static void copyValue(src,dst,tree)
	char	*src,
		*dst;
	avltree	*tree;
{
	switch(tree->sblk->keyType)
	{
		case IDX_INT:
		case IDX_UINT:
			bcopy4(src,dst);
			break;
		case IDX_REAL:
			bcopy8(src,dst);
			break;
		case IDX_CHAR:
			strncpy(dst,src,tree->sblk->keyLen-1);
			*(dst+tree->sblk->keyLen-1)=0;
			break;
		default:
			bcopy(src, dst, tree->sblk->keyLen);
	}
}




static void showIndent(d)
	int	d;
{
	int	i;

	for(i = 0; i < d; i++)
	{
		printf("   ");
	}
}



static int getNodeHeight(node)
	avl_nod	*node;
{
	return( (node)? node->height : -1);
}


#define setNodeHeight(tree, node)			\
{							\
	int	_leftH,					\
		_rightH;				\
	avl_nod	*_lNode,				\
		*_rNode;				\
							\
	if (node)					\
	{						\
		_lNode = avlGetNode(tree,node->left);	\
		_leftH = getNodeHeight(_lNode);		\
		_rNode = avlGetNode(tree,node->right);	\
		_rightH = getNodeHeight(_rNode);	\
		if (_leftH > _rightH)			\
			node->height = 1 + _leftH;	\
		else					\
			node->height = 1 + _rightH;	\
	}						\
}


static void rotateRight(tree, node)
	avltree	*tree;
	avl_nod	*node;
{
	avl_nod	*parent,
		*left,
		*tmp;

#ifdef AVL_DEBUG
	printf("Right rotate @ ");
	avlPrintElement(node->key,tree->sblk->keyType);
	printf("\n");
#endif

	parent = avlGetNode(tree,node->parent);
	left = avlGetNode(tree, node->left);
	node->left = left->right;
	tmp = avlGetNode(tree,node->left);
	if (tmp)
		tmp->parent = node->nodeNum;
	left->right = node->nodeNum;
	if (parent)
	{
		if (parent->left == node->nodeNum)
			parent->left = left->nodeNum;
		else
			parent->right = left->nodeNum;
	}
	else
	{
		tree->sblk->root = left->nodeNum;
	}
	left->parent = node->parent;
	node->parent = left->nodeNum;
	setNodeHeight(tree,left);
	setNodeHeight(tree,node);
}



static void rotateLeft(tree, node)
	avltree	*tree;
	avl_nod	*node;
{
	avl_nod	*parent,
		*right,
		*tmp;

#ifdef AVL_DEBUG
	printf("Left rotate @ ");
	avlPrintElement(node->key,tree->sblk->keyType);
	printf("\n");
#endif
	parent = avlGetNode(tree,node->parent);
	right = avlGetNode(tree, node->right);
	node->right = right->left;
	tmp = avlGetNode(tree,node->right);
	if (tmp)
		tmp->parent = node->nodeNum;
	right->left = node->nodeNum;
	if (parent)
	{
		if (parent->right == node->nodeNum)
			parent->right = right->nodeNum;
		else
			parent->left = right->nodeNum;
	}
	else
	{
		tree->sblk->root = right->nodeNum;
	}
	right->parent = node->parent;
	node->parent = right->nodeNum;
	setNodeHeight(tree,right);
	setNodeHeight(tree,node);
}



static void doubleRight(tree, node)
	avltree	*tree;
	avl_nod	*node;
{
	avl_nod	*tmp;

	tmp = avlGetNode(tree, node->left);
	rotateLeft(tree,tmp);
	rotateRight(tree,node);
}


static void doubleLeft(tree, node)
	avltree	*tree;
	avl_nod	*node;
{
	avl_nod	*tmp;

	tmp = avlGetNode(tree,node->right);
	rotateRight(tree,tmp);
	rotateLeft(tree,node);
}

static void balanceTree(tree, node)
	avltree	*tree;
	avl_nod	*node;
{
	int	leftHeight,
		rightHeight;
	avl_nod	*left,
		*right,
		*child;

	left = avlGetNode(tree, node->left);
	right = avlGetNode(tree, node->right);
	leftHeight = getNodeHeight(left);
	rightHeight = getNodeHeight(right);

	if (leftHeight > rightHeight + 1)
	{
		child = avlGetNode(tree, node->left);
		left = avlGetNode(tree,child->left);
		right = avlGetNode(tree,child->right);
		leftHeight = getNodeHeight(left);
		rightHeight = getNodeHeight(right);

		if (leftHeight >= rightHeight)
		{
			rotateRight(tree,node);
		}
		else
		{
			doubleRight(tree,node);
		}
	}
	else if (rightHeight > leftHeight + 1)
	{
		child = avlGetNode(tree, node->right);
		left = avlGetNode(tree,child->left);
		right = avlGetNode(tree,child->right);
		leftHeight = getNodeHeight(left);
		rightHeight = getNodeHeight(right);

		if (rightHeight >= leftHeight)
			rotateLeft(tree,node);
		else
			doubleLeft(tree,node);
	}
}


/*************************************************************************
**************************************************************************
**                                                                      **
**                       TYPE HANDLING ROUTINES                         **
**                                                                      **
**************************************************************************
*************************************************************************/


static int intCompare(v1,v2)
	char	*v1,
		*v2;
{
	int	int1,
		int2;

	bcopy4(v1,&int1);
	bcopy4(v2,&int2);
	if (int1 > int2)
		return(1);
	if (int1 < int2)
		return(-1);
	return(0);
}


static int uintCompare(v1,v2)
	char	*v1,
		*v2;
{
	u_int	int1,
		int2;

	bcopy4(v1,&int1);
	bcopy4(v2,&int2);
	if (int1 > int2)
		return(1);
	if (int1 < int2)
		return(-1);
	return(0);
}


static int realCompare(v1,v2)
	char	*v1,
		*v2;
{
	double	r1,
		r2;

	bcopy8(v1,&r1);
	bcopy8(v2,&r2);
	if (r1 > r2)
		return(1);
	if (r1 < r2)
		return(-1);
	return(0);
}



static int charCompare(v1,v2)
	char	*v1,
		*v2;
{
	char	*cp1,
		*cp2;

	cp1 = v1;
	cp2 = v2;
	while (*cp1 == *cp2)
	{
		if (*cp1 == 0)
		{
			return(0);
		}
		cp1++;
		cp2++;
	}
	if ((unsigned char )*cp1 > (unsigned char)*cp2)
		return(1);
	return(-1);
}


static int byteCompare(v1,v2,len)
	char	*v1,
		*v2;
	int	len;
{
	char	*cp1,
		*cp2;

	cp1 = v1;
	cp2 = v2;
	while (*cp1 == *cp2 && len)
	{
		cp1++;
		cp2++;
		len--;
	}
	if (len == 0)
		return(0);
	if ( (unsigned char) *cp1 > (unsigned char)*cp2)
		return(1);
	return(-1);
}





static int compareValues(v1,v2,tree)
	char	*v1,
		*v2;
	avltree	*tree;
{
	switch(tree->sblk->keyType)
	{
		case IDX_INT:
			return(intCompare(v1,v2));
		case IDX_UINT:
			return(uintCompare(v1,v2));
		case IDX_REAL:
			return(realCompare(v1,v2));
		case IDX_CHAR:
			return(charCompare(v1,v2));
		default:
			return(byteCompare(v1,v2,tree->sblk->keyLen));
	}
}


static void swapNodes(tree, src, dst)
	avltree	*tree;
	avl_nod	*src,
		*dst;
{
	int	tmpLeft,
		tmpRight,
		tmpParent,
		tmpHeight;
	avl_nod	*parent,
		*tmp;

	/*
	** Re-link the nodes
	*/
	tmpLeft = dst->left;
	tmpRight = dst->right;
	tmpParent = dst->parent;
	tmpHeight = dst->height;

	dst->left = src->left;
	dst->right = src->right;
	dst->parent = src->parent;
	dst->height = src->height;

	src->left = tmpLeft;
	src->right = tmpRight;
	src->parent = tmpParent;
	src->height = tmpHeight;

	/*
	** Check for wierd links left over from swapping neighbours
	*/
	if (dst->left == dst->nodeNum)
		dst->left = src->nodeNum;
	if (dst->right == dst->nodeNum)
		dst->right = src->nodeNum;
	if (dst->parent == dst->nodeNum)
		dst->parent = src->nodeNum;
	if (src->left == src->nodeNum)
		src->left = dst->nodeNum;
	if (src->right == src->nodeNum)
		src->right = dst->nodeNum;
	if (src->parent == src->nodeNum)
		src->parent = dst->nodeNum;
	


	/*
	** Relink the parents
	*/
	if (src->parent != dst->nodeNum)
	{
		parent = avlGetNode(tree, src->parent);
		if (parent)
		{
			if (parent->left == dst->nodeNum)
				parent->left = src->nodeNum;
			else
				parent->right = src->nodeNum;
		}
		else
		{
			tree->sblk->root = src->nodeNum;
		}
	}
	if (dst->parent != src->nodeNum)
	{
		parent = avlGetNode(tree,dst->parent);
		if (parent)
		{
			if (parent->left == src->nodeNum)
				parent->left = dst->nodeNum;
			else
				parent->right = dst->nodeNum;
		}
		else
		{
			tree->sblk->root = dst->nodeNum;
		}
	}

	/*
	** Relink the kids
	*/

	if (src->left != dst->nodeNum)
	{
		tmp = avlGetNode(tree,src->left);
		if (tmp)
			tmp->parent = src->nodeNum;
	}
	if (src->right != dst->nodeNum)
	{
		tmp = avlGetNode(tree,src->right);
		if (tmp)
			tmp->parent = src->nodeNum;
	}
	if (dst->left != dst->nodeNum)
	{
		tmp = avlGetNode(tree,dst->left);
		if (tmp)
			tmp->parent = dst->nodeNum;
	}
	if (dst->right != dst->nodeNum)
	{
		tmp = avlGetNode(tree,dst->right);
		if (tmp)
			tmp->parent = dst->nodeNum;
	}
}


/*************************************************************************
**************************************************************************
**                                                                      **
**                        INTERFACE ROUTINES                            **
**                                                                      **
**************************************************************************
*************************************************************************/


int avlCreate(path,mode,keyLen,keyType,flags)
	char	*path;
	int	mode,
		keyLen,
		keyType,