Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Contents of /trunk/src/cache.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1292 - (show annotations) (download) (as text)
Fri May 3 15:25:56 2013 UTC (11 years, 10 months ago) by amb
File MIME type: text/x-csrc
File size: 7265 byte(s)
Add node, segment, way and turn relation cache for slim mode.  Approx 40%
speed-up for router.

1 /***************************************
2 Functions to maintain an in-RAM cache of on-disk data for slim mode.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2013 Andrew M. Bishop
7
8 This program is free software: you can redistribute it and/or modify
9 it under the terms of the GNU Affero General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU Affero General Public License for more details.
17
18 You should have received a copy of the GNU Affero General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>.
20 ***************************************/
21
22
23 #include <stdlib.h>
24
25 #include "types.h"
26 #include "nodes.h"
27 #include "segments.h"
28 #include "ways.h"
29 #include "relations.h"
30
31 #include "cache.h"
32
33
34 #if SLIM
35
36
37 #define CACHEWIDTH 2048
38 #define CACHEDEPTH 16
39
40
41 /*+ A cache of Nodes. +*/
42 struct _NodeCache
43 {
44 int first [CACHEWIDTH]; /*+ The first entry to fill +*/
45
46 Node data [CACHEWIDTH][CACHEDEPTH]; /*+ The array of nodes. +*/
47 index_t indices[CACHEWIDTH][CACHEDEPTH]; /*+ The array of indexes. +*/
48
49 index_t accesses;
50 index_t cached;
51 };
52
53 /*+ A cache of Segments. +*/
54 struct _SegmentCache
55 {
56 int first [CACHEWIDTH]; /*+ The first entry to fill +*/
57
58 Segment data [CACHEWIDTH][CACHEDEPTH]; /*+ The array of segments. +*/
59 index_t indices[CACHEWIDTH][CACHEDEPTH]; /*+ The array of indexes. +*/
60
61 index_t accesses;
62 index_t cached;
63 };
64
65 /*+ A cache of Ways. +*/
66 struct _WayCache
67 {
68 int first [CACHEWIDTH]; /*+ The first entry to fill +*/
69
70 Way data [CACHEWIDTH][CACHEDEPTH]; /*+ The array of ways. +*/
71 index_t indices[CACHEWIDTH][CACHEDEPTH]; /*+ The array of indexes. +*/
72
73 index_t accesses;
74 index_t cached;
75 };
76
77 /*+ A cache of Turn Relations. +*/
78 struct _TurnRelationCache
79 {
80 int first [CACHEWIDTH]; /*+ The first entry to fill +*/
81
82 TurnRelation data [CACHEWIDTH][CACHEDEPTH]; /*+ The array of turn relations. +*/
83 index_t indices[CACHEWIDTH][CACHEDEPTH]; /*+ The array of indexes. +*/
84
85 index_t accesses;
86 index_t cached;
87 };
88
89
90
91 NodeCache *NewNodeCache(void)
92 {
93 NodeCache *cache;
94
95 cache=(NodeCache*)malloc(sizeof(NodeCache));
96
97 InvalidateNodeCache(cache);
98
99 return(cache);
100 }
101
102
103 void DeleteNodeCache(NodeCache *cache)
104 {
105 printf("DeleteNodeCache access=%ld cached=%ld hit-rate=%.1f%%\n",cache->accesses,cache->cached,100*(double)cache->cached/(double)cache->accesses);
106
107 free(cache);
108 }
109
110
111 Node *FetchCachedNode(Nodes *nodes,index_t index)
112 {
113 int row=index%CACHEWIDTH;
114 int col;
115
116 nodes->cache->accesses++;
117
118 for(col=0;col<CACHEDEPTH;col++)
119 if(nodes->cache->indices[row][col]==index)
120 {
121 nodes->cache->cached++;
122 return(&nodes->cache->data[row][col]);
123 }
124
125 col=nodes->cache->first[row];
126
127 nodes->cache->first[row]=(nodes->cache->first[row]+1)%CACHEDEPTH;
128
129 SeekReadFile(nodes->fd,&nodes->cache->data[row][col],sizeof(Node),nodes->nodesoffset+(off_t)index*sizeof(Node));
130
131 nodes->cache->indices[row][col]=index;
132
133 return(&nodes->cache->data[row][col]);
134 }
135
136
137 void InvalidateNodeCache(NodeCache *cache)
138 {
139 int row,col;
140
141 for(row=0;row<CACHEWIDTH;row++)
142 {
143 cache->first[row]=0;
144
145 for(col=0;col<CACHEDEPTH;col++)
146 cache->indices[row][col]=NO_NODE;
147 }
148 }
149
150
151 SegmentCache *NewSegmentCache(void)
152 {
153 SegmentCache *cache;
154
155 cache=(SegmentCache*)malloc(sizeof(SegmentCache));
156
157 InvalidateSegmentCache(cache);
158
159 return(cache);
160 }
161
162
163 void DeleteSegmentCache(SegmentCache *cache)
164 {
165 printf("DeleteSegmentCache access=%ld cached=%ld hit-rate=%.1f%%\n",cache->accesses,cache->cached,100*(double)cache->cached/(double)cache->accesses);
166
167 free(cache);
168 }
169
170
171 Segment *FetchCachedSegment(Segments *segments,index_t index)
172 {
173 int row=index%CACHEWIDTH;
174 int col;
175
176 segments->cache->accesses++;
177
178 for(col=0;col<CACHEDEPTH;col++)
179 if(segments->cache->indices[row][col]==index)
180 {
181 segments->cache->cached++;
182 return(&segments->cache->data[row][col]);
183 }
184
185 col=segments->cache->first[row];
186
187 segments->cache->first[row]=(segments->cache->first[row]+1)%CACHEDEPTH;
188
189 SeekReadFile(segments->fd,&segments->cache->data[row][col],sizeof(Segment),sizeof(SegmentsFile)+(off_t)index*sizeof(Segment));
190
191 segments->cache->indices[row][col]=index;
192
193 return(&segments->cache->data[row][col]);
194 }
195
196
197 void InvalidateSegmentCache(SegmentCache *cache)
198 {
199 int row,col;
200
201 for(row=0;row<CACHEWIDTH;row++)
202 {
203 cache->first[row]=0;
204
205 for(col=0;col<CACHEDEPTH;col++)
206 cache->indices[row][col]=NO_SEGMENT;
207 }
208 }
209
210
211 WayCache *NewWayCache(void)
212 {
213 WayCache *cache;
214
215 cache=(WayCache*)malloc(sizeof(WayCache));
216
217 InvalidateWayCache(cache);
218
219 return(cache);
220 }
221
222
223 void DeleteWayCache(WayCache *cache)
224 {
225 printf("DeleteWayCache access=%ld cached=%ld hit-rate=%.1f%%\n",cache->accesses,cache->cached,100*(double)cache->cached/(double)cache->accesses);
226
227 free(cache);
228 }
229
230
231 Way *FetchCachedWay(Ways *ways,index_t index)
232 {
233 int row=index%CACHEWIDTH;
234 int col;
235
236 ways->cache->accesses++;
237
238 for(col=0;col<CACHEDEPTH;col++)
239 if(ways->cache->indices[row][col]==index)
240 {
241 ways->cache->cached++;
242 return(&ways->cache->data[row][col]);
243 }
244
245 col=ways->cache->first[row];
246
247 ways->cache->first[row]=(ways->cache->first[row]+1)%CACHEDEPTH;
248
249 SeekReadFile(ways->fd,&ways->cache->data[row][col],sizeof(Way),sizeof(WaysFile)+(off_t)index*sizeof(Way));
250
251 ways->cache->indices[row][col]=index;
252
253 return(&ways->cache->data[row][col]);
254 }
255
256
257 void InvalidateWayCache(WayCache *cache)
258 {
259 int row,col;
260
261 for(row=0;row<CACHEWIDTH;row++)
262 {
263 cache->first[row]=0;
264
265 for(col=0;col<CACHEDEPTH;col++)
266 cache->indices[row][col]=NO_WAY;
267 }
268 }
269
270
271 TurnRelationCache *NewTurnRelationCache(void)
272 {
273 TurnRelationCache *cache;
274
275 cache=(TurnRelationCache*)malloc(sizeof(TurnRelationCache));
276
277 InvalidateTurnRelationCache(cache);
278
279 return(cache);
280 }
281
282
283 void DeleteTurnRelationCache(TurnRelationCache *cache)
284 {
285 printf("DeleteTurnRelationCache access=%ld cached=%ld hit-rate=%.1f%%\n",cache->accesses,cache->cached,100*(double)cache->cached/(double)cache->accesses);
286
287 free(cache);
288 }
289
290
291 TurnRelation *FetchCachedTurnRelation(Relations *relations,index_t index)
292 {
293 int row=index%CACHEWIDTH;
294 int col;
295
296 relations->cache->accesses++;
297
298 for(col=0;col<CACHEDEPTH;col++)
299 if(relations->cache->indices[row][col]==index)
300 {
301 relations->cache->cached++;
302 return(&relations->cache->data[row][col]);
303 }
304
305 col=relations->cache->first[row];
306
307 relations->cache->first[row]=(relations->cache->first[row]+1)%CACHEDEPTH;
308
309 SeekReadFile(relations->fd,&relations->cache->data[row][col],sizeof(TurnRelation),relations->troffset+(off_t)index*sizeof(TurnRelation));
310
311 relations->cache->indices[row][col]=index;
312
313 return(&relations->cache->data[row][col]);
314 }
315
316
317 void InvalidateTurnRelationCache(TurnRelationCache *cache)
318 {
319 int row,col;
320
321 for(row=0;row<CACHEWIDTH;row++)
322 {
323 cache->first[row]=0;
324
325 for(col=0;col<CACHEDEPTH;col++)
326 cache->indices[row][col]=NO_RELATION;
327 }
328 }
329
330 #endif