GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-f8115df121
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 
690 static off_t rtree_write_from_memory(struct gvfile *fp, off_t startpos,
691  struct RTree *t, int off_t_size)
692 {
693  off_t nextfreepos = startpos;
694  int sidx_nodesize, sidx_leafsize;
695  struct RTree_Node *n;
696  int i, j, writeout, maxcard;
697  struct spidxpstack *s = G_malloc(MAXLEVEL * sizeof(struct spidxstack));
698  int top = 0;
699 
700  /* should be foolproof */
701  sidx_nodesize = (int)(2 * PORT_INT +
702  t->nodecard * (off_t_size + NUMSIDES * PORT_DOUBLE));
703  sidx_leafsize = (int)(2 * PORT_INT +
704  t->leafcard * (off_t_size + NUMSIDES * PORT_DOUBLE));
705 
706  /* stack size of t->rootlevel + 1 would be enough because of
707  * depth-first post-order traversal:
708  * only one node per level on stack at any given time */
709 
710  /* add root node position to stack */
711  s[top].branch_id = i = 0;
712  s[top].sn = t->root;
713 
714  /* depth-first postorder traversal
715  * all children of a node are visitied and written out first
716  * when a child is written out, its position in file is stored in pos[] for
717  * the parent node and written out with the parent node */
718  /* root node is written out last and its position returned */
719 
720  while (top >= 0) {
721  if (s[top].sn == NULL)
722  G_fatal_error("NULL node ptr at top = %d", top);
723  n = s[top].sn;
724  writeout = 1;
725  /* this is an internal node in the RTree
726  * all its children are processed first,
727  * before it is written out to the sidx file */
728  if (s[top].sn->level > 0) {
729  for (i = s[top].branch_id; i < t->nodecard; i++) {
730  s[top].pos[i] = 0;
731  if (n->branch[i].child.ptr != NULL) {
732  s[top++].branch_id = i + 1;
733  s[top].sn = n->branch[i].child.ptr;
734  s[top].branch_id = 0;
735  writeout = 0;
736  break;
737  }
738  }
739  if (writeout) {
740  /* nothing else found, ready to write out */
741  s[top].branch_id = t->nodecard;
742  }
743  }
744  if (writeout) {
745  /* write node to sidx file */
746  if (G_ftell(fp->file) != nextfreepos)
747  G_fatal_error("Unable to write spatial index. "
748  "Wrong node position (%" PRId64
749  ") in file (should be %" PRId64 ").",
750  G_ftell(fp->file), nextfreepos);
751 
752  /* write with dig__fwrite_port_* fns */
753  dig__fwrite_port_I(&(s[top].sn->count), 1, fp);
754  dig__fwrite_port_I(&(s[top].sn->level), 1, fp);
755  maxcard = s[top].sn->level ? t->nodecard : t->leafcard;
756  for (j = 0; j < maxcard; j++) {
757  dig__fwrite_port_D(s[top].sn->branch[j].rect.boundary, NUMSIDES,
758  fp);
759  /* leaf node: vector object IDs are stored in child.id */
760  if (s[top].sn->level == 0)
761  s[top].pos[j] = (off_t)s[top].sn->branch[j].child.id;
762  dig__fwrite_port_O(&(s[top].pos[j]), 1, fp, off_t_size);
763  }
764 
765  top--;
766  /* update corresponding child position of parent node
767  * this node is only updated if its level is > 0, i.e.
768  * this is an internal node
769  * children of internal nodes do not have an ID, instead
770  * they hold the position in file of the next nodes down the tree */
771  if (top >= 0) {
772  s[top].pos[s[top].branch_id - 1] = nextfreepos;
773  nextfreepos +=
774  (s[top + 1].sn->level ? sidx_nodesize : sidx_leafsize);
775  }
776  }
777  }
778 
779  G_free(s);
780 
781  return nextfreepos;
782 }
783 
784 /*!
785  \brief Write RTree body from temporary file to sidx file
786  Must be called when new or updated vector is closed
787 
788  \param[out] fp pointer to struct gvfile
789  \param startpos offset to struct gvfile where to start writing out
790  \param t pointer to RTree
791  \param off_t_size size of off_t used to write struct gvfile
792 
793  \return -1 on error
794  \return offset to root node on success
795  */
796 
797 static off_t rtree_write_from_file(struct gvfile *fp, off_t startpos,
798  struct RTree *t, int off_t_size)
799 {
800  off_t nextfreepos = startpos;
801  int sidx_nodesize, sidx_leafsize;
802  struct RTree_Node *n;
803  int i, j, writeout, maxcard;
804  static struct spidxstack *s = NULL;
805  int top = 0;
806 
807  if (!s) {
808  s = G_malloc(MAXLEVEL * sizeof(struct spidxstack));
809  for (i = 0; i < MAXLEVEL; i++) {
810  s[i].sn.branch = G_malloc(MAXCARD * sizeof(struct RTree_Branch));
811  for (j = 0; j < MAXCARD; j++) {
812  s[i].sn.branch[j].rect.boundary =
813  G_malloc(6 * sizeof(RectReal));
814  }
815  }
816  }
817 
818  /* write pending changes to file */
819  RTreeFlushBuffer(t);
820 
821  /* should be foolproof */
822  sidx_nodesize = (int)(2 * PORT_INT +
823  t->nodecard * (off_t_size + NUMSIDES * PORT_DOUBLE));
824  sidx_leafsize = (int)(2 * PORT_INT +
825  t->leafcard * (off_t_size + NUMSIDES * PORT_DOUBLE));
826 
827  /* stack size of t->rootlevel + 1 would be enough because of
828  * depth-first post-order traversal:
829  * only one node per level on stack at any given time */
830 
831  /* add root node position to stack */
832  s[top].branch_id = i = 0;
833  RTreeReadNode(&s[top].sn, t->rootpos, t);
834 
835  /* depth-first postorder traversal
836  * all children of a node are visitied and written out first
837  * when a child is written out, its position in file is stored in pos[] for
838  * the parent node and written out with the parent node */
839  /* root node is written out last and its position returned */
840 
841  while (top >= 0) {
842  n = &(s[top].sn);
843  writeout = 1;
844  /* this is an internal node in the RTree
845  * all its children are processed first,
846  * before it is written out to the sidx file */
847  if (s[top].sn.level > 0) {
848  for (i = s[top].branch_id; i < t->nodecard; i++) {
849  s[top].pos[i] = 0;
850  if (n->branch[i].child.pos >= 0) {
851  s[top++].branch_id = i + 1;
852  RTreeReadNode(&s[top].sn, n->branch[i].child.pos, t);
853  s[top].branch_id = 0;
854  writeout = 0;
855  break;
856  }
857  }
858  if (writeout) {
859  /* nothing else found, ready to write out */
860  s[top].branch_id = t->nodecard;
861  }
862  }
863  if (writeout) {
864  /* write node to sidx file */
865  if (G_ftell(fp->file) != nextfreepos)
866  G_fatal_error("Unable to write spatial index. "
867  "Wrong node position (%" PRId64
868  ") in file (should be %" PRId64 ").",
869  G_ftell(fp->file), nextfreepos);
870 
871  /* write with dig__fwrite_port_* fns */
872  dig__fwrite_port_I(&(s[top].sn.count), 1, fp);
873  dig__fwrite_port_I(&(s[top].sn.level), 1, fp);
874  maxcard = s[top].sn.level ? t->nodecard : t->leafcard;
875  for (j = 0; j < maxcard; j++) {
876  dig__fwrite_port_D(s[top].sn.branch[j].rect.boundary, NUMSIDES,
877  fp);
878  /* leaf node: vector object IDs are stored in child.id */
879  if (s[top].sn.level == 0)
880  s[top].pos[j] = (off_t)s[top].sn.branch[j].child.id;
881  dig__fwrite_port_O(&(s[top].pos[j]), 1, fp, off_t_size);
882  }
883 
884  top--;
885  /* update corresponding child position of parent node
886  * this node is only updated if its level is > 0, i.e.
887  * this is an internal node
888  * children of internal nodes do not have an ID, instead
889  * they hold the position in file of the next nodes down the tree */
890  if (top >= 0) {
891  s[top].pos[s[top].branch_id - 1] = nextfreepos;
892  nextfreepos +=
893  (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 =
940  G_malloc(6 * sizeof(RectReal));
941  }
942  }
943  }
944 
945  /* stack size of t->rootlevel + 1 would be enough because of
946  * depth-first postorder traversal:
947  * only one node per level on stack at any given time */
948 
949  /* add root node position to stack */
950  last = &(s[top]);
951  G_fseek(fp->file, rootpos, SEEK_SET);
952  /* read with dig__fread_port_* fns */
953  dig__fread_port_I(&(s[top].sn.count), 1, fp);
954  dig__fread_port_I(&(s[top].sn.level), 1, fp);
955  maxcard = s[top].sn.level ? t->nodecard : t->leafcard;
956  for (j = 0; j < maxcard; j++) {
957  dig__fread_port_D(s[top].sn.branch[j].rect.boundary, NUMSIDES, fp);
958  dig__fread_port_O(&(s[top].pos[j]), 1, fp, off_t_size);
959  /* leaf node: vector object IDs are stored in child.id */
960  if (s[top].sn.level == 0) {
961  s[top].sn.branch[j].child.id = (int)s[top].pos[j];
962  }
963  else {
964  s[top].sn.branch[j].child.ptr = NULL;
965  }
966  }
967 
968  s[top].branch_id = i = 0;
969 
970  /* some sort of postorder traversal */
971  /* root node is loaded last and returned */
972 
973  while (top >= 0) {
974  last = &(s[top]);
975  loadnode = 1;
976  /* this is an internal node in the RTree
977  * all its children are read first,
978  * before it is transferred to the RTree in memory */
979  if (s[top].sn.level > 0) {
980  for (i = s[top].branch_id; i < t->nodecard; i++) {
981  if (s[top].pos[i] > 0) {
982  s[top++].branch_id = i + 1;
983  G_fseek(fp->file, last->pos[i], SEEK_SET);
984  /* read with dig__fread_port_* fns */
985  dig__fread_port_I(&(s[top].sn.count), 1, fp);
986  dig__fread_port_I(&(s[top].sn.level), 1, fp);
987  maxcard = s[top].sn.level ? t->nodecard : t->leafcard;
988  for (j = 0; j < maxcard; j++) {
989  dig__fread_port_D(s[top].sn.branch[j].rect.boundary,
990  NUMSIDES, fp);
991  dig__fread_port_O(&(s[top].pos[j]), 1, fp, 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 = (int)s[top].pos[j];
998  }
999  else {
1000  s[top].sn.branch[j].child.ptr = NULL;
1001  }
1002  }
1003  s[top].branch_id = 0;
1004  loadnode = 0;
1005  break;
1006  }
1007  else if (last->pos[i] < 0)
1008  G_fatal_error("corrupt spatial index");
1009  }
1010  if (loadnode) {
1011  /* nothing else found, ready to load */
1012  s[top].branch_id = t->nodecard;
1013  }
1014  }
1015  if (loadnode) {
1016  /* ready to load node to memory */
1017 
1018  newnode = RTreeAllocNode(t, s[top].sn.level);
1019  /* copy from stack node */
1020  RTreeCopyNode(newnode, &(s[top].sn), t);
1021 
1022  top--;
1023  /* update child of parent node
1024  * this node is only updated if its level is > 0, i.e.
1025  * this is an internal node
1026  * children of internal nodes do not have an ID, instead
1027  * they point to the next nodes down the tree */
1028  if (top >= 0) {
1029  s[top].sn.branch[s[top].branch_id - 1].child.ptr = newnode;
1030  }
1031  }
1032  }
1033 
1034  t->root = newnode;
1035 }
1036 
1037 /*!
1038  \brief Load RTree body from sidx file to temporary file
1039  Must be called when old vector is opened in update mode
1040 
1041  \param fp pointer to struct gvfile
1042  \param rootpos position of root node in file
1043  \param t pointer to RTree
1044  \param off_t_size size of off_t used to read struct gvfile
1045 
1046  \return offset to root node
1047  */
1048 
1049 static void rtree_load_to_file(struct gvfile *fp, off_t rootpos,
1050  struct RTree *t, int off_t_size)
1051 {
1052  off_t newnode_pos = -1;
1053  int i, j, loadnode, maxcard;
1054  struct spidxstack *last;
1055  static struct spidxstack *s = NULL;
1056  int top = 0;
1057 
1058  if (!s) {
1059  s = G_malloc(MAXLEVEL * sizeof(struct spidxstack));
1060  for (i = 0; i < MAXLEVEL; i++) {
1061  s[i].sn.branch = G_malloc(MAXCARD * sizeof(struct RTree_Branch));
1062  for (j = 0; j < MAXCARD; j++) {
1063  s[i].sn.branch[j].rect.boundary =
1064  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, off_t_size);
1116  /* leaf node
1117  * vector object IDs are stored in file as
1118  * off_t but always fit into an int, see dig_structs.h
1119  * vector object IDs are transferred to child.id */
1120  if (s[top].sn.level == 0) {
1121  s[top].sn.branch[j].child.id = (int)s[top].pos[j];
1122  }
1123  else {
1124  s[top].sn.branch[j].child.pos = -1;
1125  }
1126  }
1127  s[top].branch_id = 0;
1128  loadnode = 0;
1129  break;
1130  }
1131  else if (last->pos[i] < 0)
1132  G_fatal_error("corrupt spatial index");
1133  }
1134  if (loadnode) {
1135  /* nothing else found, ready to load */
1136  s[top].branch_id = t->nodecard;
1137  }
1138  }
1139  if (loadnode) {
1140  /* ready to load node and write to temp file */
1141 
1142  newnode_pos = RTreeGetNodePos(t);
1143  RTreeWriteNode(&(s[top].sn), t);
1144 
1145  top--;
1146  /* update child of parent node
1147  * this node is only updated if its level is > 0, i.e.
1148  * this is an internal node
1149  * children of internal nodes do not have an ID, instead
1150  * they point to the next nodes down the tree */
1151  if (top >= 0) {
1152  s[top].sn.branch[s[top].branch_id - 1].child.pos = newnode_pos;
1153  }
1154  }
1155  }
1156 
1157  t->rootpos = newnode_pos;
1158 }
1159 
1160 static void rtree_load_from_sidx(struct gvfile *fp, off_t rootpos,
1161  struct RTree *t, int off_t_size)
1162 {
1163  if (t->fd > -1)
1164  rtree_load_to_file(fp, rootpos, t, off_t_size);
1165  else
1166  rtree_load_to_memory(fp, rootpos, t, off_t_size);
1167 }
1168 
1169 /*!
1170  \brief Write spatial index to file
1171 
1172  \param[out] fp pointer to struct gvfile
1173  \param Plus pointer to Plus_head structure
1174 
1175  \return 0
1176  */
1177 int dig_Wr_spidx(struct gvfile *fp, struct Plus_head *Plus)
1178 {
1179  G_debug(1, "dig_Wr_spidx()");
1180 
1181  dig_set_cur_port(&(Plus->spidx_port));
1182  dig_rewind(fp);
1183 
1184  dig_Wr_spidx_head(fp, Plus);
1185 
1186  /* Nodes */
1187  Plus->Node_spidx_offset = rtree_write_to_sidx(
1188  fp, dig_ftell(fp), Plus->Node_spidx, Plus->spidx_port.off_t_size);
1189 
1190  /* Lines */
1191  Plus->Line_spidx_offset = rtree_write_to_sidx(
1192  fp, dig_ftell(fp), Plus->Line_spidx, Plus->spidx_port.off_t_size);
1193 
1194  /* Areas */
1195  Plus->Area_spidx_offset = rtree_write_to_sidx(
1196  fp, dig_ftell(fp), Plus->Area_spidx, Plus->spidx_port.off_t_size);
1197 
1198  /* Isles */
1199  Plus->Isle_spidx_offset = rtree_write_to_sidx(
1200  fp, dig_ftell(fp), Plus->Isle_spidx, Plus->spidx_port.off_t_size);
1201 
1202  /* 3D future : */
1203  /* Faces */
1204  /* Volumes */
1205  /* Holes */
1206 
1207  dig_rewind(fp);
1208  dig_Wr_spidx_head(fp, Plus); /* rewrite with offsets */
1209 
1210  dig_fflush(fp);
1211  return 0;
1212 }
1213 
1214 /*!
1215  \brief Read spatial index from sidx file
1216  Only needed when old vector is opened in update mode
1217 
1218  \param fp pointer to struct gvfile
1219  \param[in,out] Plus pointer to Plus_head structure
1220 
1221  \return 0
1222  */
1223 int dig_Rd_spidx(struct gvfile *fp, struct Plus_head *Plus)
1224 {
1225  G_debug(1, "dig_read_spindx()");
1226 
1227  /* free old trees, init new trees */
1228  dig_spidx_free(Plus);
1229  dig_spidx_init(Plus);
1230 
1231  dig_rewind(fp);
1232  dig_Rd_spidx_head(fp, Plus);
1233  dig_set_cur_port(&(Plus->spidx_port));
1234 
1235  /* Nodes */
1236  rtree_load_from_sidx(fp, Plus->Node_spidx_offset, Plus->Node_spidx,
1237  Plus->spidx_port.off_t_size);
1238 
1239  /* Lines */
1240  rtree_load_from_sidx(fp, Plus->Line_spidx_offset, Plus->Line_spidx,
1241  Plus->spidx_port.off_t_size);
1242 
1243  /* Areas */
1244  rtree_load_from_sidx(fp, Plus->Area_spidx_offset, Plus->Area_spidx,
1245  Plus->spidx_port.off_t_size);
1246 
1247  /* Isles */
1248  rtree_load_from_sidx(fp, Plus->Isle_spidx_offset, Plus->Isle_spidx,
1249  Plus->spidx_port.off_t_size);
1250 
1251  /* 3D future : */
1252  /* Faces */
1253  /* Volumes */
1254  /* Holes */
1255 
1256  return 0;
1257 }
1258 
1259 /*!
1260  \brief Dump spatial index
1261 
1262  \param[out] fp pointer to FILE
1263  \param Plus pointer to Plus_head structure
1264 
1265  \return 0
1266  */
1267 int dig_dump_spidx(FILE *fp, const struct Plus_head *Plus)
1268 {
1269  fprintf(fp, "Nodes\n");
1270  if (Plus->Node_spidx->fd < 0)
1271  rtree_dump_node(fp, Plus->Node_spidx->root, Plus->with_z);
1272  else {
1273  RTreeFlushBuffer(Plus->Node_spidx);
1274  rtree_dump_node_file(fp, Plus->Node_spidx->rootpos, Plus->with_z,
1275  Plus->Node_spidx);
1276  }
1277 
1278  fprintf(fp, "Lines\n");
1279  if (Plus->Line_spidx->fd < 0)
1280  rtree_dump_node(fp, Plus->Line_spidx->root, Plus->with_z);
1281  else {
1282  RTreeFlushBuffer(Plus->Line_spidx);
1283  rtree_dump_node_file(fp, Plus->Line_spidx->rootpos, Plus->with_z,
1284  Plus->Line_spidx);
1285  }
1286 
1287  fprintf(fp, "Areas\n");
1288  if (Plus->Area_spidx->fd < 0)
1289  rtree_dump_node(fp, Plus->Area_spidx->root, Plus->with_z);
1290  else {
1291  RTreeFlushBuffer(Plus->Area_spidx);
1292  rtree_dump_node_file(fp, Plus->Area_spidx->rootpos, Plus->with_z,
1293  Plus->Area_spidx);
1294  }
1295 
1296  fprintf(fp, "Isles\n");
1297  if (Plus->Isle_spidx->fd < 0)
1298  rtree_dump_node(fp, Plus->Isle_spidx->root, Plus->with_z);
1299  else {
1300  RTreeFlushBuffer(Plus->Isle_spidx);
1301  rtree_dump_node_file(fp, Plus->Isle_spidx->rootpos, Plus->with_z,
1302  Plus->Isle_spidx);
1303  }
1304 
1305  return 0;
1306 }
1307 
1308 /* read node from file */
1309 static void rtree_read_node(struct NodeBuffer *nb, off_t nodepos,
1310  struct RTree *t, struct Plus_head *Plus)
1311 {
1312  int i, maxcard;
1313  off_t pos;
1314  struct gvfile *file = &(Plus->spidx_fp);
1315 
1316  dig_fseek(file, nodepos, SEEK_SET);
1317  /* read with dig__fread_port_* fns */
1318  dig__fread_port_I(&(nb->n.count), 1, file);
1319  dig__fread_port_I(&(nb->n.level), 1, file);
1320  maxcard = nb->n.level ? t->nodecard : t->leafcard;
1321  for (i = 0; i < maxcard; i++) {
1322  dig__fread_port_D(nb->n.branch[i].rect.boundary, NUMSIDES, file);
1323  dig__fread_port_O(&pos, 1, file, Plus->spidx_port.off_t_size);
1324  /* leaf node: vector object IDs are stored in child.id */
1325  if (nb->n.level == 0) {
1326  nb->n.branch[i].child.id = (int)pos;
1327  }
1328  else {
1329  nb->n.branch[i].child.pos = pos;
1330  }
1331  }
1332 }
1333 
1334 /* get node from buffer or file */
1335 static struct RTree_Node *rtree_get_node(off_t nodepos, int level,
1336  struct RTree *t,
1337  struct Plus_head *Plus)
1338 {
1339  int which, i = 0;
1340 
1341  /* check mru first */
1342  /* t->used[level][i] */
1343  while (t->nb[level][t->used[level][i]].pos != nodepos &&
1344  t->nb[level][t->used[level][i]].pos >= 0 &&
1345  i < NODE_BUFFER_SIZE - 1) {
1346  i++;
1347  }
1348 
1349  which = t->used[level][i];
1350 
1351  if (t->nb[level][which].pos != nodepos) {
1352  rtree_read_node(&(t->nb[level][which]), nodepos, t, Plus);
1353  t->nb[level][which].pos = nodepos;
1354  }
1355  assert(t->nb[level][which].n.level == level);
1356 
1357  /* make it mru */
1358  if (i) { /* t->used[level][0] != which */
1359 #if 0
1360  t->used[level][i] = t->used[level][0];
1361  t->used[level][0] = which;
1362 #else
1363  while (i) {
1364  t->used[level][i] = t->used[level][i - 1];
1365  i--;
1366  }
1367  t->used[level][0] = which;
1368 #endif
1369  }
1370 
1371  return &(t->nb[level][which].n);
1372 }
1373 
1374 /*!
1375  \brief Search spatial index file
1376  Can't use regular RTreeSearch() here because sidx must be read
1377  with dig__fread_port_*() functions
1378 
1379  \param t pointer to RTree
1380  \param r search rectangle
1381  \param shcb user-provided callback
1382  \param cbarg argument for shcb
1383  \param Plus pointer to Plus_head structure
1384 
1385  \return number of qualifying rectangles
1386  */
1387 int rtree_search(struct RTree *t, struct RTree_Rect *r, SearchHitCallback shcb,
1388  void *cbarg, struct Plus_head *Plus)
1389 {
1390  int hitCount = 0, found;
1391 
1392  /* int j, maxcard; */
1393  int i;
1394  struct spidxpstack s[MAXLEVEL];
1395  int top = 0, level;
1396  off_t lastpos;
1397 
1398  assert(r);
1399  assert(t);
1400 
1401  /* stack size of t->rootlevel + 1 is enough because of depth first search */
1402  /* only one node per level on stack at any given time */
1403 
1404  dig_set_cur_port(&(Plus->spidx_port));
1405 
1406  /* add root node position to stack */
1407  s[top].sn = rtree_get_node(t->rootpos, t->rootlevel, t, Plus);
1408 #if 0
1409  dig_fseek(&(Plus->spidx_fp), t->rootpos, SEEK_SET);
1410  /* read with dig__fread_port_* fns */
1411  dig__fread_port_I(&(s[top].sn.count), 1, &(Plus->spidx_fp));
1412  dig__fread_port_I(&(s[top].sn.level), 1, &(Plus->spidx_fp));
1413  maxcard = t->rootlevel ? t->nodecard : t->leafcard;
1414  for (j = 0; j < maxcard; j++) {
1415  dig__fread_port_D(s[top].sn.branch[j].rect.boundary, NUMSIDES,
1416  &(Plus->spidx_fp));
1417  dig__fread_port_O(&(s[top].pos[j]), 1, &(Plus->spidx_fp),
1418  Plus->spidx_port.off_t_size);
1419  /* leaf node: vector object IDs are stored in child.id */
1420  if (s[top].sn.level == 0) {
1421  s[top].sn.branch[j].child.id = (int)s[top].pos[j];
1422  }
1423  else {
1424  s[top].sn.branch[j].child.pos = s[top].pos[j];
1425  }
1426  }
1427 #endif
1428 
1429  s[top].branch_id = i = 0;
1430 
1431  while (top >= 0) {
1432  level = s[top].sn->level;
1433  if (level > 0) { /* this is an internal node in the tree */
1434  found = 1;
1435  for (i = s[top].branch_id; i < t->nodecard; i++) {
1436  lastpos = s[top].sn->branch[i].child.pos;
1437  if (lastpos > 0 &&
1438  RTreeOverlap(r, &(s[top].sn->branch[i].rect), t)) {
1439  s[top++].branch_id = i + 1;
1440  s[top].sn = rtree_get_node(lastpos, level - 1, t, Plus);
1441 
1442 #if 0
1443  dig_fseek(&(Plus->spidx_fp), lastpos, SEEK_SET);
1444  /* read with dig__fread_port_* fns */
1445  dig__fread_port_I(&(s[top].sn.count), 1,
1446  &(Plus->spidx_fp));
1447  dig__fread_port_I(&(s[top].sn.level), 1,
1448  &(Plus->spidx_fp));
1449  maxcard = s[top].sn.level ? t->nodecard : t->leafcard;
1450  for (j = 0; j < maxcard; j++) {
1451  dig__fread_port_D(s[top].sn.branch[j].rect.boundary,
1452  NUMSIDES, &(Plus->spidx_fp));
1453  dig__fread_port_O(&(s[top].pos[j]), 1,
1454  &(Plus->spidx_fp),
1455  Plus->spidx_port.off_t_size);
1456  if (s[top].sn.level == 0) {
1457  s[top].sn.branch[j].child.id = (int)s[top].pos[j];
1458  }
1459  else {
1460  s[top].sn.branch[j].child.pos = s[top].pos[j];
1461  }
1462  }
1463 #endif
1464  s[top].branch_id = 0;
1465  found = 0;
1466  break;
1467  }
1468  }
1469  if (found) {
1470  /* nothing else found, go back up */
1471  s[top].branch_id = t->nodecard;
1472  top--;
1473  }
1474  }
1475  else { /* this is a leaf node */
1476  for (i = 0; i < t->leafcard; i++) {
1477  if (s[top].sn->branch[i].child.id &&
1478  RTreeOverlap(r, &(s[top].sn->branch[i].rect), t)) {
1479  hitCount++;
1480  if (shcb) { /* call the user-provided callback */
1481  if (!shcb((int)s[top].sn->branch[i].child.id,
1482  &s[top].sn->branch[i].rect, cbarg)) {
1483  /* callback wants to terminate search early */
1484  return hitCount;
1485  }
1486  }
1487  }
1488  }
1489  top--;
1490  }
1491  }
1492 
1493  return hitCount;
1494 }
NULL
#define NULL
Definition: ccmath.h:32
G_free
void G_free(void *)
Free allocated memory.
Definition: gis/alloc.c:150
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:235
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:393
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:1177
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:1223
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:1267
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:1387
if
if(!(yy_init))
Definition: sqlp.yy.c:775
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
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