Routino SVN Repository Browser

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

/[routino]/branches/libroutino/src/superx.c
ViewVC logotype

Contents of /branches/libroutino/src/superx.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 1710 - (show annotations) (download) (as text)
Sun Jun 14 09:07:05 2015 UTC (9 years, 10 months ago) by amb
File MIME type: text/x-csrc
File size: 16193 byte(s) 
Audit the use of function static variables to make sure that there are
no implicit assumptions about initialisation conditions that would be
wrong for library usage.  Fix problems and add comments for clarity.
1 /***************************************
2 Super-Segment data type functions.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2008-2015 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 "segments.h"
27 #include "ways.h"
28
29 #include "typesx.h"
30 #include "nodesx.h"
31 #include "segmentsx.h"
32 #include "waysx.h"
33 #include "superx.h"
34
35 #include "files.h"
36 #include "logging.h"
37 #include "results.h"
38
39
40 /* Local functions */
41
42 static Results *FindSuperRoutes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match);
43
44
45 /*++++++++++++++++++++++++++++++++++++++
46 Select the super-nodes from the list of nodes.
47
48 NodesX *nodesx The set of nodes to use.
49
50 SegmentsX *segmentsx The set of segments to use.
51
52 WaysX *waysx The set of ways to use.
53 ++++++++++++++++++++++++++++++++++++++*/
54
55 void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
56 {
57 index_t i;
58 index_t nnodes=0;
59
60 if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0)
61 return;
62
63 /* Print the start message */
64
65 printf_first("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
66
67 /* Allocate and set the super-node markers */
68
69 if(!nodesx->super)
70 {
71 nodesx->super=AllocBitMask(nodesx->number);
72 log_malloc(nodesx->super,LengthBitMask(nodesx->number)*sizeof(BitMask));
73
74 logassert(nodesx->super,"Failed to allocate memory (try using slim mode?)"); /* Check AllocBitMask() worked */
75
76 SetAllBits(nodesx->super,nodesx->number);
77 }
78
79 /* Map into memory / open the files */
80
81 nodesx->fd=ReOpenFileBuffered(nodesx->filename_tmp);
82
83 #if !SLIM
84 segmentsx->data=MapFile(segmentsx->filename_tmp);
85 waysx->data=MapFile(waysx->filename_tmp);
86 #else
87 segmentsx->fd=SlimMapFile(segmentsx->filename_tmp);
88 waysx->fd=SlimMapFile(waysx->filename_tmp);
89
90 InvalidateSegmentXCache(segmentsx->cache);
91 InvalidateWayXCache(waysx->cache);
92 #endif
93
94 /* Find super-nodes */
95
96 for(i=0;i<nodesx->number;i++)
97 {
98 NodeX nodex;
99
100 ReadFileBuffered(nodesx->fd,&nodex,sizeof(NodeX));
101
102 if(IsBitSet(nodesx->super,i))
103 {
104 int issuper=0;
105
106 if(nodex.flags&(NODE_TURNRSTRCT|NODE_TURNRSTRCT2))
107 issuper=1;
108 else
109 {
110 int count=0,j;
111 Way segmentway[MAX_SEG_PER_NODE];
112 int segmentweight[MAX_SEG_PER_NODE];
113 SegmentX *segmentx=FirstSegmentX(segmentsx,i,1);
114
115 while(segmentx)
116 {
117 WayX *wayx=LookupWayX(waysx,segmentx->way,1);
118 int nsegments;
119
120 /* Segments that are loops count twice */
121
122 logassert(count<MAX_SEG_PER_NODE,"Too many segments for one node (increase MAX_SEG_PER_NODE?)"); /* Only a limited amount of information stored. */
123
124 if(segmentx->node1==segmentx->node2)
125 segmentweight[count]=2;
126 else
127 segmentweight[count]=1;
128
129 segmentway[count]=wayx->way;
130
131 /* If the node allows less traffic types than any connecting way then it is super if it allows anything */
132
133 if((wayx->way.allow&nodex.allow)!=wayx->way.allow && nodex.allow!=Transports_None)
134 {
135 issuper=1;
136 break;
137 }
138
139 nsegments=segmentweight[count];
140
141 for(j=0;j<count;j++)
142 if(wayx->way.allow & segmentway[j].allow)
143 {
144 /* If two ways are different in any attribute and there is a type of traffic that can use both then it is super */
145
146 if(WaysCompare(&segmentway[j],&wayx->way))
147 {
148 issuper=1;
149 break;
150 }
151
152 /* If there are two other segments that can be used by the same types of traffic as this one then it is super */
153
154 nsegments+=segmentweight[j];
155 if(nsegments>2)
156 {
157 issuper=1;
158 break;
159 }
160 }
161
162 if(issuper)
163 break;
164
165 segmentx=NextSegmentX(segmentsx,segmentx,i);
166
167 count++;
168 }
169 }
170
171 /* Mark the node as super if it is. */
172
173 if(issuper)
174 nnodes++;
175 else
176 ClearBit(nodesx->super,i);
177 }
178
179 if(!((i+1)%10000))
180 printf_middle("Finding Super-Nodes: Nodes=%"Pindex_t" Super-Nodes=%"Pindex_t,i+1,nnodes);
181 }
182
183 /* Unmap from memory / close the files */
184
185 #if !SLIM
186 segmentsx->data=UnmapFile(segmentsx->data);
187 waysx->data=UnmapFile(waysx->data);
188 #else
189 segmentsx->fd=SlimUnmapFile(segmentsx->fd);
190 waysx->fd=SlimUnmapFile(waysx->fd);
191 #endif
192
193 nodesx->fd=CloseFileBuffered(nodesx->fd);
194
195 /* Print the final message */
196
197 printf_last("Found Super-Nodes: Nodes=%"Pindex_t" Super-Nodes=%"Pindex_t,nodesx->number,nnodes);
198 }
199
200
201 /*++++++++++++++++++++++++++++++++++++++
202 Create the super-segments from the existing segments.
203
204 SegmentsX *CreateSuperSegments Returns the new super segments.
205
206 NodesX *nodesx The set of nodes to use.
207
208 SegmentsX *segmentsx The set of segments to use.
209
210 WaysX *waysx The set of ways to use.
211 ++++++++++++++++++++++++++++++++++++++*/
212
213 SegmentsX *CreateSuperSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
214 {
215 index_t i;
216 SegmentsX *supersegmentsx;
217 index_t sn=0,ss=0;
218
219 supersegmentsx=NewSegmentList();
220
221 if(segmentsx->number==0 || waysx->number==0)
222 {
223 FinishSegmentList(supersegmentsx);
224
225 return(supersegmentsx);
226 }
227
228 /* Print the start message */
229
230 printf_first("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
231
232 /* Map into memory / open the files */
233
234 #if !SLIM
235 nodesx->data=MapFile(nodesx->filename_tmp);
236 segmentsx->data=MapFile(segmentsx->filename_tmp);
237 waysx->data=MapFile(waysx->filename_tmp);
238 #else
239 nodesx->fd=SlimMapFile(nodesx->filename_tmp);
240 segmentsx->fd=SlimMapFile(segmentsx->filename_tmp);
241 waysx->fd=SlimMapFile(waysx->filename_tmp);
242
243 InvalidateNodeXCache(nodesx->cache);
244 InvalidateSegmentXCache(segmentsx->cache);
245 InvalidateWayXCache(waysx->cache);
246 #endif
247
248 /* Create super-segments for each super-node. */
249
250 for(i=0;i<nodesx->number;i++)
251 {
252 if(IsBitSet(nodesx->super,i))
253 {
254 SegmentX *segmentx;
255 int count=0,match;
256 Way prevway[MAX_SEG_PER_NODE];
257
258 segmentx=FirstSegmentX(segmentsx,i,1);
259
260 while(segmentx)
261 {
262 WayX *wayx=LookupWayX(waysx,segmentx->way,1);
263
264 /* Check that this type of way hasn't already been routed */
265
266 match=0;
267
268 if(count>0)
269 {
270 int j;
271
272 for(j=0;j<count;j++)
273 if(!WaysCompare(&prevway[j],&wayx->way))
274 {
275 match=1;
276 break;
277 }
278 }
279
280 logassert(count<MAX_SEG_PER_NODE,"Too many segments for one node (increase MAX_SEG_PER_NODE?)"); /* Only a limited amount of history stored. */
281
282 prevway[count++]=wayx->way;
283
284 /* Route the way and store the super-segments. */
285
286 if(!match)
287 {
288 Results *results=FindSuperRoutes(nodesx,segmentsx,waysx,i,&wayx->way);
289 Result *result=FirstResult(results);
290
291 while(result)
292 {
293 if(IsBitSet(nodesx->super,result->node) && result->segment!=NO_SEGMENT)
294 {
295 if(wayx->way.type&Highway_OneWay && result->node!=i)
296 AppendSegmentList(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);
297 else
298 AppendSegmentList(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));
299
300 ss++;
301 }
302
303 result=NextResult(results,result);
304 }
305 }
306
307 segmentx=NextSegmentX(segmentsx,segmentx,i);
308 }
309
310 sn++;
311
312 if(!(sn%10000))
313 printf_middle("Creating Super-Segments: Super-Nodes=%"Pindex_t" Super-Segments=%"Pindex_t,sn,ss);
314 }
315 }
316
317 FinishSegmentList(supersegmentsx);
318
319 /* Unmap from memory / close the files */
320
321 #if !SLIM
322 nodesx->data=UnmapFile(nodesx->data);
323 segmentsx->data=UnmapFile(segmentsx->data);
324 waysx->data=UnmapFile(waysx->data);
325 #else
326 nodesx->fd=SlimUnmapFile(nodesx->fd);
327 segmentsx->fd=SlimUnmapFile(segmentsx->fd);
328 waysx->fd=SlimUnmapFile(waysx->fd);
329 #endif
330
331 /* Free the no-longer required memory */
332
333 if(segmentsx->firstnode)
334 {
335 log_free(segmentsx->firstnode);
336 free(segmentsx->firstnode);
337 segmentsx->firstnode=NULL;
338 }
339
340 /* Print the final message */
341
342 printf_last("Created Super-Segments: Super-Nodes=%"Pindex_t" Super-Segments=%"Pindex_t,sn,ss);
343
344 return(supersegmentsx);
345 }
346
347
348 /*++++++++++++++++++++++++++++++++++++++
349 Merge the segments and super-segments into a new segment list.
350
351 SegmentsX *MergeSuperSegments Returns a new set of merged segments.
352
353 SegmentsX *segmentsx The set of segments to use.
354
355 SegmentsX *supersegmentsx The set of super-segments to use.
356 ++++++++++++++++++++++++++++++++++++++*/
357
358 SegmentsX *MergeSuperSegments(SegmentsX *segmentsx,SegmentsX *supersegmentsx)
359 {
360 index_t i,j,lastj;
361 index_t merged=0,added=0;
362 SegmentsX *mergedsegmentsx;
363 SegmentX supersegmentx;
364
365 mergedsegmentsx=NewSegmentList();
366
367 if(segmentsx->number==0)
368 {
369 FinishSegmentList(mergedsegmentsx);
370
371 return(mergedsegmentsx);
372 }
373
374 /* Print the start message */
375
376 printf_first("Merging Segments: Segments=0 Super=0 Merged=0 Added=0");
377
378 /* Open the files */
379
380 segmentsx->fd=ReOpenFileBuffered(segmentsx->filename_tmp);
381 if(supersegmentsx->number>0)
382 supersegmentsx->fd=ReOpenFileBuffered(supersegmentsx->filename_tmp);
383
384 /* Loop through and create a new list of combined segments */
385
386 lastj=-1;
387 j=0;
388
389 for(i=0;i<segmentsx->number;i++)
390 {
391 int super=0;
392 SegmentX segmentx;
393
394 ReadFileBuffered(segmentsx->fd,&segmentx,sizeof(SegmentX));
395
396 while(j<supersegmentsx->number)
397 {
398 if(j!=lastj)
399 {
400 ReadFileBuffered(supersegmentsx->fd,&supersegmentx,sizeof(SegmentX));
401 lastj=j;
402 }
403
404 if(segmentx.node1 ==supersegmentx.node1 &&
405 segmentx.node2 ==supersegmentx.node2 &&
406 segmentx.distance==supersegmentx.distance)
407 {
408 merged++;
409 j++;
410 /* mark as super-segment and normal segment */
411 super=1;
412 break;
413 }
414 else if((segmentx.node1==supersegmentx.node1 &&
415 segmentx.node2==supersegmentx.node2) ||
416 (segmentx.node1==supersegmentx.node1 &&
417 segmentx.node2>supersegmentx.node2) ||
418 (segmentx.node1>supersegmentx.node1))
419 {
420 /* mark as super-segment */
421 AppendSegmentList(mergedsegmentsx,supersegmentx.way,supersegmentx.node1,supersegmentx.node2,supersegmentx.distance|SEGMENT_SUPER);
422 added++;
423 j++;
424 }
425 else
426 {
427 /* mark as normal segment */
428 break;
429 }
430 }
431
432 if(super)
433 AppendSegmentList(mergedsegmentsx,segmentx.way,segmentx.node1,segmentx.node2,segmentx.distance|SEGMENT_SUPER|SEGMENT_NORMAL);
434 else
435 AppendSegmentList(mergedsegmentsx,segmentx.way,segmentx.node1,segmentx.node2,segmentx.distance|SEGMENT_NORMAL);
436
437 if(!((i+1)%10000))
438 printf_middle("Merging Segments: Segments=%"Pindex_t" Super=%"Pindex_t" Merged=%"Pindex_t" Added=%"Pindex_t,i+1,j,merged,added);
439 }
440
441 if(j<supersegmentsx->number)
442 {
443 if(j==lastj)
444 {
445 AppendSegmentList(mergedsegmentsx,supersegmentx.way,supersegmentx.node1,supersegmentx.node2,supersegmentx.distance|SEGMENT_SUPER);
446
447 j++;
448 }
449
450 while(j<supersegmentsx->number)
451 {
452 ReadFileBuffered(supersegmentsx->fd,&supersegmentx,sizeof(SegmentX));
453
454 AppendSegmentList(mergedsegmentsx,supersegmentx.way,supersegmentx.node1,supersegmentx.node2,supersegmentx.distance|SEGMENT_SUPER);
455
456 added++;
457 j++;
458 }
459 }
460
461 FinishSegmentList(mergedsegmentsx);
462
463 /* Close the files */
464
465 segmentsx->fd=CloseFileBuffered(segmentsx->fd);
466 if(supersegmentsx->number>0)
467 supersegmentsx->fd=CloseFileBuffered(supersegmentsx->fd);
468
469 /* Print the final message */
470
471 printf_last("Merged Segments: Segments=%"Pindex_t" Super=%"Pindex_t" Merged=%"Pindex_t" Added=%"Pindex_t,segmentsx->number,supersegmentsx->number,merged,added);
472
473 return(mergedsegmentsx);
474 }
475
476
477 /*++++++++++++++++++++++++++++++++++++++
478 Find all routes from a specified super-node to any other super-node that follows a certain type of way.
479
480 Results *FindSuperRoutes Returns a set of results.
481
482 NodesX *nodesx The set of nodes to use.
483
484 SegmentsX *segmentsx The set of segments to use.
485
486 WaysX *waysx The set of ways to use.
487
488 node_t start The start node.
489
490 Way *match A template for the type of way that the route must follow.
491 ++++++++++++++++++++++++++++++++++++++*/
492
493 static Results *FindSuperRoutes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match)
494 {
495 static Results *results=NULL; /* static allocation of return value (reset each call) */
496 static Queue *queue=NULL; /* static allocation of internal value (reset each call) */
497 Result *result1,*result2;
498 WayX *wayx;
499
500 /* Insert the first node into the queue */
501
502 if(!results)
503 results=NewResultsList(8);
504 else
505 ResetResultsList(results);
506
507 if(!queue)
508 queue=NewQueueList(8);
509 else
510 ResetQueueList(queue);
511
512 result1=InsertResult(results,start,NO_SEGMENT);
513
514 InsertInQueue(queue,result1,0);
515
516 /* Loop across all nodes in the queue */
517
518 while((result1=PopFromQueue(queue)))
519 {
520 index_t node1;
521 SegmentX *segmentx;
522
523 node1=result1->node;
524
525 segmentx=FirstSegmentX(segmentsx,node1,2); /* position 1 is already used */
526
527 while(segmentx)
528 {
529 NodeX *node2x;
530 index_t node2,seg2;
531 distance_t cumulative_distance;
532
533 /* must not be one-way against the direction of travel */
534 if(IsOnewayTo(segmentx,node1))
535 goto endloop;
536
537 seg2=IndexSegmentX(segmentsx,segmentx);
538
539 /* must not be a u-turn */
540 if(result1->segment==seg2)
541 goto endloop;
542
543 wayx=LookupWayX(waysx,segmentx->way,2); /* position 1 is already used */
544
545 /* must be the right type of way */
546 if(WaysCompare(&wayx->way,match))
547 goto endloop;
548
549 node2=OtherNode(segmentx,node1);
550
551 node2x=LookupNodeX(nodesx,node2,2); /* position 1 is already used */
552
553 /* Don't route beyond a node with no access */
554 if(node2x->allow==Transports_None)
555 goto endloop;
556
557 cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
558
559 result2=FindResult(results,node2,seg2);
560
561 if(!result2) /* New end node */
562 {
563 result2=InsertResult(results,node2,seg2);
564 result2->prev=result1;
565 result2->score=cumulative_distance;
566
567 /* don't route beyond a super-node. */
568 if(!IsBitSet(nodesx->super,node2))
569 InsertInQueue(queue,result2,cumulative_distance);
570 }
571 else if(cumulative_distance<result2->score)
572 {
573 result2->prev=result1;
574 result2->score=cumulative_distance;
575
576 /* don't route beyond a super-node. */
577 if(!IsBitSet(nodesx->super,node2))
578 InsertInQueue(queue,result2,cumulative_distance);
579 }
580
581 endloop:
582
583 segmentx=NextSegmentX(segmentsx,segmentx,node1);
584 }
585 }
586
587 return(results);
588 }

Properties

Name Value
cvs:description Super-nodes and super-segments functions.
Index: This Site Routino Software Download Source Code Documentation XML Files Links
Index: View SVN Development Recent changes Development (destination-access branch) Version 3.4.2 (destination-access branch) Version 3.4.2 Version 3.4.1 (destination-access branch) Version 3.4.1 Version 3.4 (destination-access branch) Version 3.4 Version 3.3.3 (destination-access branch) Version 3.3.3 Version 3.3.2 (destination-access branch) Version 3.3.2 Version 3.3.1 (destination-access branch) Version 3.3.1 Version 3.3 (destination-access branch) Version 3.3 Version 3.2 Version 3.1.1 Version 3.1 Version 3.0 Version 2.7.3 Version 2.7.2 Version 2.7.1 Version 2.7 Version 2.6 Version 2.5.1 Version 2.5 Version 2.4.1 Version 2.4 Version 2.3.2 Version 2.3.1 Version 2.3 Version 2.2 Version 2.1.2 Version 2.1.1 Version 2.1 Version 2.0.3 Version 2.0.2 Version 2.0.1 Version 2.0 Version 1.5.1 Version 1.5 Version 1.4.1 Version 1.4 Version 1.3 Version 1.2 Version 1.1 Version 1.0
Powered by ViewVC 1.3.0-dev ViewVC Help
© Andrew M. Bishop = < amb @ ... >
Root