Routino SVN Repository Browser

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

/[routino]/trunk/src/superx.c
ViewVC logotype

Contents of /trunk/src/superx.c

Parent Directory Parent Directory | Revision Log Revision Log

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

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.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