GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
btree/update.c
Go to the documentation of this file.
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <grass/btree.h>
5 
6 static void *store(const void *, int);
7 
9  const void *key, int keylen, const void *data, int datalen)
10 {
11  int p = 0;
12  int q;
13  int N;
14  int (*cmp) ();
15  int dir;
16 
17  /* first node is special case */
18  N = B->N;
19  if (N == 0) {
20  N = B->N = 1;
21  B->node[N].key = store(key, keylen);
22  B->node[N].data = store(data, datalen);
23  B->node[N].left = 0;
24  B->node[N].right = 0;
25  if (B->node[N].key && B->node[N].data)
26  return 1;
27  else
28  return 0;
29  }
30 
31  cmp = B->cmp;
32 
33  q = 1;
34  while (q > 0) {
35  p = q;
36  dir = (*cmp) (B->node[q].key, key);
37  if (dir == 0) {
38  free(B->node[q].data);
39  return ((B->node[q].data = store(data, datalen))) ? 1 : 0;
40  }
41  if (dir > 0)
42  q = B->node[q].left; /* go left */
43  else
44  q = B->node[q].right; /* go right */
45  }
46 
47  /* new node */
48  B->N++;
49  N = B->N;
50 
51  /* grow the tree? */
52  if (N >= B->tlen) {
53  B->node =
54  (BTREE_NODE *) realloc(B->node,
55  sizeof(BTREE_NODE) * (B->tlen += B->incr));
56  if (B->node == NULL)
57  return 0;
58  }
59 
60  /* add node to tree */
61  B->node[N].key = store(key, keylen);
62  B->node[N].data = store(data, datalen);
63  B->node[N].left = 0;
64 
65  if (dir > 0) {
66  B->node[N].right = -p; /* create thread */
67  B->node[p].left = N; /* insert left */
68  }
69  else {
70  B->node[N].right = B->node[p].right; /* copy right link/thread */
71  B->node[p].right = N; /* add right */
72  }
73  return 1;
74 }
75 
76 static void *store(const void *s, int n)
77 {
78  void *b;
79 
80  if (n <= 0)
81  return NULL;
82 
83  b = malloc(n);
84  if (b == NULL)
85  return b;
86 
87  memcpy(b, s, n);
88 
89  return b;
90 }
int btree_update(BTREE *B, const void *key, int keylen, const void *data, int datalen)
Definition: btree/update.c:8
int N
Definition: btree.h:16
int incr
Definition: btree.h:17
int left
Definition: btree.h:8
#define N
Definition: e_intersect.c:917
void free(void *)
#define NULL
Definition: ccmath.h:32
void * malloc(YYSIZE_T)
Definition: btree.h:12
double b
Definition: r_raster.c:39
void * key
Definition: btree.h:6
int(* cmp)(const void *, const void *)
Definition: btree.h:19
void * data
Definition: btree.h:7
BTREE_NODE * node
Definition: btree.h:14
int tlen
Definition: btree.h:15
int right
Definition: btree.h:9