/* 
 * PDFlow -- btree.c
 *
 *  Copyright (c) 2010 Alberto Cuda
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
 *  USA.
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <stdint.h>
#include <string.h>
#include <assert.h>

#include "btree.h"

static enum s_status split (struct bt_tree *tree,
			    struct bt_node **nodep, int *idxp);
static void merge (struct bt_tree *tree, struct bt_node **node);
static enum s_status load_node_data (struct bt_tree *tree, 
				     struct bt_node *parent,
				     int i, struct bt_imp_info *ii,
				     void *closure,
				     struct bt_node **nodep);
static void switch_node (struct bt_cursor *pc, struct bt_node *node, int idx);

static enum s_status node_init (struct bt_node *node, struct bt_node *parent,
				enum bt_node_type nt, bt_node_data_t *ndata,
				struct bt_param *param)
{
	node -> parent = parent;
	node -> type = nt;

	node -> ndata = ndata;
	node -> size = 2 * param -> min_size - 1;
	node -> used = 0;

	node -> key = calloc (node -> size, param -> key_size);
	node -> p = calloc (node -> size, sizeof (union bt_ptr));
	if (node -> key == NULL || node -> p == NULL)
		return S_CSC_OUT_OF_MEMORY;

	return S_CSC_OK;
}

static enum s_status trim_size (struct bt_tree *tree, struct bt_node *node)
{
	void *p;

	if (node -> size < 2 * tree -> param.min_size - 1)
		return S_CSC_OK;

	p = realloc (node -> key, node -> size * tree -> param.key_size);
	if (p == NULL)
		return S_CSC_OUT_OF_MEMORY;
	node -> key = p;

	p = realloc (node -> p, node -> size * sizeof (union bt_ptr));
	if (p == NULL)
		return S_CSC_OUT_OF_MEMORY;
	node -> p = p;
	
	node -> size = 2 * tree -> param.min_size - 1;

	return S_CSC_OK;
}	

static void assure (struct bt_tree *tree, unsigned size)
{
	if (size > tree -> param.min_size * 2)
		tree -> param.min_size = size / 2 + 1;
}

static void node_ref (struct bt_node *node, struct ref_owner *p)
{
	ref_up (&node -> refs, p);
}

static void node_unref (struct bt_node *node, struct bt_param *param,
			struct ref_owner *p)
{
	int i;

	if (ref_down (&node -> refs, p))
		return;

	if (node -> p != NULL) {
		if (node -> type == BT_NT_LEAF &&
		    param -> destroy_data != NULL) {
			for (i = 0; i < node -> used; i++)
				param -> destroy_data (param -> tdata, 
						       node -> p [i].data);
		} else {
			for (i = 0; i < node -> used; i++)
				node_unref (node -> p [i].child, param, 
					    ref_rown (&node -> refs));
		}
		free (node -> p);
	}

	if (node -> key != NULL)
		free (node -> key);

	if (param -> destroy_node_data != NULL)
		param -> destroy_node_data (param -> tdata, node -> ndata);

	ref_zero (&node -> refs);

	free (node);
}

static enum s_status node_new (struct bt_node **nodep, struct bt_node *parent,
			       enum bt_node_type nt, bt_node_data_t *ndata,
			       struct bt_param *param, struct ref_owner *p)
{
	struct bt_node *node;
	bt_node_data_t *pdata;
	enum s_status res;
	int allocated;

	node = malloc (sizeof (struct bt_node));
	if (node == NULL)
		return S_CSC_OUT_OF_MEMORY;
	memset (node, 0, sizeof (struct bt_node));

	if (ndata == NULL && param -> create_node_data != NULL) {
		pdata = parent != NULL ? parent -> ndata : NULL;
		res = param -> create_node_data (param -> tdata, 
						 pdata, &ndata);
		if (res != S_CSC_OK) {
			free (node);
			return res;
		}
		allocated = 1;
	} else
		allocated = 0;

	ref_init (&node -> refs, "bt_node", p);
	
	res = node_init (node, parent, nt, ndata, param);
	if (res != S_CSC_OK) {
		/* Destroy data only if allocated */
		if (allocated)
			node -> ndata = ndata;
		node_unref (node, param, p);
		return res;
	}

	*nodep = node;

	return S_CSC_OK;
}

static enum s_status init (struct bt_tree *tree, struct bt_param *param)
{
	tree -> param = *param;

	return node_new (&tree -> root, NULL, BT_NT_LEAF, NULL,
			 &tree -> param, ref_rown (&tree -> refs));
}

enum s_status bt_init (struct bt_tree **treep, struct bt_param *param,
		       struct ref_owner *p)

{
	struct bt_tree *tree;
	enum s_status res;

	tree = malloc (sizeof (struct bt_tree));
	if (tree == NULL)
		return S_CSC_OUT_OF_MEMORY;
	memset (tree, 0, sizeof (struct bt_tree));
	
	ref_init (&tree -> refs, "btree", p);

	res = init (tree, param);
	if (res != S_CSC_OK) {
		bt_unref (tree, p);
		return res;
	}

	*treep = tree;

	return S_CSC_OK;
}

void bt_ref (struct bt_tree *tree, struct ref_owner *p)
{
	ref_up (&tree -> refs, p);
}

void bt_unref (struct bt_tree *tree, struct ref_owner *p)
{
	if (ref_down (&tree -> refs, p))
		return;

	if (tree -> root != NULL)
		node_unref (tree -> root, &tree -> param, 
			    ref_rown (&tree -> refs));

	if (tree -> param.destroy_tree_data != NULL)
		tree -> param.destroy_tree_data (tree -> param.tdata);
	
	ref_zero (&tree -> refs);

	free (tree);
}

static struct ref_owner *get_owner (struct bt_tree *tree, struct bt_node *node)
{
	return ref_rown (node != NULL ? &node -> refs : &tree -> refs);
}

static struct ref_owner *owner_of (struct bt_tree *tree, struct bt_node *node)
{
	return get_owner (tree, node -> parent);
}

static void *aok (struct bt_tree *tree, struct bt_node *node, int idx)
{
	uint8_t *k;

	k = (uint8_t *) node -> key;
	
	return k + idx * tree -> param.key_size;
}

static void *aolk (struct bt_tree *tree, struct bt_node *node)
{
	return	aok (tree, node, node -> used - 1);
}

static int ion (struct bt_tree *tree, struct bt_node *node)
{
	struct bt_node *parent;
	int i;

	parent = node -> parent;
	for (i = 0; i < parent -> used; i++)
		if (parent -> p [i].child == node)
			return i;

	assert (0);
}

static void move (struct bt_tree *tree,
		  struct bt_node *snode, int sidx,
		  struct bt_node *dnode, int didx)
{
	int n;

	n = snode -> used - sidx;

	memmove (dnode -> p + didx, snode -> p + sidx, 
		 n * sizeof (union bt_ptr));

	memmove (aok (tree, dnode, didx), aok (tree, snode, sidx),
		 n * tree -> param.key_size);

	dnode -> used = didx + n;
}

static void push (struct bt_tree *tree,
		  struct bt_node *snode, int sidx,
		  struct bt_node *dnode, int didx)
{
	int n, m;

	n = snode -> used - sidx;
	m = dnode -> used - didx;

	memmove (dnode -> p + didx + n, dnode -> p + didx, 
		 m * sizeof (union bt_ptr));

	memmove (aok (tree, dnode, didx + n), aok (tree, dnode, didx),
		 m * tree -> param.key_size);

	memmove (dnode -> p + didx, snode -> p + sidx, 
		 n * sizeof (union bt_ptr));

	memmove (aok (tree, dnode, didx), aok (tree, snode, sidx),
		 n * tree -> param.key_size);

	dnode -> used += n;
}

static int find_in_node (struct bt_tree *tree, struct bt_node *node, 
			 bt_key_t *key, int *lcp)
{
	uint8_t *kp;
	int i, lc;

	kp = (uint8_t *) node -> key;
	lc = 1;
	for (i = 0; i < node -> used; i++) {
		lc = tree -> param.compare (kp, key);
		if (lc >= 0)
			break;
		kp += tree -> param.key_size;
	}
	
	if (lcp != NULL)
		*lcp = lc;

	return i;
}

static struct bt_node *find_in_tree (struct bt_tree *tree, bt_key_t *key, 
				     int *idx, int *lcp)
{
	struct bt_node *node;	
	int i, lc;

	node = tree -> root;
	while (1) {
		i = find_in_node (tree, node, key, &lc);
		if (node -> type == BT_NT_LEAF)
			break;
		
		if (i == node -> used) {
			do {
				node = node -> p [i - 1].child;
				i = node -> used;
			} while (node -> type == BT_NT_INTERMEDIATE);
			break;
		}

		node = node -> p [i].child;
	}

	if (idx != NULL)
		*idx = i;

	if (lcp != NULL)
		*lcp = lc;

	return node;
}

static void reparent (struct bt_tree *tree, struct bt_node *parent,
		      struct bt_node *node)
{
	node_ref (node, ref_rown (&parent -> refs));
	node_unref (node, &tree -> param, owner_of (tree, node));
	node -> parent = parent;
}

static enum s_status insert_into_node (struct bt_tree *tree,
				       struct bt_node **nodep, int *idxp,
				       bt_key_t *key, bt_data_t *data,
				       struct bt_node *child)
{
	struct bt_node *node;
	enum s_status res;
	int idx;

	node = *nodep;
	idx = *idxp;
	if (node -> used >= node -> size) {
		res = split (tree, &node, &idx);
		if (res != S_CSC_OK)
			return res;
		if (node -> type == BT_NT_INTERMEDIATE)
			reparent (tree, node, child);
	}

	move (tree, node, idx, node, idx + 1);

	if (node -> type == BT_NT_INTERMEDIATE)
		node -> p [idx].child = child;
	else
		node -> p [idx].data = data;
	memcpy (aok (tree, node, idx), key, tree -> param.key_size);

	*nodep = node;
	*idxp = idx;

	return S_CSC_OK;
}

static void fix_keys (struct bt_tree *tree, struct bt_node *node,
		      int idx, bt_key_t *key)
{
	while (node -> parent != NULL && idx == node -> used - 1) {
		idx = ion (tree, node);
		node = node -> parent;
		memcpy (aok (tree, node, idx), key, tree -> param.key_size);
	}
}

static void fix_node_keys (struct bt_tree *tree, struct bt_node *node)
{
	fix_keys (tree, node, node -> used - 1, 
		  aok (tree, node, node -> used - 1));
}

static enum s_status split (struct bt_tree *tree,
			    struct bt_node **nodep, int *idxp)
{
	struct bt_node *lnode, *rnode, *rrnode;
	enum s_status res;
	int i, mid, go_right, n_size;

	lnode = *nodep;

	res = node_new (&rnode, lnode -> parent, lnode -> type, 
			NULL, &tree -> param, owner_of (tree, lnode));
	if (res != S_CSC_OK)
		return res;

	n_size = lnode -> used;
	mid = n_size / 2;
	go_right = *idxp > mid;
	/* If new key will go into rnode, make lnode larger */
	if (go_right)
		mid++;

	move (tree, lnode, mid, rnode, 0);
	lnode -> used = mid;

	if (lnode -> parent != NULL) {
		i = ion (tree, lnode);
		i++;
		res = insert_into_node (tree, &rnode -> parent, &i,
					aolk (tree, rnode), NULL, rnode);
		if (res != S_CSC_OK) {
			node_unref (rnode, &tree -> param, 
				    owner_of (tree, rnode));
			lnode -> used = n_size;
			return res;
		}
		fix_node_keys (tree, lnode);
		fix_node_keys (tree, rnode);
	} else {
		res = node_new (&rrnode, NULL, BT_NT_INTERMEDIATE,
				NULL, &tree -> param, 
				ref_rown (&tree -> refs));
		if (res != S_CSC_OK) {
			node_unref (rnode, &tree -> param, 
				    owner_of (tree, rnode));
			lnode -> used = n_size;
			return res;
		}

		i = 0;
		insert_into_node (tree, &rrnode, &i, 
				  aolk (tree, lnode), NULL, lnode);
		reparent (tree, rrnode, lnode);

		i++;
		insert_into_node (tree, &rrnode, &i, 
				  aolk (tree, rnode), NULL, rnode);
		reparent (tree, rrnode, rnode);

		tree -> root = rrnode;
	}

	if (lnode -> type == BT_NT_INTERMEDIATE)
		for (i = 0; i < rnode -> used; i++)
			reparent (tree, rnode, rnode -> p [i].child);

	if (go_right) {
		*nodep = rnode;
		*idxp -= mid;
	}

	return S_CSC_OK;
}

enum s_status bt_insert (struct bt_tree *tree, bt_key_t *key, bt_data_t *data,
			 struct bt_cursor *pc)
{
	struct bt_node *node;
	int idx, lc;

	node = find_in_tree (tree, key, &idx, &lc);
	if (lc == 0) {
		if (tree -> param.destroy_data != NULL)
			tree -> param.destroy_data (tree -> param.tdata,
						    node -> p [idx].data);
		node -> p [idx].data = data;

		return S_CSC_OK;
	}

	insert_into_node (tree, &node, &idx, key, data, NULL);

	if (pc != NULL) 
		switch_node (pc, node, idx);

	fix_keys (tree, node, idx, key);

	return S_CSC_OK;
}

enum s_status bt_get (struct bt_tree *tree, bt_key_t *key, bt_data_t **data)
{
	struct bt_node *node;
	int idx, lc;

	node = find_in_tree (tree, key, &idx, &lc);
	*data = !lc ? node -> p [idx].data : NULL;

	return S_CSC_OK;
}

bt_node_data_t *bt_get_node_data (struct bt_cursor *pc)
{
	return pc -> node != NULL ? 
		pc -> node -> ndata : pc -> tree -> root -> ndata;
}

static int rotate_left (struct bt_tree *tree, struct bt_node *parent, int idx)
{
	struct bt_node *lnode, *rnode;

	if (!idx)
		return 0;

	lnode = parent -> p [idx - 1].child;
	rnode = parent -> p [idx].child;

	if (lnode -> used <= tree -> param.min_size)
		return 0;

	move (tree, rnode, 0, rnode, 1);
	rnode -> p [0] = lnode -> p [lnode -> used - 1];
	if (rnode -> type == BT_NT_INTERMEDIATE)
		reparent (tree, rnode, rnode -> p [0].child);

	memcpy (aok (tree, parent, idx - 1),
		aolk (tree, lnode), tree -> param.key_size);

	lnode -> used--;

	return 1;
}

static int rotate_right (struct bt_tree *tree, struct bt_node *parent, int idx)
{
	struct bt_node *lnode, *rnode;

	if (idx == parent -> used - 1)
		return 0;

	lnode = parent -> p [idx].child;
	rnode = parent -> p [idx + 1].child;

	if (rnode -> used <= tree -> param.min_size)
		return 0;

	lnode -> p [lnode -> used] = rnode -> p [0];
	if (rnode -> type == BT_NT_INTERMEDIATE)
		reparent (tree, lnode, lnode -> p [lnode -> used].child);
	move (tree, rnode, 1, rnode, 0);

	lnode -> used++;
	memcpy (aok (tree, parent, idx),
		aolk (tree, lnode), tree -> param.key_size);

	return 1;
}

static enum s_status delete_from_node (struct bt_tree *tree,
				       struct bt_node **nodep, int idx)
{
	struct bt_node *node;
	int i;

	node = *nodep;
	if (node -> type == BT_NT_INTERMEDIATE)
		node_unref (node -> p [idx].child, 
			    &tree -> param, ref_rown (&node -> refs));
	else if (tree -> param.destroy_data != NULL)
		tree -> param.destroy_data (tree -> param.tdata,
					    node -> p [idx].data);
       
	move (tree, node, idx + 1, node, idx);
	if (node -> parent != NULL && node -> used < tree -> param.min_size) {
		i = ion (tree, node);
		if (!rotate_left (tree, node -> parent, i) &&
		    !rotate_right (tree, node -> parent, i))
			merge (tree, &node);
	}

	*nodep = node;

	return S_CSC_OK;
}

static void merge (struct bt_tree *tree, struct bt_node **nodep)
{
	struct bt_node *lnode, *rnode, *parent;
	int i, idx;
	
	parent = (*nodep) -> parent;
	idx = ion (tree, *nodep);
	
	if (idx)
		idx--;

	lnode = parent -> p [idx].child;
	rnode = parent -> p [idx + 1].child;

	push (tree, lnode, 0, rnode, 0);
	if (lnode -> type == BT_NT_INTERMEDIATE)
		for (i = 0; i < lnode -> used; i++)
			reparent (tree, rnode, rnode -> p [i].child);
	lnode -> used = 0;

	delete_from_node (tree, &parent, idx);

	if (rnode -> parent -> used == 1) {
		node_ref (rnode, ref_rown (&tree -> refs));
		node_unref (rnode -> parent, &tree -> param,
			    ref_rown (&tree -> refs));

		tree -> root = rnode;
		rnode -> parent = NULL;
	}

	*nodep = rnode;
}

enum s_status bt_delete (struct bt_tree *tree, bt_key_t *key)
{
	struct bt_node *node;
	int idx, lc;

	node = find_in_tree (tree, key, &idx, &lc);
	if (lc)
		return S_CSC_OK;

	delete_from_node (tree, &node, idx);

	fix_node_keys (tree, node);

	return S_CSC_OK;
}

static enum s_status init_leaf (struct bt_tree *tree,
				struct bt_node **nodep,
				struct bt_imp_info *ii,
				void *closure,
				struct bt_imp_data *imps)
{
	struct bt_node *node;
	uint8_t *id;
	int i;

	node = *nodep;

	node -> used = imps -> size;
	for (i = 0; i < imps -> size; i++)
		node -> p [i].data = imps -> data [i];
	free (imps -> data);
	
	id = (uint8_t *) imps -> key;
	if (id != NULL) {
		for (i = 0; i < imps -> size; i++) {
			memcpy (aok (tree, node, i), id, 
				tree -> param.key_size);
			id += tree -> param.key_size;
		}
	}

	return S_CSC_OK;
}

static enum s_status init_intermediate (struct bt_tree *tree,
					struct bt_node **nodep,
					struct bt_imp_info *ii,
					void *closure,
					struct bt_imp_data *imps)
{
	enum s_status res;
	struct bt_node *node, *child;
	int i;

	res = S_CSC_OK;
	node = *nodep;
	for (i = 0; i < imps -> size; i++) {
		res = load_node_data (tree, node, i, ii, closure, &child);
		if (res != S_CSC_OK)
			break;

		if (!child -> used) {
			node_unref (child, &tree -> param,
				    owner_of (tree, child));
			i--;
			imps -> size--;
		} else
			node -> p [i].child = child;
	}

	if (res != S_CSC_OK) {
		while (i--) {
			child = node -> p [i].child;
			node_unref (child, &tree -> param,
				    owner_of (tree, child));
		}
		return res;
	}

	if (i == 1) {
		reparent (tree, node -> parent, child);
		node_unref (node, &tree -> param, owner_of (tree, node));
		node = child;
	} else {
		node -> used = i;
		for (i = 0; i < node -> used; i++)
			memcpy (aok (tree, node, i),
				aolk (tree, node -> p [i].child),
				tree -> param.key_size);
	}

	*nodep = node;

	return S_CSC_OK;
}

static enum s_status load_node_data (struct bt_tree *tree, 
				     struct bt_node *parent,
				     int i, struct bt_imp_info *ii,
				     void *closure,
				     struct bt_node **nodep)
{
	struct bt_imp_data imps;
	struct bt_node *node;
	enum s_status res;

	res = ii -> import (tree -> param.tdata, 
			    parent != NULL ? parent -> ndata : NULL,
			    i, &imps, closure);
	if (res != S_CSC_OK)
		return res;

	assure (tree, imps.size);

	res = node_new (&node, parent, imps.type, 
			imps.ndata, &tree -> param, get_owner (tree, parent));
	if (res != S_CSC_OK)
		return res;

	res = imps.type == BT_NT_INTERMEDIATE ?
		init_intermediate (tree, &node, ii, closure, &imps) : 
		init_leaf (tree, &node, ii, closure, &imps);

	if (res != S_CSC_OK) {
		node_unref (node, &tree -> param, get_owner (tree, parent));
		return res;
	}
	
	*nodep = node;

	return S_CSC_OK;
}

static unsigned get_depth (struct bt_tree *tree, struct bt_node *node)
{
	unsigned ml, cl;
	int i;

	if (node -> type == BT_NT_LEAF)
		return 1;

	ml = 0;
	for (i = 0; i < node -> used; i++) {
		cl = get_depth (tree, node -> p [i].child);
		if (cl > ml)
			ml = cl;
	}
		
	return ml + 1;
}

static enum s_status target_depth (struct bt_tree *tree, struct bt_node *node, 
				   unsigned depth)
{
	struct bt_node *nn;
	enum s_status res;
	int i;

	res = trim_size (tree, node);
	if (res != S_CSC_OK)
		return res;

	if (node -> type == BT_NT_LEAF) {
		for (i = 1; i < depth; i++) {
			res = node_new (&nn, node -> parent, 
					BT_NT_INTERMEDIATE, NULL,
					&tree -> param, owner_of (tree, node));
			if (res != S_CSC_OK)
				return res;

			node -> parent -> p [ion (tree, node)].child = nn;
			reparent (tree, nn, node);

			nn -> used = 1;
			nn -> p [0].child = node;
		}		
	} else {
		for (i = 0; i < node -> used; i++) {
			res = target_depth (tree, node -> p [i].child, 
					    depth - 1);
			if (res != S_CSC_OK)
				return res;
		}
	}

	return S_CSC_OK;
}

static enum s_status fix_levels (struct bt_tree *tree)
{
	
	return target_depth (tree, tree -> root,
			     get_depth (tree, tree -> root));
}

static enum s_status import (struct bt_tree *tree, struct bt_imp_info *ii,
			     void *closure)
{
	enum s_status res;

	res = load_node_data (tree, NULL, 0, ii, closure, &tree -> root);
	if (res != S_CSC_OK)
		return res;

	res = fix_levels (tree);
	if (res != S_CSC_OK)
		return res;

	return S_CSC_OK;
}

enum s_status bt_import (struct bt_tree *tree, struct bt_imp_info *ii,
			 void *closure)
{
	struct bt_node *sroot;
	struct bt_param sparam;
	enum s_status res;

	sroot = tree -> root;
	sparam = tree -> param;

	tree -> root = NULL;

	res = import (tree, ii, closure);
	if (res != S_CSC_OK) {
		tree -> root = sroot;
		tree -> param = sparam;
		return res;
	}

	node_unref (sroot, &sparam, ref_rown (&tree -> refs));

	return S_CSC_OK;
}

static enum s_status export (struct bt_tree *tree, struct bt_node *node,
			     struct bt_exp_info *ei, bt_key_t **hip,
			     va_list ap)
{
	struct bt_exp_data exps;
	bt_key_t *hi;
	enum s_status res;
	int i; 

	if (node -> type == BT_NT_INTERMEDIATE) {
		assert (node -> used);
		hi = NULL;	/* Just to make the compiler happy */
		for (i = 0; i < node -> used; i++) {
			res = export (tree, node -> p [i].child, ei, &hi, ap);
			if (res != S_CSC_OK)
				return res;
		}
	} else
		hi = aok (tree, node, node -> used - 1);

	exps.type = node -> type;
	exps.size = node -> used;
	exps.ndata = node -> ndata;
	exps.parent = node -> parent != NULL ? node -> parent -> ndata : NULL;
	exps.lo = aok (tree, node, 0);
	exps.hi = hi;
	if (node -> type == BT_NT_INTERMEDIATE) {
		exps.child = calloc (node -> used, 
					sizeof (struct bt_node_data *));
		if (exps.child == NULL)
			return S_CSC_OUT_OF_MEMORY;
		for (i = 0; i < node -> used; i++)
			exps.child [i] = node -> p [i].child -> ndata;
		exps.data = NULL;
	} else {
		exps.child = NULL;
		exps.data = calloc (node -> used, 
					sizeof (bt_data_t *));
		if (exps.data == NULL)
			return S_CSC_OUT_OF_MEMORY;
		for (i = 0; i < node -> used; i++)
			exps.data [i] = node -> p [i].data;
	}

	res = ei -> export (&tree -> param.tdata, &exps, ap);
	if (exps.child != NULL)
		free (exps.child);
	if (exps.data != NULL)
		free (exps.data);
	if (res != S_CSC_OK)
		return res;

	*hip = hi;

	return S_CSC_OK;
}

enum s_status bt_export (struct bt_tree *tree, struct bt_exp_info *ei, ...)
{
	bt_key_t *hi;
	enum s_status res;
	va_list ap;

	va_start (ap, ei);
	res = export (tree, tree -> root, ei, &hi, ap);
	va_end (ap);
		
	return res;
}

static void rekey (struct bt_tree *tree, struct bt_node *node, int idx,
		   bt_rekey_f rfun, int *seq, void *closure)
{
	int i;

	if (node -> type == BT_NT_INTERMEDIATE) {
		for (i = 0; i < node -> used; i++) {
			rekey (tree, node -> p [i].child, 
			       0, rfun, seq, closure);
			memcpy (aok (tree, node, i),
				aolk (tree, node -> p [i].child),
				tree -> param.key_size);
		}
	} else
		for (i = idx; i < node -> used; i++)
			rfun (node -> p [i].data, aok (tree, node, i), 
			      (*seq)++, closure);
}

void bt_rekey (struct bt_tree *tree, bt_rekey_f rfun, void *closure)
{
	bt_rekey_from (tree, NULL, rfun, closure);
}

void bt_rekey_from (struct bt_tree *tree, struct bt_cursor *pc,
		    bt_rekey_f rfun, void *closure)
{
	struct bt_node *node;
	int idx, n;

	if (pc != NULL && pc -> node != NULL) {
		node = pc -> node;
		idx = pc -> idx;
	} else {
		node = tree -> root;
		idx = 0;
	}
	
	n = 0;
	rekey (tree, node, idx, rfun, &n, closure);
}

enum s_status bt_cursor_init (struct bt_tree *tree, struct bt_cursor **pcp,
			      struct ref_owner *p, int *eof)
{
	struct bt_cursor *pc;
	int ans;

	pc = malloc (sizeof (struct bt_cursor));
	if (pc == NULL)
		return S_CSC_OUT_OF_MEMORY;
	memset (pc, 0, sizeof (struct bt_cursor));

	ref_init (&pc -> refs, "bt_cursor", p);

	pc -> tree = tree;
	pc -> node = NULL;

	ans = !bt_cursor_first (pc);
	if (eof != NULL)
		*eof = ans;

	*pcp = pc;
		
	return S_CSC_OK;
}

static void switch_node (struct bt_cursor *pc, struct bt_node *node, int idx)
{
	if (pc -> node != NULL)
		node_unref (pc -> node, &pc -> tree -> param, 
			    ref_rown (&pc -> refs));
	pc -> node = node;
	pc -> idx = idx;
	
	if (node != NULL)
		node_ref (pc -> node, ref_rown (&pc -> refs));
}

int bt_cursor_goto (struct bt_cursor *pc, bt_key_t *key)
{
	struct bt_node *node;
	int idx, lcp;

	node = find_in_tree (pc -> tree, key, &idx, &lcp);
	if (lcp)
		return 0;

	switch_node (pc, node, idx);

	return 1;
}

int bt_cursor_first (struct bt_cursor *pc)
{
	struct bt_node *node;

	node = pc -> tree -> root;
	while (1) {
		if (!node -> used) 
			return 0;
		
		if (node -> type == BT_NT_LEAF)
			break;

		node = node -> p [0].child;
	}

	switch_node (pc, node, 0);

	return 1;
}

int bt_cursor_last (struct bt_cursor *pc)
{
	struct bt_node *node;

	node = pc -> tree -> root;
	while (1) {
		if (!node -> used)
			return 0;
		
		if (node -> type == BT_NT_LEAF)
			break;

		node = node -> p [node -> used - 1].child;
	}

	switch_node (pc, node, node -> used - 1);

	return 1;
}

int bt_cursor_prev (struct bt_cursor *pc)
{
	struct bt_node *node;
	int idx;

	node = pc -> node;
	idx = pc -> idx;
	while (node -> parent != NULL && !idx) {
		idx = ion (pc -> tree, node);
		node = node -> parent;
	}

	if (idx >= node -> used - 1)
		return 0;

	while (node -> type == BT_NT_INTERMEDIATE) {
		node = node -> p [idx - 1].child;
		idx = node -> used;
	}

	switch_node (pc, node, idx - 1);

	return 1;
}

int bt_cursor_next (struct bt_cursor *pc)
{
	struct bt_node *node;
	int idx;

	node = pc -> node;
	idx = pc -> idx;

	if (node == NULL)
		return bt_cursor_first (pc);

	while (node -> parent != NULL && idx >= node -> used - 1) {
		idx = ion (pc -> tree, node);
		node = node -> parent;
	}

	if (idx >= node -> used - 1)
		return 0;

	while (node -> type == BT_NT_INTERMEDIATE) {
		node = node -> p [idx + 1].child;
		idx = -1;
	}

	switch_node (pc, node, idx + 1);

	return 1;
}

void bt_cursor_ref (struct bt_cursor *pc, struct ref_owner *p)
{
	ref_up (&pc -> refs, p);
}

void bt_cursor_unref (struct bt_cursor *pc, struct ref_owner *p)
{
	if (ref_down (&pc -> refs, p))
		return;

	switch_node (pc, NULL, 0);

	ref_zero (&pc -> refs);

	free (pc);
}

bt_data_t *bt_cursor_get (struct bt_cursor *pc)
{
	return pc -> node != NULL ?
		pc -> node -> p [pc -> idx].data : NULL;
}

bt_data_t *bt_cursor_get_key (struct bt_cursor *pc)
{
	return pc -> node != NULL ?
		aok (pc -> tree, pc -> node, pc -> idx) : NULL;
}

static enum s_status traverse (struct bt_tree *tree, struct bt_node *node,
			       bt_traverse_f tfun, va_list ap)
{
	enum s_status res;
	int i;

	if (node -> type == BT_NT_INTERMEDIATE) {
		for (i = 0; i < node -> used; i++) {
			res = traverse (tree, node -> p [i].child, tfun, ap);
			if (res != S_CSC_OK)
				return res;
		} 
	} else {
		for (i = 0; i < node -> used; i++) {
			res = tfun (node -> ndata, node -> p [i].data, ap);
			if (res != S_CSC_OK)
				return res;
		} 
	}

	res = tfun (node -> ndata, NULL, ap);
	if (res != S_CSC_OK)
		return res;

	return S_CSC_OK;
}

enum s_status bt_traverse (struct bt_tree *tree, bt_traverse_f tfun, ...)
{
	enum s_status res;
	va_list ap;

	va_start (ap, tfun);
	res = traverse (tree, tree -> root, tfun, ap);
	va_end (ap);

	return res;
}