#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <grass/btree.h>

static void *store(const void *, int);

int btree_update(BTREE * B,
		 const void *key, int keylen, const void *data, int datalen)
{
    int p = 0;
    int q;
    int N;
    int (*cmp) ();
    int dir;

    /* first node is special case */
    N = B->N;
    if (N == 0) {
	N = B->N = 1;
	B->node[N].key = store(key, keylen);
	B->node[N].data = store(data, datalen);
	B->node[N].left = 0;
	B->node[N].right = 0;
	if (B->node[N].key && B->node[N].data)
	    return 1;
	else
	    return 0;
    }

    cmp = B->cmp;

    q = 1;
    while (q > 0) {
	p = q;
	dir = (*cmp) (B->node[q].key, key);
	if (dir == 0) {
	    free(B->node[q].data);
	    return ((B->node[q].data = store(data, datalen))) ? 1 : 0;
	}
	if (dir > 0)
	    q = B->node[q].left;	/* go left */
	else
	    q = B->node[q].right;	/* go right */
    }

    /* new node */
    B->N++;
    N = B->N;

    /* grow the tree? */
    if (N >= B->tlen) {
	B->node =
	    (BTREE_NODE *) realloc(B->node,
				   sizeof(BTREE_NODE) * (B->tlen += B->incr));
	if (B->node == NULL)
	    return 0;
    }

    /* add node to tree */
    B->node[N].key = store(key, keylen);
    B->node[N].data = store(data, datalen);
    B->node[N].left = 0;

    if (dir > 0) {
	B->node[N].right = -p;	/* create thread */
	B->node[p].left = N;	/* insert left */
    }
    else {
	B->node[N].right = B->node[p].right;	/* copy right link/thread */
	B->node[p].right = N;	/* add right */
    }
    return 1;
}

static void *store(const void *s, int n)
{
    void *b;

    if (n <= 0)
	return NULL;

    b = malloc(n);
    if (b == NULL)
	return b;

    memcpy(b, s, n);

    return b;
}