trunk/src/cache.c

/***************************************
 Functions to maintain an in-RAM cache of on-disk data for slim mode.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2013 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#include <stdlib.h>

#include "types.h"
#include "nodes.h"
#include "segments.h"
#include "ways.h"
#include "relations.h"

#include "cache.h"


#if SLIM


#define CACHEWIDTH 2048
#define CACHEDEPTH   16


/*+ A cache of Nodes. +*/
struct _NodeCache
{
 int     first  [CACHEWIDTH];             /*+ The first entry to fill +*/

 Node    data   [CACHEWIDTH][CACHEDEPTH]; /*+ The array of nodes. +*/
 index_t indices[CACHEWIDTH][CACHEDEPTH]; /*+ The array of indexes. +*/

 index_t accesses;
 index_t cached;
};

/*+ A cache of Segments. +*/
struct _SegmentCache
{
 int     first  [CACHEWIDTH];             /*+ The first entry to fill +*/

 Segment data   [CACHEWIDTH][CACHEDEPTH]; /*+ The array of segments. +*/
 index_t indices[CACHEWIDTH][CACHEDEPTH]; /*+ The array of indexes. +*/

 index_t accesses;
 index_t cached;
};

/*+ A cache of Ways. +*/
struct _WayCache
{
 int     first  [CACHEWIDTH];             /*+ The first entry to fill +*/

 Way     data   [CACHEWIDTH][CACHEDEPTH]; /*+ The array of ways. +*/
 index_t indices[CACHEWIDTH][CACHEDEPTH]; /*+ The array of indexes. +*/

 index_t accesses;
 index_t cached;
};

/*+ A cache of Turn Relations. +*/
struct _TurnRelationCache
{
 int     first  [CACHEWIDTH];             /*+ The first entry to fill +*/

 TurnRelation data   [CACHEWIDTH][CACHEDEPTH]; /*+ The array of turn relations. +*/
 index_t      indices[CACHEWIDTH][CACHEDEPTH]; /*+ The array of indexes. +*/

 index_t accesses;
 index_t cached;
};


NodeCache *NewNodeCache(void)
{
 NodeCache *cache;

 cache=(NodeCache*)malloc(sizeof(NodeCache));

 InvalidateNodeCache(cache);

 return(cache);
}


void DeleteNodeCache(NodeCache *cache)
{
 printf("DeleteNodeCache access=%ld cached=%ld hit-rate=%.1f%%\n",cache->accesses,cache->cached,100*(double)cache->cached/(double)cache->accesses);

 free(cache);
}


Node *FetchCachedNode(Nodes *nodes,index_t index)
{
 int row=index%CACHEWIDTH;
 int col;

 nodes->cache->accesses++;

 for(col=0;col<CACHEDEPTH;col++)
    if(nodes->cache->indices[row][col]==index)
      {
       nodes->cache->cached++;
       return(&nodes->cache->data[row][col]);
      }

 col=nodes->cache->first[row];

 nodes->cache->first[row]=(nodes->cache->first[row]+1)%CACHEDEPTH;

 SeekReadFile(nodes->fd,&nodes->cache->data[row][col],sizeof(Node),nodes->nodesoffset+(off_t)index*sizeof(Node));

 nodes->cache->indices[row][col]=index;

 return(&nodes->cache->data[row][col]);
}


void InvalidateNodeCache(NodeCache *cache)
{
 int row,col;

 for(row=0;row<CACHEWIDTH;row++)
   {
    cache->first[row]=0;

    for(col=0;col<CACHEDEPTH;col++)
       cache->indices[row][col]=NO_NODE;
   }
}


SegmentCache *NewSegmentCache(void)
{
 SegmentCache *cache;

 cache=(SegmentCache*)malloc(sizeof(SegmentCache));

 InvalidateSegmentCache(cache);

 return(cache);
}


void DeleteSegmentCache(SegmentCache *cache)
{
 printf("DeleteSegmentCache access=%ld cached=%ld hit-rate=%.1f%%\n",cache->accesses,cache->cached,100*(double)cache->cached/(double)cache->accesses);

 free(cache);
}


Segment *FetchCachedSegment(Segments *segments,index_t index)
{
 int row=index%CACHEWIDTH;
 int col;

 segments->cache->accesses++;

 for(col=0;col<CACHEDEPTH;col++)
    if(segments->cache->indices[row][col]==index)
      {
       segments->cache->cached++;
       return(&segments->cache->data[row][col]);
      }

 col=segments->cache->first[row];

 segments->cache->first[row]=(segments->cache->first[row]+1)%CACHEDEPTH;

 SeekReadFile(segments->fd,&segments->cache->data[row][col],sizeof(Segment),sizeof(SegmentsFile)+(off_t)index*sizeof(Segment));

 segments->cache->indices[row][col]=index;

 return(&segments->cache->data[row][col]);
}


void InvalidateSegmentCache(SegmentCache *cache)
{
 int row,col;

 for(row=0;row<CACHEWIDTH;row++)
   {
    cache->first[row]=0;

    for(col=0;col<CACHEDEPTH;col++)
       cache->indices[row][col]=NO_SEGMENT;
   }
}


WayCache *NewWayCache(void)
{
 WayCache *cache;

 cache=(WayCache*)malloc(sizeof(WayCache));

 InvalidateWayCache(cache);

 return(cache);
}


void DeleteWayCache(WayCache *cache)
{
 printf("DeleteWayCache access=%ld cached=%ld hit-rate=%.1f%%\n",cache->accesses,cache->cached,100*(double)cache->cached/(double)cache->accesses);

 free(cache);
}


Way *FetchCachedWay(Ways *ways,index_t index)
{
 int row=index%CACHEWIDTH;
 int col;

 ways->cache->accesses++;

 for(col=0;col<CACHEDEPTH;col++)
    if(ways->cache->indices[row][col]==index)
      {
       ways->cache->cached++;
       return(&ways->cache->data[row][col]);
      }

 col=ways->cache->first[row];

 ways->cache->first[row]=(ways->cache->first[row]+1)%CACHEDEPTH;

 SeekReadFile(ways->fd,&ways->cache->data[row][col],sizeof(Way),sizeof(WaysFile)+(off_t)index*sizeof(Way));

 ways->cache->indices[row][col]=index;

 return(&ways->cache->data[row][col]);
}


void InvalidateWayCache(WayCache *cache)
{
 int row,col;

 for(row=0;row<CACHEWIDTH;row++)
   {
    cache->first[row]=0;

    for(col=0;col<CACHEDEPTH;col++)
       cache->indices[row][col]=NO_WAY;
   }
}


TurnRelationCache *NewTurnRelationCache(void)
{
 TurnRelationCache *cache;

 cache=(TurnRelationCache*)malloc(sizeof(TurnRelationCache));

 InvalidateTurnRelationCache(cache);

 return(cache);
}


void DeleteTurnRelationCache(TurnRelationCache *cache)
{
 printf("DeleteTurnRelationCache access=%ld cached=%ld hit-rate=%.1f%%\n",cache->accesses,cache->cached,100*(double)cache->cached/(double)cache->accesses);

 free(cache);
}


TurnRelation *FetchCachedTurnRelation(Relations *relations,index_t index)
{
 int row=index%CACHEWIDTH;
 int col;

 relations->cache->accesses++;

 for(col=0;col<CACHEDEPTH;col++)
    if(relations->cache->indices[row][col]==index)
      {
       relations->cache->cached++;
       return(&relations->cache->data[row][col]);
      }

 col=relations->cache->first[row];

 relations->cache->first[row]=(relations->cache->first[row]+1)%CACHEDEPTH;

 SeekReadFile(relations->fd,&relations->cache->data[row][col],sizeof(TurnRelation),relations->troffset+(off_t)index*sizeof(TurnRelation));

 relations->cache->indices[row][col]=index;

 return(&relations->cache->data[row][col]);
}


void InvalidateTurnRelationCache(TurnRelationCache *cache)
{
 int row,col;

 for(row=0;row<CACHEWIDTH;row++)
   {
    cache->first[row]=0;

    for(col=0;col<CACHEDEPTH;col++)
       cache->indices[row][col]=NO_RELATION;
   }
}

#endif
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