🚀 go-pugleaf

Here is the updated implementation of the in-memory B-tree that has been
used as sample code for this thread.  Please see the related posting
identified as <28982@athertn.Atherton.COM>.
----------
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
#	btpriv.h
#	btree.h
#	bt_last.c
#	bt_next.c
#	bt_prev.c
#	btdelete.c
#	btdestroy.c
#	btdump.c
#	btfirst.c
#	btinsert.c
#	btmalloc.c
#	btnew.c
#	btsearch.c
#	bttraverse.c
#	btutil.c
#	test.c
# This archive created: Fri Aug 17 20:48:43 1990
export PATH; PATH=/bin:/usr/bin:$PATH
if test -f 'btpriv.h'
then
	echo shar: "will not over-write existing file 'btpriv.h'"
else
cat << \SHAR_EOF > 'btpriv.h'
/* The following structure describes a B-tree node. */

struct btnode {
	int		nkeys;		/* Number of keys stored here */
	int		currKey;	/* Last key found */
	struct btnode	*parent;	/* Parent of this node */
	char		**keys;		/* array[order-1] of keys */
	struct btnode	**children;	/* array[order] of children */
};

/* The following structure describes a B-tree. */

struct btree {
	int		order;		/* Max children permitted */
	int		(*comp)();	/* Comparison function for keys */
	struct btnode	*root;		/* Root of tree */
	int		capacity;	/* Max keys that will fit */
	int		contains;	/* Key currently stored */
	struct btnode	*currNode;	/* Node accessed */
	int		nextOk;		/* Indicates last search successful */
};

typedef struct btree *BTREE;
typedef struct btnode BTNODE;

#ifndef DEBUG
#define bt_malloc malloc
#define bt_free free
#else
extern char *bt_malloc();
extern char *bt_free();
#endif

extern bt_malloc_verify();

#ifdef __BTUTIL_C__
extern int bt_searchNode();
extern int bt_rotateRight();
extern int bt_rotateLeft();
#endif

SHAR_EOF
fi
if test -f 'btree.h'
then
	echo shar: "will not over-write existing file 'btree.h'"
else
cat << \SHAR_EOF > 'btree.h'
/* Header file for in-memory B-tree implementation */

typedef char *BTREE;

extern	void	bt_dump();
extern	char	*bt_search();
extern	BTREE	bt_new();
extern	void	bt_destroy();
extern	int	bt_insert();
extern	void	bt_traverse();
extern	char	*bt_delete();
extern	char	*bt_first();
extern	char	*bt_next();
extern	char	*bt_last();
extern	char	*bt_prev();
SHAR_EOF
fi
if test -f 'bt_last.c'
then
	echo shar: "will not over-write existing file 'bt_last.c'"
else
cat << \SHAR_EOF > 'bt_last.c'
/********************************************************************
 *
 * bt_last.c -- This file contains functions needed to find the
 *              key that is highest in the lexical order of keys
 *              stored in an in-memory B-tree.
 ********************************************************************/

#include <stdio.h>
#include "btpriv.h"

/********************************************************************
 *
 * bt_last -- This function returns the key that appears last in
 *            the lexical order of the items stored in the tree.
 *            NULL is returned if the tree is empty.
 *
 *******************************************************************/

char *bt_last(tree)
BTREE	tree;
{
	BTNODE	*node;

	if (tree == NULL) return NULL;
	node = tree->root;
	if (node->nkeys == 0) return NULL;
	while (node->children != NULL)
	{
		node->currKey = node->nkeys;
		node = node->children[node->nkeys];
	}
	node->currKey = node->nkeys - 1;
	tree->currNode = node;
	tree->nextOk = 1;
	return node->keys[node->nkeys - 1];
}
SHAR_EOF
fi
if test -f 'bt_next.c'
then
	echo shar: "will not over-write existing file 'bt_next.c'"
else
cat << \SHAR_EOF > 'bt_next.c'
/********************************************************************
 *
 * bt_next.c -- This file contains functions needed to scan an in-memory
 *              B-tree in ascending order.
 *
 ********************************************************************/

#include <stdio.h>
#include "btpriv.h"

/********************************************************************
 *
 * bt_next -- This function returns the key that appears next in
 *            the lexical order of the items stored in the tree,
 *            after the last bt_search, bt_next, bt_prev, bt_last,
 *            or bt_first.  NULL is returned if the tree is empty, an
 *            insertion or deletion invalidated the state of the
 *            tree, or the last item in the tree was already visited.
 *
 *******************************************************************/

char *bt_next(tree)
BTREE	tree;
{
	BTNODE	*node;
	int	key;

	/* Return if error, or insertion/deletion invalidated state */
	if ((tree == NULL) || (tree->currNode == NULL)) return NULL;

	/* Set up temporaries */
	node = tree->currNode;
	key = node->currKey;

	/* Return if we've overrun the tree */
	if (key >= node->nkeys) return NULL;

	/*
	 * Bump current key in current node, compensating for unsuccessful
	 * search
	 */
	if (tree->nextOk) key++;
	tree->nextOk = 1;

	/* If node has children, return leftmost key of next child */
	if (node->children != NULL)
	{
		node->currKey = key;
		node = node->children[key];
		while (node->children != NULL)
		{
			node->currKey = 0;
			node = node->children[0];
		}
		node->currKey = 0;
		tree->currNode = node;
		return node->keys[0];
	}

	/* Leaf node, return next key */
	if (key < node->nkeys)
	{
		node->currKey = key;
		return node->keys[key];
	}

	/* Already visited rightmost key of leaf, go back to parent */
	while ((node->parent != NULL) && (key >= node->nkeys))
	{
		node = node->parent;
		key = node->currKey;
	}

	/* Return NULL after last key in tree */
	if (key >= node->nkeys)
	{
		tree->currNode = node;
		node->currKey = key;
		return NULL;
	}

	/* Return next key in parent */
	tree->currNode = node;
	return node->keys[key];
}
SHAR_EOF
fi
if test -f 'bt_prev.c'
then
	echo shar: "will not over-write existing file 'bt_prev.c'"
else
cat << \SHAR_EOF > 'bt_prev.c'
/********************************************************************
 *
 * btprev.c -- This file contains functions needed to scan an in-memory
 *             B-tree in descending order.
 *
 ********************************************************************/

#include <stdio.h>
#include "btpriv.h"

/********************************************************************
 *
 * bt_prev -- This function returns the next key that appears
 *            earlier in the lexical order of the items stored in
 *            the tree, after the last bt_search, bt_next, bt_prev, or
 *            bt_last.  NULL is returned if the tree is empty, an
 *            insertion or deletion invalidated the state of the
 *            tree, or the next item in the tree was already visited.
 *
 *******************************************************************/

char *bt_prev(tree)
BTREE	tree;
{
	BTNODE	*node;
	int	key;

	/* Return if error, or insertion/deletion invalidated state */
	if ((tree == NULL) || (tree->currNode == NULL)) return NULL;
	tree->nextOk = 1;

	/* Set up temporaries */
	node = tree->currNode;
	key = node->currKey;

	/* Return if we've overrun the tree */
	if (key < 0) return NULL;

	/*
	 * If node has children, return rightmost key of previous
	 * child
	 */
	if (node->children != NULL)
	{
		node = node->children[key];
		while (node->children != NULL)
		{
			node->currKey = node->nkeys;
			node = node->children[node->nkeys];
		}
		node->currKey = node->nkeys - 1;
		tree->currNode = node;
		return node->keys[node->currKey];
	}

	/* Leaf node, return previous key */
	key--;
	if (key >= 0)
	{
		node->currKey = key;
		return node->keys[key];
	}

	/* Already visited leftmost key of node, go back to parent */
	while ((node->parent != NULL) && (key < 0))
	{
		node = node->parent;
		key = node->currKey - 1;
	}

	/* Return NULL after last key in tree */
	if (key < 0)
	{
		node->currKey = -1;
		tree->currNode = node;
		return NULL;
	}

	/* Return next key in parent */
	node->currKey = key;
	tree->currNode = node;
	return node->keys[key];
}
SHAR_EOF
fi
if test -f 'btdelete.c'
then
	echo shar: "will not over-write existing file 'btdelete.c'"
else
cat << \SHAR_EOF > 'btdelete.c'
/********************************************************************
 *
 * btdelete.c -- This file contains functions needed to delete a key
 *               from an in-memory B-tree.
 *
 ********************************************************************/

#include <stdio.h>
#include "btpriv.h"

/********************************************************************
 *
 * bt_delKey -- This function deletes the specified key from the
 *              specified node.
 *
 ********************************************************************/

static bt_delKey(node,n)
BTNODE	*node;
int	n;
{
	int	i;

	for (i = n; i < node->nkeys - 1; i++)
	{
		node->keys[i] = node->keys[i+1];
	}
	if (node->children != NULL)
	{
		for (i = n; i < node->nkeys; i++)
		{
			node->children[i] = node->children[i+1];
		}
	}
	node->nkeys--;
	return;
}

/********************************************************************
 *
 * bt_weld -- This function is the opposite of burst, above.  It joins
 *            two neighboring children of the given node, and lowers a
 *            key into the result.
 *
 ********************************************************************/

static bt_weld(tree,node,n)
BTREE	tree;
BTNODE	*node;
int	n;
{
	int	i;
	int	j;
	BTNODE	*left;
	BTNODE	*right;

	if (node->children == NULL) return;
	left = node->children[n];
	right = node->children[n+1];
	i = left->nkeys;
	left->keys[i] = node->keys[n];
	for (i++, j = 0; j < right->nkeys; i++, j++)
	{
		left->keys[i] = right->keys[j];
	}
	for (i = n + 1; i <= node->nkeys; i++)
	{
		node->keys[i-1] = node->keys[i];
		node->children[i] = node->children[i+1];
	}
	node->nkeys--;
	if (left->children != NULL)
	{
		for (i = left->nkeys + 1, j = 0; j <= right->nkeys; i++, j++)
		{
			left->children[i] = right->children[j];
			left->children[i]->parent = left;
		}
		bt_free(right->children);
	}
	left->nkeys += right->nkeys + 1;
	bt_free(right->keys);
	bt_free(right);
	tree->capacity -= tree->order - 1;
	return;
}

/********************************************************************
 *
 * bt_delPred -- This function searches a sub-tree, and deletes the
 *               highest key it finds, and returns it to its caller.
 *               If any node along the way  loses its b-tree'ness, the
 *               tree is reorganized after the deletion.
 *
 ********************************************************************/

static char *bt_delPred(tree,node)
BTREE	tree;
BTNODE	*node;
{
	BTNODE	*pnode;
	int	res;
	char	*retval;

	/*
	 * If at a leaf node, delete the highest key, otherwise
	 * call self recursively
	 */
	if (node->children == NULL)
	{
		retval = node->keys[node->nkeys - 1];
		node->nkeys--;
	}
	else
	{
		pnode = node->children[node->nkeys];
		retval = bt_delPred(tree,pnode);

		/* Reorganize tree if node gets too empty */
		if (pnode->nkeys < (tree->order - 1) / 2)
		{
			res = bt_rotateRight(node,node->nkeys - 1,tree->order);
			if (res == 0) bt_weld(tree,node,node->nkeys - 1);
		}
	}
	return retval;
}

/********************************************************************
 *
 * bt_delNode -- This function searches a sub-tree for a key, and
 *               deletes the key.  If the key is found in a leaf node,
 *               it is simple removed and returned to the caller;
 *               otherwise, it is swapped with its predecessor, and
 *               the returned to the caller.  If any node loses its
 *               b-tree'ness, the tree is reorganized.  If the key is
 *               not found, NULL is returned.
 *
 ********************************************************************/

static char *bt_delNode(tree,node,key)
BTREE	tree;
BTNODE	*node;
char	*key;
{
	int	i;
	int	res;
	char	*retval;

	/* Key not found */
	if (node == NULL) return NULL;

	/* Search for key, descend tree until found or find leaf */
	i = bt_searchNode(node,key,tree->comp,&res);
	if (res == 0)
	{
		if (node->children == NULL) return NULL;
		retval = bt_delNode(tree,node->children[i],key);
	}
	else
	{
		/* Return the deleted node to caller */
		retval = node->keys[i];

		if (node->children == NULL)
		{
			/* Delete from leaf */
			bt_delKey(node,i);
		}
		else
		{
			/* Swap with predecessor */
			node->keys[i] = bt_delPred(tree,node->children[i]);
		}
	}

	/* If a child node was reorganized, rebalancing may be necessary */
	if ((node->children != NULL) &&
	    (node->children[i]->nkeys < (tree->order - 1) / 2))
	{
		res = bt_rotateRight(node,i - 1,tree->order);
		if (res == 0) res = bt_rotateLeft(node,i,tree->order);
		if (res == 0)
		{
			if (i >= node->nkeys) i--;
			bt_weld(tree,node,i);
		}
	}
	return retval;
}

/********************************************************************
 *
 * bt_delete -- This function deletes the specified key from a
 *              b-tree and reorganizes it as necessary.  The deleted
 *              key is returned to the caller if it is found, NULL
 *              is returned otherwise.
 *
 ********************************************************************/

char	*bt_delete(ptree,key)
char	*ptree;
char	*key;
{
	BTNODE	*root;
	char	*retval;
	BTREE	tree;

	tree = (BTREE) ptree;

	/* Do no deletion if tree is empty */
	root = tree->root;
	if (root->nkeys == 0) return NULL;

	/* Delete the key */
	retval = bt_delNode(tree,root,key);

	/*
	 * Delete the root if it is empty, yet its children are not.
	 * This happens after a weld on the last key in the root.
	 */
	if ((root->nkeys == 0) && (root->children != NULL))
	{
		tree->root = root->children[0];
		bt_free(root->keys);
		bt_free(root->children);
		bt_free(root);
		tree->capacity -= tree->order - 1;
		tree->root->parent = NULL;
	}
	if (retval != NULL)
	{
		tree->contains--;
		tree->currNode = NULL;
	}
	return retval;
}
SHAR_EOF
fi
if test -f 'btdestroy.c'
then
	echo shar: "will not over-write existing file 'btdestroy.c'"
else
cat << \SHAR_EOF > 'btdestroy.c'
/********************************************************************
 *
 * btdestroy.c -- This function contains functions needed to deallocate
 *                an in-memory B-tree in its entirety.
 *
 ********************************************************************/

#include <stdio.h>
#include "btpriv.h"

/********************************************************************
 *
 * bt_freeNode -- This function frees a node in a b-tree.  It is
 *              provided with a function that frees each key in the
 *              node also.  The free_key function has the following
 *              protocol:
 *
 *			free_key(key)
 *			char *key;
 *
 *              If NULL is passed as the free_key function, the node
 *              is freed, but no action is taken for the keys.
 *
 ********************************************************************/

static void bt_freeNode(node,free_key)
BTNODE	*node;
void	(*free_key)();
{
	int	i;

	if (node->children != NULL)
	{
		for (i = 0; i <= node->nkeys; i++)
		{
			bt_freeNode(node->children[i],free_key);
		}
		bt_free(node->children);
	}
	if (free_key != NULL)
	{
		for (i = 0; i < node->nkeys; i++)
		{
			(*free_key)(node->keys[i]);
		}
	}
	bt_free(node->keys);
	bt_free(node);
	return;
}

/********************************************************************
 *
 * bt_destroy -- This function frees a b-tree structure.  It is also
 *               passed a function that frees the keys contained by the
 *               tree.  The free_key function has the same calling
 *               protocol as the free_key function passed to bt_freeNode
 *               above.
 *
 ********************************************************************/

void bt_destroy(ptree,free_key)
char	*ptree;
void	(*free_key)();
{
	BTREE	tree;

	tree = (BTREE) ptree;
	bt_freeNode(tree->root,free_key);
	bt_free(tree);
	return;
}
SHAR_EOF
fi
if test -f 'btdump.c'
then
	echo shar: "will not over-write existing file 'btdump.c'"
else
cat << \SHAR_EOF > 'btdump.c'
/*********************************************************************
 *
 * btdump.c -- This function contains functions needed to display
 *             the contents of an in-memory B-tree, passing each key
 *             to a callback function.  This file contains non-portable
 *             code that is intended to help debug the B-tree
 *             implementation.
 *
 *********************************************************************/

#include <stdio.h>
#include "btpriv.h"

/*********************************************************************
 *
 * bt_dumpNode -- This function displays the contents of a node and
 *                then recursively displays its children.  Note
 *                that this function assumes that a pointer to a node
 *                is the same size as an integer.
 *
 *********************************************************************/

void bt_dumpNode(node,key_dump)
BTNODE	*node;
void	(*key_dump)();
{
	int	i;

	if (node == NULL)
	{
		printf("ERROR:  null node pointer\n");
		return;
	}
	printf("%08x:  %d keys (keys %08x, children %08x), currKey = %d,\n",
	       (int) node,node->nkeys,node->keys,node->children,node->currKey);
	printf("parent = %08x\n", (int) node->parent);
	printf("--------\n");
	for (i = 0; i < node->nkeys; i++)
	{
		if (node->children != NULL)
		{
			printf("    %08x\n",node->children[i]);
		}
		else
		{
			printf("    %08x\n",0);
		}
		if (key_dump != NULL)
		{
			printf("        ");
			(*key_dump)(node->keys[i]);
		}
	}
	if (node->children != NULL)
	{
		printf("    %08x\n",node->children[i]);
		for (i = 0; i <= node->nkeys; i++)
		{
			bt_dumpNode(node->children[i],key_dump);
		}
	}
	else
	{
		printf("    %08x\n",0);
	}

	fflush(stdout);
	return;
}

/*********************************************************************
 *
 * bt_dump -- This function displays the contents of a B-tree.  The
 *            caller passes in a function that displays the contents
 *            of one of the keys stored in the tree.  The calling
 *            protocol for this function is:
 *
 *                       key_dump(key)
 *                       char *key;
 *
 *            Also, if key_dump is NULL, no action is taken.  This is
 *            useful if the structure of the tree is desired without
 *            including its contents.
 *
 *********************************************************************/

void bt_dump(ptree,key_dump)
char	*ptree;
void	(*key_dump)();
{
	BTREE	tree;

	tree = (BTREE) ptree;
	printf("B-tree dump:\n\n");
	printf("order = %d\n",tree->order);
	printf("capacity = %d\n",tree->capacity);
	printf("contains %d keys\n",tree->contains);
	printf("efficiency is %d per cent\n",
	       (tree->contains*100)/tree->capacity);
	printf("handle at %08x\n",tree);
	printf("root  = %08x\n\n",(int) tree->root);
	printf("currNode  = %08x\n\n",(int) tree->currNode);
	bt_dumpNode(tree->root,key_dump);
	return;
}
SHAR_EOF
fi
if test -f 'btfirst.c'
then
	echo shar: "will not over-write existing file 'btfirst.c'"
else
cat << \SHAR_EOF > 'btfirst.c'
/********************************************************************
 *
 * btfirst.c -- This file contains functions to locate the key
 *              falling first in the lexical order of items stored
 *              in an in-memory B-tree.
 *
 ********************************************************************/

#include <stdio.h>
#include "btpriv.h"

/********************************************************************
 *
 * bt_first -- This function returns the key that appears first in
 *             the lexical order of the items stored in the tree.
 *             NULL is returned if the tree is empty.
 *
 *******************************************************************/

char *bt_first(tree)
BTREE	tree;
{
	BTNODE	*node;

	if (tree == NULL) return NULL;
	node = tree->root;
	if (node->nkeys == 0) return NULL;
	while (node->children != NULL)
	{
		node->currKey = 0;
		node = node->children[0];
	}
	node->currKey = 0;
	tree->currNode = node;
	tree->nextOk = 1;
	return node->keys[0];
}
SHAR_EOF
fi
if test -f 'btinsert.c'
then
	echo shar: "will not over-write existing file 'btinsert.c'"
else
cat << \SHAR_EOF > 'btinsert.c'
/*********************************************************************
 * 
 * btinsert.c -- This file contains functions needed to insert new
 *               items into an in-memory B-tree.
 *
 *********************************************************************/

#include <stdio.h>
#include "btpriv.h"

/*********************************************************************
 *
 * bt_insertKey -- This function inserts a key into a specified node at
 *                 a specified location in its key array.  0 is returned
 *                 if the node is already full, 1 otherwise.
 *
 *********************************************************************/

static int bt_insertKey(node,key,n,order)
BTNODE	*node;
char	*key;
int	n;
int	order;
{
	int	i;

	/* Return FALSE if insertion is not possible */
	if (node->nkeys >= order - 1)
	{
		return 0;
	}

	/* Shift keys to make room, then insert new key */
	for (i = node->nkeys - 1; i >= n; i--)
	{
		node->keys[i+1] = node->keys[i];
	}
	node->keys[n] = key;
	node->nkeys++;
	return 1;
}

/*********************************************************************
 *
 * bt_burst -- Given a node and an index into its key and child arrays,
 *             this function splits the specified child node in half,
 *             elevating the key at the child's split point into this
 *             specified node.  0 is returned if the child array index
 *             is out of range, or the node is full, or malloc fails;
 *             1 is returned otherwise.
 *
 *********************************************************************/

static int bt_burst(tree,node,n)
BTREE	tree;
BTNODE	*node;
int	n;
{
	BTNODE	*new;
	int	i;
	int	m;
	BTNODE	*left;
	int	lkeys;

	/* Test parameters */
	if (((node->nkeys > 0) && (node->nkeys >= tree->order - 1)) ||
	    (n < 0))
	{
		return 0;
	}
	/* Create a new node */
	new = (BTNODE*) bt_malloc(sizeof(BTNODE));
	if (new != NULL)
	{
		new->parent = node;

		/* Allocate new key array */
		new->keys = (char**) bt_malloc(tree->order*sizeof(char*));
		if (new->keys != NULL)
		{
			/* Calculate needed partial results */
			m = tree->order / 2;
			left = node->children[n];
			lkeys = left->nkeys;

			/* Allocate new child array */
			if (left->children != NULL)
			{
				new->children =
				       (BTNODE**) bt_malloc((tree->order + 1) * 
				                            sizeof(BTNODE*));
				if (new->children != NULL)
				{
					for (i = 0; i <= lkeys - m; i++)
					{
						new->children[i] =
						         left->children[m + i];
						new->children[i]->parent = new;
					}
				}
				else
				{
					bt_free(new->keys);
					bt_free(new);
					return 0;
				}
			}
			else
			{
				new->children = NULL;
			}

			/* Split keys */
			for (i = 0; i < lkeys - m; i++)
			{
				new->keys[i] = left->keys[m + i];
			}
			new->nkeys = lkeys - m;
			left->nkeys = m - 1;

			/* Elevate the key where the split was made */
			for (i = node->nkeys; i > n; i--)
			{
				node->keys[i] = node->keys[i-1];
				node->children[i+1] = node->children[i];
			}
			node->children[n+1] = new;
			node->keys[n] = left->keys[m - 1];
			node->nkeys++;
			tree->capacity += tree->order - 1;
			return 1;
		}
		/* Failed to allocate new child array, free node */
		bt_free(new);
	}
	/* Failed to allocate new node, return FALSE */
	return 0;
}

/*********************************************************************
 *
 * bt_rebalance -- This function tries to rebalance the two adjacent
 *                 nodes.  This is needed when an insertion is attempted
 *                 into a node that is already full but its neighbors are
 *                 not, or when a deletion is made and the node is less
 *                 than half-full.
 *
 *********************************************************************/

static bt_rebalance(node,n,order)
BTNODE	*node;
int	n;
int	order;
{
	int	res;

	if (node->children[n]->nkeys < (order-1)/2)
	{
		res = bt_rotateLeft(node,n,order);
	}
	else
	if ((n < node->nkeys) && (node->children[n+1]->nkeys < (order-1)/2))
	{
		res = bt_rotateRight(node,n,order);
	}
	return;
}

/*********************************************************************
 *
 * bt_insertNode -- This function performs a recursive-descent of a b-tree,
 *                  inserting a new key in a leaf node.  If the leaf is
 *                  full, the tree is reorganized to make room.  -1 is
 *                  returned if the insert fails due to a duplicate key.
 *                  0 is returned if the insert fails for some other
 *                  reason.  1 is returned if successful.
 *
 *********************************************************************/

static int bt_insertNode(tree,node,key)
BTREE	tree;
BTNODE	*node;
char	*key;
{
	int	i;
	int	res;

	/* Locate proper place for new key in node */
	i = bt_searchNode(node,key,tree->comp,&res);
	if (res) return -1;

	/* If no children, insert key in this node */
	if (node->children == NULL)
	{
		return bt_insertKey(node,key,i,tree->order);
	}

	/* Try to insert the new key in a child node */
	res = bt_insertNode(tree,node->children[i],key);

	/* Child is full, reorganize */
	if (res == 0)
	{
		/* Try rotating right */
		if ((res == 0) && (i < node->nkeys) &&
		    (node->children[i+1]->nkeys < tree->order - 2))
		{
			res = bt_rotateRight(node,i,tree->order);
		}

		/* Try rotating left */
		if ((res == 0) && (i > 0) &&
		    (node->children[i-1]->nkeys < tree->order - 2))
		{
			res = bt_rotateLeft(node,i - 1,tree->order);
		}

		/* Can't rotate, try bursting */
		if (res == 0) res = bt_burst(tree,node,i);
		if (res > 0)
		{
			res = bt_insertNode(tree,node,key);
			if (res > 0)
			{
				bt_rebalance(node,i,tree->order);
			}
		}
	}
	return res;
}

/*********************************************************************
 *
 * bt_insert -- This function inserts a new key into a b-tree.  -1 is
 *              returned if the insert fails due to a duplicate key.
 *              0 is returned if the insert fails for some other
 *              reason.  1 is returned if successful.
 *
 *********************************************************************/

int bt_insert(ptree,key)
char	*ptree;
char	*key;
{
	int	res;
	BTNODE	*new;
	BTNODE	*node;
	BTREE	tree;

	tree = (BTREE) ptree;

	/* Begin at root */
	node = tree->root;

	/* If root is empty, insert first key */
	if (node->nkeys == 0)
	{
		node->keys[0] = key;
		node->nkeys = 1;
		tree->contains = 1;
		tree->currNode = NULL;
		return 1;
	}

	/* Try inserting new key */
	res = bt_insertNode(tree,node,key);

	/* If 0 return, burst the root, rebalance, and try again */
	if (res == 0)
	{
		new = (BTNODE*) bt_malloc(sizeof(BTNODE));
		if (new != NULL)
		{
			new->children = (BTNODE**) bt_malloc((tree->order + 1) *
			                                  sizeof(BTNODE*));
			if (new->children != NULL)
			{
				new->keys = (char**) bt_malloc((tree->order) *
				                                sizeof(char*));
				if (new->keys != NULL)
				{
					new->nkeys = 0;
					new->children[0] = node;
					node->parent = new;
					tree->root = new;
					tree->capacity += tree->order - 1;
					res = bt_burst(tree,new,0);
					if (res > 0)
					{
						res=bt_insertNode(tree,new,key);
					}
					if (res > 0)
					{
						tree->contains++;
						bt_rebalance(new,0,tree->order);
						tree->currNode = NULL;
					}
					return res;
				}
				bt_free(new->children);
			}
			bt_free(new);
		}
	}
	if (res > 0)
	{
		tree->contains++;
		tree->currNode = NULL;
	}
	return res;
}
SHAR_EOF
fi
if test -f 'btmalloc.c'
then
	echo shar: "will not over-write existing file 'btmalloc.c'"
else
cat << \SHAR_EOF > 'btmalloc.c'
/**************************************************************
 *
 * btmalloc.c -- This file contains functions that augment the
 *               C runtime library memory allocator in order
 *               to aid debugging.
 *
 **************************************************************/

#include <stdio.h>

/* The following structure is used for debugging heap corruptions */

struct heapblk {
	char	*blk;
	int	freeNext;
};

struct heap_struct {
	int		allocSeq;
	int		freeLast;
	struct heapblk	blks[10000];
};

struct heap_struct btheap = {0,-1}; 


/*
 * The following code is used for allocating space on the heap.  When not
 * debugging heap corruptions, a macro aliases bt_malloc with malloc.
 */

char *bt_malloc(size)
unsigned	size;
{
	char	*temp;

	temp = (char*) malloc(size);
	btheap.blks[btheap.allocSeq].blk = temp;
	btheap.blks[btheap.allocSeq].freeNext = -2;
	btheap.allocSeq++;
	return temp;
}

/*
 * The following code is used for freeing memory on the heap.  If not
 * debugging heap corruptions, bt_free is aliased with free.
 */


bt_free(ptr)
char	*ptr;
{
	int	i;

	printf("Freeing heap storage at %x\n",ptr);
	for (i = 0; i < btheap.allocSeq; i++)
	{
		if (ptr == btheap.blks[i].blk)
		{
			if (btheap.blks[i].freeNext == -2)
			{
				btheap.blks[i].freeNext = btheap.freeLast;
				btheap.freeLast = i;
				free(ptr);
				return;
			}
			else
			{
				printf(
				  "ERROR: freeing %x which was already freed\n",
				  ptr);
				printf("Block\n");
				i = btheap.freeLast;
				while (i > 0)
				{
					printf("%x\n",btheap.blks[i].blk);
					i = btheap.blks[i].freeNext;
				}
				fflush(stdout);
				kill(getpid(),5);
			}
		}
	}
	printf("ERROR:  Freeing %x which has not been allocated\n",ptr);
	fflush(stdout);
	kill(getpid(),5);
}

/* The following verifies the integrity of the heap. */

int bt_malloc_verify()
{
	int	retval;
	int	once;
	int	i;

	retval = 1;
	once = 0;

#ifdef DEBUG
	for (i = 0; i < btheap.allocSeq; i++)
	{
		if (btheap.blks[i].freeNext == -2)
		{
			if (!once)
			{
				once = 1;
				printf("The following blocks are allocated:\n");
			}
			printf("%x\n",btheap.blks[i].blk);
		}
	}
	fflush(stdout);
#endif

#ifdef sun
	retval = malloc_verify();
#endif

	return retval;
}
SHAR_EOF
fi
if test -f 'btnew.c'
then
	echo shar: "will not over-write existing file 'btnew.c'"
else
cat << \SHAR_EOF > 'btnew.c'
/***********************************************************************
 *
 * btnew.c -- This file contains functions to create a new in-memory
 *            B-tree.
 *
 ***********************************************************************/

#include <stdio.h>
#include "btpriv.h"

/***********************************************************************
 *
 * bt_new -- Given the number of children each node is allowed to have,
 *           and a pointer to a strcmp-like function that compares two
 *           keys, this function creates an empty b-tree structure.
 *
 ***********************************************************************/

char	*bt_new(order,comp)
int	order;
int	(*comp)();
{
	BTREE	tree;
	int	i;

	/* Validate parameters */
	if ((comp == NULL) || (order < 3)) return (char *) NULL;

	/* Allocate the handle */
	tree = (BTREE) bt_malloc(sizeof(struct btree));
	if (tree != NULL)
	{
		/* Allocate the root */
		tree->root = (BTNODE*) bt_malloc(sizeof(struct btnode));
		if (tree->root != NULL)
		{
			/* Initialize root */
			tree->order = order;
			tree->comp = comp;
			tree->root->nkeys = 0;
			tree->root->children = NULL;

			/* Allocate key array */
			tree->root->keys =
				(char**)bt_malloc((order - 1) * sizeof(char*));
			if (tree->root->keys != NULL)
			{
				/* Initialize keys */
				for (i = 0; i < order - 1; i++)
				{
					tree->root->keys[i] = NULL;
				}
				tree->root->nkeys = 0;
				tree->root->parent = NULL;
				tree->contains = 0;
				tree->capacity = order - 1;
				tree->currNode = NULL;
				return (char *) tree;
			}

			/* Failed to allocate keys, free tree */
			bt_free(tree->root);
		}
		/* Failed to allocate root, free handle */
		bt_free(tree);
	}
	/* Failed to allocate handle, return null (error) */
	return (char *) NULL;
}
SHAR_EOF
fi
if test -f 'btsearch.c'
then
	echo shar: "will not over-write existing file 'btsearch.c'"
else
cat << \SHAR_EOF > 'btsearch.c'
/********************************************************************
 * btsearch -- This file contains functions needed to locate an
 *             item in an in-memory B-tree.
 *
 ********************************************************************/

#include <stdio.h>
#include "btpriv.h"

/********************************************************************
 *
 * bt_searchNode -- This function searches a node for a key.  If the key
 *                  is found, its index in the node's key array is
 *                  returned, along with a flag indicating that the key
 *                  was found.  If the key is not found, the index of the
 *                  next higher key in the key array is returned, along
 *                  with a "not found" indication.
 *
 ********************************************************************/

static int bt_searchNode(node,target,comp,eq)
BTNODE	*node;		/* Node to be searched */
char	*target;	/* Key to search for */
int	(*comp)();	/* strcmp()-like comparison function */
int	*eq;		/* 0 if not found, non-zero otherwise */
{
	int	i;
	int	res;
	int	hi;
	int	lo;

	res = -1;

	/*
	 * Perform linear search of node contains 7 keys or less,
	 * otherwise perform binary search
	 */
	if (node->nkeys <= 7)
	{
		for (i = 0; i < node->nkeys; i++)
		{
			res = (*comp)(node->keys[i],target);
			if (res >= 0) break;
		}
	}
	else
	{
		lo = 0;
		hi = node->nkeys - 1;
		while ((lo <= hi) && (res != 0))
		{
			i = (lo + hi) / 2;
			res = (*comp)(node->keys[i],target);
			if (res < 0) lo = i + 1;
			else if (res > 0) hi = i - 1;
		}
		if (res < 0) i++;
	}
	*eq = (res == 0);	/* Indicate successful search */
	node->currKey = i + *eq - 1;
	return i;
}

/***********************************************************************
 *
 * bt_locate -- This function performs a recursive-descent search of
 *              a sub-tree for a key.  The key is returned if found,
 *              or NULL otherwise.
 *
 ***********************************************************************/

static char *bt_locate(tree,node,target,comp)
BTREE	tree;
BTNODE	*node;
char	*target;
int	(*comp)();
{
	int	res;
	int	i;
	int	eq;

	i = bt_searchNode(node,target,comp,&eq);
	node->currKey = i;
	if (eq)
	{
		tree->currNode = node;
		tree->nextOk = 1;
		return node->keys[i];
	}
	else if (node->children == NULL)
	{
		tree->currNode = node;
		tree->nextOk = 0;
		return NULL;
	}
	else
	{
		return bt_locate(tree,node->children[i],target,comp);
	}
}

/***********************************************************************
 *
 * bt_search -- This function searches a tree for a specified key.  The
 *              key is returned if found, or NULL if not.
 *
 ***********************************************************************/

char *bt_search(tree,target)
BTREE	tree;
char	*target;
{
	if (tree == NULL) return NULL;
	return bt_locate(tree,tree->root,target,tree->comp);
}
SHAR_EOF
fi
if test -f 'bttraverse.c'
then
	echo shar: "will not over-write existing file 'bttraverse.c'"
else
cat << \SHAR_EOF > 'bttraverse.c'
/****************************************************************
 *
 * bttraverse.c -- This file contains functions needed to
 *                 traverse an in-memory B-tree, passing each
 *                 item stored there to a callback function.
 *
 ****************************************************************/

#include <stdio.h>
#include "btpriv.h"

/****************************************************************
 *
 * bt_visit -- This function is used while traversing a b-tree.
 *             It is called once for each node.  It calls some
 *             specified function once for each key in its
 *             key array, and calls itself once for each child
 *             in its child array.
 *
 ****************************************************************/

static void bt_visit(node,fn,parms)
BTNODE	*node;
void	(*fn)();
char	*parms;
{
	int	i;

	if (node == NULL) return;
	for (i = 0; i < node->nkeys; i++)
	{
		if (node->children != NULL)
		{
			bt_visit(node->children[i],fn,parms);
		}
		(*fn)(node->keys[i],parms);
	}
	if (node->children != NULL)
	{
		bt_visit(node->children[i],fn,parms);
	}
	return;
}

/****************************************************************
 *
 * bt_traverse -- This function traverses a b-tree, calling some
 *                specified function once for each key stored in
 *                it.  The specified function has the following
 *                protocol:
 *
 *			fn(key,parms)
 *			char *key;
 *			char *parms;
 *
 *                where key is a pointer to a key stored in the
 *                btree, and parms is the parameter structure
 *                passed by the caller.
 *
 *                The nodes are visited in descending order, if
 *                the comp function passed to bt_new is
 *                strcmp-like.
 *
 ****************************************************************/

void bt_traverse(ptree,fn,parms)
char	*ptree;
void	(*fn)();
char	*parms;
{
	BTREE	tree;

	tree = (BTREE) ptree;
	bt_visit(tree->root,fn,parms);
	return;
}
SHAR_EOF
fi
if test -f 'btutil.c'
then
	echo shar: "will not over-write existing file 'btutil.c'"
else
cat << \SHAR_EOF > 'btutil.c'
/********************************************************************
 *
 * btutil.c -- This function contains utility functions that are
 *             used for many features of an in-memory B-tree
 *             implementation.
 *
 ********************************************************************/

#define __BTUTIL_C__
#include <stdio.h>
#include "btpriv.h"

/********************************************************************
 *
 * bt_searchNode -- This function searches a node for a key.  If the key
 *                  is found, its index in the node's key array is
 *                  returned, along with a flag indicating that the key
 *                  was found.  If the key is not found, the index of the
 *                  next higher key in the key array is returned, along
 *                  with a "not found" indication.
 *
 ********************************************************************/

int bt_searchNode(node,target,comp,eq)
BTNODE	*node;		/* Node to be searched */
char	*target;	/* Key to search for */
int	(*comp)();	/* strcmp()-like comparison function */
int	*eq;		/* 0 if not found, non-zero otherwise */
{
	int	i;
	int	res;
	int	hi;
	int	lo;

	res = -1;

	/*
	 * Perform linear search of node contains 7 keys or less,
	 * otherwise perform binary search
	 */
	if (node->nkeys <= 7)
	{
		for (i = 0; i < node->nkeys; i++)
		{
			res = (*comp)(node->keys[i],target);
			if (res >= 0) break;
		}
	}
	else
	{
		lo = 0;
		hi = node->nkeys - 1;
		while ((lo <= hi) && (res != 0))
		{
			i = (lo + hi) / 2;
			res = (*comp)(node->keys[i],target);
			if (res < 0) lo = i + 1;
			else if (res > 0) hi = i - 1;
		}
		if (res < 0) i++;
	}
	*eq = (res == 0);	/* Indicate successful search */
	node->currKey = i + *eq - 1;
	return i;
}

/******************************************************************
 *
 * bt_rotateRight -- Given a node and an index into its key array, this
 *                   function rotates the node right at the specified
 *                   key.  This is used during insertion and deletion to
 *                   keep the tree balanced.  The return value is 0 if
 *                   the function fails, i.e. the node on the left
 *                   cannot lose keys, the node on the right cannot
 *                   gain keys, or the specified node is a leaf; 1 is
 *                   returned if successful.
 *
 ******************************************************************/

int bt_rotateRight(node,n,order)
BTNODE	*node;
int	n;
int	order;
{
	int	i;
	BTNODE	*right;
	BTNODE	*left;

	/* Test parameters */
	if ((n >= node->nkeys) || (n < 0))
	{
		return 0;
	}

	/* Point to children */
	left = node->children[n];
	right = node->children[n+1];

	/* Return FALSE if rotation is not possible */
	if ((left == NULL) ||
	    (left->nkeys <= order/2) ||
	    (right->nkeys >= order - 1))
	{
		return 0;
	}

	/* Shift the right child's keys */
	for (i = right->nkeys; i > 0; i--)
	{
		right->keys[i] = right->keys[i - 1];
	}

	/* Rotate keys */
	right->keys[0] = node->keys[n];
	node->keys[n] = left->keys[left->nkeys - 1];
	left->keys[left->nkeys - 1] = NULL;

	if (right->children != NULL)
	{
		/* Shift the right child's children */
		for (i = right->nkeys; i >= 0; i--)
		{
			right->children[i + 1] = right->children[i];
		}

		/* Rotate children */
		right->children[0] = left->children[left->nkeys];
		right->children[0]->parent = right;
		left->children[left->nkeys] = NULL;
	}

	/* Update key count and return TRUE */
	right->nkeys++;
	left->nkeys--;
	return 1;
}

/******************************************************************
 *
 * bt_rotateLeft -- Given a node and an index into its key array, this
 *                  function rotates the node left at the specified
 *                  key.  This is used during insertion and deletion to
 *                  keep the tree balanced.  The return value is 0 if
 *                  the function fails, i.e. the node on the right
 *                  cannot lose keys, the node on the left cannot
 *                  gain keys, or the specified node is a leaf; 1 is
 *                  returned when successful.
 *
 ******************************************************************/

int bt_rotateLeft(node,n,order)
BTNODE	*node;
int	n;
int	order;
{
	int	i;
	BTNODE	*right;
	BTNODE	*left;

	/* Test parameters */
	if ((n < 0) || (n >= node->nkeys))
	{
		return 0;
	}

	/* Point to children */
	right = node->children[n+1];
	left = node->children[n];

	/* Return FALSE if rotation is not possible */
	if ((left == NULL) ||
	    (right->nkeys <= order/2) ||
	    (left->nkeys >= order - 1))
	{
		return 0;
	}

	/* Rotate keys */
	left->keys[left->nkeys] = node->keys[n];
	node->keys[n] = right->keys[0];

	/* Update key counts */
	left->nkeys ++;
	right->nkeys --;

	/* Shift the right child's keys */
	for (i = 0; i < right->nkeys; i++)
	{
		right->keys[i] = right->keys[i+1];
	}
	right->keys[i] = NULL;

	if (left->children != NULL)
	{
		/* Rotate children */
		left->children[left->nkeys] = right->children[0];
		left->children[left->nkeys]->parent = left;

		/* Shift the right child's children */
		for (i = 0; i <= right->nkeys; i++)
		{
			right->children[i] = right->children[i+1];
		}
		right->children[i+1] = NULL;
	}

	/* Return TRUE */
	return 1;
}
SHAR_EOF
fi
if test -f 'test.c'
then
	echo shar: "will not over-write existing file 'test.c'"
else
cat << \SHAR_EOF > 'test.c'
#include <stdio.h>
#include "btree.h"

/* #define DEBUGGING */

#define	LOOPS	500
#define	ORDER	12

typedef struct key {
	int	key;
} KEY;

KEY	savedKeys[LOOPS];

dump(key)
KEY	*key;
{
	if (key == NULL) printf("********NULL**********\n");
	else printf("%x: %d\n",key,key->key);
}

visit(key,parms)
KEY	*key;
char	*parms;
{
	dump(key);
}

comp(k1,k2)
KEY	*k1,*k2;
{
	return (k1->key - k2->key);
}

main()
{
	BTREE	tree;
	KEY	*key;
	int	i;
	int	res;
	KEY	*key1;
	KEY	*key2;
	KEY	*key3;
	KEY	*key4;
	KEY	tkey;

#ifdef DEBUGGING
#ifdef sun
	malloc_debug(2);
#endif
#endif
	tree = (BTREE)bt_new(ORDER,comp);
	if (tree == NULL)
	{
		printf("Failed to create tree\n");
		exit(1);
	}
	(void) bt_malloc_verify();

	for (i = 0; i < LOOPS; i++)
	{
		printf("Iteration %d\n",i+1);
		key = &savedKeys[i];
		key->key = rand();
		printf("Inserting %d\n",key->key);
		fflush(stdout);
		res = bt_insert(tree,key);
		if (res > 0)
		{
			printf("Inserted %d\n",key->key);
		}
		else if (res < 0)
		{
			printf("Duplicate key %d\n",key->key);
		}
		else
		{
			printf("Error inserting key %d\n");
			exit(3);
		}
		printf("Trying duplicate\n");
		res = bt_insert(tree,key);
		if (res < 0)
		{
			printf("Failed to insert duplicate\n");
		}
		else if (res == 0)
		{
			printf("Error inserting duplicate\n");
			exit(4);
		}
		else
		{
			printf("Succeeded in inserting duplicate\n");
			exit(5);
		}
#if 0
#ifdef DEBUGGING
		printf("Contents of tree:\n");
		bt_dump(tree,dump);
#endif
#endif 0
	}
	printf("Finished creating the tree.\n");
	printf("Contents of tree follow:\n");
	bt_traverse(tree,visit,NULL);
	for (i = 0; i < LOOPS; i++)
	{
		printf("Iteration %d\n",i);
		printf("Seeking %d at %x\n",savedKeys[i].key,&savedKeys[i]);
		key = (KEY*)bt_search(tree,&savedKeys[i]);
		if (key != &savedKeys[i])
		{
			printf("Can't find %d, returned %x\n",savedKeys[i].key,
			       key);
		}
		printf("Freeing %d at %x\n",savedKeys[i].key,&savedKeys[i]);
		fflush(stdout);
		key = (KEY*)bt_delete(tree,&savedKeys[i]);
		if (key != &savedKeys[i])
		{
			printf("Problem freeing %d at %x, returned %x\n",
			       savedKeys[i].key,&savedKeys[i].key,key);
		}
		else
		{
			printf("Freed %d, returned %x\n",savedKeys[i].key,key);
		}
#ifdef DEBUGGING
	printf("Contents of tree:\n");
	bt_dump(tree,dump);
	fflush(stdout);
#endif 
		key = (KEY*)bt_search(tree,&savedKeys[i]);
		if (key == &savedKeys[i])
		{
			printf("Found %d after deletion\n",savedKeys[i].key);
		}
		key = (KEY*)bt_delete(tree,&savedKeys[i]);
		if (key != NULL)
		{
			printf("%d remained in tree after deletion at %x\n",
			       savedKeys[i].key,key);
		}
#if 0
#ifdef DEBUGGING
		printf("Contents of tree:\n");
		bt_dump(tree,dump);
#endif
#endif 0
	}
	(void) bt_malloc_verify();
	printf("Freeing tree\n");
	bt_destroy(tree,NULL);
	printf("Finished freeing tree\n");
	printf("Malloc verify:  ");
	if (bt_malloc_verify())
	{
		printf("success\n");
		fflush(stdout);
	}
	else
	{
		printf("failure\n");
		fflush(stdout);
		exit(6);
	}

	printf("Creating second tree\n");
	tree = (BTREE)bt_new(ORDER,comp);
	if (tree == NULL)
	{
		printf("Failed to create tree\n");
		exit(7);
	}
	(void) bt_malloc_verify();
	printf("Contents of tree:\n");
	bt_dump(tree,dump);

	for (i = 0; i < LOOPS; i++)
	{
		printf("Iteration %d\n",i+1);
		key = &savedKeys[i];
		key->key = rand();
		printf("Inserting %d\n",key->key);
		fflush(stdout);
		res = bt_insert(tree,key);
		if (res > 0)
		{
			printf("Inserted %d\n",key->key);
		}
		else if (res < 0)
		{
			printf("Duplicate key %d\n",key->key);
		}
		else
		{
			printf("Error inserting key %d\n");
			exit(8);
		}
#if 0
#ifdef DEBUGGING
		printf("Contents of tree:\n");
		bt_dump(tree,dump);
#endif
#endif 0
	}
	printf("Finished creating the tree.\n");
	printf("Contents of tree follow:\n");
	bt_traverse(tree,visit,NULL);
	printf("Contents of tree:\n");
	bt_dump(tree,dump);

	printf("Testing first and next\n");
	key = (KEY *) bt_first(tree);
	while (key != NULL)
	{
		dump(key);
		key = (KEY *) bt_next(tree);
	}
	printf("Backing up\n");
	key = (KEY *) bt_prev(tree);
	dump(key);

	printf("Testing last and prev\n");
	key = (KEY *) bt_last(tree);
	while (key != NULL)
	{
		dump(key);
		key = (KEY *) bt_prev(tree);
	}
	printf("Stepping forward\n");
	key = (KEY *) bt_next(tree);
	dump(key);

	printf("Testing search\n");
	key1 = (KEY *) bt_first(tree);
	key2 = (KEY *) bt_next(tree);
	key4 = (KEY *) bt_last(tree);
	key3 = (KEY *) bt_prev(tree);
	dump(key1);
	dump(key2);
	dump(key3);
	dump(key4);

	printf("Testing search at beginning\n");
	key = (KEY *) bt_search(tree,key1);
	if (key == key1)
	{
		printf("Successful search okay\n");
		key = (KEY *) bt_next(tree);
		if (key == key2) printf("next okay\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,key1);
		key = (KEY *) bt_prev(tree);
		if (key == NULL) printf("prev Ok\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Successful search failed\n");
	}

	printf("Testing search at end\n");
	key = (KEY *) bt_search(tree,key4);
	if (key == key4)
	{
		printf("Successful search okay\n");
		key = (KEY *) bt_prev(tree);
		if (key == key3) printf("prev okay\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,key4);
		key = (KEY *) bt_next(tree);
		if (key == NULL) printf("next Ok\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Successful search failed\n");
	}

	printf("Testing first unsuccessful key\n");
	tkey.key = key1->key + 1;
	key = (KEY *) bt_search(tree,&tkey);
	if (key == NULL)
	{
		printf("Unsuccessful search okay\n");
		key = (KEY *) bt_next(tree);
		if (key == key2) printf("next ok\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,&tkey);
		key = (KEY *) bt_prev(tree);
		if (key == key1) printf("prev ok\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Unsuccessful search failed\n");
	}

	printf("Testing second unsuccessful key\n");
	tkey.key = key4->key - 1;
	key = (KEY *) bt_search(tree,&tkey);
	if (key == NULL)
	{
		printf("Unsuccessful search okay\n");
		key = (KEY *) bt_next(tree);
		if (key == key4) printf("next ok\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,&tkey);
		key = (KEY *) bt_prev(tree);
		if (key == key3) printf("prev ok\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Unsuccessful search failed\n");
	}

	printf("Testing third unsuccessful key\n");
	tkey.key = key1->key - 1;
	key = (KEY *) bt_search(tree,&tkey);
	if (key == NULL)
	{
		printf("Unsuccessful search okay\n");
		key = (KEY *) bt_next(tree);
		if (key == key1) printf("next ok\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,&tkey);
		key = (KEY *) bt_prev(tree);
		if (key == NULL) printf("prev ok\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Unsuccessful search failed\n");
	}

	printf("Testing fourth unsuccessful key\n");
	tkey.key = key4->key + 1;
	key = (KEY *) bt_search(tree,&tkey);
	if (key == NULL)
	{
		printf("Unsuccessful search okay\n");
		key = (KEY *) bt_next(tree);
		if (key == NULL) printf("next ok\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,&tkey);
		key = (KEY *) bt_prev(tree);
		if (key == key4) printf("prev ok\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Unsuccessful search failed\n");
	}

	printf("Freeing 3/4 of the keys\n");
	for (i = 0; i < 3 * LOOPS / 4; i++)
	{
		printf("Iteration %d\n",i+1);
		key = &savedKeys[i];
		key1 = (KEY*) bt_delete(tree,key);
		if (key1 == key) printf("Deletion okay\n");
		else printf("Deletion error, wanted %x, got %x\n",key,key1);
		fflush(stdout);
#if 0
#ifdef DEBUGGING
		printf("Contents of tree:\n");
		bt_dump(tree,dump);
#endif
#endif 0
	}
	printf("Finished deleting keys.\n");
	printf("Contents of tree follow:\n");
	bt_traverse(tree,visit,NULL);
	printf("Contents of tree:\n");
	bt_dump(tree,dump);

	printf("Testing first and next\n");
	key = (KEY *) bt_first(tree);
	while (key != NULL)
	{
		dump(key);
		key = (KEY *) bt_next(tree);
	}
	printf("Backing up\n");
	key = (KEY *) bt_prev(tree);
	dump(key);

	printf("Testing last and prev\n");
	key = (KEY *) bt_last(tree);
	while (key != NULL)
	{
		dump(key);
		key = (KEY *) bt_prev(tree);
	}
	printf("Stepping forward\n");
	key = (KEY *) bt_next(tree);
	dump(key);

	printf("Testing search\n");
	key1 = (KEY *) bt_first(tree);
	key2 = (KEY *) bt_next(tree);
	key4 = (KEY *) bt_last(tree);
	key3 = (KEY *) bt_prev(tree);
	dump(key1);
	dump(key2);
	dump(key3);
	dump(key4);

	printf("Testing search at beginning\n");
	key = (KEY *) bt_search(tree,key1);
	if (key == key1)
	{
		printf("Successful search okay\n");
		key = (KEY *) bt_next(tree);
		if (key == key2) printf("next okay\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,key1);
		key = (KEY *) bt_prev(tree);
		if (key == NULL) printf("prev Ok\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Successful search failed\n");
	}

	printf("Testing search at end\n");
	key = (KEY *) bt_search(tree,key4);
	if (key == key4)
	{
		printf("Successful search okay\n");
		key = (KEY *) bt_prev(tree);
		if (key == key3) printf("prev okay\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,key4);
		key = (KEY *) bt_next(tree);
		if (key == NULL) printf("next Ok\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Successful search failed\n");
	}

	printf("Testing first unsuccessful key\n");
	tkey.key = key1->key + 1;
	key = (KEY *) bt_search(tree,&tkey);
	if (key == NULL)
	{
		printf("Unsuccessful search okay\n");
		key = (KEY *) bt_next(tree);
		if (key == key2) printf("next ok\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,&tkey);
		key = (KEY *) bt_prev(tree);
		if (key == key1) printf("prev ok\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Unsuccessful search failed\n");
	}

	printf("Testing second unsuccessful key\n");
	tkey.key = key4->key - 1;
	key = (KEY *) bt_search(tree,&tkey);
	if (key == NULL)
	{
		printf("Unsuccessful search okay\n");
		key = (KEY *) bt_next(tree);
		if (key == key4) printf("next ok\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,&tkey);
		key = (KEY *) bt_prev(tree);
		if (key == key3) printf("prev ok\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Unsuccessful search failed\n");
	}

	printf("Testing third unsuccessful key\n");
	tkey.key = key1->key - 1;
	key = (KEY *) bt_search(tree,&tkey);
	if (key == NULL)
	{
		printf("Unsuccessful search okay\n");
		key = (KEY *) bt_next(tree);
		if (key == key1) printf("next ok\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,&tkey);
		key = (KEY *) bt_prev(tree);
		if (key == NULL) printf("prev ok\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Unsuccessful search failed\n");
	}

	printf("Testing fourth unsuccessful key\n");
	tkey.key = key4->key + 1;
	key = (KEY *) bt_search(tree,&tkey);
	if (key == NULL)
	{
		printf("Unsuccessful search okay\n");
		key = (KEY *) bt_next(tree);
		if (key == NULL) printf("next ok\n");
		else
		{
			printf("next bad\n");
			dump(key);
		}
		key = (KEY *) bt_search(tree,&tkey);
		key = (KEY *) bt_prev(tree);
		if (key == key4) printf("prev ok\n");
		else
		{
			printf("prev bad\n");
			dump(key);
		}
	}
	else
	{
		printf("Unsuccessful search failed\n");
	}

	printf("Freeing tree\n");
	bt_destroy(tree,NULL);
	printf("Finished freeing tree\n");
	printf("Malloc verify:  ");
	if (bt_malloc_verify()) printf("success\n");
	else printf("failure\n");
	fflush(stdout);

	exit(0);
}
SHAR_EOF
fi
exit 0
#	End of shell archive
-- 
Paul Sander        (408) 734-9822  | "Passwords are like underwear," she said,
paul@Atherton.COM                  | "Both should be changed often."
{decwrl,pyramid,sun}!athertn!paul  | -- Bennett Falk in "Mom Meets Unix"