GRASS Programmer's Manual
6.4.2(2012)
|
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 }