grass  7.8.6
About: GRASS (Geographic Resources Analysis Support System) is a raster- and vector-based GIS, image processing system, graphics production system and spatial modeling system.
  Fossies Dox: grass-7.8.6.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

io.c
Go to the documentation of this file.
1
2/****************************************************************************
3* MODULE: R-Tree library
4*
5* AUTHOR(S): Antonin Guttman - original code
6* Daniel Green (green@superliminal.com) - major clean-up
7* and implementation of bounding spheres
8* Markus Metz - file-based and memory-based R*-tree
9*
10* PURPOSE: Multidimensional index
11*
12* COPYRIGHT: (C) 2001 by the GRASS Development Team
13*
14* This program is free software under the GNU General Public
15* License (>=v2). Read the file COPYING that comes with GRASS
16* for details.
17*****************************************************************************/
18
19#include <stdlib.h>
20#include <stdio.h>
21#include <string.h>
22#include <sys/types.h>
23#include <unistd.h>
24#include <assert.h>
25#include <errno.h>
26#include <grass/gis.h>
27#include "index.h"
28
29/* #define USAGE_SWAP */
30
31/* add new free node position for recycling */
32void RTreeAddNodePos(off_t pos, int level, struct RTree *t)
33{
34 int which, i;
35
36 if (t->free_nodes.avail >= t->free_nodes.alloc) {
37 size_t size;
38
39 t->free_nodes.alloc += 100;
40 size = t->free_nodes.alloc * sizeof(off_t);
41 t->free_nodes.pos = (off_t *)realloc((void *)t->free_nodes.pos, size);
42 assert(t->free_nodes.pos);
43 }
44 t->free_nodes.pos[t->free_nodes.avail++] = pos;
45
46 /* check mru first */
47 i = 0;
48 while (t->nb[level][t->used[level][i]].pos != pos &&
50 i++;
51
52 /* is it possible that this node is not in the buffer? */
54 which = t->used[level][i];
55 t->nb[level][which].pos = -1;
56 t->nb[level][which].dirty = 0;
57
58 /* make it lru */
59 if (i < NODE_BUFFER_SIZE - 1) { /* which != t->used[level][NODE_BUFFER_SIZE - 1] */
60 /* simple swap does not work here */
61 while (i < NODE_BUFFER_SIZE - 1 &&
62 t->nb[level][t->used[level][i + 1]].pos != -1) {
63 t->used[level][i] = t->used[level][i + 1];
64 i++;
65 }
67 t->used[level][i] = which;
68 }
69}
70
71/* look for free node position, set file pointer, return position */
72off_t RTreeGetNodePos(struct RTree *t)
73{
74 if (t->free_nodes.avail > 0) {
75 t->free_nodes.avail--;
76 return lseek(t->fd, t->free_nodes.pos[t->free_nodes.avail], SEEK_SET);
77 }
78 else {
79 return lseek(t->fd, 0, SEEK_END);
80 }
81}
82
83/* read branch from file */
84size_t RTreeReadBranch(struct RTree_Branch *b, struct RTree *t)
85{
86 size_t size = 0;
87
88 size += read(t->fd, b->rect.boundary, t->rectsize);
89 size += read(t->fd, &(b->child), sizeof(union RTree_Child));
90
91 return size;
92}
93
94/* read node from file */
95size_t RTreeReadNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
96{
97 int i;
98 size_t size = 0;
99
100 lseek(t->fd, nodepos, SEEK_SET);
101 size += read(t->fd, &(n->count), sizeof(int));
102 size += read(t->fd, &(n->level), sizeof(int));
103
104 for (i = 0; i < MAXCARD; i++) {
105 size += RTreeReadBranch(&(n->branch[i]), t);
106 }
107
108 return size;
109}
110
111/* get node from buffer or file */
112struct RTree_Node *RTreeGetNode(off_t nodepos, int level, struct RTree *t)
113{
114 int which, i = 0;
115
116 /* check mru first */
117 while (t->nb[level][t->used[level][i]].pos != nodepos &&
118 t->nb[level][t->used[level][i]].pos >= 0 &&
119 i < NODE_BUFFER_SIZE - 1)
120 i++;
121
122 which = t->used[level][i];
123
124 if (t->nb[level][which].pos != nodepos) {
125 /* rewrite node in buffer */
126 if (t->nb[level][which].dirty) {
127 RTreeRewriteNode(&(t->nb[level][which].n),
128 t->nb[level][which].pos, t);
129 t->nb[level][which].dirty = 0;
130 }
131 RTreeReadNode(&(t->nb[level][which].n), nodepos, t);
132 t->nb[level][which].pos = nodepos;
133 }
134 /* make it mru */
135 if (i) { /* t->used[level][0] != which */
136#ifdef USAGE_SWAP
137 t->used[level][i] = t->used[level][0];
138 t->used[level][0] = which;
139#else
140 while (i) {
141 t->used[level][i] = t->used[level][i - 1];
142 i--;
143 }
144 t->used[level][0] = which;
145#endif
146 }
147
148 /* RTreeCopyNode(n, &(t->nb[level][which].n), t); */
149
150 return &(t->nb[level][which].n);
151}
152
153/* write branch to file */
154size_t RTreeWriteBranch(struct RTree_Branch *b, struct RTree *t)
155{
156 size_t size = 0;
157
158 if (write(t->fd, b->rect.boundary, t->rectsize) != t->rectsize)
159 G_fatal_error("RTreeWriteBranch(): Unable to write (%s)", strerror(errno));
160 size += t->rectsize;
161 if (write(t->fd, &(b->child), sizeof(union RTree_Child)) != sizeof(union RTree_Child))
162 G_fatal_error("RTreeWriteBranch(): Unable to write (%s)", strerror(errno));
163 size += sizeof(union RTree_Child);
164
165 return size;
166}
167
168/* write new node to file */
169size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
170{
171 int i;
172 size_t size = 0;
173
174 /* file position must be set first with RTreeGetFNodePos() */
175 if (write(t->fd, &(n->count), sizeof(int)) != sizeof(int))
176 G_fatal_error("RTreeWriteNode(): Unable to write (%s)", strerror(errno));
177 size += sizeof(int);
178 if (write(t->fd, &(n->level), sizeof(int)) != sizeof(int))
179 G_fatal_error("RTreeWriteNode(): Unable to write (%s)", strerror(errno));
180 size += sizeof(int);
181
182 for (i = 0; i < MAXCARD; i++) {
183 size += RTreeWriteBranch(&(n->branch[i]), t);
184 }
185
186 return size;
187}
188
189/* rewrite updated node to file */
190size_t RTreeRewriteNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
191{
192 lseek(t->fd, nodepos, SEEK_SET);
193
194 return RTreeWriteNode(n, t);
195}
196
197/* mark node in buffer as changed */
198void RTreeNodeChanged(struct RTree_Node *n, off_t nodepos, struct RTree *t)
199{
200 int which, i = 0;
201
202 /* check mru first */
203 while (t->nb[n->level][t->used[n->level][i]].pos != nodepos &&
205 i++;
206
208 /* as it is used, it should always be mru */
209 assert(i == 0);
210 which = t->used[n->level][i];
211
212 t->nb[n->level][which].dirty = 1;
213
214 /* make it mru */
215 if (i) { /* t->used[level][0] != which */
216#ifdef USAGE_SWAP
217 t->used[n->level][i] = t->used[n->level][0];
218 t->used[n->level][0] = which;
219#else
220 while (i) {
221 t->used[n->level][i] = t->used[n->level][i - 1];
222 i--;
223 }
224 t->used[n->level][0] = which;
225#endif
226 }
227}
228
229/* flush pending changes to file */
231{
232 int i, j;
233
234 for (i = 0; i <= t->rootlevel; i++) {
235 for (j = 0; j < NODE_BUFFER_SIZE; j++) {
236 if (t->nb[i][j].dirty) {
237 RTreeRewriteNode(&(t->nb[i][j].n), t->nb[i][j].pos, t);
238 t->nb[i][j].dirty = 0;
239 }
240 }
241 }
242}
void G_fatal_error(const char *msg,...)
Print a fatal error message to stderr.
Definition: error.c:160
off_t RTreeGetNodePos(struct RTree *t)
Definition: io.c:72
void RTreeNodeChanged(struct RTree_Node *n, off_t nodepos, struct RTree *t)
Definition: io.c:198
size_t RTreeWriteBranch(struct RTree_Branch *b, struct RTree *t)
Definition: io.c:154
size_t RTreeReadNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
Definition: io.c:95
void RTreeFlushBuffer(struct RTree *t)
Definition: io.c:230
size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
Definition: io.c:169
size_t RTreeRewriteNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
Definition: io.c:190
struct RTree_Node * RTreeGetNode(off_t nodepos, int level, struct RTree *t)
Definition: io.c:112
void RTreeAddNodePos(off_t pos, int level, struct RTree *t)
Definition: io.c:32
size_t RTreeReadBranch(struct RTree_Branch *b, struct RTree *t)
Definition: io.c:84
#define assert(condition)
Definition: lz4.c:324
double b
Definition: r_raster.c:39
double t
Definition: r_raster.c:39
#define MAXCARD
Definition: rtree.h:46
#define NODE_BUFFER_SIZE
Definition: rtree.h:55
int count
Definition: rtree.h:79
int level
Definition: rtree.h:80
struct RTree_Branch * branch
Definition: rtree.h:81
Definition: rtree.h:129