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