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