GRASS Programmer's Manual  6.4.2(2012)
btree/update.c
Go to the documentation of this file.
00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 #include <string.h>
00004 #include <grass/btree.h>
00005 
00006 static void *store(const void *, int);
00007 
00008 int btree_update(BTREE * B,
00009                  const void *key, int keylen, const void *data, int datalen)
00010 {
00011     int p = 0;
00012     int q;
00013     int N;
00014     int (*cmp) ();
00015     int dir;
00016 
00017     /* first node is special case */
00018     N = B->N;
00019     if (N == 0) {
00020         N = B->N = 1;
00021         B->node[N].key = store(key, keylen);
00022         B->node[N].data = store(data, datalen);
00023         B->node[N].left = 0;
00024         B->node[N].right = 0;
00025         if (B->node[N].key && B->node[N].data)
00026             return 1;
00027         else
00028             return 0;
00029     }
00030 
00031     cmp = B->cmp;
00032 
00033     q = 1;
00034     while (q > 0) {
00035         p = q;
00036         dir = (*cmp) (B->node[q].key, key);
00037         if (dir == 0) {
00038             free(B->node[q].data);
00039             return ((B->node[q].data = store(data, datalen))) ? 1 : 0;
00040         }
00041         if (dir > 0)
00042             q = B->node[q].left;        /* go left */
00043         else
00044             q = B->node[q].right;       /* go right */
00045     }
00046 
00047     /* new node */
00048     B->N++;
00049     N = B->N;
00050 
00051     /* grow the tree? */
00052     if (N >= B->tlen) {
00053         B->node =
00054             (BTREE_NODE *) realloc(B->node,
00055                                    sizeof(BTREE_NODE) * (B->tlen += B->incr));
00056         if (B->node == NULL)
00057             return 0;
00058     }
00059 
00060     /* add node to tree */
00061     B->node[N].key = store(key, keylen);
00062     B->node[N].data = store(data, datalen);
00063     B->node[N].left = 0;
00064 
00065     if (dir > 0) {
00066         B->node[N].right = -p;  /* create thread */
00067         B->node[p].left = N;    /* insert left */
00068     }
00069     else {
00070         B->node[N].right = B->node[p].right;    /* copy right link/thread */
00071         B->node[p].right = N;   /* add right */
00072     }
00073     return 1;
00074 }
00075 
00076 static void *store(const void *s, int n)
00077 {
00078     void *b;
00079 
00080     if (n <= 0)
00081         return NULL;
00082 
00083     b = malloc(n);
00084     if (b == NULL)
00085         return b;
00086 
00087     memcpy(b, s, n);
00088 
00089     return b;
00090 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines