Routino SVN Repository Browser

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

ViewVC logotype

Contents of /branches/destination-access/src/relations.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2078 - (show annotations) (download) (as text)
Thu Nov 19 11:39:07 2020 UTC (4 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 10304 byte(s)
Merged source code changes from trunk [zero unused space in files, fix
library database loader, update binary search].

1 /***************************************
2 Relation data type functions.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2008-2015, 2019, 2020 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 "relations.h"
27 #include "fakes.h"
28
29 #include "files.h"
30
31
32 /*++++++++++++++++++++++++++++++++++++++
33 Load in a relation list from a file.
34
35 Relations *LoadRelationList Returns the relation list.
36
37 const char *filename The name of the file to load.
38 ++++++++++++++++++++++++++++++++++++++*/
39
40 Relations *LoadRelationList(const char *filename)
41 {
42 Relations *relations;
43
44 relations=(Relations*)malloc(sizeof(Relations));
45
46 #if !SLIM
47
48 relations->data=MapFile(filename);
49
50 /* Copy the RelationsFile header structure from the loaded data */
51
52 relations->file=*((RelationsFile*)relations->data);
53
54 /* Set the pointers in the Relations structure. */
55
56 relations->turnrelations=(TurnRelation*)(relations->data+sizeof(RelationsFile));
57
58 #else
59
60 relations->fd=SlimMapFile(filename);
61
62 /* Copy the RelationsFile header structure from the loaded data */
63
64 SlimFetch(relations->fd,&relations->file,sizeof(RelationsFile),0);
65
66 relations->troffset=sizeof(RelationsFile);
67
68 relations->cache=NewTurnRelationCache();
69 #ifndef LIBROUTINO
70 log_malloc(relations->cache,sizeof(*relations->cache));
71 #endif
72
73 #endif
74
75 if(relations->file.trnumber>0)
76 {
77 TurnRelation *relation;
78
79 relation=LookupTurnRelation(relations,0,1);
80
81 relations->via_start =relation->via;
82
83 relation=LookupTurnRelation(relations,relations->file.trnumber-1,1);
84
85 relations->via_end =relation->via;
86 }
87
88 return(relations);
89 }
90
91
92 /*++++++++++++++++++++++++++++++++++++++
93 Destroy the relation list.
94
95 Relations *relations The relation list to destroy.
96 ++++++++++++++++++++++++++++++++++++++*/
97
98 void DestroyRelationList(Relations *relations)
99 {
100 #if !SLIM
101
102 relations->data=UnmapFile(relations->data);
103
104 #else
105
106 relations->fd=SlimUnmapFile(relations->fd);
107
108 #ifndef LIBROUTINO
109 log_free(relations->cache);
110 #endif
111 DeleteTurnRelationCache(relations->cache);
112
113 #endif
114
115 free(relations);
116 }
117
118
119 /*++++++++++++++++++++++++++++++++++++++
120 Find the first turn relation in the file whose 'via' matches a specific node.
121
122 index_t FindFirstTurnRelation1 Returns the index of the first turn relation matching.
123
124 Relations *relations The set of relations to use.
125
126 index_t via The node that the route is going via.
127 ++++++++++++++++++++++++++++++++++++++*/
128
129 index_t FindFirstTurnRelation1(Relations *relations,index_t via)
130 {
131 TurnRelation *relation;
132 index_t start=0;
133 index_t end=relations->file.trnumber-1;
134 index_t mid;
135 index_t match=NO_RELATION;
136
137 /* Binary search - search key any exact match (may be multiple) is required.
138 *
139 * # <- start | Check mid and exit if it matches else move start or end.
140 * # |
141 * # | Since an exact match is wanted we can set end=mid-1
142 * # <- mid | or start=mid+1 if we find that mid doesn't match.
143 * # |
144 * # | Eventually either end=start or end=start+1 and one of
145 * # <- end | start or end matches or neither does.
146 */
147
148 while((end-start)>1)
149 {
150 mid=start+(end-start)/2; /* Choose mid point (avoid overflow) */
151
152 relation=LookupTurnRelation(relations,mid,1);
153
154 if(relation->via<via) /* Mid point is too low for 'via' */
155 start=mid+1;
156 else if(relation->via>via) /* Mid point is too high for 'via' */
157 end=mid-1;
158 else /* Mid point is correct for 'from' */
159 {
160 match=mid;
161 break;
162 }
163 }
164
165 if(match==NO_RELATION) /* Check if start matches */
166 {
167 relation=LookupTurnRelation(relations,start,1);
168
169 if(relation->via==via)
170 match=start;
171 }
172
173 if(match==NO_RELATION) /* Check if end matches */
174 {
175 relation=LookupTurnRelation(relations,end,1);
176
177 if(relation->via==via)
178 match=end;
179 }
180
181 if(match==NO_RELATION)
182 return(match);
183
184 while(match>0) /* Search backwards for the first match */
185 {
186 relation=LookupTurnRelation(relations,match-1,1);
187
188 if(relation->via==via)
189 match--;
190 else
191 break;
192 }
193
194 return(match);
195 }
196
197
198 /*++++++++++++++++++++++++++++++++++++++
199 Find the next turn relation in the file whose 'via' matches a specific node.
200
201 index_t FindNextTurnRelation1 Returns the index of the next turn relation matching.
202
203 Relations *relations The set of relations to use.
204
205 index_t current The current index of a relation that matches.
206 ++++++++++++++++++++++++++++++++++++++*/
207
208 index_t FindNextTurnRelation1(Relations *relations,index_t current)
209 {
210 TurnRelation *relation;
211 index_t via;
212
213 relation=LookupTurnRelation(relations,current,1);
214
215 via=relation->via;
216
217 current++;
218
219 if(current==relations->file.trnumber)
220 return(NO_RELATION);
221
222 relation=LookupTurnRelation(relations,current,1);
223
224 if(relation->via==via)
225 return(current);
226 else
227 return(NO_RELATION);
228 }
229
230
231 /*++++++++++++++++++++++++++++++++++++++
232 Find the first turn relation in the file whose 'via' and 'from' match a specific node and segment.
233
234 index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching.
235
236 Relations *relations The set of relations to use.
237
238 index_t via The node that the route is going via.
239
240 index_t from The segment that the route is coming from.
241 ++++++++++++++++++++++++++++++++++++++*/
242
243 index_t FindFirstTurnRelation2(Relations *relations,index_t via,index_t from)
244 {
245 TurnRelation *relation;
246 index_t start=0;
247 index_t end=relations->file.trnumber-1;
248 index_t mid;
249 index_t match=NO_RELATION;
250
251 if(IsFakeSegment(from))
252 from=IndexRealSegment(from);
253
254 /* Binary search - search key any exact match (may be multiple) is required.
255 *
256 * # <- start | Check mid and exit if it matches else move start or end.
257 * # |
258 * # | Since an exact match is wanted we can set end=mid-1
259 * # <- mid | or start=mid+1 if we find that mid doesn't match.
260 * # |
261 * # | Eventually either end=start or end=start+1 and one of
262 * # <- end | start or end matches or neither does.
263 */
264
265 while((end-start)>1)
266 {
267 mid=start+(end-start)/2; /* Choose mid point (avoid overflow) */
268
269 relation=LookupTurnRelation(relations,mid,1);
270
271 if(relation->via<via) /* Mid point is too low for 'via' */
272 start=mid+1;
273 else if(relation->via>via) /* Mid point is too high for 'via' */
274 end=mid-1;
275 else /* Mid point is correct for 'via' */
276 {
277 if(relation->from<from) /* Mid point is too low for 'from' */
278 start=mid+1;
279 else if(relation->from>from) /* Mid point is too high for 'from' */
280 end=mid-1;
281 else /* Mid point is correct for 'from' */
282 {
283 match=mid;
284 break;
285 }
286 }
287 }
288
289 if(match==NO_RELATION) /* Check if start matches */
290 {
291 relation=LookupTurnRelation(relations,start,1);
292
293 if(relation->via==via && relation->from==from)
294 match=start;
295 }
296
297 if(match==NO_RELATION) /* Check if end matches */
298 {
299 relation=LookupTurnRelation(relations,end,1);
300
301 if(relation->via==via && relation->from==from)
302 match=end;
303 }
304
305 if(match==NO_RELATION)
306 return(match);
307
308 while(match>0) /* Search backwards for the first match */
309 {
310 relation=LookupTurnRelation(relations,match-1,1);
311
312 if(relation->via==via && relation->from==from)
313 match--;
314 else
315 break;
316 }
317
318 return(match);
319 }
320
321
322 /*++++++++++++++++++++++++++++++++++++++
323 Find the next turn relation in the file whose 'via' and 'from' match a specific node and segment.
324
325 index_t FindNextTurnRelation2 Returns the index of the next turn relation matching.
326
327 Relations *relations The set of relations to use.
328
329 index_t current The current index of a relation that matches.
330 ++++++++++++++++++++++++++++++++++++++*/
331
332 index_t FindNextTurnRelation2(Relations *relations,index_t current)
333 {
334 TurnRelation *relation;
335 index_t via,from;
336
337 relation=LookupTurnRelation(relations,current,1);
338
339 via=relation->via;
340 from=relation->from;
341
342 current++;
343
344 if(current==relations->file.trnumber)
345 return(NO_RELATION);
346
347 relation=LookupTurnRelation(relations,current,1);
348
349 if(relation->via==via && relation->from==from)
350 return(current);
351 else
352 return(NO_RELATION);
353 }
354
355
356 /*++++++++++++++++++++++++++++++++++++++
357 Determine if a turn is allowed between the nodes 'from', 'via' and 'to' for a particular transport type.
358
359 int IsTurnAllowed Return 1 if the turn is allowed or 0 if not.
360
361 Relations *relations The set of relations to use.
362
363 index_t index The index of the first turn relation containing 'via' and 'from'.
364
365 index_t via The via node.
366
367 index_t from The from segment.
368
369 index_t to The to segment.
370
371 transports_t transport The type of transport that is being routed.
372 ++++++++++++++++++++++++++++++++++++++*/
373
374 int IsTurnAllowed(Relations *relations,index_t index,index_t via,index_t from,index_t to,transports_t transport)
375 {
376 if(IsFakeSegment(from))
377 from=IndexRealSegment(from);
378
379 if(IsFakeSegment(to))
380 to=IndexRealSegment(to);
381
382 while(index<relations->file.trnumber)
383 {
384 TurnRelation *relation=LookupTurnRelation(relations,index,1);
385
386 if(relation->via!=via)
387 return(1);
388
389 if(relation->from!=from)
390 return(1);
391
392 if(relation->to>to)
393 return(1);
394
395 if(relation->to==to)
396 if(!(relation->except & transport))
397 return(0);
398
399 index++;
400 }
401
402 return(1);
403 }