avl_tree.c

uClinux下用的数据库

		flags;
{
	int	fd;
	avl_sbk	sblk;
	char	blank[1];

	/*
	** Create the actual file
	*/
	fd = open(path,O_RDWR | O_CREAT, mode);
	if (fd < 0)
	{
		return(-1);
	}

	/*
	** Create the base contents
	*/
	bzero(&sblk, sizeof(avl_sbk));
	sblk.magic = AVL_MAGIC;
	sblk.keyType = keyType;
	if (keyType == IDX_CHAR)
		keyLen++;
	sblk.keyLen = keyLen;
	sblk.flags = flags;
	sblk.nodeLen = DISK_NODE_SIZE(keyLen) + (8 -
                (DISK_NODE_SIZE(keyLen) % 8));

	if (write(fd,&sblk,sizeof(sblk)) < sizeof(sblk))
	{
		close(fd);
		unlink(path);
		return(-1);
	}
	if (sizeof(sblk) < SBLK_SIZE)
	{
		*blank = 0;
		lseek(fd,SBLK_SIZE-1,SEEK_SET);
		write(fd,blank,1);
	}
	close(fd);
	return(0);
}



avltree *avlMemCreate(keyLen,keyType,flags)
	int	keyLen,
		keyType,
		flags;
{
	avltree	*new;
	int	nodeLen;


	/*
	** Create the base contents
	*/
	new = (avltree *)malloc(sizeof(avltree));
	bzero(new, sizeof(avltree));
	nodeLen = DISK_NODE_SIZE(keyLen) + (8 - (DISK_NODE_SIZE(keyLen) % 8));
	new->memLen = SBLK_SIZE;
	new->memTree = (char *)malloc(new->memLen);
	bzero(new->memTree, new->memLen);

	new->sblk = (avl_sbk *)new->memTree;
	new->sblk->magic = AVL_MAGIC;
	new->sblk->keyType = keyType;
	if (keyType == IDX_CHAR)
		keyLen++;
	new->sblk->keyLen = keyLen;
	new->sblk->flags = flags;
	new->sblk->nodeLen = DISK_NODE_SIZE(keyLen) + (8 -
                (DISK_NODE_SIZE(keyLen) % 8));

	new->mapLen = new->memLen;
	new->mapRegion = new->memTree;
	return(new);
}


avltree *avlOpen(path)
	char	*path;
{
	int	fd;
	avltree	*new;
	struct	stat sbuf;


	fd = open(path,O_RDWR, 0);
	if (fd < 0)
	{
		return(NULL);
	}

	if (fstat(fd, &sbuf) < 0)
	{
		return(NULL);
	}
	new = (avltree *)malloc(sizeof(avltree));
	bzero(new,sizeof(avltree));
	new->fd = fd;
	new->mapLen = sbuf.st_size;
	new->mapRegion = mmap(NULL, new->mapLen, PROT_READ|PROT_WRITE,
		MAP_SHARED, new->fd, (off_t)0);
	if (new->mapRegion == (caddr_t)-1)
	{
		close(fd);
		free(new);
		return(NULL);
	}
	new->sblk = (avl_sbk *)new->mapRegion;
	new->sblk->fileLen = new->mapLen;
	return(new);
}


void avlClose(tree)
	avltree	*tree;
{
	if (tree->memTree == NULL)
	{
		munmap(tree->mapRegion, tree->mapLen);
		close(tree->fd);
	}
	else
	{
		free(tree->memTree);
		tree->memTree = NULL;
	}
	free(tree);
}



void avlSync(tree)
	avltree	*tree;
{
	if (tree->mapLen)
		MSYNC(tree->mapRegion, tree->mapLen, 0);
}



avl_nod *avlLookup(tree, key, flags)
	avltree	*tree;
	char	*key;
	int	flags;
{
	REG 	int	res;
	REG	avl_nod	*cur;


#ifdef AVL_DEBUG
	printf("AVL Lookup of ");
	avlPrintElement(key,tree->sblk->keyType);
	printf("\n");
#endif

	tree->curNode = 0;
	cur = avlGetNode(tree,tree->sblk->root);
	while(cur)
	{
		tree->curNode = cur->nodeNum;
		res = compareValues(key, cur->key, tree);
#ifdef AVL_DEBUG
		printf("\tCompare node %d ",cur->nodeNum);
		avlPrintElement(cur->key,tree->sblk->keyType);
		printf(".  Result = %d\n",res);
#endif
		if (res > 0)
		{
			if (cur->right == 0)
			{
				if (flags & IDX_EXACT)
					return(NULL);
				else
					return(cur);
			}
			cur = avlGetNode(tree,cur->right);
			continue;
		}
		if (res < 0)
		{
			if (cur->left == 0)
			{
				if (flags & IDX_EXACT)
					return(NULL);
				else
					return(cur);
			}
			cur = avlGetNode(tree,cur->left);
			continue;
		}
		return(cur);
	}
	return(NULL);
}



void avlSetCursor(tree, cursor)
	avltree	*tree;
	avl_cur	*cursor;
{
	cursor->curNode = tree->curNode;
	cursor->curDup = 0;
}



avl_nod *avlGetFirst(tree)
	avltree	*tree;
{
	avl_nod	*cur;

	cur = avlGetNode(tree,tree->sblk->root);
	tree->curNode = 0;
	if (!cur)
		return(NULL);
	while(cur->left)
	{
		cur = avlGetNode(tree,cur->left);
	}
	tree->curNode = cur->nodeNum;
	return(cur);
}


avl_nod *avlGetLast(tree)
	avltree	*tree;
{
	avl_nod	*cur;

	cur = avlGetNode(tree,tree->sblk->root);
	tree->curNode = 0;
	if (!cur)
		return(NULL);
	while(cur->right)
	{
		cur = avlGetNode(tree,cur->right);
	}
	tree->curNode = cur->nodeNum;
	return(cur);
}



avl_nod *avlGetNext(tree,cursor)
	avltree	*tree;
	avl_cur	*cursor;
{
	avl_nod	*cur;
	int	prevNode;

	/*
	** Are we somewhere down a dup chain?
	*/
	if (cursor->curDup != 0)
	{
		cur = avlGetNode(tree,cursor->curDup);
		if (cur->dup)
		{
			cur = avlGetNode(tree,cur->dup);
			cursor->curDup = cur->nodeNum;
			return(cur);
		}
	}
	cur = avlGetNode(tree,cursor->curNode);
	if (cur->dup != 0 && cursor->curDup == 0)
	{
		cursor->curDup = cur->dup;
		cur = avlGetNode(tree,cur->dup);
		return(cur);
	}


	/*
	** No dups to return so move onto the next node
	*/
	if (cur->right)
	{
		cur = avlGetNode(tree,cur->right);
		while(cur->left)
			cur = avlGetNode(tree,cur->left);
		cursor->curNode = cur->nodeNum;
		cursor->curDup = 0;
		return(cur);
	}

	while (cur->parent)
	{
		prevNode = cur->nodeNum;
		cur = avlGetNode(tree,cur->parent);
		if (cur->left == prevNode)
		{
			cursor->curNode = cur->nodeNum;
			cursor->curDup = 0;
			return(cur);
		}
	}
	cursor->curNode = cursor->curDup = 0;
	return(NULL);
}



avl_nod *avlGetPrev(tree,cursor)
	avltree	*tree;
	avl_cur	*cursor;
{
	avl_nod	*cur;
	int	prevNode;

	/*
	** Are we somewhere down a dup chain?
	*/
	if (cursor->curDup != 0)
	{
		cur = avlGetNode(tree,cursor->curDup);
		if (cur->dup)
		{
			cur = avlGetNode(tree,cur->dup);
			cursor->curDup = cur->nodeNum;
			return(cur);
		}
	}
	cur = avlGetNode(tree,cursor->curNode);
	if (cur->dup != 0 && cursor->curDup == 0)
	{
		cursor->curDup = cur->dup;
		cur = avlGetNode(tree,cur->dup);
		return(cur);
	}

	cur = avlGetNode(tree,cursor->curNode);
	if (cur->left)
	{
		cur = avlGetNode(tree,cur->left);
		while(cur->right)
			cur = avlGetNode(tree,cur->right);
		cursor->curNode = cur->nodeNum;
		cursor->curDup = 0;
		return(cur);
	}

	while (cur->parent)
	{
		prevNode = cur->nodeNum;
		cur = avlGetNode(tree,cur->parent);
		if (cur->right == prevNode)
		{
			cursor->curNode = cur->nodeNum;
			cursor->curDup = 0;
			return(cur);
		}
	}
	cursor->curNode = 0;
	cursor->curDup = 0;
	return(NULL);
}


int avlInsert(tree, key, data)
	avltree	*tree;
	char	*key;
	off_t	data;
{
	avl_nod	*cur,
		*new;
	int	res,
		oldHeight;

#ifdef AVL_DEBUG
	printf("Inserting value ");
	avlPrintElement(key,tree->sblk->keyType);
	printf("\n\n");
#endif

	/*
	** Find the insertion point
	*/
	new = getFreeNode(tree);
	if (new == NULL)
	{
		return(IDX_UNKNOWN);
	}
	cur = avlLookup(tree, key, IDX_CLOSEST);
	if (!cur)
	{
		/*
		** Tree must be empty
		*/
		new->left = new->right = new->parent = new->height = 0;
		copyValue(key, new->key, tree);
		new->data = data;
		tree->sblk->root = new->nodeNum;
		return(IDX_OK);
	}

	/*
	** Add the node
	*/
	res = compareValues(key,cur->key,tree);

#ifdef AVL_DEBUG
	switch (res)
	{
		case 0:
			printf("Duplicate value!\n");
			break;
		case 1:
			printf("Inserting to the right\n");
			break;
		case -1:
			printf("Inserting to the left\n");
			break;
	}
#endif
	if (res == 0)
	{
		/*
		** Duplicate Value
		*/
		new->dup = cur->dup;
		cur->dup = new->nodeNum;
		new->height = -1;
		new->data = data;
		copyValue(key, new->key, tree);
		tree->sblk->numEntries++;
		return(IDX_OK);
	}

	/*
	** It's not a dup
	*/
	if (res < 0)
		cur->left = new->nodeNum;
	else
		cur->right = new->nodeNum;
	new->left = new->right = new->height = 0;
	copyValue(key, new->key, tree);
	new->data = data;
	new->parent = cur->nodeNum;
	tree->sblk->numEntries++;
	tree->sblk->numKeys++;

	/*
	** Update height values as required if this is a new layer
	** (i.e. this is the first node placed under our parent)
	*/
	if (cur->left == 0 || cur->right == 0)
	{
		while(cur)
		{
			oldHeight = cur->height;
			setNodeHeight(tree,cur);
			if (cur->height == oldHeight)
				break;
			balanceTree(tree,cur);
			cur = avlGetNode(tree,cur->parent);
		}
	}
	return(IDX_OK);
}




int avlDelete(tree, key, data)
	avltree	*tree;
	char	*key;
	off_t	data;
{
	avl_nod	*cur,
		*parent = NULL,
		*next = NULL,
		*prev,
		*tmp;
	avl_cur	cursor;
	int	done = 0,
		oldHeight;


	/*
	** Find the node that matches both the key and the data
	*/
	cur = avlLookup(tree,key,IDX_EXACT);
	if (!cur)
		return(IDX_NOT_FOUND);
	avlSetCursor(tree,&cursor);

	if (cur->dup)
	{
		if (cur->data == data)
		{
			tmp = avlGetNode(tree,cur->dup);
			cur->dup = tmp->dup;
			cur->data = tmp->data;
			dropNode(tree,tmp);
			tree->sblk->numEntries--;
			return(IDX_OK);
		}
		prev = cur;
		cur = avlGetNode(tree,cur->dup);
		while(cur)
		{
			if (cur->data == data)
			{
				prev->dup = cur->dup;
				tree->sblk->numEntries--;
				dropNode(tree,cur);
				return(IDX_OK);
			}
			prev = cur;
			cur = avlGetNode(tree,cur->dup);
		}
		return(IDX_NOT_FOUND);
	}

	/*
	** OK, so I'm a whimp!  Let's take the ultra easy option on
	** this.  What we want is for this node to be a leaf node with
	** no kids.  Lets just keep swapping it with it's next greater
	** or lesser node until it becomes a leaf.  We want to ensure
	** that the swap direction is down the tree so check our kids.
	*/
	if (cur->right)
	{
		while(cur->left || cur->right)
		{
			next = avlGetNext(tree,&cursor);
			if (!next)
				break;
			swapNodes(tree, cur, next);
			avlSetCursor(tree,&cursor);
		}
		if (!next)
		{
			/*
			** Hmmm, can't get away from the child link.
			** We know that there's only 1 child though so
			** we can just collapse this branch
			*/
			next = avlGetNode(tree,cur->left);
			next->parent = cur->parent;
			parent = avlGetNode(tree,cur->parent);
			if (parent->left == cur->nodeNum)
				parent->left = next->nodeNum;
			else
				parent->right = next->nodeNum;
			dropNode(tree,cur);
			tree->sblk->numEntries--;
			tree->sblk->numKeys--;
			done = 1;
		}
	}
	else if (cur->left)
	{
		while(cur->left || cur->right)
		{
			next = avlGetPrev(tree,&cursor);
			if (!next)
				break;
			swapNodes(tree, cur, next);
			avlSetCursor(tree,&cursor);
		}
		if (!next)
		{
			/*
			** As above
			*/
			next = avlGetNode(tree,cur->right);
			next->parent = cur->parent;
			parent = avlGetNode(tree,cur->parent);
			if (parent->left == cur->nodeNum)
				parent->left = next->nodeNum;
			else
				parent->right = next->nodeNum;
			dropNode(tree,cur);
			tree->sblk->numEntries--;
			tree->sblk->numKeys--;
			done = 1;
		}
	}

	/*
	** By this time it must be a leaf node.
	*/
	if (!done)
	{
		parent = avlGetNode(tree,cur->parent);
		if (!parent)
		{
			/*
			** It's the last node in the tree
			*/
			dropNode(tree,cur);
			tree->sblk->root = 0;
			tree->sblk->numEntries = tree->sblk->numKeys = 0;
			return(IDX_OK);
		}
		if (parent->left == cur->nodeNum)
		{
			parent->left = 0;
			if (parent->right == 0)
			{
				parent->height = 0;
				parent = avlGetNode(tree, parent->parent);
			}
			dropNode(tree,cur);
			tree->sblk->numEntries--;
			tree->sblk->numKeys--;
		}
		else if (parent->right == cur->nodeNum)
		{
			parent->right = 0;
			if (parent->left == 0)
			{
				parent->height = 0;
				parent = avlGetNode(tree, parent->parent);
			}
			dropNode(tree,cur);
			tree->sblk->numEntries--;
			tree->sblk->numKeys--;
		}
	}

	/*
	** Rebalance as required
	*/
	while(parent)
	{
		oldHeight = parent->height;
		setNodeHeight(tree,parent);
		if (parent->height == oldHeight)
			break;
		balanceTree(tree,parent);
		parent = avlGetNode(tree,parent->parent);
	}
	return(IDX_OK);
}



/**************************************************************************
** Debugging Code
*/

static void printNode(tree, cur, depth, vFlag)
	avltree	*tree;
	avl_nod	*cur;
	int	depth,
		vFlag;
{
	if (vFlag)
	{
		showIndent(depth);
		printf("N=%d, P=%d, L=%d, R=%d H=%d D=%d\n",cur->nodeNum, 
			cur->parent, cur->left, cur->right, cur->height,
			cur->dup);
		showIndent(depth);
	}
	avlPrintElement(cur->key, tree->sblk->keyType);
	printf("data = %d\n", (int)cur->data);
}



static void dumpSubTree(tree, node, depth, vFlag)
	avltree	*tree;
	int	node,
		depth,
		vFlag;
{
	avl_nod	*cur;

	if (node == 0)
		return;

	cur = avlGetNode(tree, node);
	dumpSubTree(tree, cur->left, depth+1, vFlag);
	printNode(tree, cur, depth, vFlag);
	dumpSubTree(tree, cur->right, depth+1, vFlag);
}



void avlDumpTree(tree, verbose)
	avltree	*tree;
	int	verbose;
{
	dumpSubTree(tree,tree->sblk->root, 0,verbose);
}



int avlTestTree(tree)
	avltree	*tree;
{
	avl_nod	*cur,
		*prev = NULL;
	avl_cur	cursor;
	int	count,
		prev1 = 0,
		prev2 = 0,
		prev3 = 0,
		prev4 = 0;

	cur = avlGetFirst(tree);
	if (!cur)
		return(0);
	count = 1;
	avlSetCursor(tree,&cursor);
	prev = cur;
	cur = avlGetNext(tree,&cursor);
	while(cur)
	{
		if (cur->nodeNum == prev1 || cur->nodeNum == prev2 ||
			cur->nodeNum == prev3 || cur->nodeNum == prev4)
		{
			abort();
		}
		count++;
		if (compareValues(prev->key, cur->key, tree) > 0)
		{
			return(-1);
		}
		prev = cur;
		prev4 = prev3;
		prev3 = prev2;
		prev2 = prev1;
		prev1 = cur->nodeNum;
		cur = avlGetNext(tree,&cursor);
	}
	return(count);
}