Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/cache.c
Parent Directory
|
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)
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 |