GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
io.c
Go to the documentation of this file.
1 
2 /****************************************************************************
3 * MODULE: R-Tree library
4 *
5 * AUTHOR(S): Antonin Guttman - original code
6 * Daniel Green (green@superliminal.com) - major clean-up
7 * and implementation of bounding spheres
8 * Markus Metz - file-based and memory-based R*-tree
9 *
10 * PURPOSE: Multidimensional index
11 *
12 * COPYRIGHT: (C) 2001 by the GRASS Development Team
13 *
14 * This program is free software under the GNU General Public
15 * License (>=v2). Read the file COPYING that comes with GRASS
16 * for details.
17 *****************************************************************************/
18 
19 #include <stdlib.h>
20 #include <stdio.h>
21 #include <string.h>
22 #include <sys/types.h>
23 #include <unistd.h>
24 #include <assert.h>
25 #include <errno.h>
26 #include <grass/gis.h>
27 #include "index.h"
28 
29 /* #define USAGE_SWAP */
30 
31 /* add new free node position for recycling */
32 void RTreeAddNodePos(off_t pos, int level, struct RTree *t)
33 {
34  int which, i;
35 
36  if (t->free_nodes.avail >= t->free_nodes.alloc) {
37  size_t size;
38 
39  t->free_nodes.alloc += 100;
40  size = t->free_nodes.alloc * sizeof(off_t);
41  t->free_nodes.pos = (off_t *)realloc((void *)t->free_nodes.pos, size);
42  assert(t->free_nodes.pos);
43  }
44  t->free_nodes.pos[t->free_nodes.avail++] = pos;
45 
46  /* check mru first */
47  i = 0;
48  while (t->nb[level][t->used[level][i]].pos != pos &&
49  i < NODE_BUFFER_SIZE)
50  i++;
51 
52  /* is it possible that this node is not in the buffer? */
54  which = t->used[level][i];
55  t->nb[level][which].pos = -1;
56  t->nb[level][which].dirty = 0;
57 
58  /* make it lru */
59  if (i < NODE_BUFFER_SIZE - 1) { /* which != t->used[level][NODE_BUFFER_SIZE - 1] */
60  /* simple swap does not work here */
61  while (i < NODE_BUFFER_SIZE - 1 &&
62  t->nb[level][t->used[level][i + 1]].pos != -1) {
63  t->used[level][i] = t->used[level][i + 1];
64  i++;
65  }
67  t->used[level][i] = which;
68  }
69 }
70 
71 /* look for free node position, set file pointer, return position */
72 off_t RTreeGetNodePos(struct RTree *t)
73 {
74  if (t->free_nodes.avail > 0) {
75  t->free_nodes.avail--;
76  return lseek(t->fd, t->free_nodes.pos[t->free_nodes.avail], SEEK_SET);
77  }
78  else {
79  return lseek(t->fd, 0, SEEK_END);
80  }
81 }
82 
83 /* read branch from file */
84 size_t RTreeReadBranch(struct RTree_Branch *b, struct RTree *t)
85 {
86  size_t size = 0;
87 
88  size += read(t->fd, b->rect.boundary, t->rectsize);
89  size += read(t->fd, &(b->child), sizeof(union RTree_Child));
90 
91  return size;
92 }
93 
94 /* read node from file */
95 size_t RTreeReadNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
96 {
97  int i;
98  size_t size = 0;
99 
100  lseek(t->fd, nodepos, SEEK_SET);
101  size += read(t->fd, &(n->count), sizeof(int));
102  size += read(t->fd, &(n->level), sizeof(int));
103 
104  for (i = 0; i < MAXCARD; i++) {
105  size += RTreeReadBranch(&(n->branch[i]), t);
106  }
107 
108  return size;
109 }
110 
111 /* get node from buffer or file */
112 struct RTree_Node *RTreeGetNode(off_t nodepos, int level, struct RTree *t)
113 {
114  int which, i = 0;
115 
116  /* check mru first */
117  while (t->nb[level][t->used[level][i]].pos != nodepos &&
118  t->nb[level][t->used[level][i]].pos >= 0 &&
119  i < NODE_BUFFER_SIZE - 1)
120  i++;
121 
122  which = t->used[level][i];
123 
124  if (t->nb[level][which].pos != nodepos) {
125  /* rewrite node in buffer */
126  if (t->nb[level][which].dirty) {
127  RTreeRewriteNode(&(t->nb[level][which].n),
128  t->nb[level][which].pos, t);
129  t->nb[level][which].dirty = 0;
130  }
131  RTreeReadNode(&(t->nb[level][which].n), nodepos, t);
132  t->nb[level][which].pos = nodepos;
133  }
134  /* make it mru */
135  if (i) { /* t->used[level][0] != which */
136 #ifdef USAGE_SWAP
137  t->used[level][i] = t->used[level][0];
138  t->used[level][0] = which;
139 #else
140  while (i) {
141  t->used[level][i] = t->used[level][i - 1];
142  i--;
143  }
144  t->used[level][0] = which;
145 #endif
146  }
147 
148  /* RTreeCopyNode(n, &(t->nb[level][which].n), t); */
149 
150  return &(t->nb[level][which].n);
151 }
152 
153 /* write branch to file */
154 size_t RTreeWriteBranch(struct RTree_Branch *b, struct RTree *t)
155 {
156  size_t size = 0;
157 
158  if (write(t->fd, b->rect.boundary, t->rectsize) != t->rectsize)
159  G_fatal_error("RTreeWriteBranch(): Unable to write (%s)", strerror(errno));
160  size += t->rectsize;
161  if (write(t->fd, &(b->child), sizeof(union RTree_Child)) != sizeof(union RTree_Child))
162  G_fatal_error("RTreeWriteBranch(): Unable to write (%s)", strerror(errno));
163  size += sizeof(union RTree_Child);
164 
165  return size;
166 }
167 
168 /* write new node to file */
169 size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
170 {
171  int i;
172  size_t size = 0;
173 
174  /* file position must be set first with RTreeGetFNodePos() */
175  if (write(t->fd, &(n->count), sizeof(int)) != sizeof(int))
176  G_fatal_error("RTreeWriteNode(): Unable to write (%s)", strerror(errno));
177  size += sizeof(int);
178  if (write(t->fd, &(n->level), sizeof(int)) != sizeof(int))
179  G_fatal_error("RTreeWriteNode(): Unable to write (%s)", strerror(errno));
180  size += sizeof(int);
181 
182  for (i = 0; i < MAXCARD; i++) {
183  size += RTreeWriteBranch(&(n->branch[i]), t);
184  }
185 
186  return size;
187 }
188 
189 /* rewrite updated node to file */
190 size_t RTreeRewriteNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
191 {
192  lseek(t->fd, nodepos, SEEK_SET);
193 
194  return RTreeWriteNode(n, t);
195 }
196 
197 /* mark node in buffer as changed */
198 void RTreeNodeChanged(struct RTree_Node *n, off_t nodepos, struct RTree *t)
199 {
200  int which, i = 0;
201 
202  /* check mru first */
203  while (t->nb[n->level][t->used[n->level][i]].pos != nodepos &&
204  i < NODE_BUFFER_SIZE)
205  i++;
206 
208  /* as it is used, it should always be mru */
209  assert(i == 0);
210  which = t->used[n->level][i];
211 
212  t->nb[n->level][which].dirty = 1;
213 
214  /* make it mru */
215  if (i) { /* t->used[level][0] != which */
216 #ifdef USAGE_SWAP
217  t->used[n->level][i] = t->used[n->level][0];
218  t->used[n->level][0] = which;
219 #else
220  while (i) {
221  t->used[n->level][i] = t->used[n->level][i - 1];
222  i--;
223  }
224  t->used[n->level][0] = which;
225 #endif
226  }
227 }
228 
229 /* flush pending changes to file */
230 void RTreeFlushBuffer(struct RTree *t)
231 {
232  int i, j;
233 
234  for (i = 0; i <= t->rootlevel; i++) {
235  for (j = 0; j < NODE_BUFFER_SIZE; j++) {
236  if (t->nb[i][j].dirty) {
237  RTreeRewriteNode(&(t->nb[i][j].n), t->nb[i][j].pos, t);
238  t->nb[i][j].dirty = 0;
239  }
240  }
241  }
242 }
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
size_t RTreeRewriteNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
Definition: io.c:190
void RTreeNodeChanged(struct RTree_Node *n, off_t nodepos, struct RTree *t)
Definition: io.c:198
int level
Definition: rtree.h:80
size_t RTreeReadNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
Definition: io.c:95
struct RTree::_recycle free_nodes
struct NodeBuffer ** nb
Definition: rtree.h:162
char dirty
Definition: rtree.h:115
int rootlevel
Definition: rtree.h:143
#define NODE_BUFFER_SIZE
Definition: rtree.h:55
int count
Definition: rtree.h:79
off_t * pos
Definition: rtree.h:158
void RTreeFlushBuffer(struct RTree *t)
Definition: io.c:230
double t
Definition: r_raster.c:39
#define assert(condition)
Definition: lz4.c:324
double b
Definition: r_raster.c:39
off_t pos
Definition: rtree.h:114
struct RTree_Branch * branch
Definition: rtree.h:81
size_t RTreeReadBranch(struct RTree_Branch *b, struct RTree *t)
Definition: io.c:84
int rectsize
Definition: rtree.h:138
off_t RTreeGetNodePos(struct RTree *t)
Definition: io.c:72
int fd
Definition: rtree.h:131
int ** used
Definition: rtree.h:167
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
struct RTree_Node * RTreeGetNode(off_t nodepos, int level, struct RTree *t)
Definition: io.c:112
size_t RTreeWriteBranch(struct RTree_Branch *b, struct RTree *t)
Definition: io.c:154
size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
Definition: io.c:169
struct RTree_Rect rect
Definition: rtree.h:73
Definition: rtree.h:128
void RTreeAddNodePos(off_t pos, int level, struct RTree *t)
Definition: io.c:32