GRASS GIS 7 Programmer's Manual
7.9.dev(2021)-e5379bbd7
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
8
int
btree_update
(
BTREE
* B,
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
}
btree_update
int btree_update(BTREE *B, const void *key, int keylen, const void *data, int datalen)
Definition:
btree/update.c:8
btree.h
BTREE_NODE
Definition:
btree.h:4
BTREE::N
int N
Definition:
btree.h:16
BTREE::incr
int incr
Definition:
btree.h:17
BTREE_NODE::left
int left
Definition:
btree.h:8
N
#define N
Definition:
e_intersect.c:923
free
void free(void *)
NULL
#define NULL
Definition:
ccmath.h:32
malloc
void * malloc(YYSIZE_T)
BTREE
Definition:
btree.h:12
b
double b
Definition:
r_raster.c:39
BTREE_NODE::key
void * key
Definition:
btree.h:6
BTREE::cmp
int(* cmp)(const void *, const void *)
Definition:
btree.h:19
BTREE_NODE::data
void * data
Definition:
btree.h:7
BTREE::node
BTREE_NODE * node
Definition:
btree.h:14
BTREE::tlen
int tlen
Definition:
btree.h:15
BTREE_NODE::right
int right
Definition:
btree.h:9
lib
btree
update.c
Generated on Mon May 31 2021 05:21:32 for GRASS GIS 7 Programmer's Manual by
1.8.13