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