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