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