btree/update.c

Go to the documentation of this file.

#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)(const void *, const void *);
    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;
}