#ifndef __BStreeh
#define __BStreeh

/* routines for managing B-tree data structures */

/* Note, if __TREE_RETURN is specified, then our error handling */
/* routines will be CHKERRN and MY_SETERRN, otherwise, they will be */
/* CHKERR and MY_SETERR */

#define MAX_KIDS	9
#define MAX_KEYS	(MAX_KIDS-1)
#define MIN_KIDS	((MAX_KIDS+1)/2)
#define MIN_KEYS	(MIN_KIDS-1)
typedef	struct __BStree_node {
	int	num_keys;
	int	keys[MAX_KEYS];
	char	*data_ptr[MAX_KEYS];
	struct	__BStree_node	*child[MAX_KIDS], *parent;
} BStree_node;
typedef	struct __BStree_ptr {
	BStree_node *ptr;
	int	ind;
} BStree_ptr;

/* used in the special memory management routines */
typedef struct __BSMBlock {
	int	base_size;
	int	num_units;
	double	*top, *bottom;			/* bounds of memory for this block */
									/* used for free'ing quickly */
	struct	__BSMBlock   *next;     /* Pointer to next BSMBlock */
	double	*free_blocks;
	int	num_allocated;
	double v;                        /* Dummy for top */
} BSMBlock;

typedef	struct __BStree {
	BStree_node	*root;
	int	u_data_size;
	BSMBlock	*node_blocks;
	BSMBlock	*user_blocks;
} BStree;

/* ********************** */
/* special memory section */
/* ********************** */
/* on the Intel DELTA, the memory allocation routines *can* be be quite slow */
/* thus, we have an option of using our own memory allocation routines that */
/* were adopted from those in petsc */
#if defined(PARCH_intelnx)
#define __SLOW_MALLOC
#endif

#if defined(__SLOW_MALLOC)
	BSMBlock *BSsbinit(long,int);
	double *BSsbmalloc();
	void BSsbfree();
	void	BSmem_clean();
#endif

#if defined(__SLOW_MALLOC)
#if defined (__TREE_RETURN)
#define	MY_MALLOC_USER_DATA(tree,data_ptr) \
{ \
	if (tree.u_data_size > 0) { \
		if ((data_ptr = (char *) BSsbmalloc(&(tree.user_blocks))) == NULL) { \
			MY_SETERRCN(MEM_ERROR,"Out of memory allocating user data\n"); \
		} \
	} \
}
#else
#define	MY_MALLOC_USER_DATA(tree,data_ptr) \
{ \
	if (tree.u_data_size > 0) { \
		if ((data_ptr = (char *) BSsbmalloc(&(tree.user_blocks))) == NULL) { \
			MY_SETERRCN(MEM_ERROR,"Out of memory allocating user data\n"); \
		} \
	} \
}
#endif
#else
#if defined (__TREE_RETURN)
#define	MY_MALLOC_USER_DATA(tree,data_ptr) \
{ \
	if (tree.u_data_size > 0) { \
		MY_MALLOCN(data_ptr,(char *),tree.u_data_size,1); \
	} \
}
#else
#define	MY_MALLOC_USER_DATA(tree,data_ptr) \
{ \
	if (tree.u_data_size > 0) { \
		MY_MALLOCN(data_ptr,(char *),tree.u_data_size,1); \
	} \
}
#endif
#endif

#if defined(__SLOW_MALLOC)
#define	MY_FREE_USER_DATA(tree,data_ptr) \
{ \
	if (data_ptr != NULL) { \
		BSsbfree(data_ptr,&(tree.user_blocks)); \
	} \
}
#else
#define	MY_FREE_USER_DATA(tree,data_ptr) \
{ \
	if (data_ptr != NULL) { \
		MY_FREEN(data_ptr); \
	} \
}
#endif

#if defined(__SLOW_MALLOC)
#define	MY_FREE_TREE_NODE(tree,inptr) \
{ \
	int	i99; \
	for (i99=0;i99<MAX_KEYS;i99++) { \
		MY_FREE_USER_DATA(tree,inptr->data_ptr[i99]); \
	} \
	BSsbfree(inptr,&(tree.node_blocks)); \
}
#else
#define	MY_FREE_TREE_NODE(tree,inptr) \
{ \
	int	i99; \
	for (i99=0;i99<MAX_KEYS;i99++) { \
		MY_FREE_USER_DATA(tree,inptr->data_ptr[i99]); \
	} \
	MY_FREEN(inptr); \
}
#endif

#if defined(__SLOW_MALLOC)
#if defined (__TREE_RETURN)
#define	MY_GET_TREE_NODE(tree,inptr) \
{ \
	int	i99; \
	if ((inptr = (BStree_node *) BSsbmalloc(&(tree.node_blocks))) == NULL) { \
		MY_SETERRCN(MEM_ERROR,"Out of memory allocating node data\n"); \
	} \
	inptr->num_keys = 0; \
	inptr->parent = NULL; \
	for (i99=0;i99<MAX_KIDS;i99++) { \
		inptr->child[i99] = NULL; \
	} \
	for (i99=0;i99<MAX_KEYS;i99++) { \
		inptr->data_ptr[i99] = NULL; \
	} \
}
#else
#define	MY_GET_TREE_NODE(tree,inptr) \
{ \
	int	i99; \
	if ((inptr = (BStree_node *) BSsbmalloc(&(tree.node_blocks))) == NULL) { \
		MY_SETERRCN(MEM_ERROR,"Out of memory allocating node data\n"); \
	} \
	inptr->num_keys = 0; \
	inptr->parent = NULL; \
	for (i99=0;i99<MAX_KIDS;i99++) { \
		inptr->child[i99] = NULL; \
	} \
	for (i99=0;i99<MAX_KEYS;i99++) { \
		inptr->data_ptr[i99] = NULL; \
	} \
}
#endif
#else
#if defined (__TREE_RETURN)
#define	MY_GET_TREE_NODE(tree,inptr) \
{ \
	int	i99; \
	MY_MALLOCN(inptr,(BStree_node *),sizeof(BStree_node),1); \
	inptr->num_keys = 0; \
	inptr->parent = NULL; \
	for (i99=0;i99<MAX_KIDS;i99++) { \
		inptr->child[i99] = NULL; \
	} \
	for (i99=0;i99<MAX_KEYS;i99++) { \
		inptr->data_ptr[i99] = NULL; \
	} \
}
#else
#define	MY_GET_TREE_NODE(tree,inptr) \
{ \
	int	i99; \
	MY_MALLOCN(inptr,(BStree_node *),sizeof(BStree_node),1); \
	inptr->num_keys = 0; \
	inptr->parent = NULL; \
	for (i99=0;i99<MAX_KIDS;i99++) { \
		inptr->child[i99] = NULL; \
	} \
	for (i99=0;i99<MAX_KEYS;i99++) { \
		inptr->data_ptr[i99] = NULL; \
	} \
}
#endif
#endif

#if defined(__SLOW_MALLOC)
#if defined (__TREE_RETURN)
#define	MY_INIT_TREE(tree,user_data_size) \
{ \
	tree.root = NULL; \
	tree.u_data_size = user_data_size; \
	if ((tree.user_blocks = (void *) BSsbinit(tree.u_data_size,MAX_KEYS*128)) \
		== NULL) { \
		MY_SETERRCN(MEM_ERROR,"Out of memory initing user data\n"); \
	} \
	if ((tree.node_blocks = (void *) BSsbinit(sizeof(BStree_node),128)) \
		== NULL) { \
		MY_SETERRCN(MEM_ERROR,"Out of memory initing node data\n"); \
	} \
}
#else
#define	MY_INIT_TREE(tree,user_data_size) \
{ \
	tree.root = NULL; \
	tree.u_data_size = user_data_size; \
	if ((tree.user_blocks = (void *) BSsbinit(tree.u_data_size,MAX_KEYS*128)) \
		== NULL) { \
		MY_SETERRC(MEM_ERROR,"Out of memory initing user data\n"); \
	} \
	if ((tree.node_blocks = (void *) BSsbinit(sizeof(BStree_node),128)) \
		== NULL) { \
		MY_SETERRC(MEM_ERROR,"Out of memory initing node data\n"); \
	} \
}
#endif
#else
#define	MY_INIT_TREE(tree,user_data_size) \
{ \
	tree.root = NULL; \
	tree.u_data_size = user_data_size; \
}
#endif

#if defined(__SLOW_MALLOC)
#define MY_CLEAN_TREE(tree) \
{ \
	BSmem_clean(&(tree.user_blocks)); \
	BSmem_clean(&(tree.node_blocks)); \
}
#else
#define MY_CLEAN_TREE(tree)
#endif

/* ***************************** */
/* end of special memory section */
/* ***************************** */


#define MY_PRINT_NODE(tptr) \
{ \
	int	i99; \
	if (tptr == NULL) { \
		printf("NULL NODE\n"); \
	} else { \
		printf("Node has %d keys: ",tptr->num_keys); \
		if (tptr->child[0] != NULL) { \
			printf(" Child "); \
		} else { \
			printf(" NoChild "); \
		} \
		for (i99=0;i99<tptr->num_keys;i99++) { \
			printf("%d ",tptr->keys[i99]); \
			if (tptr->child[i99+1] != NULL) { \
				printf(" Child "); \
			} else { \
				printf(" NoChild "); \
			} \
		} \
		printf("\n"); \
	} \
}

#define MY_NEXT_IN_TREE(node_ptr) \
{ \
	BStree_node	*curptr99, *prevptr99, *chkptr99; \
	int	done99, i99; \
	curptr99 = node_ptr.ptr->child[node_ptr.ind+1]; \
	if (curptr99 == NULL) { \
		node_ptr.ind++; \
		if (node_ptr.ind == node_ptr.ptr->num_keys) { \
			chkptr99 = node_ptr.ptr; \
			curptr99 = chkptr99->parent; \
			done99 = FALSE; \
			while ((curptr99 != NULL) && (! done99)) { \
				for (i99=0;i99<curptr99->num_keys+1;i99++) { \
					if (curptr99->child[i99] == chkptr99) break; \
				} \
				if (i99 < curptr99->num_keys) { \
					done99 = TRUE; \
				} else { \
					chkptr99 = curptr99; \
					curptr99 = curptr99->parent; \
				} \
			} \
			node_ptr.ptr = curptr99; \
			node_ptr.ind = i99; \
		} \
	} else { \
		while (curptr99 != NULL) { \
			prevptr99 = curptr99; \
			curptr99 = curptr99->child[0]; \
		} \
		node_ptr.ptr = prevptr99; \
		node_ptr.ind = 0; \
	} \
}

#define IS_TREE_PTR_NULL(tree_ptr) ((tree_ptr.ptr == NULL)?1:0)

#define MY_FIRST_IN_TREE(tree,node_ptr) \
{ \
	BStree_node	*tptr99, *pptr99; \
	tptr99 = tree.root; \
	pptr99 = tptr99; \
	while (tptr99 != NULL) { \
		pptr99 = tptr99; \
		tptr99 = tptr99->child[0]; \
	} \
	node_ptr.ptr = pptr99; \
	node_ptr.ind = 0; \
}

#define MY_KEY_LT(key1,key2) (((key1) < (key2))?1:0)
#define MY_KEY_EQUAL(key1,key2) (((key1) == (key2))?1:0)

#define MY_MAKE_PARENT(inchild,inparent) \
{ \
	if (inchild != NULL) inchild->parent = inparent; \
}

#define MY_PUT_IN_TREE(tree,inkey,inptr) \
{ \
	int	done99, i99; \
	BStree_node	*tptr99, *cur_right99, *tright99; \
	char	*cur_data99, *tdata99; \
	int	cur_key99, tkey99; \
	int	temp_keys99[MAX_KEYS+1]; \
	BStree_node	*temp_kids99[MAX_KEYS+1]; \
	char	*temp_data99[MAX_KEYS+1]; \
	if (tree.root == NULL) { \
		MY_GET_TREE_NODE(tree,tree.root); \
		tree.root->num_keys = 1; \
		tree.root->keys[0] = inkey; \
		MY_MALLOC_USER_DATA(tree,tree.root->data_ptr[0]); \
	} else { \
		done99 = FALSE; \
		tptr99 = inptr; \
		cur_key99 = inkey; \
		cur_right99 = NULL; \
		MY_MALLOC_USER_DATA(tree,cur_data99); \
		while (! done99) { \
			if (tptr99 == NULL) { \
				MY_GET_TREE_NODE(tree,tptr99); \
				tptr99->num_keys = 1; \
				tptr99->keys[0] = cur_key99; \
				tptr99->data_ptr[0] = cur_data99; \
				tptr99->child[0] = tree.root; \
				tree.root->parent = tptr99; \
				tptr99->child[1] = cur_right99; \
				cur_right99->parent = tptr99; \
				tree.root = tptr99; \
				done99 = TRUE; \
			} else if (tptr99->num_keys < MAX_KEYS) { \
				MY_MAKE_PARENT(cur_right99,tptr99); \
				tptr99->keys[tptr99->num_keys] = cur_key99; \
				tptr99->child[tptr99->num_keys+1] = cur_right99; \
				tptr99->data_ptr[tptr99->num_keys] = cur_data99; \
				tptr99->num_keys++; \
				for (i99=tptr99->num_keys-1;i99>0;i99--) { \
					if (MY_KEY_LT(tptr99->keys[i99],tptr99->keys[i99-1])) { \
						tkey99 = tptr99->keys[i99]; \
						tright99 = tptr99->child[i99+1]; \
						tdata99 = tptr99->data_ptr[i99]; \
						tptr99->keys[i99] = tptr99->keys[i99-1]; \
						tptr99->child[i99+1] = tptr99->child[i99]; \
						tptr99->data_ptr[i99] = tptr99->data_ptr[i99-1]; \
						tptr99->keys[i99-1] = tkey99; \
						tptr99->child[i99] = tright99; \
						tptr99->data_ptr[i99-1] = tdata99; \
					} else { \
						break; \
					} \
				} \
				done99 = TRUE; \
			} else { \
				for (i99=0;i99<MAX_KEYS;i99++) { \
					temp_keys99[i99] = tptr99->keys[i99]; \
					temp_data99[i99] = tptr99->data_ptr[i99]; \
					temp_kids99[i99] = tptr99->child[i99+1]; \
				} \
				temp_keys99[MAX_KEYS] = cur_key99; \
				temp_data99[MAX_KEYS] = cur_data99; \
				temp_kids99[MAX_KEYS] = cur_right99; \
				for (i99=MAX_KEYS;i99>0;i99--) { \
					if (MY_KEY_LT(temp_keys99[i99],temp_keys99[i99-1])) { \
						tkey99 = temp_keys99[i99]; \
						tright99 = temp_kids99[i99]; \
						tdata99 = temp_data99[i99]; \
						temp_keys99[i99] = temp_keys99[i99-1]; \
						temp_kids99[i99] = temp_kids99[i99-1]; \
						temp_data99[i99] = temp_data99[i99-1]; \
						temp_keys99[i99-1] = tkey99; \
						temp_kids99[i99-1] = tright99; \
						temp_data99[i99-1] = tdata99; \
					} else { \
						break; \
					} \
				} \
				tptr99->num_keys = MIN_KEYS; \
				for (i99=0;i99<MIN_KEYS;i99++) { \
					tptr99->keys[i99] = temp_keys99[i99]; \
					tptr99->child[i99+1] = temp_kids99[i99]; \
					MY_MAKE_PARENT(tptr99->child[i99+1],tptr99); \
					tptr99->data_ptr[i99] = temp_data99[i99]; \
				} \
				for (i99=MIN_KEYS;i99<MAX_KEYS;i99++) { \
					tptr99->data_ptr[i99] = NULL; \
				} \
				MY_GET_TREE_NODE(tree,cur_right99); \
				cur_right99->num_keys = MIN_KEYS; \
				cur_right99->child[0] = temp_kids99[MIN_KEYS]; \
				MY_MAKE_PARENT(cur_right99->child[0],cur_right99); \
				for (i99=0;i99<MIN_KEYS;i99++) { \
					cur_right99->keys[i99] = temp_keys99[i99+MIN_KEYS+1]; \
					cur_right99->child[i99+1] = temp_kids99[i99+MIN_KEYS+1]; \
					MY_MAKE_PARENT(cur_right99->child[i99+1],cur_right99); \
					cur_right99->data_ptr[i99] = temp_data99[i99+MIN_KEYS+1]; \
				} \
				cur_key99 = temp_keys99[MIN_KEYS]; \
				cur_data99 = temp_data99[MIN_KEYS]; \
				tptr99 = tptr99->parent; \
			} \
		} \
	}  \
}

#define MY_SEARCH_TREE(tree,inkey,found,node_ptr) \
{ \
	BStree_node	*tptr99, *pptr99; \
	int	down99, i99; \
	tptr99 = tree.root; \
	pptr99 = tptr99; \
	found = FALSE; \
	while ((tptr99 != NULL) && (! found)) { \
		down99 = FALSE; \
		pptr99 = tptr99; \
		for (i99=0;i99<tptr99->num_keys;i99++) { \
			if (MY_KEY_EQUAL(inkey,tptr99->keys[i99])) { \
				found = TRUE; \
				down99 = TRUE; \
				node_ptr.ptr = tptr99; \
				node_ptr.ind = i99; \
				break; \
			} else if (MY_KEY_LT(inkey,tptr99->keys[i99])) { \
				down99 = TRUE; \
				tptr99 = tptr99->child[i99]; \
				break; \
			} \
		} \
		if (! down99) { \
			tptr99 = tptr99->child[tptr99->num_keys]; \
		} \
	} \
	if (!found) { \
		node_ptr.ptr = pptr99; \
	} \
}

#define MY_INSERT_TREE_NODE(tree,inkey,found,node_ptr,key_count) \
{ \
	MY_SEARCH_TREE(tree,inkey,found,node_ptr); \
	if (!found) { \
		key_count++; \
		MY_PUT_IN_TREE(tree,inkey,(node_ptr.ptr)); \
		MY_SEARCH_TREE(tree,inkey,found,node_ptr); \
		found = FALSE; \
	} \
}

#define	MY_GET_TREE_DATA(node_ptr) node_ptr.ptr->data_ptr[node_ptr.ind]

#define	MY_GET_TREE_KEY(node_ptr) node_ptr.ptr->keys[node_ptr.ind]

#define MY_FREE_TREE(tree) \
{ \
	BStree_node	*curptr99, *tptr99; \
	int	i99, found99; \
	curptr99 = tree.root; \
	while (curptr99 != NULL) { \
		found99 = FALSE; \
		for (i99=0;i99<curptr99->num_keys+1;i99++) { \
			tptr99 = curptr99->child[i99]; \
			if (tptr99 != NULL) { \
				curptr99->child[i99] = NULL; \
				curptr99 = tptr99; \
				found99 = TRUE; \
				break; \
			} \
		} \
		if (! found99) { \
			tptr99 = curptr99; \
			curptr99 = curptr99->parent; \
			MY_FREE_TREE_NODE(tree,tptr99); \
		} \
	} \
	MY_CLEAN_TREE(tree); \
}

#endif