GRASS 8 Programmer's Manual 8.6.0dev(2026)-4bb960b182
Loading...
Searching...
No Matches
spindex_rw.c
Go to the documentation of this file.
1/*!
2 \file diglib/spindex.c
3
4 \brief Vector library - spatial index - read/write (lower level functions)
5
6 Lower level functions for reading/writing/manipulating vectors.
7
8 SPDX-FileCopyrightText: 2001-2009 GRASS Development Team
9 SPDX-License-Identifier: GPL-2.0-or-later
10
11 \author Original author CERL, probably Dave Gerdes
12 \author Update to GRASS 5.7 Radim Blazek
13 \author Update to GRASS 7 Markus Metz
14 */
15
16#include <inttypes.h>
17#include <sys/types.h>
18#include <stdlib.h>
19#include <string.h>
20#include <unistd.h>
21#include <assert.h>
22#include <grass/vector.h>
23#include <grass/glocale.h>
24#include <grass/version.h>
25
26/* TODO: only write out actually used sides */
27#ifndef NUMSIDES
28#define NUMSIDES 6
29#endif
30
31/* TODO: merge these two */
32struct spidxstack {
33 off_t pos[MAXCARD]; /* file position of child node, object ID on level 0 */
34 struct RTree_Node sn; /* stack node */
35 int branch_id; /* branch no to follow down */
36};
37
38struct spidxpstack {
39 off_t pos[MAXCARD]; /* file position of child node, object ID on level 0 */
40 struct RTree_Node *sn; /* stack node pointer */
41 int branch_id; /* branch no to follow down */
42};
43
44/*!
45 \brief Write spatial index header to file
46
47 \param[in,out] fp pointer to struct gvfile
48 \param ptr pointer to Plus_head structure
49
50 \return 0 on success
51 \return -1 on error
52 */
53int dig_Wr_spidx_head(struct gvfile *fp, struct Plus_head *ptr)
54{
55 unsigned char buf[6];
56 long length = 81; /* header length in bytes */
57 struct RTree *t;
58
59 dig_rewind(fp);
60 dig_set_cur_port(&(ptr->spidx_port));
61
62 /* use ptr->off_t_size = 4 if possible */
63 if (sizeof(off_t) > 4) {
64 off_t size;
65
66 size = 145; /* max header size, see below */
67 size += (off_t)ptr->Node_spidx->n_nodes * ptr->Node_spidx->nodesize;
68 size += (off_t)ptr->Line_spidx->n_nodes * ptr->Line_spidx->nodesize;
69 size += (off_t)ptr->Area_spidx->n_nodes * ptr->Area_spidx->nodesize;
70 size += (off_t)ptr->Isle_spidx->n_nodes * ptr->Isle_spidx->nodesize;
71
72 if (size < PORT_INT_MAX)
73 ptr->spidx_port.off_t_size = 4;
74 else
75 ptr->spidx_port.off_t_size = 8;
76 }
77 else
78 ptr->spidx_port.off_t_size = 4;
79
80 /* bytes 1 - 6 */
81 buf[0] = GV_SIDX_VER_MAJOR;
82 buf[1] = GV_SIDX_VER_MINOR;
83 buf[2] = GV_SIDX_EARLIEST_MAJOR;
84 buf[3] = GV_SIDX_EARLIEST_MINOR;
85 buf[4] = ptr->spidx_port.byte_order;
86 buf[5] = (unsigned char)ptr->spidx_port.off_t_size;
87 if (0 >= dig__fwrite_port_C((const char *)buf, 6, fp))
88 return (-1);
89
90 /* adjust header size for large files */
91 if (ptr->spidx_port.off_t_size == 4) {
92 if (ptr->off_t_size == 4)
93 length = 113;
94 else if (ptr->off_t_size == 8)
95 length = 117;
96 else
97 G_fatal_error(
98 _("Topology file must be written before spatial index file"));
99 }
100 else if (ptr->spidx_port.off_t_size == 8) {
101 if (ptr->off_t_size == 4)
102 length = 141;
103 else if (ptr->off_t_size == 8)
104 length = 145;
105 else
106 G_fatal_error(
107 _("Topology file must be written before spatial index file"));
108 }
109
110 /* bytes 7 - 10 : header size */
111 if (0 >= dig__fwrite_port_L(&length, 1, fp))
112 return (0);
113
114 ptr->spidx_head_size = length;
115
116 /* byte 11 : dimension 2D or 3D */
117 buf[0] = ptr->spidx_with_z;
118 if (0 >= dig__fwrite_port_C((const char *)buf, 1, fp))
119 return (-1);
120
121 /* identical for all spatial indices: */
122 t = ptr->Node_spidx;
123 /* byte 12 : n dimensions */
124 if (0 >= dig__fwrite_port_C((const char *)&(t->ndims), 1, fp))
125 return (-1);
126 /* byte 13 : n sides */
127 if (0 >= dig__fwrite_port_C((const char *)&(t->nsides), 1, fp))
128 return (-1);
129 /* bytes 14 - 17 : nodesize */
130 if (0 >= dig__fwrite_port_I(&(t->nodesize), 1, fp))
131 return (-1);
132 /* bytes 18 - 21 : nodecard */
133 if (0 >= dig__fwrite_port_I(&(t->nodecard), 1, fp))
134 return (-1);
135 /* bytes 22 - 25 : leafcard */
136 if (0 >= dig__fwrite_port_I(&(t->leafcard), 1, fp))
137 return (-1);
138 /* bytes 26 - 29 : min node fill */
139 if (0 >= dig__fwrite_port_I(&(t->min_node_fill), 1, fp))
140 return (-1);
141 /* bytes 30 - 33 : min leaf fill */
142 if (0 >= dig__fwrite_port_I(&(t->min_leaf_fill), 1, fp))
143 return (-1);
144
145 /* for each spatial index : */
146
147 /* Node spatial index */
148 /* bytes 34 - 37 : n nodes */
149 if (0 >= dig__fwrite_port_I((const int *)&(t->n_nodes), 1, fp))
150 return (-1);
151 /* bytes 38 - 41 : n leafs */
152 if (0 >= dig__fwrite_port_I((const int *)&(t->n_leafs), 1, fp))
153 return (-1);
154 /* bytes 42 - 45 : n levels */
155 if (0 >= dig__fwrite_port_I(&(t->rootlevel), 1, fp))
156 return (-1);
157 /* bytes 46 - 49 (LFS 53) : root node offset */
158 if (0 >= dig__fwrite_port_O(&(ptr->Node_spidx_offset), 1, fp,
159 ptr->spidx_port.off_t_size))
160 return (-1);
161
162 /* Line spatial index */
163 t = ptr->Line_spidx;
164 /* bytes 50 - 53 (LFS 54 - 57) : n nodes */
165 if (0 >= dig__fwrite_port_I((const int *)&(t->n_nodes), 1, fp))
166 return (-1);
167 /* bytes 54 - 57 (LFS 58 - 61) : n leafs */
168 if (0 >= dig__fwrite_port_I((const int *)&(t->n_leafs), 1, fp))
169 return (-1);
170 /* bytes 58 - 61 (LFS 62 - 65) : n levels */
171 if (0 >= dig__fwrite_port_I(&(t->rootlevel), 1, fp))
172 return (-1);
173 /* bytes 62 - 65 (LFS 66 - 73) : root node offset */
174 if (0 >= dig__fwrite_port_O(&(ptr->Line_spidx_offset), 1, fp,
175 ptr->spidx_port.off_t_size))
176 return (-1);
177
178 /* Area spatial index */
179 t = ptr->Area_spidx;
180 /* bytes 66 - 69 (LFS 74 - 77) : n nodes */
181 if (0 >= dig__fwrite_port_I((const int *)&(t->n_nodes), 1, fp))
182 return (-1);
183 /* bytes 70 - 73 (LFS 78 - 81) : n leafs */
184 if (0 >= dig__fwrite_port_I((const int *)&(t->n_leafs), 1, fp))
185 return (-1);
186 /* bytes 74 - 77 (LFS 82 - 85) : n levels */
187 if (0 >= dig__fwrite_port_I(&(t->rootlevel), 1, fp))
188 return (-1);
189 /* bytes 78 - 81 (LFS 86 - 93) : root node offset */
190 if (0 >= dig__fwrite_port_O(&(ptr->Area_spidx_offset), 1, fp,
191 ptr->spidx_port.off_t_size))
192 return (-1);
193
194 /* Isle spatial index */
195 t = ptr->Isle_spidx;
196 /* bytes 82 - 85 (LFS 94 - 97) : n nodes */
197 if (0 >= dig__fwrite_port_I((const int *)&(t->n_nodes), 1, fp))
198 return (-1);
199 /* bytes 86 - 89 (LFS 98 - 101) : n leafs */
200 if (0 >= dig__fwrite_port_I((const int *)&(t->n_leafs), 1, fp))
201 return (-1);
202 /* bytes 90 - 93 (LFS 102 - 105) : n levels */
203 if (0 >= dig__fwrite_port_I(&(t->rootlevel), 1, fp))
204 return (-1);
205 /* bytes 94 - 97 (LFS 106 - 113) : root node offset */
206 if (0 >= dig__fwrite_port_O(&(ptr->Isle_spidx_offset), 1, fp,
207 ptr->spidx_port.off_t_size))
208 return (-1);
209
210 /* 3D future : */
211 /* Face spatial index */
212 /* bytes 98 - 101 (LFS 114 - 121) : root node offset */
213 if (0 >= dig__fwrite_port_O(&(ptr->Face_spidx_offset), 1, fp,
214 ptr->spidx_port.off_t_size))
215 return (-1);
216 /* ptr->Face_spidx->rootpos = ptr->Face_spidx_offset; */
217
218 /* Volume spatial index */
219 /* bytes 102 - 105 (LFS 122 - 129) : root node offset */
220 if (0 >= dig__fwrite_port_O(&(ptr->Volume_spidx_offset), 1, fp,
221 ptr->spidx_port.off_t_size))
222 return (-1);
223 /* ptr->Volume_spidx->rootpos = ptr->Volume_spidx_offset; */
224
225 /* Hole spatial index */
226 /* bytes 106 - 109 (LFS 130 - 137) : root node offset */
227 if (0 >= dig__fwrite_port_O(&(ptr->Hole_spidx_offset), 1, fp,
228 ptr->spidx_port.off_t_size))
229 return (-1);
230 /* ptr->Hole_spidx->rootpos = ptr->Hole_spidx_offset; */
231
232 G_debug(3, "spidx offset node = %lu line = %lu, area = %lu isle = %lu",
233 (long unsigned)ptr->Node_spidx_offset,
234 (long unsigned)ptr->Line_spidx_offset,
235 (long unsigned)ptr->Area_spidx_offset,
236 (long unsigned)ptr->Isle_spidx_offset);
237
238 /* coor file size : bytes 110 - 113 (117) (LFS: 138 - 141 (145)) */
239 if (0 >= dig__fwrite_port_O(&(ptr->coor_size), 1, fp, ptr->off_t_size))
240 return (-1);
241
242 length = (long unsigned)dig_ftell(fp);
243 G_debug(1, "spidx body offset %lu", length);
244
245 if (ptr->spidx_head_size != length)
246 G_fatal_error("wrong sidx head length %ld", ptr->spidx_head_size);
247
248 return (0);
249}
250
251/*!
252 \brief Read spatial index header from sidx file
253
254 \param fp pointer to struct gvfile
255 \param[in,out] ptr pointer to Plus_head structure
256
257 \return 0 on success
258 \return -1 on error
259 */
260int dig_Rd_spidx_head(struct gvfile *fp, struct Plus_head *ptr)
261{
262 unsigned char buf[6];
263 int byte_order;
264 struct RTree *t;
265
266 dig_rewind(fp);
267
268 /* bytes 1 - 6 */
269 if (0 >= dig__fread_port_C((char *)buf, 6, fp))
270 return (-1);
271 ptr->version.spidx.major = buf[0];
272 ptr->version.spidx.minor = buf[1];
273 ptr->version.spidx.back_major = buf[2];
274 ptr->version.spidx.back_minor = buf[3];
275 byte_order = buf[4];
276 ptr->spidx_port.off_t_size = buf[5];
277
278 G_debug(
279 2,
280 "Spidx header: file version %d.%d , supported from GRASS version %d.%d",
281 ptr->version.spidx.major, ptr->version.spidx.minor,
282 ptr->version.spidx.back_major, ptr->version.spidx.back_minor);
283
284 G_debug(2, " byte order %d", byte_order);
285 G_debug(2, " off_t size %d", ptr->spidx_port.off_t_size);
286
287 /* check version numbers */
288 if (ptr->version.spidx.major > GV_SIDX_VER_MAJOR ||
289 ptr->version.spidx.minor > GV_SIDX_VER_MINOR) {
290 /* The file was created by GRASS library with higher version than this
291 * one */
292
293 if (ptr->version.spidx.back_major > GV_SIDX_VER_MAJOR ||
294 ptr->version.spidx.back_minor > GV_SIDX_VER_MINOR) {
295 /* This version of GRASS lib is lower than the oldest which can read
296 * this format */
297 G_debug(1, "Spatial index format version %d.%d",
298 ptr->version.spidx.major, ptr->version.spidx.minor);
299 G_fatal_error(_("This version of GRASS (%d.%d) is too old to read "
300 "this spatial index format."
301 " Try to rebuild topology or upgrade GRASS to at "
302 "least version %d."),
303 GRASS_VERSION_MAJOR, GRASS_VERSION_MINOR,
304 GRASS_VERSION_MAJOR + 1);
305 return (-1);
306 }
307
308 G_warning(_("Your GRASS version does not fully support "
309 "spatial index format %d.%d of the vector."
310 " Consider to rebuild topology or upgrade GRASS."),
311 ptr->version.spidx.major, ptr->version.spidx.minor);
312 }
313 if (ptr->version.spidx.major < GV_SIDX_VER_MAJOR ||
314 (ptr->version.spidx.major == GV_SIDX_VER_MAJOR &&
315 ptr->version.spidx.minor < GV_SIDX_VER_MINOR)) {
316 /* The file was created by GRASS library with lower version than this
317 * one */
318 G_fatal_error(_("Spatial index format version %d.%d is not "
319 "supported by this release."
320 " Please rebuild topology."),
321 ptr->version.spidx.major, ptr->version.spidx.minor);
322 return (-1);
323 }
324
325 /* can this library read the sidx file ? */
326 if (ptr->spidx_port.off_t_size > (int)sizeof(off_t)) {
327 G_fatal_error("Spatial index was written with LFS but this "
328 "GRASS version does not support LFS. "
329 "Please get a GRASS version with LFS support.");
330 }
331
332 dig_init_portable(&(ptr->spidx_port), byte_order);
333 dig_set_cur_port(&(ptr->spidx_port));
334
335 /* bytes 7 - 10 : header size */
336 if (0 >= dig__fread_port_L(&(ptr->spidx_head_size), 1, fp))
337 return (-1);
338 G_debug(2, " header size %ld", ptr->spidx_head_size);
339
340 /* byte 11 : dimension 2D or 3D */
341 if (0 >= dig__fread_port_C((char *)buf, 1, fp))
342 return (-1);
343 ptr->spidx_with_z = buf[0];
344 G_debug(2, " with_z %d", ptr->spidx_with_z);
345
346 /* identical for all spatial indices: */
347 t = ptr->Node_spidx;
348 /* byte 12 : n dimensions */
349 if (0 >= dig__fread_port_C((char *)&(t->ndims), 1, fp))
350 return (-1);
351 ptr->Node_spidx->ndims = t->ndims;
352 ptr->Line_spidx->ndims = t->ndims;
353 ptr->Area_spidx->ndims = t->ndims;
354 ptr->Isle_spidx->ndims = t->ndims;
355
356 /* byte 13 : n sides */
357 if (0 >= dig__fread_port_C((char *)&(t->nsides), 1, fp))
358 return (-1);
359 ptr->Node_spidx->nsides = t->nsides;
360 ptr->Line_spidx->nsides = t->nsides;
361 ptr->Area_spidx->nsides = t->nsides;
362 ptr->Isle_spidx->nsides = t->nsides;
363
364 /* bytes 14 - 17 : nodesize */
365 if (0 >= dig__fread_port_I(&(t->nodesize), 1, fp))
366 return (-1);
367 ptr->Node_spidx->nodesize = t->nodesize;
368 ptr->Line_spidx->nodesize = t->nodesize;
369 ptr->Area_spidx->nodesize = t->nodesize;
370 ptr->Isle_spidx->nodesize = t->nodesize;
371
372 /* bytes 18 - 21 : nodecard */
373 if (0 >= dig__fread_port_I(&(t->nodecard), 1, fp))
374 return (-1);
375 ptr->Node_spidx->nodecard = t->nodecard;
376 ptr->Line_spidx->nodecard = t->nodecard;
377 ptr->Area_spidx->nodecard = t->nodecard;
378 ptr->Isle_spidx->nodecard = t->nodecard;
379
380 /* bytes 22 - 25 : leafcard */
381 if (0 >= dig__fread_port_I(&(t->leafcard), 1, fp))
382 return (-1);
383 ptr->Node_spidx->leafcard = t->leafcard;
384 ptr->Line_spidx->leafcard = t->leafcard;
385 ptr->Area_spidx->leafcard = t->leafcard;
386 ptr->Isle_spidx->leafcard = t->leafcard;
387
388 /* bytes 26 - 29 : min node fill */
389 if (0 >= dig__fread_port_I(&(t->min_node_fill), 1, fp))
390 return (-1);
391 ptr->Node_spidx->min_node_fill = t->min_node_fill;
392 ptr->Line_spidx->min_node_fill = t->min_node_fill;
393 ptr->Area_spidx->min_node_fill = t->min_node_fill;
394 ptr->Isle_spidx->min_node_fill = t->min_node_fill;
395
396 /* bytes 30 - 33 : min leaf fill */
397 if (0 >= dig__fread_port_I(&(t->min_leaf_fill), 1, fp))
398 return (-1);
399 ptr->Node_spidx->min_leaf_fill = t->min_leaf_fill;
400 ptr->Line_spidx->min_leaf_fill = t->min_leaf_fill;
401 ptr->Area_spidx->min_leaf_fill = t->min_leaf_fill;
402 ptr->Isle_spidx->min_leaf_fill = t->min_leaf_fill;
403
404 /* for each spatial index : */
405
406 /* Node spatial index */
407 /* bytes 34 - 37 : n nodes */
408 if (0 >= dig__fread_port_I((int *)&(t->n_nodes), 1, fp))
409 return (-1);
410 /* bytes 38 - 41 : n leafs */
411 if (0 >= dig__fread_port_I((int *)&(t->n_leafs), 1, fp))
412 return (-1);
413 /* bytes 42 - 45 : n levels */
414 if (0 >= dig__fread_port_I(&(t->rootlevel), 1, fp))
415 return (-1);
416 /* bytes 46 - 49 (LFS 53) : root node offset */
417 if (0 >= dig__fread_port_O(&(ptr->Node_spidx_offset), 1, fp,
418 ptr->spidx_port.off_t_size))
419 return (-1);
420 t->rootpos = ptr->Node_spidx_offset;
421
422 /* Line spatial index */
423 t = ptr->Line_spidx;
424 /* bytes 50 - 53 (LFS 54 - 57) : n nodes */
425 if (0 >= dig__fread_port_I((int *)&(t->n_nodes), 1, fp))
426 return (-1);
427 /* bytes 54 - 57 (LFS 58 - 61) : n leafs */
428 if (0 >= dig__fread_port_I((int *)&(t->n_leafs), 1, fp))
429 return (-1);
430 /* bytes 58 - 61 (LFS 62 - 65) : n levels */
431 if (0 >= dig__fread_port_I(&(t->rootlevel), 1, fp))
432 return (-1);
433 /* bytes 62 - 65 (LFS 66 - 73) : root node offset */
434 if (0 >= dig__fread_port_O(&(ptr->Line_spidx_offset), 1, fp,
435 ptr->spidx_port.off_t_size))
436 return (-1);
437 ptr->Line_spidx->rootpos = ptr->Line_spidx_offset;
438
439 /* Area spatial index */
440 t = ptr->Area_spidx;
441 /* bytes 66 - 69 (LFS 74 - 77) : n nodes */
442 if (0 >= dig__fread_port_I((int *)&(t->n_nodes), 1, fp))
443 return (-1);
444 /* bytes 70 - 73 (LFS 78 - 81) : n leafs */
445 if (0 >= dig__fread_port_I((int *)&(t->n_leafs), 1, fp))
446 return (-1);
447 /* bytes 74 - 77 (LFS 82 - 85) : n levels */
448 if (0 >= dig__fread_port_I(&(t->rootlevel), 1, fp))
449 return (-1);
450 /* bytes 78 - 81 (LFS 86 - 93) : root node offset */
451 if (0 >= dig__fread_port_O(&(ptr->Area_spidx_offset), 1, fp,
452 ptr->spidx_port.off_t_size))
453 return (-1);
454 ptr->Area_spidx->rootpos = ptr->Area_spidx_offset;
455
456 /* Isle spatial index */
457 t = ptr->Isle_spidx;
458 /* bytes 82 - 85 (LFS 94 - 97) : n nodes */
459 if (0 >= dig__fread_port_I((int *)&(t->n_nodes), 1, fp))
460 return (-1);
461 /* bytes 86 - 89 (LFS 98 - 101) : n leafs */
462 if (0 >= dig__fread_port_I((int *)&(t->n_leafs), 1, fp))
463 return (-1);
464 /* bytes 90 - 93 (LFS 102 - 105) : n levels */
465 if (0 >= dig__fread_port_I(&(t->rootlevel), 1, fp))
466 return (-1);
467 /* bytes 94 - 97 (LFS 106 - 113) : root node offset */
468 if (0 >= dig__fread_port_O(&(ptr->Isle_spidx_offset), 1, fp,
469 ptr->spidx_port.off_t_size))
470 return (-1);
471 ptr->Isle_spidx->rootpos = ptr->Isle_spidx_offset;
472
473 /* 3D future : */
474 /* Face spatial index */
475 /* bytes 98 - 101 (LFS 114 - 121) : root node offset */
476 if (0 >= dig__fread_port_O(&(ptr->Face_spidx_offset), 1, fp,
477 ptr->spidx_port.off_t_size))
478 return (-1);
479 /* ptr->Face_spidx->rootpos = ptr->Face_spidx_offset; */
480
481 /* Volume spatial index */
482 /* bytes 102 - 105 (LFS 122 - 129) : root node offset */
483 if (0 >= dig__fread_port_O(&(ptr->Volume_spidx_offset), 1, fp,
484 ptr->spidx_port.off_t_size))
485 return (-1);
486 /* ptr->Volume_spidx->rootpos = ptr->Volume_spidx_offset; */
487
488 /* Hole spatial index */
489 /* bytes 106 - 109 (LFS 130 - 137) : root node offset */
490 if (0 >= dig__fread_port_O(&(ptr->Hole_spidx_offset), 1, fp,
491 ptr->spidx_port.off_t_size))
492 return (-1);
493 /* ptr->Hole_spidx->rootpos = ptr->Hole_spidx_offset; */
494
495 /* coor file size : bytes 110 - 113 (117) (LFS: 138 - 145) */
496 if (ptr->off_t_size == -1)
497 ptr->off_t_size = ptr->spidx_port.off_t_size;
498 if (0 >= dig__fread_port_O(&(ptr->coor_size), 1, fp, ptr->off_t_size))
499 return (-1);
500 G_debug(2, " coor size %lu", (long unsigned)ptr->coor_size);
501
502 dig_fseek(fp, ptr->spidx_head_size, SEEK_SET);
503
504 return (0);
505}
506
507static int rtree_dump_node(FILE *, struct RTree_Node *n, int);
508
509/*!
510 \brief Dump R-tree branch to the file
511
512 \param fp pointer to FILE
513 \param b pointer to Branch structure
514 \param with_z non-zero value for 3D vector data
515 \param level level value
516
517 \return 0
518 */
519static int rtree_dump_branch(FILE *fp, struct RTree_Branch *b, int with_z,
520 int level)
521{
522 const struct RTree_Rect *r;
523
524 r = &(b->rect);
525
526 if (level == 0)
527 fprintf(fp, " id = %d ", b->child.id);
528
529 fprintf(fp, " %f %f %f %f %f %f\n", r->boundary[0], r->boundary[1],
530 r->boundary[2], r->boundary[3], r->boundary[4], r->boundary[5]);
531
532 if (level > 0) {
533 rtree_dump_node(fp, b->child.ptr, with_z);
534 }
535 return 0;
536}
537
538/*!
539 \brief Dump R-tree node to the file
540
541 \param fp pointer to FILE
542 \param n pointer to Node structure
543 \param with_z non-zero value for 3D vector data
544
545 \return 0
546 */
547int rtree_dump_node(FILE *fp, struct RTree_Node *n, int with_z)
548{
549 int i;
550
551 /* recursive nearly-but-a-bit-messy depth-first pre-order traversal
552 * potentially filling up memory */
553 /* TODO: change to non-recursive depth-first post-order traversal */
554 /* left for comparison with GRASS6.x */
555
556 fprintf(fp, "Node level=%d count=%d\n", n->level, n->count);
557
558 if (n->level > 0)
559 for (i = 0; i < NODECARD; i++) {
560 if (n->branch[i].child.ptr) {
561 fprintf(fp, " Branch %d", i);
562 rtree_dump_branch(fp, &n->branch[i], with_z, n->level);
563 }
564 }
565 else
566 for (i = 0; i < LEAFCARD; i++) {
567 if (n->branch[i].child.id) {
568 fprintf(fp, " Branch %d", i);
569 rtree_dump_branch(fp, &n->branch[i], with_z, n->level);
570 }
571 }
572
573 return 0;
574}
575
576static int rtree_dump_node_file(FILE *, off_t, int, struct RTree *);
577
578/*!
579 \brief Dump R-tree branch from temp file to the file
580
581 \param fp pointer to FILE
582 \param b pointer to Branch structure
583 \param with_z non-zero value for 3D vector data
584 \param level level value
585
586 \return 0
587 */
588static int rtree_dump_branch_file(FILE *fp, struct RTree_Branch *b, int with_z,
589 int level, struct RTree *t)
590{
591 const struct RTree_Rect *r;
592
593 r = &(b->rect);
594
595 if (level == 0)
596 fprintf(fp, " id = %d ", b->child.id);
597
598 fprintf(fp, " %f %f %f %f %f %f\n", r->boundary[0], r->boundary[1],
599 r->boundary[2], r->boundary[3], r->boundary[4], r->boundary[5]);
600
601 if (level > 0) {
602 rtree_dump_node_file(fp, b->child.pos, with_z, t);
603 }
604 return 0;
605}
606
607/*!
608 \brief Dump R-tree node from temp file to the file
609
610 \param fp pointer to FILE
611 \param pos position of Node in temp file
612 \param with_z non-zero value for 3D vector data
613 \param t RTree to dump
614
615 \return 0
616 */
617int rtree_dump_node_file(FILE *fp, off_t pos, int with_z, struct RTree *t)
618{
619 int i;
620 static struct RTree_Node *n = NULL;
621
622 if (!n) {
623 n = RTreeAllocNode(t, 1);
624 }
625
626 /* recursive nearly-but-a-bit-messy depth-first pre-order traversal
627 * potentially filling up memory */
628 /* TODO: change to non-recursive depth-first post-order traversal */
629 /* left for comparison with GRASS6.x */
630
631 RTreeReadNode(n, pos, t);
632 fprintf(fp, "Node level=%d count=%d\n", n->level, n->count);
633
634 if (n->level > 0)
635 for (i = 0; i < NODECARD; i++) {
636 if (n->branch[i].child.pos >= 0) {
637 fprintf(fp, " Branch %d", i);
638 rtree_dump_branch_file(fp, &(n->branch[i]), with_z, n->level,
639 t);
640 }
641 }
642 else
643 for (i = 0; i < LEAFCARD; i++) {
644 if (n->branch[i].child.id) {
645 fprintf(fp, " Branch %d", i);
646 rtree_dump_branch_file(fp, &(n->branch[i]), with_z, n->level,
647 t);
648 }
649 }
650
651 return 0;
652}
653
654/*
655 * all following methods to transfer spatial indices (rtrees) are based
656 * on the same idea
657 * do a postorder depth-first non-recursive traversal of the rtree
658 * a leaf node is transferred first
659 * the root node is transferred last
660 *
661 * this applies to all four scenarios
662 * - from intermediate file to sidx file
663 * - from sidx file to intermediate file
664 * - from memory to sidx file
665 * - from sidx file to memory
666 *
667 * I could not think of one function that's good for all four scenarios,
668 * but that doesn't mean there is none...
669 *
670 * maybe something like V2_read_line_array and Write_line_array
671 * in Vlib/read.c and Vlib/write.c, at least for transferring from sidx
672 * and transferrring to sidx?
673 */
674
675/*!
676 \brief Write RTree body from memory to sidx file
677 Must be called when new or updated vector is closed
678
679 \param[out] fp pointer to struct gvfile
680 \param startpos offset to struct gvfile where to start writing out
681 \param t pointer to RTree
682 \param off_t_size size of off_t used to write struct gvfile
683
684 \return -1 on error
685 \return offset to root node on success
686 */
687static off_t rtree_write_from_memory(struct gvfile *fp, off_t startpos,
688 struct RTree *t, int off_t_size)
689{
690 off_t nextfreepos = startpos;
691 int sidx_nodesize, sidx_leafsize;
692 struct RTree_Node *n;
693 int i, j, writeout, maxcard;
694 struct spidxpstack *s = G_malloc(MAXLEVEL * sizeof(struct spidxstack));
695 int top = 0;
696
697 /* should be foolproof */
698 sidx_nodesize = (int)(2 * PORT_INT +
699 t->nodecard * (off_t_size + NUMSIDES * PORT_DOUBLE));
700 sidx_leafsize = (int)(2 * PORT_INT +
701 t->leafcard * (off_t_size + NUMSIDES * PORT_DOUBLE));
702
703 /* stack size of t->rootlevel + 1 would be enough because of
704 * depth-first post-order traversal:
705 * only one node per level on stack at any given time */
706
707 /* add root node position to stack */
708 s[top].branch_id = i = 0;
709 s[top].sn = t->root;
710
711 /* depth-first postorder traversal
712 * all children of a node are visitied and written out first
713 * when a child is written out, its position in file is stored in pos[] for
714 * the parent node and written out with the parent node */
715 /* root node is written out last and its position returned */
716
717 while (top >= 0) {
718 if (s[top].sn == NULL)
719 G_fatal_error("NULL node ptr at top = %d", top);
720 n = s[top].sn;
721 writeout = 1;
722 /* this is an internal node in the RTree
723 * all its children are processed first,
724 * before it is written out to the sidx file */
725 if (s[top].sn->level > 0) {
726 for (i = s[top].branch_id; i < t->nodecard; i++) {
727 s[top].pos[i] = 0;
728 if (n->branch[i].child.ptr != NULL) {
729 s[top++].branch_id = i + 1;
730 s[top].sn = n->branch[i].child.ptr;
731 s[top].branch_id = 0;
732 writeout = 0;
733 break;
734 }
735 }
736 if (writeout) {
737 /* nothing else found, ready to write out */
738 s[top].branch_id = t->nodecard;
739 }
740 }
741 if (writeout) {
742 /* write node to sidx file */
743 if (G_ftell(fp->file) != nextfreepos)
744 G_fatal_error("Unable to write spatial index. "
745 "Wrong node position (%" PRId64
746 ") in file (should be %" PRId64 ").",
747 G_ftell(fp->file), nextfreepos);
748
749 /* write with dig__fwrite_port_* fns */
750 dig__fwrite_port_I(&(s[top].sn->count), 1, fp);
751 dig__fwrite_port_I(&(s[top].sn->level), 1, fp);
752 maxcard = s[top].sn->level ? t->nodecard : t->leafcard;
753 for (j = 0; j < maxcard; j++) {
754 dig__fwrite_port_D(s[top].sn->branch[j].rect.boundary, NUMSIDES,
755 fp);
756 /* leaf node: vector object IDs are stored in child.id */
757 if (s[top].sn->level == 0)
758 s[top].pos[j] = (off_t)s[top].sn->branch[j].child.id;
759 dig__fwrite_port_O(&(s[top].pos[j]), 1, fp, off_t_size);
760 }
761
762 top--;
763 /* update corresponding child position of parent node
764 * this node is only updated if its level is > 0, i.e.
765 * this is an internal node
766 * children of internal nodes do not have an ID, instead
767 * they hold the position in file of the next nodes down the tree */
768 if (top >= 0) {
769 s[top].pos[s[top].branch_id - 1] = nextfreepos;
770 nextfreepos +=
771 (s[top + 1].sn->level ? sidx_nodesize : sidx_leafsize);
772 }
773 }
774 }
775
776 G_free(s);
777
778 return nextfreepos;
779}
780
781/*!
782 \brief Write RTree body from temporary file to sidx file
783 Must be called when new or updated vector is closed
784
785 \param[out] fp pointer to struct gvfile
786 \param startpos offset to struct gvfile where to start writing out
787 \param t pointer to RTree
788 \param off_t_size size of off_t used to write struct gvfile
789
790 \return -1 on error
791 \return offset to root node on success
792 */
793static off_t rtree_write_from_file(struct gvfile *fp, off_t startpos,
794 struct RTree *t, int off_t_size)
795{
796 off_t nextfreepos = startpos;
797 int sidx_nodesize, sidx_leafsize;
798 struct RTree_Node *n;
799 int i, j, writeout, maxcard;
800 static struct spidxstack *s = NULL;
801 int top = 0;
802
803 if (!s) {
804 s = G_malloc(MAXLEVEL * sizeof(struct spidxstack));
805 for (i = 0; i < MAXLEVEL; i++) {
806 s[i].sn.branch = G_malloc(MAXCARD * sizeof(struct RTree_Branch));
807 for (j = 0; j < MAXCARD; j++) {
808 s[i].sn.branch[j].rect.boundary =
809 G_malloc(6 * sizeof(RectReal));
810 }
811 }
812 }
813
814 /* write pending changes to file */
815 RTreeFlushBuffer(t);
816
817 /* should be foolproof */
818 sidx_nodesize = (int)(2 * PORT_INT +
819 t->nodecard * (off_t_size + NUMSIDES * PORT_DOUBLE));
820 sidx_leafsize = (int)(2 * PORT_INT +
821 t->leafcard * (off_t_size + NUMSIDES * PORT_DOUBLE));
822
823 /* stack size of t->rootlevel + 1 would be enough because of
824 * depth-first post-order traversal:
825 * only one node per level on stack at any given time */
826
827 /* add root node position to stack */
828 s[top].branch_id = i = 0;
829 RTreeReadNode(&s[top].sn, t->rootpos, t);
830
831 /* depth-first postorder traversal
832 * all children of a node are visitied and written out first
833 * when a child is written out, its position in file is stored in pos[] for
834 * the parent node and written out with the parent node */
835 /* root node is written out last and its position returned */
836
837 while (top >= 0) {
838 n = &(s[top].sn);
839 writeout = 1;
840 /* this is an internal node in the RTree
841 * all its children are processed first,
842 * before it is written out to the sidx file */
843 if (s[top].sn.level > 0) {
844 for (i = s[top].branch_id; i < t->nodecard; i++) {
845 s[top].pos[i] = 0;
846 if (n->branch[i].child.pos >= 0) {
847 s[top++].branch_id = i + 1;
848 RTreeReadNode(&s[top].sn, n->branch[i].child.pos, t);
849 s[top].branch_id = 0;
850 writeout = 0;
851 break;
852 }
853 }
854 if (writeout) {
855 /* nothing else found, ready to write out */
856 s[top].branch_id = t->nodecard;
857 }
858 }
859 if (writeout) {
860 /* write node to sidx file */
861 if (G_ftell(fp->file) != nextfreepos)
862 G_fatal_error("Unable to write spatial index. "
863 "Wrong node position (%" PRId64
864 ") in file (should be %" PRId64 ").",
865 G_ftell(fp->file), nextfreepos);
866
867 /* write with dig__fwrite_port_* fns */
868 dig__fwrite_port_I(&(s[top].sn.count), 1, fp);
869 dig__fwrite_port_I(&(s[top].sn.level), 1, fp);
870 maxcard = s[top].sn.level ? t->nodecard : t->leafcard;
871 for (j = 0; j < maxcard; j++) {
872 dig__fwrite_port_D(s[top].sn.branch[j].rect.boundary, NUMSIDES,
873 fp);
874 /* leaf node: vector object IDs are stored in child.id */
875 if (s[top].sn.level == 0)
876 s[top].pos[j] = (off_t)s[top].sn.branch[j].child.id;
877 dig__fwrite_port_O(&(s[top].pos[j]), 1, fp, off_t_size);
878 }
879
880 top--;
881 /* update corresponding child position of parent node
882 * this node is only updated if its level is > 0, i.e.
883 * this is an internal node
884 * children of internal nodes do not have an ID, instead
885 * they hold the position in file of the next nodes down the tree */
886 if (top >= 0) {
887 s[top].pos[s[top].branch_id - 1] = nextfreepos;
888 nextfreepos +=
889 (s[top + 1].sn.level ? sidx_nodesize : sidx_leafsize);
890 }
891 }
892 }
893
894 close(t->fd);
895
896 return nextfreepos;
897}
898
899/* write RTree body to sidx file */
900static off_t rtree_write_to_sidx(struct gvfile *fp, off_t startpos,
901 struct RTree *t, int off_t_size)
902{
903 if (t->fd > -1)
904 return rtree_write_from_file(fp, startpos, t, off_t_size);
905 else
906 return rtree_write_from_memory(fp, startpos, t, off_t_size);
907}
908
909/*!
910 \brief Load RTree body from sidx file to memory
911 Must be called when old vector is opened in update mode
912
913 \param fp pointer to struct gvfile
914 \param rootpos position of root node in file
915 \param t pointer to RTree
916 \param off_t_size size of off_t used to read struct gvfile
917
918 \return pointer to root node on success
919 */
920static void rtree_load_to_memory(struct gvfile *fp, off_t rootpos,
921 struct RTree *t, int off_t_size)
922{
923 struct RTree_Node *newnode = NULL;
924 int i, j, loadnode, maxcard;
925 struct spidxstack *last;
926 static struct spidxstack *s = NULL;
927 int top = 0;
928
929 if (!s) {
930 s = G_malloc(MAXLEVEL * sizeof(struct spidxstack));
931 for (i = 0; i < MAXLEVEL; i++) {
932 s[i].sn.branch = G_malloc(MAXCARD * sizeof(struct RTree_Branch));
933 for (j = 0; j < MAXCARD; j++) {
934 s[i].sn.branch[j].rect.boundary =
935 G_malloc(6 * sizeof(RectReal));
936 }
937 }
938 }
939
940 /* stack size of t->rootlevel + 1 would be enough because of
941 * depth-first postorder traversal:
942 * only one node per level on stack at any given time */
943
944 /* add root node position to stack */
945 last = &(s[top]);
946 G_fseek(fp->file, rootpos, SEEK_SET);
947 /* read with dig__fread_port_* fns */
948 dig__fread_port_I(&(s[top].sn.count), 1, fp);
949 dig__fread_port_I(&(s[top].sn.level), 1, fp);
950 maxcard = s[top].sn.level ? t->nodecard : t->leafcard;
951 for (j = 0; j < maxcard; j++) {
952 dig__fread_port_D(s[top].sn.branch[j].rect.boundary, NUMSIDES, fp);
953 dig__fread_port_O(&(s[top].pos[j]), 1, fp, off_t_size);
954 /* leaf node: vector object IDs are stored in child.id */
955 if (s[top].sn.level == 0) {
956 s[top].sn.branch[j].child.id = (int)s[top].pos[j];
957 }
958 else {
959 s[top].sn.branch[j].child.ptr = NULL;
960 }
961 }
962
963 s[top].branch_id = i = 0;
964
965 /* some sort of postorder traversal */
966 /* root node is loaded last and returned */
967
968 while (top >= 0) {
969 last = &(s[top]);
970 loadnode = 1;
971 /* this is an internal node in the RTree
972 * all its children are read first,
973 * before it is transferred to the RTree in memory */
974 if (s[top].sn.level > 0) {
975 for (i = s[top].branch_id; i < t->nodecard; i++) {
976 if (s[top].pos[i] > 0) {
977 s[top++].branch_id = i + 1;
978 G_fseek(fp->file, last->pos[i], SEEK_SET);
979 /* read with dig__fread_port_* fns */
980 dig__fread_port_I(&(s[top].sn.count), 1, fp);
981 dig__fread_port_I(&(s[top].sn.level), 1, fp);
982 maxcard = s[top].sn.level ? t->nodecard : t->leafcard;
983 for (j = 0; j < maxcard; j++) {
984 dig__fread_port_D(s[top].sn.branch[j].rect.boundary,
985 NUMSIDES, fp);
986 dig__fread_port_O(&(s[top].pos[j]), 1, fp, off_t_size);
987 /* leaf node
988 * vector object IDs are stored in file as
989 * off_t but always fit into an int, see dig_structs.h
990 * vector object IDs are transferred to child.id */
991 if (s[top].sn.level == 0) {
992 s[top].sn.branch[j].child.id = (int)s[top].pos[j];
993 }
994 else {
995 s[top].sn.branch[j].child.ptr = NULL;
996 }
997 }
998 s[top].branch_id = 0;
999 loadnode = 0;
1000 break;
1001 }
1002 else if (last->pos[i] < 0)
1003 G_fatal_error("corrupt spatial index");
1004 }
1005 if (loadnode) {
1006 /* nothing else found, ready to load */
1007 s[top].branch_id = t->nodecard;
1008 }
1009 }
1010 if (loadnode) {
1011 /* ready to load node to memory */
1012
1013 newnode = RTreeAllocNode(t, s[top].sn.level);
1014 /* copy from stack node */
1015 RTreeCopyNode(newnode, &(s[top].sn), t);
1016
1017 top--;
1018 /* update child of parent node
1019 * this node is only updated if its level is > 0, i.e.
1020 * this is an internal node
1021 * children of internal nodes do not have an ID, instead
1022 * they point to the next nodes down the tree */
1023 if (top >= 0) {
1024 s[top].sn.branch[s[top].branch_id - 1].child.ptr = newnode;
1025 }
1026 }
1027 }
1028
1029 t->root = newnode;
1030}
1031
1032/*!
1033 \brief Load RTree body from sidx file to temporary file
1034 Must be called when old vector is opened in update mode
1035
1036 \param fp pointer to struct gvfile
1037 \param rootpos position of root node in file
1038 \param t pointer to RTree
1039 \param off_t_size size of off_t used to read struct gvfile
1040
1041 \return offset to root node
1042 */
1043static void rtree_load_to_file(struct gvfile *fp, off_t rootpos,
1044 struct RTree *t, int off_t_size)
1045{
1046 off_t newnode_pos = -1;
1047 int i, j, loadnode, maxcard;
1048 struct spidxstack *last;
1049 static struct spidxstack *s = NULL;
1050 int top = 0;
1051
1052 if (!s) {
1053 s = G_malloc(MAXLEVEL * sizeof(struct spidxstack));
1054 for (i = 0; i < MAXLEVEL; i++) {
1055 s[i].sn.branch = G_malloc(MAXCARD * sizeof(struct RTree_Branch));
1056 for (j = 0; j < MAXCARD; j++) {
1057 s[i].sn.branch[j].rect.boundary =
1058 G_malloc(6 * sizeof(RectReal));
1059 }
1060 }
1061 }
1062
1063 /* stack size of t->rootlevel + 1 would be enough because of
1064 * depth-first postorder traversal:
1065 * only one node per level on stack at any given time */
1066
1067 /* add root node position to stack */
1068 last = &(s[top]);
1069 G_fseek(fp->file, rootpos, SEEK_SET);
1070 /* read with dig__fread_port_* fns */
1071 dig__fread_port_I(&(s[top].sn.count), 1, fp);
1072 dig__fread_port_I(&(s[top].sn.level), 1, fp);
1073 maxcard = t->rootlevel ? t->nodecard : t->leafcard;
1074 for (j = 0; j < maxcard; j++) {
1075 dig__fread_port_D(s[top].sn.branch[j].rect.boundary, NUMSIDES, fp);
1076 dig__fread_port_O(&(s[top].pos[j]), 1, fp, off_t_size);
1077 /* leaf node: vector object IDs are stored in child.id */
1078 if (s[top].sn.level == 0) {
1079 s[top].sn.branch[j].child.id = (int)s[top].pos[j];
1080 }
1081 else {
1082 s[top].sn.branch[j].child.pos = -1;
1083 }
1084 }
1085
1086 s[top].branch_id = i = 0;
1087
1088 /* depth-first postorder traversal */
1089 /* root node is loaded last and returned */
1090
1091 while (top >= 0) {
1092 last = &(s[top]);
1093 loadnode = 1;
1094 /* this is an internal node in the RTree
1095 * all its children are read first,
1096 * before it is transferred to the RTree in memory */
1097 if (s[top].sn.level > 0) {
1098 for (i = s[top].branch_id; i < t->nodecard; i++) {
1099 if (s[top].pos[i] > 0) {
1100 s[top++].branch_id = i + 1;
1101 G_fseek(fp->file, last->pos[i], SEEK_SET);
1102 /* read with dig__fread_port_* fns */
1103 dig__fread_port_I(&(s[top].sn.count), 1, fp);
1104 dig__fread_port_I(&(s[top].sn.level), 1, fp);
1105 maxcard = s[top].sn.level ? t->nodecard : t->leafcard;
1106 for (j = 0; j < maxcard; j++) {
1107 dig__fread_port_D(s[top].sn.branch[j].rect.boundary,
1108 NUMSIDES, fp);
1109 dig__fread_port_O(&(s[top].pos[j]), 1, fp, off_t_size);
1110 /* leaf node
1111 * vector object IDs are stored in file as
1112 * off_t but always fit into an int, see dig_structs.h
1113 * vector object IDs are transferred to child.id */
1114 if (s[top].sn.level == 0) {
1115 s[top].sn.branch[j].child.id = (int)s[top].pos[j];
1116 }
1117 else {
1118 s[top].sn.branch[j].child.pos = -1;
1119 }
1120 }
1121 s[top].branch_id = 0;
1122 loadnode = 0;
1123 break;
1124 }
1125 else if (last->pos[i] < 0)
1126 G_fatal_error("corrupt spatial index");
1127 }
1128 if (loadnode) {
1129 /* nothing else found, ready to load */
1130 s[top].branch_id = t->nodecard;
1131 }
1132 }
1133 if (loadnode) {
1134 /* ready to load node and write to temp file */
1135
1136 newnode_pos = RTreeGetNodePos(t);
1137 RTreeWriteNode(&(s[top].sn), t);
1138
1139 top--;
1140 /* update child of parent node
1141 * this node is only updated if its level is > 0, i.e.
1142 * this is an internal node
1143 * children of internal nodes do not have an ID, instead
1144 * they point to the next nodes down the tree */
1145 if (top >= 0) {
1146 s[top].sn.branch[s[top].branch_id - 1].child.pos = newnode_pos;
1147 }
1148 }
1149 }
1150
1151 t->rootpos = newnode_pos;
1152}
1153
1154static void rtree_load_from_sidx(struct gvfile *fp, off_t rootpos,
1155 struct RTree *t, int off_t_size)
1156{
1157 if (t->fd > -1)
1158 rtree_load_to_file(fp, rootpos, t, off_t_size);
1159 else
1160 rtree_load_to_memory(fp, rootpos, t, off_t_size);
1161}
1162
1163/*!
1164 \brief Write spatial index to file
1165
1166 \param[out] fp pointer to struct gvfile
1167 \param Plus pointer to Plus_head structure
1168
1169 \return 0
1170 */
1171int dig_Wr_spidx(struct gvfile *fp, struct Plus_head *Plus)
1172{
1173 G_debug(1, "dig_Wr_spidx()");
1174
1175 dig_set_cur_port(&(Plus->spidx_port));
1176 dig_rewind(fp);
1177
1178 dig_Wr_spidx_head(fp, Plus);
1179
1180 /* Nodes */
1181 Plus->Node_spidx_offset = rtree_write_to_sidx(
1182 fp, dig_ftell(fp), Plus->Node_spidx, Plus->spidx_port.off_t_size);
1183
1184 /* Lines */
1185 Plus->Line_spidx_offset = rtree_write_to_sidx(
1186 fp, dig_ftell(fp), Plus->Line_spidx, Plus->spidx_port.off_t_size);
1187
1188 /* Areas */
1189 Plus->Area_spidx_offset = rtree_write_to_sidx(
1190 fp, dig_ftell(fp), Plus->Area_spidx, Plus->spidx_port.off_t_size);
1191
1192 /* Isles */
1193 Plus->Isle_spidx_offset = rtree_write_to_sidx(
1194 fp, dig_ftell(fp), Plus->Isle_spidx, Plus->spidx_port.off_t_size);
1195
1196 /* 3D future : */
1197 /* Faces */
1198 /* Volumes */
1199 /* Holes */
1200
1201 dig_rewind(fp);
1202 dig_Wr_spidx_head(fp, Plus); /* rewrite with offsets */
1203
1204 dig_fflush(fp);
1205 return 0;
1206}
1207
1208/*!
1209 \brief Read spatial index from sidx file
1210 Only needed when old vector is opened in update mode
1211
1212 \param fp pointer to struct gvfile
1213 \param[in,out] Plus pointer to Plus_head structure
1214
1215 \return 0
1216 */
1217int dig_Rd_spidx(struct gvfile *fp, struct Plus_head *Plus)
1218{
1219 G_debug(1, "dig_read_spindx()");
1220
1221 /* free old trees, init new trees */
1222 dig_spidx_free(Plus);
1223 dig_spidx_init(Plus);
1224
1225 dig_rewind(fp);
1226 dig_Rd_spidx_head(fp, Plus);
1227 dig_set_cur_port(&(Plus->spidx_port));
1228
1229 /* Nodes */
1230 rtree_load_from_sidx(fp, Plus->Node_spidx_offset, Plus->Node_spidx,
1231 Plus->spidx_port.off_t_size);
1232
1233 /* Lines */
1234 rtree_load_from_sidx(fp, Plus->Line_spidx_offset, Plus->Line_spidx,
1235 Plus->spidx_port.off_t_size);
1236
1237 /* Areas */
1238 rtree_load_from_sidx(fp, Plus->Area_spidx_offset, Plus->Area_spidx,
1239 Plus->spidx_port.off_t_size);
1240
1241 /* Isles */
1242 rtree_load_from_sidx(fp, Plus->Isle_spidx_offset, Plus->Isle_spidx,
1243 Plus->spidx_port.off_t_size);
1244
1245 /* 3D future : */
1246 /* Faces */
1247 /* Volumes */
1248 /* Holes */
1249
1250 return 0;
1251}
1252
1253/*!
1254 \brief Dump spatial index
1255
1256 \param[out] fp pointer to FILE
1257 \param Plus pointer to Plus_head structure
1258
1259 \return 0
1260 */
1261int dig_dump_spidx(FILE *fp, const struct Plus_head *Plus)
1262{
1263 fprintf(fp, "Nodes\n");
1264 if (Plus->Node_spidx->fd < 0)
1265 rtree_dump_node(fp, Plus->Node_spidx->root, Plus->with_z);
1266 else {
1267 RTreeFlushBuffer(Plus->Node_spidx);
1268 rtree_dump_node_file(fp, Plus->Node_spidx->rootpos, Plus->with_z,
1269 Plus->Node_spidx);
1270 }
1271
1272 fprintf(fp, "Lines\n");
1273 if (Plus->Line_spidx->fd < 0)
1274 rtree_dump_node(fp, Plus->Line_spidx->root, Plus->with_z);
1275 else {
1276 RTreeFlushBuffer(Plus->Line_spidx);
1277 rtree_dump_node_file(fp, Plus->Line_spidx->rootpos, Plus->with_z,
1278 Plus->Line_spidx);
1279 }
1280
1281 fprintf(fp, "Areas\n");
1282 if (Plus->Area_spidx->fd < 0)
1283 rtree_dump_node(fp, Plus->Area_spidx->root, Plus->with_z);
1284 else {
1285 RTreeFlushBuffer(Plus->Area_spidx);
1286 rtree_dump_node_file(fp, Plus->Area_spidx->rootpos, Plus->with_z,
1287 Plus->Area_spidx);
1288 }
1289
1290 fprintf(fp, "Isles\n");
1291 if (Plus->Isle_spidx->fd < 0)
1292 rtree_dump_node(fp, Plus->Isle_spidx->root, Plus->with_z);
1293 else {
1294 RTreeFlushBuffer(Plus->Isle_spidx);
1295 rtree_dump_node_file(fp, Plus->Isle_spidx->rootpos, Plus->with_z,
1296 Plus->Isle_spidx);
1297 }
1298
1299 return 0;
1300}
1301
1302/* read node from file */
1303static void rtree_read_node(struct NodeBuffer *nb, off_t nodepos,
1304 struct RTree *t, struct Plus_head *Plus)
1305{
1306 int i, maxcard;
1307 off_t pos;
1308 struct gvfile *file = &(Plus->spidx_fp);
1309
1310 dig_fseek(file, nodepos, SEEK_SET);
1311 /* read with dig__fread_port_* fns */
1312 dig__fread_port_I(&(nb->n.count), 1, file);
1313 dig__fread_port_I(&(nb->n.level), 1, file);
1314 maxcard = nb->n.level ? t->nodecard : t->leafcard;
1315 for (i = 0; i < maxcard; i++) {
1316 dig__fread_port_D(nb->n.branch[i].rect.boundary, NUMSIDES, file);
1317 dig__fread_port_O(&pos, 1, file, Plus->spidx_port.off_t_size);
1318 /* leaf node: vector object IDs are stored in child.id */
1319 if (nb->n.level == 0) {
1320 nb->n.branch[i].child.id = (int)pos;
1321 }
1322 else {
1323 nb->n.branch[i].child.pos = pos;
1324 }
1325 }
1326}
1327
1328/* get node from buffer or file */
1329static struct RTree_Node *rtree_get_node(off_t nodepos, int level,
1330 struct RTree *t,
1331 struct Plus_head *Plus)
1332{
1333 int which, i = 0;
1334
1335 /* check mru first */
1336 /* t->used[level][i] */
1337 while (t->nb[level][t->used[level][i]].pos != nodepos &&
1338 t->nb[level][t->used[level][i]].pos >= 0 &&
1339 i < NODE_BUFFER_SIZE - 1) {
1340 i++;
1341 }
1342
1343 which = t->used[level][i];
1344
1345 if (t->nb[level][which].pos != nodepos) {
1346 rtree_read_node(&(t->nb[level][which]), nodepos, t, Plus);
1347 t->nb[level][which].pos = nodepos;
1348 }
1349 assert(t->nb[level][which].n.level == level);
1350
1351 /* make it mru */
1352 if (i) { /* t->used[level][0] != which */
1353#if 0
1354 t->used[level][i] = t->used[level][0];
1355 t->used[level][0] = which;
1356#else
1357 while (i) {
1358 t->used[level][i] = t->used[level][i - 1];
1359 i--;
1360 }
1361 t->used[level][0] = which;
1362#endif
1363 }
1364
1365 return &(t->nb[level][which].n);
1366}
1367
1368/*!
1369 \brief Search spatial index file
1370 Can't use regular RTreeSearch() here because sidx must be read
1371 with dig__fread_port_*() functions
1372
1373 \param t pointer to RTree
1374 \param r search rectangle
1375 \param shcb user-provided callback
1376 \param cbarg argument for shcb
1377 \param Plus pointer to Plus_head structure
1378
1379 \return number of qualifying rectangles
1380 */
1381int rtree_search(struct RTree *t, struct RTree_Rect *r, SearchHitCallback shcb,
1382 void *cbarg, struct Plus_head *Plus)
1383{
1384 int hitCount = 0, found;
1385
1386 /* int j, maxcard; */
1387 int i;
1388 struct spidxpstack s[MAXLEVEL];
1389 int top = 0, level;
1390 off_t lastpos;
1391
1392 assert(r);
1393 assert(t);
1394
1395 /* stack size of t->rootlevel + 1 is enough because of depth first search */
1396 /* only one node per level on stack at any given time */
1397
1398 dig_set_cur_port(&(Plus->spidx_port));
1399
1400 /* add root node position to stack */
1401 s[top].sn = rtree_get_node(t->rootpos, t->rootlevel, t, Plus);
1402#if 0
1403 dig_fseek(&(Plus->spidx_fp), t->rootpos, SEEK_SET);
1404 /* read with dig__fread_port_* fns */
1405 dig__fread_port_I(&(s[top].sn.count), 1, &(Plus->spidx_fp));
1406 dig__fread_port_I(&(s[top].sn.level), 1, &(Plus->spidx_fp));
1407 maxcard = t->rootlevel ? t->nodecard : t->leafcard;
1408 for (j = 0; j < maxcard; j++) {
1409 dig__fread_port_D(s[top].sn.branch[j].rect.boundary, NUMSIDES,
1410 &(Plus->spidx_fp));
1411 dig__fread_port_O(&(s[top].pos[j]), 1, &(Plus->spidx_fp),
1412 Plus->spidx_port.off_t_size);
1413 /* leaf node: vector object IDs are stored in child.id */
1414 if (s[top].sn.level == 0) {
1415 s[top].sn.branch[j].child.id = (int)s[top].pos[j];
1416 }
1417 else {
1418 s[top].sn.branch[j].child.pos = s[top].pos[j];
1419 }
1420 }
1421#endif
1422
1423 s[top].branch_id = i = 0;
1424
1425 while (top >= 0) {
1426 level = s[top].sn->level;
1427 if (level > 0) { /* this is an internal node in the tree */
1428 found = 1;
1429 for (i = s[top].branch_id; i < t->nodecard; i++) {
1430 lastpos = s[top].sn->branch[i].child.pos;
1431 if (lastpos > 0 &&
1432 RTreeOverlap(r, &(s[top].sn->branch[i].rect), t)) {
1433 s[top++].branch_id = i + 1;
1434 s[top].sn = rtree_get_node(lastpos, level - 1, t, Plus);
1435
1436#if 0
1437 dig_fseek(&(Plus->spidx_fp), lastpos, SEEK_SET);
1438 /* read with dig__fread_port_* fns */
1439 dig__fread_port_I(&(s[top].sn.count), 1,
1440 &(Plus->spidx_fp));
1441 dig__fread_port_I(&(s[top].sn.level), 1,
1442 &(Plus->spidx_fp));
1443 maxcard = s[top].sn.level ? t->nodecard : t->leafcard;
1444 for (j = 0; j < maxcard; j++) {
1445 dig__fread_port_D(s[top].sn.branch[j].rect.boundary,
1446 NUMSIDES, &(Plus->spidx_fp));
1447 dig__fread_port_O(&(s[top].pos[j]), 1,
1448 &(Plus->spidx_fp),
1449 Plus->spidx_port.off_t_size);
1450 if (s[top].sn.level == 0) {
1451 s[top].sn.branch[j].child.id = (int)s[top].pos[j];
1452 }
1453 else {
1454 s[top].sn.branch[j].child.pos = s[top].pos[j];
1455 }
1456 }
1457#endif
1458 s[top].branch_id = 0;
1459 found = 0;
1460 break;
1461 }
1462 }
1463 if (found) {
1464 /* nothing else found, go back up */
1465 s[top].branch_id = t->nodecard;
1466 top--;
1467 }
1468 }
1469 else { /* this is a leaf node */
1470 for (i = 0; i < t->leafcard; i++) {
1471 if (s[top].sn->branch[i].child.id &&
1472 RTreeOverlap(r, &(s[top].sn->branch[i].rect), t)) {
1473 hitCount++;
1474 if (shcb) { /* call the user-provided callback */
1475 if (!shcb((int)s[top].sn->branch[i].child.id,
1476 &s[top].sn->branch[i].rect, cbarg)) {
1477 /* callback wants to terminate search early */
1478 return hitCount;
1479 }
1480 }
1481 }
1482 }
1483 top--;
1484 }
1485 }
1486
1487 return hitCount;
1488}
NULL
#define NULL
Definition ccmath.h:32
AMI_STREAM
Definition ami_stream.h:153
G_free
void G_free(void *)
Free allocated memory.
Definition gis/alloc.c:145
G_fatal_error
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
G_warning
void G_warning(const char *,...) __attribute__((format(printf
G_malloc
#define G_malloc(n)
Definition defs/gis.h:136
G_fseek
void G_fseek(FILE *, off_t, int)
Change the file position of the stream.
Definition gis/seek.c:48
G_ftell
off_t G_ftell(FILE *)
Get the current file position of the stream.
Definition gis/seek.c:27
G_debug
int G_debug(int, const char *,...) __attribute__((format(printf
GV_SIDX_VER_MINOR
#define GV_SIDX_VER_MINOR
Definition dig_defines.h:155
PORT_DOUBLE
#define PORT_DOUBLE
Sizes of types used in portable format (different names used in Vlib/ and diglib/ for the same thing)
Definition dig_defines.h:45
GV_SIDX_VER_MAJOR
#define GV_SIDX_VER_MAJOR
Definition dig_defines.h:154
GV_SIDX_EARLIEST_MAJOR
#define GV_SIDX_EARLIEST_MAJOR
Definition dig_defines.h:165
PORT_INT
#define PORT_INT
Definition dig_defines.h:48
PORT_INT_MAX
#define PORT_INT_MAX
Definition dig_defines.h:72
GV_SIDX_EARLIEST_MINOR
#define GV_SIDX_EARLIEST_MINOR
Definition dig_defines.h:166
dig__fread_port_D
int dig__fread_port_D(double *, size_t, struct gvfile *)
Read doubles from the Portable Vector Format.
Definition portable.c:77
dig__fread_port_O
int dig__fread_port_O(off_t *, size_t, struct gvfile *, size_t)
Read off_ts from the Portable Vector Format.
Definition portable.c:165
dig__fwrite_port_C
int dig__fwrite_port_C(const char *, size_t, struct gvfile *)
Write chars to the Portable Vector Format.
Definition portable.c:884
dig_init_portable
void dig_init_portable(struct Port_info *, int)
Set Port_info structure to byte order of file.
Definition portable.c:898
dig__fread_port_L
int dig__fread_port_L(long *, size_t, struct gvfile *)
Read longs from the Portable Vector Format.
Definition portable.c:260
dig__fwrite_port_L
int dig__fwrite_port_L(const long *, size_t, struct gvfile *)
Write longs to the Portable Vector Format.
Definition portable.c:701
dig__fwrite_port_I
int dig__fwrite_port_I(const int *, size_t, struct gvfile *)
Write integers to the Portable Vector Format.
Definition portable.c:756
dig_ftell
off_t dig_ftell(struct gvfile *file)
Get struct gvfile position.
Definition file.c:34
dig_set_cur_port
int dig_set_cur_port(struct Port_info *)
Set current Port_info structure.
Definition portable.c:994
dig__fwrite_port_D
int dig__fwrite_port_D(const double *, size_t, struct gvfile *)
Write doubles to the Portable Vector Format.
Definition portable.c:557
dig_rewind
void dig_rewind(struct gvfile *file)
Rewind file position.
Definition file.c:85
dig__fread_port_C
int dig__fread_port_C(char *, size_t, struct gvfile *)
Read chars from the Portable Vector Format.
Definition portable.c:509
dig__fread_port_I
int dig__fread_port_I(int *, size_t, struct gvfile *)
Read integers from the Portable Vector Format.
Definition portable.c:343
dig_fseek
int dig_fseek(struct gvfile *file, off_t offset, int whence)
Set struct gvfile position.
Definition file.c:58
dig_fflush
int dig_fflush(struct gvfile *file)
Flush struct gvfile.
Definition file.c:102
dig_spidx_free
void dig_spidx_free(struct Plus_head *)
Free spatial index (nodes, lines, areas, isles)
Definition spindex.c:241
dig_spidx_init
int dig_spidx_init(struct Plus_head *)
Initit spatial index (nodes, lines, areas, isles)
Definition spindex.c:33
dig__fwrite_port_O
int dig__fwrite_port_O(const off_t *, size_t, struct gvfile *, size_t)
Write off_ts to the Portable Vector Format.
Definition portable.c:634
_
#define _(str)
Definition glocale.h:10
RTreeGetNodePos
off_t RTreeGetNodePos(struct RTree *t)
Definition io.c:71
RTreeReadNode
size_t RTreeReadNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
Definition io.c:94
RTreeFlushBuffer
void RTreeFlushBuffer(struct RTree *t)
Definition io.c:241
RTreeWriteNode
size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
Definition io.c:174
file
#define file
assert
#define assert(condition)
Definition lz4.c:291
RTreeCopyNode
void RTreeCopyNode(struct RTree_Node *n1, struct RTree_Node *n2, struct RTree *t)
Definition node.c:106
RTreeAllocNode
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
Definition node.c:71
b
double b
Definition r_raster.c:37
t
double t
Definition r_raster.c:37
r
double r
Definition r_raster.c:37
RTreeOverlap
int RTreeOverlap(struct RTree_Rect *r, struct RTree_Rect *s, struct RTree *t)
Definition rect.c:587
MAXCARD
#define MAXCARD
Definition rtree.h:41
SearchHitCallback
int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)
Definition rtree.h:83
LEAFCARD
#define LEAFCARD
Definition rtree.h:43
NODE_BUFFER_SIZE
#define NODE_BUFFER_SIZE
Definition rtree.h:49
NODECARD
#define NODECARD
Definition rtree.h:42
dig_Wr_spidx_head
int dig_Wr_spidx_head(struct gvfile *fp, struct Plus_head *ptr)
Write spatial index header to file.
Definition spindex_rw.c:53
dig_Wr_spidx
int dig_Wr_spidx(struct gvfile *fp, struct Plus_head *Plus)
Write spatial index to file.
Definition spindex_rw.c:1171
dig_Rd_spidx
int dig_Rd_spidx(struct gvfile *fp, struct Plus_head *Plus)
Read spatial index from sidx file Only needed when old vector is opened in update mode.
Definition spindex_rw.c:1217
dig_Rd_spidx_head
int dig_Rd_spidx_head(struct gvfile *fp, struct Plus_head *ptr)
Read spatial index header from sidx file.
Definition spindex_rw.c:260
NUMSIDES
#define NUMSIDES
Definition spindex_rw.c:28
dig_dump_spidx
int dig_dump_spidx(FILE *fp, const struct Plus_head *Plus)
Dump spatial index.
Definition spindex_rw.c:1261
rtree_search
int rtree_search(struct RTree *t, struct RTree_Rect *r, SearchHitCallback shcb, void *cbarg, struct Plus_head *Plus)
Search spatial index file Can't use regular RTreeSearch() here because sidx must be read with dig__fr...
Definition spindex_rw.c:1381
NodeBuffer::n
struct RTree_Node n
Definition rtree.h:105
Plus_head
Basic topology-related info.
Definition dig_structs.h:757
Plus_head::Area_spidx_offset
off_t Area_spidx_offset
Offset of areas in sidx file.
Definition dig_structs.h:1055
Plus_head::coor_size
off_t coor_size
Size of coor file.
Definition dig_structs.h:1133
Plus_head::Isle_spidx_offset
off_t Isle_spidx_offset
Offset of isles in sidx file.
Definition dig_structs.h:1059
Plus_head::version
struct Plus_head::@9 version
Backward compatibility version info.
Plus_head::Hole_spidx_offset
off_t Hole_spidx_offset
Offset of holes in sidx file.
Definition dig_structs.h:1071
Plus_head::Isle_spidx
struct RTree * Isle_spidx
Isles spatial index.
Definition dig_structs.h:1088
Plus_head::Face_spidx_offset
off_t Face_spidx_offset
Offset of faces in sidx file.
Definition dig_structs.h:1063
Plus_head::off_t_size
int off_t_size
Offset size.
Definition dig_structs.h:789
Plus_head::Area_spidx
struct RTree * Area_spidx
Area spatial index.
Definition dig_structs.h:1084
Plus_head::Volume_spidx_offset
off_t Volume_spidx_offset
Offset of volumes in sidx file.
Definition dig_structs.h:1067
Plus_head::Line_spidx
struct RTree * Line_spidx
Line spatial index.
Definition dig_structs.h:1080
Plus_head::spidx_with_z
int spidx_with_z
2D/3D spatial index
Definition dig_structs.h:781
Plus_head::spidx_head_size
long spidx_head_size
Spatial index header size.
Definition dig_structs.h:800
Plus_head::spidx_port
struct Port_info spidx_port
Portability information for spatial index.
Definition dig_structs.h:821
Plus_head::Line_spidx_offset
off_t Line_spidx_offset
Offset of lines in sidx file.
Definition dig_structs.h:1051
Plus_head::Node_spidx
struct RTree * Node_spidx
Node spatial index.
Definition dig_structs.h:1076
Plus_head::Node_spidx_offset
off_t Node_spidx_offset
Offset of nodes in sidx file.
Definition dig_structs.h:1047
RTree_Branch
Definition rtree.h:64
RTree_Node
Definition rtree.h:70
RTree_Node::count
int count
Definition rtree.h:71
RTree_Node::level
int level
Definition rtree.h:72
RTree_Node::branch
struct RTree_Branch * branch
Definition rtree.h:73
RTree_Rect
Definition rtree.h:51
RTree
Definition rtree.h:120
gvfile
File definition.
Definition dig_structs.h:92
gvfile::file
FILE * file
File descriptor.
Definition dig_structs.h:96
close
#define close
Definition unistd.h:8
MAXLEVEL
#define MAXLEVEL
Maximum verbosity level.
Definition verbose.c:28
GRASS_VERSION_MINOR
#define GRASS_VERSION_MINOR
Definition version.h:3
GRASS_VERSION_MAJOR
#define GRASS_VERSION_MAJOR
Definition version.h:2