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