GRASS GIS 7 Programmer's Manual  7.5.svn(2017)-r71769
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 <sys/types.h>
22 #include <unistd.h>
23 #include <assert.h>
24 #include <grass/config.h>
25 #include "index.h"
26 
27 /* #define USAGE_SWAP */
28 
29 /* add new free node position for recycling */
30 void RTreeAddNodePos(off_t pos, int level, struct RTree *t)
31 {
32  int which, i;
33 
34  if (t->free_nodes.avail >= t->free_nodes.alloc) {
35  size_t size;
36 
37  t->free_nodes.alloc += 100;
38  size = t->free_nodes.alloc * sizeof(off_t);
39  t->free_nodes.pos = (off_t *)realloc((void *)t->free_nodes.pos, size);
40  assert(t->free_nodes.pos);
41  }
42  t->free_nodes.pos[t->free_nodes.avail++] = pos;
43 
44  /* check mru first */
45  i = 0;
46  while (t->nb[level][t->used[level][i]].pos != pos &&
47  i < NODE_BUFFER_SIZE)
48  i++;
49 
50  /* is it possible that this node is not in the buffer? */
51  assert(i < NODE_BUFFER_SIZE);
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 - 1) { /* which != t->used[level][NODE_BUFFER_SIZE - 1] */
58  /* simple swap does not work here */
59  while (i < NODE_BUFFER_SIZE - 1 &&
60  t->nb[level][t->used[level][i + 1]].pos != -1) {
61  t->used[level][i] = t->used[level][i + 1];
62  i++;
63  }
64  assert(i < NODE_BUFFER_SIZE);
65  t->used[level][i] = which;
66  }
67 }
68 
69 /* look for free node position, set file pointer, return position */
70 off_t RTreeGetNodePos(struct RTree *t)
71 {
72  if (t->free_nodes.avail > 0) {
73  t->free_nodes.avail--;
74  return lseek(t->fd, t->free_nodes.pos[t->free_nodes.avail], SEEK_SET);
75  }
76  else {
77  return lseek(t->fd, 0, SEEK_END);
78  }
79 }
80 
81 /* read branch from file */
82 size_t RTreeReadBranch(struct RTree_Branch *b, struct RTree *t)
83 {
84  size_t size = 0;
85 
86  size += read(t->fd, b->rect.boundary, t->rectsize);
87  size += read(t->fd, &(b->child), sizeof(union RTree_Child));
88 
89  return size;
90 }
91 
92 /* read node from file */
93 size_t RTreeReadNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
94 {
95  int i;
96  size_t size = 0;
97 
98  lseek(t->fd, nodepos, SEEK_SET);
99  size += read(t->fd, &(n->count), sizeof(int));
100  size += read(t->fd, &(n->level), sizeof(int));
101 
102  for (i = 0; i < MAXCARD; i++) {
103  size += RTreeReadBranch(&(n->branch[i]), t);
104  }
105 
106  return size;
107 }
108 
109 /* get node from buffer or file */
110 struct RTree_Node *RTreeGetNode(off_t nodepos, int level, struct RTree *t)
111 {
112  int which, i = 0;
113 
114  /* check mru first */
115  while (t->nb[level][t->used[level][i]].pos != nodepos &&
116  t->nb[level][t->used[level][i]].pos >= 0 &&
117  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),
126  t->nb[level][which].pos, 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  size += write(t->fd, b->rect.boundary, t->rectsize);
157  size += write(t->fd, &(b->child), sizeof(union RTree_Child));
158 
159  return size;
160 }
161 
162 /* write new node to file */
163 size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
164 {
165  int i;
166  size_t size = 0;
167 
168  /* file position must be set first with RTreeGetFNodePos() */
169  size += write(t->fd, &(n->count), sizeof(int));
170  size += write(t->fd, &(n->level), sizeof(int));
171 
172  for (i = 0; i < MAXCARD; i++) {
173  size += RTreeWriteBranch(&(n->branch[i]), t);
174  }
175 
176  return size;
177 }
178 
179 /* rewrite updated node to file */
180 size_t RTreeRewriteNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
181 {
182  lseek(t->fd, nodepos, SEEK_SET);
183 
184  return RTreeWriteNode(n, t);
185 }
186 
187 /* mark node in buffer as changed */
188 void RTreeNodeChanged(struct RTree_Node *n, off_t nodepos, struct RTree *t)
189 {
190  int which, i = 0;
191 
192  /* check mru first */
193  while (t->nb[n->level][t->used[n->level][i]].pos != nodepos &&
194  i < NODE_BUFFER_SIZE)
195  i++;
196 
197  assert(i < NODE_BUFFER_SIZE);
198  /* as it is used, it should always be mru */
199  assert(i == 0);
200  which = t->used[n->level][i];
201 
202  t->nb[n->level][which].dirty = 1;
203 
204  /* make it mru */
205  if (i) { /* t->used[level][0] != which */
206 #ifdef USAGE_SWAP
207  t->used[n->level][i] = t->used[n->level][0];
208  t->used[n->level][0] = which;
209 #else
210  while (i) {
211  t->used[n->level][i] = t->used[n->level][i - 1];
212  i--;
213  }
214  t->used[n->level][0] = which;
215 #endif
216  }
217 }
218 
219 /* flush pending changes to file */
220 void RTreeFlushBuffer(struct RTree *t)
221 {
222  int i, j;
223 
224  for (i = 0; i <= t->rootlevel; i++) {
225  for (j = 0; j < NODE_BUFFER_SIZE; j++) {
226  if (t->nb[i][j].dirty) {
227  RTreeRewriteNode(&(t->nb[i][j].n), t->nb[i][j].pos, t);
228  t->nb[i][j].dirty = 0;
229  }
230  }
231  }
232 }
int level
Definition: rtree.h:80
size_t RTreeReadNode(struct RTree_Node *n, off_t nodepos, struct RTree *t)
Definition: io.c:93
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:220
double t
Definition: r_raster.c:39
double b
Definition: r_raster.c:39
off_t pos
Definition: rtree.h:114
void RTreeAddNodePos(off_t, int, struct RTree *)
Definition: io.c:30
struct RTree_Branch * branch
Definition: rtree.h:81
size_t RTreeReadBranch(struct RTree_Branch *b, struct RTree *t)
Definition: io.c:82
int rectsize
Definition: rtree.h:138
off_t RTreeGetNodePos(struct RTree *t)
Definition: io.c:70
size_t RTreeRewriteNode(struct RTree_Node *, off_t, struct RTree *)
Definition: io.c:180
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
void RTreeNodeChanged(struct RTree_Node *, off_t, struct RTree *)
Definition: io.c:188
struct RTree_Node * RTreeGetNode(off_t, int, struct RTree *)
Definition: io.c:110
size_t RTreeWriteBranch(struct RTree_Branch *b, struct RTree *t)
Definition: io.c:152
size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
Definition: io.c:163
struct RTree_Rect rect
Definition: rtree.h:73
Definition: rtree.h:128