Routino SVN Repository Browser

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

ViewVC logotype

Annotation of /trunk/src/segmentsx.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 277 - (hide annotations) (download) (as text)
Wed Oct 7 18:53:19 2009 UTC (15 years, 5 months ago) by amb
File MIME type: text/x-csrc
File size: 23599 byte(s)
AppendSegment adds a single segment and not a pair.

1 amb 110 /***************************************
2 amb 277 $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.39 2009-10-07 18:53:19 amb Exp $
3 amb 110
4     Extended Segment data type functions.
5 amb 151
6     Part of the Routino routing software.
7 amb 110 ******************/ /******************
8 amb 151 This file Copyright 2008,2009 Andrew M. Bishop
9 amb 110
10 amb 151 This program is free software: you can redistribute it and/or modify
11     it under the terms of the GNU Affero General Public License as published by
12     the Free Software Foundation, either version 3 of the License, or
13     (at your option) any later version.
14    
15     This program is distributed in the hope that it will be useful,
16     but WITHOUT ANY WARRANTY; without even the implied warranty of
17     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18     GNU Affero General Public License for more details.
19    
20     You should have received a copy of the GNU Affero General Public License
21     along with this program. If not, see <http://www.gnu.org/licenses/>.
22 amb 110 ***************************************/
23    
24    
25     #include <assert.h>
26     #include <math.h>
27     #include <stdlib.h>
28     #include <stdio.h>
29 amb 256 #include <string.h>
30 amb 110
31     #include "types.h"
32     #include "functions.h"
33     #include "nodesx.h"
34     #include "segmentsx.h"
35     #include "waysx.h"
36 amb 228 #include "nodes.h"
37     #include "segments.h"
38     #include "ways.h"
39 amb 110
40    
41 amb 275 /* Constants */
42    
43     #define SORT_RAMSIZE (64*1024*1024)
44    
45 amb 256 /* Variables */
46 amb 110
47 amb 256 extern int option_slim;
48     extern char *tmpdirname;
49 amb 110
50 amb 228 /* Local Functions */
51 amb 110
52 amb 275 static int sort_by_id(SegmentX *a,SegmentX *b);
53     static int index_by_id(SegmentX *segmentx,index_t index);
54    
55 amb 228 static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2);
56 amb 110
57    
58     /*++++++++++++++++++++++++++++++++++++++
59     Allocate a new segment list.
60    
61     SegmentsX *NewSegmentList Returns the segment list.
62     ++++++++++++++++++++++++++++++++++++++*/
63    
64     SegmentsX *NewSegmentList(void)
65     {
66     SegmentsX *segmentsx;
67    
68 amb 213 segmentsx=(SegmentsX*)calloc(1,sizeof(SegmentsX));
69 amb 110
70 amb 243 assert(segmentsx); /* Check calloc() worked */
71    
72 amb 256 segmentsx->filename=(char*)malloc(strlen(tmpdirname)+24);
73     sprintf(segmentsx->filename,"%s/segments.%p.tmp",tmpdirname,segmentsx);
74 amb 216
75 amb 256 segmentsx->fd=OpenFile(segmentsx->filename);
76    
77 amb 110 return(segmentsx);
78     }
79    
80    
81     /*++++++++++++++++++++++++++++++++++++++
82 amb 226 Free a segment list.
83 amb 110
84     SegmentsX *segmentsx The list to be freed.
85     ++++++++++++++++++++++++++++++++++++++*/
86    
87     void FreeSegmentList(SegmentsX *segmentsx)
88     {
89 amb 213 if(segmentsx->xdata)
90 amb 256 UnmapFile(segmentsx->filename);
91 amb 226
92 amb 256 DeleteFile(segmentsx->filename);
93    
94 amb 275 if(segmentsx->idata)
95     free(segmentsx->idata);
96 amb 226
97     if(segmentsx->sdata)
98     free(segmentsx->sdata);
99    
100 amb 110 free(segmentsx);
101     }
102    
103    
104     /*++++++++++++++++++++++++++++++++++++++
105     Save the segment list to a file.
106    
107     SegmentsX* segmentsx The set of segments to save.
108    
109     const char *filename The name of the file to save.
110     ++++++++++++++++++++++++++++++++++++++*/
111    
112     void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
113     {
114 amb 214 index_t i;
115 amb 110 int fd;
116 amb 243 Segments *segments;
117 amb 232 int super_number=0,normal_number=0;
118 amb 110
119 amb 243 assert(segmentsx->sdata); /* Must have sdata filled in => real segments */
120 amb 110
121 amb 227 printf("Writing Segments: Segments=0");
122     fflush(stdout);
123    
124 amb 232 for(i=0;i<segmentsx->number;i++)
125     {
126     if(IsSuperSegment(&segmentsx->sdata[i]))
127     super_number++;
128     if(IsNormalSegment(&segmentsx->sdata[i]))
129     normal_number++;
130     }
131    
132 amb 110 /* Fill in a Segments structure with the offset of the real data in the file after
133     the Segment structure itself. */
134    
135 amb 243 segments=calloc(1,sizeof(Segments));
136    
137     assert(segments); /* Check calloc() worked */
138    
139 amb 110 segments->number=segmentsx->number;
140 amb 232 segments->snumber=super_number;
141     segments->nnumber=normal_number;
142    
143 amb 110 segments->data=NULL;
144 amb 232
145 amb 110 segments->segments=(void*)sizeof(Segments);
146    
147     /* Write out the Segments structure and then the real data. */
148    
149     fd=OpenFile(filename);
150    
151     WriteFile(fd,segments,sizeof(Segments));
152    
153 amb 203 for(i=0;i<segments->number;i++)
154 amb 132 {
155 amb 209 WriteFile(fd,&segmentsx->sdata[i],sizeof(Segment));
156 amb 110
157 amb 132 if(!((i+1)%10000))
158     {
159     printf("\rWriting Segments: Segments=%d",i+1);
160     fflush(stdout);
161     }
162     }
163    
164 amb 203 printf("\rWrote Segments: Segments=%d \n",segments->number);
165 amb 132 fflush(stdout);
166    
167 amb 110 CloseFile(fd);
168    
169     /* Free the fake Segments */
170    
171     free(segments);
172     }
173    
174    
175     /*++++++++++++++++++++++++++++++++++++++
176 amb 257 Lookup a particular segment.
177 amb 110
178 amb 257 SegmentX *LookupSegmentX Returns a pointer to the extended segment with the specified id.
179 amb 110
180     SegmentsX* segmentsx The set of segments to process.
181    
182 amb 256 index_t index The segment index to look for.
183 amb 275
184     int position The position in the cache to use.
185 amb 256 ++++++++++++++++++++++++++++++++++++++*/
186    
187 amb 275 SegmentX *LookupSegmentX(SegmentsX* segmentsx,index_t index,int position)
188 amb 256 {
189     assert(index!=NO_SEGMENT); /* Must be a valid segment */
190    
191     if(option_slim)
192     {
193     SeekFile(segmentsx->fd,index*sizeof(SegmentX));
194    
195 amb 275 ReadFile(segmentsx->fd,&segmentsx->cached[position-1],sizeof(SegmentX));
196 amb 256
197 amb 275 return(&segmentsx->cached[position-1]);
198 amb 256 }
199     else
200     {
201     return(&segmentsx->xdata[index]);
202     }
203     }
204    
205    
206     /*++++++++++++++++++++++++++++++++++++++
207 amb 275 Find the first segment index with a particular starting node.
208 amb 257
209 amb 275 index_t IndexFirstSegmentX Returns a pointer to the index of the first extended segment with the specified id.
210 amb 256
211     SegmentsX* segmentsx The set of segments to process.
212    
213 amb 110 node_t node The node to look for.
214     ++++++++++++++++++++++++++++++++++++++*/
215    
216 amb 275 index_t IndexFirstSegmentX(SegmentsX* segmentsx,node_t node)
217 amb 110 {
218     int start=0;
219     int end=segmentsx->number-1;
220     int mid;
221     int found;
222    
223 amb 275 assert(segmentsx->idata); /* Must have idata filled in => sorted by node 1 */
224 amb 110
225     /* Binary search - search key exact match only is required.
226     *
227     * # <- start | Check mid and move start or end if it doesn't match
228     * # |
229     * # | Since an exact match is wanted we can set end=mid-1
230     * # <- mid | or start=mid+1 because we know that mid doesn't match.
231     * # |
232     * # | Eventually either end=start or end=start+1 and one of
233     * # <- end | start or end is the wanted one.
234     */
235    
236 amb 275 if(end<start) /* There are no nodes */
237     return(NO_SEGMENT);
238     else if(node<segmentsx->idata[start]) /* Check key is not before start */
239     return(NO_SEGMENT);
240     else if(node>segmentsx->idata[end]) /* Check key is not after end */
241     return(NO_SEGMENT);
242 amb 257 else
243 amb 110 {
244 amb 257 do
245     {
246 amb 275 mid=(start+end)/2; /* Choose mid point */
247 amb 110
248 amb 275 if(segmentsx->idata[mid]<node) /* Mid point is too low */
249 amb 257 start=mid;
250 amb 275 else if(segmentsx->idata[mid]>node) /* Mid point is too high */
251 amb 257 end=mid;
252 amb 275 else /* Mid point is correct */
253 amb 257 {found=mid; goto found;}
254     }
255     while((end-start)>1);
256 amb 110
257 amb 275 if(segmentsx->idata[start]==node) /* Start is correct */
258 amb 257 {found=start; goto found;}
259    
260 amb 275 if(segmentsx->idata[end]==node) /* End is correct */
261 amb 257 {found=end; goto found;}
262 amb 110 }
263    
264 amb 275 return(NO_SEGMENT);
265 amb 110
266     found:
267    
268 amb 275 while(found>0 && segmentsx->idata[found-1]==node)
269 amb 110 found--;
270    
271 amb 275 return(found);
272 amb 110 }
273    
274    
275     /*++++++++++++++++++++++++++++++++++++++
276 amb 257 Find the next segment index with a particular starting node.
277 amb 110
278 amb 275 index_t IndexNextSegmentX Returns the index of the next segment with the same id.
279 amb 110
280     SegmentsX* segmentsx The set of segments to process.
281    
282 amb 275 index_t index The current segment.
283 amb 110 ++++++++++++++++++++++++++++++++++++++*/
284    
285 amb 275 index_t IndexNextSegmentX(SegmentsX* segmentsx,index_t index)
286 amb 110 {
287 amb 275 if(++index==segmentsx->number)
288     return(NO_SEGMENT);
289     else if(segmentsx->idata[index]==segmentsx->idata[index-1])
290     return(index);
291 amb 229 else
292 amb 275 return(NO_SEGMENT);
293 amb 110 }
294    
295    
296     /*++++++++++++++++++++++++++++++++++++++
297 amb 277 Append a single segment to a segment list.
298 amb 110
299     SegmentsX* segmentsx The set of segments to process.
300    
301 amb 203 way_t way The way that the segment belongs to.
302    
303 amb 110 node_t node1 The first node in the segment.
304    
305     node_t node2 The second node in the segment.
306 amb 228
307     distance_t distance The distance between the nodes (or just the flags).
308 amb 110 ++++++++++++++++++++++++++++++++++++++*/
309    
310 amb 209 void AppendSegment(SegmentsX* segmentsx,way_t way,node_t node1,node_t node2,distance_t distance)
311 amb 110 {
312 amb 256 SegmentX segmentx;
313 amb 110
314 amb 275 assert(!segmentsx->idata); /* Must not have idata filled in => unsorted */
315 amb 110
316 amb 277 segmentx.node1=node1;
317     segmentx.node2=node2;
318 amb 256 segmentx.way=way;
319     segmentx.distance=distance;
320 amb 216
321 amb 256 WriteFile(segmentsx->fd,&segmentx,sizeof(SegmentX));
322    
323     segmentsx->xnumber++;
324     }
325    
326    
327     /*+ A temporary file-local variable for use by the sort function. +*/
328     static SegmentsX *sortsegmentsx;
329    
330    
331     /*++++++++++++++++++++++++++++++++++++++
332 amb 275 Sort the segment list.
333 amb 256
334     SegmentsX* segmentsx The set of segments to process.
335     ++++++++++++++++++++++++++++++++++++++*/
336    
337 amb 275 void SortSegmentList(SegmentsX* segmentsx)
338 amb 256 {
339 amb 275 int fd;
340 amb 256
341 amb 275 /* Check the start conditions */
342 amb 256
343 amb 275 assert(!segmentsx->idata); /* Must not have idata filled in => unsorted */
344 amb 256
345 amb 275 /* Print the start message */
346 amb 256
347 amb 275 printf("Sorting Segments");
348 amb 227 fflush(stdout);
349 amb 110
350 amb 275 /* Close the files and re-open them (finished appending) */
351 amb 110
352 amb 275 CloseFile(segmentsx->fd);
353     segmentsx->fd=ReOpenFile(segmentsx->filename);
354 amb 256
355 amb 275 DeleteFile(segmentsx->filename);
356 amb 256
357 amb 275 fd=OpenFile(segmentsx->filename);
358 amb 256
359 amb 275 /* Allocate the array of indexes */
360 amb 256
361 amb 275 segmentsx->idata=(node_t*)malloc(segmentsx->xnumber*sizeof(node_t));
362 amb 256
363 amb 275 assert(segmentsx->idata); /* Check malloc() worked */
364 amb 256
365 amb 275 /* Sort by node indexes */
366 amb 256
367 amb 275 sortsegmentsx=segmentsx;
368 amb 256
369 amb 275 filesort(segmentsx->fd,fd,sizeof(SegmentX),SORT_RAMSIZE,(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))index_by_id);
370 amb 256
371 amb 275 /* Close the files and re-open them */
372 amb 256
373 amb 275 CloseFile(segmentsx->fd);
374     CloseFile(fd);
375 amb 256
376 amb 275 segmentsx->fd=ReOpenFile(segmentsx->filename);
377 amb 256
378 amb 275 /* Print the final message */
379 amb 258
380 amb 275 printf("\rSorted Segments: Segments=%d\n",segmentsx->xnumber);
381 amb 256 fflush(stdout);
382     }
383    
384    
385     /*++++++++++++++++++++++++++++++++++++++
386 amb 275 Sort the segments into id order (node1 then node2).
387 amb 110
388 amb 275 int sort_by_id Returns the comparison of the node fields.
389 amb 110
390 amb 275 SegmentX *a The first segment.
391 amb 110
392 amb 275 SegmentX *b The second segment.
393 amb 110 ++++++++++++++++++++++++++++++++++++++*/
394    
395 amb 275 static int sort_by_id(SegmentX *a,SegmentX *b)
396 amb 110 {
397 amb 275 node_t a_id1=a->node1;
398     node_t b_id1=b->node1;
399    
400     if(a_id1<b_id1)
401     return(-1);
402     else if(a_id1>b_id1)
403 amb 256 return(1);
404 amb 275 else /* if(a_id1==b_id1) */
405 amb 110 {
406 amb 275 node_t a_id2=a->node2;
407     node_t b_id2=b->node2;
408 amb 110
409 amb 275 if(a_id2<b_id2)
410 amb 110 return(-1);
411 amb 275 else if(a_id2>b_id2)
412 amb 110 return(1);
413 amb 275 else
414 amb 110 {
415 amb 275 distance_t a_distance=a->distance;
416     distance_t b_distance=b->distance;
417 amb 110
418 amb 275 if(a_distance<b_distance)
419 amb 110 return(-1);
420 amb 275 else if(a_distance>b_distance)
421 amb 110 return(1);
422     else
423 amb 275 return(0);
424 amb 110 }
425     }
426     }
427    
428    
429     /*++++++++++++++++++++++++++++++++++++++
430 amb 275 Index the segments after sorting.
431 amb 229
432 amb 275 index_by_id Return 1 if the value is to be kept, otherwise zero.
433 amb 229
434 amb 275 SegmentX *segmentx The extended segment.
435 amb 229
436 amb 275 index_t index The index of this segment in the total.
437 amb 229 ++++++++++++++++++++++++++++++++++++++*/
438    
439 amb 275 static int index_by_id(SegmentX *segmentx,index_t index)
440 amb 229 {
441 amb 275 /* Could de-duplicate here, but then it would interfere with the special
442     de-duplication used for super-segments. */
443 amb 229
444 amb 275 sortsegmentsx->idata[index]=segmentx->node1;
445 amb 256
446 amb 275 sortsegmentsx->number++;
447 amb 229
448 amb 275 return(1);
449 amb 229 }
450    
451    
452     /*++++++++++++++++++++++++++++++++++++++
453 amb 275 Remove bad segments (duplicated, zero length or missing nodes).
454 amb 110
455 amb 195 NodesX *nodesx The nodes to check.
456    
457 amb 110 SegmentsX *segmentsx The segments to modify.
458     ++++++++++++++++++++++++++++++++++++++*/
459    
460 amb 204 void RemoveBadSegments(NodesX *nodesx,SegmentsX *segmentsx)
461 amb 110 {
462 amb 275 int duplicate=0,loop=0,missing=0,good=0,total=0;
463     SegmentX segmentx;
464     int fd;
465     node_t *idata;
466     node_t prevnode1=NO_NODE,prevnode2=NO_NODE;
467 amb 110
468 amb 275 /* Check the start conditions */
469 amb 110
470 amb 275 assert(segmentsx->idata); /* Must have idata filled in => sorted by node 1 */
471    
472     /* Print the start message */
473    
474 amb 227 printf("Checking: Segments=0 Duplicate=0 Loop=0 Missing-Node=0");
475     fflush(stdout);
476    
477 amb 275 /* Modify the on-disk image */
478    
479     DeleteFile(segmentsx->filename);
480    
481     fd=OpenFile(segmentsx->filename);
482     SeekFile(segmentsx->fd,0);
483    
484     while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
485 amb 110 {
486 amb 275 if(prevnode1==segmentx.node1 && prevnode2==segmentx.node2)
487     duplicate++;
488     else if(segmentx.node1==segmentx.node2)
489 amb 257 loop++;
490 amb 275 else if(IndexNodeX(nodesx,segmentx.node1)==NO_NODE ||
491     IndexNodeX(nodesx,segmentx.node2)==NO_NODE)
492     missing++;
493     else
494 amb 257 {
495 amb 275 WriteFile(fd,&segmentx,sizeof(SegmentX));
496    
497     segmentsx->idata[good]=segmentsx->idata[total];
498     good++;
499    
500     prevnode1=segmentx.node1;
501     prevnode2=segmentx.node2;
502 amb 110 }
503    
504 amb 275 total++;
505 amb 256
506 amb 275 if(!(total%10000))
507 amb 110 {
508 amb 275 printf("\rChecking: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d",total,duplicate,loop,missing);
509 amb 110 fflush(stdout);
510     }
511     }
512    
513 amb 275 /* Close the files and re-open them */
514    
515     CloseFile(segmentsx->fd);
516     CloseFile(fd);
517    
518     segmentsx->fd=ReOpenFile(segmentsx->filename);
519    
520     /* Allocate a smaller array for the segment index (don't trust realloc to make it smaller) */
521    
522     idata=(node_t*)malloc(good*sizeof(node_t));
523    
524     assert(idata); /* Check malloc() worked */
525    
526     memcpy(idata,segmentsx->idata,good*sizeof(node_t));
527    
528     free(segmentsx->idata);
529    
530     segmentsx->idata=idata;
531     segmentsx->number=good;
532    
533     /* Print the final message */
534    
535     printf("\rChecked: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d \n",total,duplicate,loop,missing);
536 amb 110 fflush(stdout);
537     }
538    
539    
540     /*++++++++++++++++++++++++++++++++++++++
541     Measure the segments.
542    
543     SegmentsX* segmentsx The set of segments to process.
544    
545     NodesX *nodesx The list of nodes to use.
546     ++++++++++++++++++++++++++++++++++++++*/
547    
548     void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx)
549     {
550 amb 275 index_t total=0;
551 amb 256 int fd;
552     SegmentX segmentx;
553 amb 110
554 amb 275 /* Print the start message */
555    
556 amb 227 printf("Measuring Segments: Segments=0");
557     fflush(stdout);
558    
559 amb 275 /* Map into memory */
560 amb 257
561 amb 258 if(!option_slim)
562 amb 275 nodesx->xdata=MapFile(nodesx->filename);
563 amb 258
564 amb 275 /* Modify the on-disk image */
565    
566 amb 256 DeleteFile(segmentsx->filename);
567    
568     fd=OpenFile(segmentsx->filename);
569     SeekFile(segmentsx->fd,0);
570    
571     while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
572 amb 110 {
573 amb 275 NodeX *nodex1=LookupNodeX(nodesx,IndexNodeX(nodesx,segmentx.node1),1);
574     NodeX *nodex2=LookupNodeX(nodesx,IndexNodeX(nodesx,segmentx.node2),2);
575 amb 110
576 amb 275 /* Set the distance but preserve the ONEWAY_* flags */
577    
578     segmentx.distance|=DISTANCE(DistanceX(nodex1,nodex2));
579    
580     WriteFile(fd,&segmentx,sizeof(SegmentX));
581    
582     total++;
583    
584     if(!(total%10000))
585 amb 257 {
586 amb 275 printf("\rMeasuring Segments: Segments=%d",total);
587     fflush(stdout);
588     }
589     }
590 amb 110
591 amb 275 /* Close the files and re-open them */
592 amb 257
593 amb 275 CloseFile(segmentsx->fd);
594     CloseFile(fd);
595    
596     segmentsx->fd=ReOpenFile(segmentsx->filename);
597    
598     /* Unmap from memory */
599    
600     if(!option_slim)
601     nodesx->xdata=UnmapFile(nodesx->filename);
602    
603     /* Print the final message */
604    
605     printf("\rMeasured Segments: Segments=%d \n",segmentsx->number);
606     fflush(stdout);
607     }
608    
609    
610     /*++++++++++++++++++++++++++++++++++++++
611     Make the segments all point the same way (node1<node2).
612    
613     SegmentsX* segmentsx The set of segments to process.
614     ++++++++++++++++++++++++++++++++++++++*/
615    
616     void RotateSegments(SegmentsX* segmentsx)
617     {
618     int index=0,rotated=0;
619     int fd;
620     SegmentX segmentx;
621    
622     /* Check the start conditions */
623    
624     assert(!segmentsx->idata); /* Must not have idata filled in => not sorted by node 1 */
625    
626     /* Print the start message */
627    
628     printf("Rotating Segments: Segments=0 Rotated=0");
629     fflush(stdout);
630    
631     /* Close the files and re-open them (finished appending) */
632    
633     CloseFile(segmentsx->fd);
634     segmentsx->fd=ReOpenFile(segmentsx->filename);
635    
636     DeleteFile(segmentsx->filename);
637    
638     fd=OpenFile(segmentsx->filename);
639    
640     /* Modify the file contents */
641    
642     while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
643     {
644     if(segmentx.node1>segmentx.node2)
645     {
646     node_t temp;
647    
648     temp=segmentx.node1;
649     segmentx.node1=segmentx.node2;
650     segmentx.node2=temp;
651    
652     if(segmentx.distance&(ONEWAY_2TO1|ONEWAY_1TO2))
653     segmentx.distance^=ONEWAY_2TO1|ONEWAY_1TO2;
654    
655     rotated++;
656 amb 257 }
657 amb 110
658 amb 256 WriteFile(fd,&segmentx,sizeof(SegmentX));
659    
660 amb 275 index++;
661 amb 256
662 amb 275 if(!(index%10000))
663 amb 110 {
664 amb 275 printf("\rRotating Segments: Segments=%d Rotated=%d",index,rotated);
665 amb 110 fflush(stdout);
666     }
667     }
668    
669 amb 275 /* Close the files and re-open them */
670    
671 amb 256 CloseFile(segmentsx->fd);
672     CloseFile(fd);
673    
674     segmentsx->fd=ReOpenFile(segmentsx->filename);
675    
676 amb 275 /* Print the final message */
677 amb 256
678 amb 275 printf("\rRotated Segments: Segments=%d Rotated=%d \n",index,rotated);
679 amb 110 fflush(stdout);
680     }
681    
682    
683     /*++++++++++++++++++++++++++++++++++++++
684 amb 275 Remove the duplicate segments.
685 amb 110
686     SegmentsX* segmentsx The set of segments to process.
687    
688     WaysX *waysx The list of ways to use.
689     ++++++++++++++++++++++++++++++++++++++*/
690    
691 amb 212 void DeduplicateSegments(SegmentsX* segmentsx,WaysX *waysx)
692 amb 110 {
693 amb 275 int duplicate=0,good=0;
694     index_t firstindex=0,index=0;
695     node_t *idata;
696     int fd;
697     SegmentX prevsegmentx[16],segmentx;
698 amb 110
699 amb 275 /* Check the start conditions */
700 amb 110
701 amb 275 assert(segmentsx->idata); /* Must have idata filled in => sorted by node 1 */
702    
703     /* Print the start message */
704    
705 amb 227 printf("Deduplicating Segments: Segments=0 Duplicate=0");
706     fflush(stdout);
707    
708 amb 275 /* Map into memory */
709 amb 256
710 amb 275 if(!option_slim)
711     waysx->xdata=MapFile(waysx->filename);
712    
713     /* Modify the on-disk image */
714    
715     DeleteFile(segmentsx->filename);
716    
717     fd=OpenFile(segmentsx->filename);
718     SeekFile(segmentsx->fd,0);
719    
720     while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
721 amb 110 {
722 amb 275 int isduplicate=0;
723 amb 256
724 amb 275 if(index && segmentx.node1==prevsegmentx[0].node1 &&
725     segmentx.node2==prevsegmentx[0].node2)
726 amb 110 {
727 amb 264 index_t previndex=firstindex;
728 amb 110
729 amb 275 while(previndex<index)
730 amb 110 {
731 amb 275 int offset=previndex-firstindex;
732    
733     if(DISTFLAG(segmentx.distance)==DISTFLAG(prevsegmentx[offset].distance))
734 amb 264 {
735 amb 275 WayX *wayx1=LookupWayX(waysx,IndexWayX(waysx,prevsegmentx[offset].way),1);
736     WayX *wayx2=LookupWayX(waysx,IndexWayX(waysx, segmentx .way),2);
737 amb 110
738 amb 275 if(!WaysCompare(&wayx1->way,&wayx2->way))
739 amb 264 {
740 amb 275 isduplicate=1;
741     duplicate++;
742     break;
743 amb 264 }
744     }
745    
746     previndex++;
747 amb 110 }
748 amb 275
749     assert((index-firstindex)<(sizeof(prevsegmentx)/sizeof(prevsegmentx[0])));
750    
751     prevsegmentx[index-firstindex]=segmentx;
752 amb 110 }
753 amb 264 else
754     {
755 amb 275 firstindex=index;
756     prevsegmentx[0]=segmentx;
757 amb 264 }
758 amb 110
759 amb 275 if(!isduplicate)
760 amb 110 {
761 amb 275 WriteFile(fd,&segmentx,sizeof(SegmentX));
762    
763     segmentsx->idata[good]=segmentsx->idata[index];
764     good++;
765     }
766    
767     index++;
768    
769     if(!(index%10000))
770     {
771     printf("\rDeduplicating Segments: Segments=%d Duplicate=%d",index,duplicate);
772 amb 110 fflush(stdout);
773     }
774     }
775    
776 amb 275 /* Close the files and re-open them */
777    
778     CloseFile(segmentsx->fd);
779     CloseFile(fd);
780    
781     segmentsx->fd=ReOpenFile(segmentsx->filename);
782    
783     /* Allocate a smaller array for the segment index (don't trust realloc to make it smaller) */
784    
785     idata=(node_t*)malloc(good*sizeof(node_t));
786    
787     assert(idata); /* Check malloc() worked */
788    
789     memcpy(idata,segmentsx->idata,good*sizeof(node_t));
790    
791     free(segmentsx->idata);
792    
793     segmentsx->idata=idata;
794     segmentsx->number=good;
795    
796     /* Unmap from memory */
797    
798     if(!option_slim)
799     waysx->xdata=UnmapFile(waysx->filename);
800    
801     /* Print the final message */
802    
803     printf("\rDeduplicated Segments: Segments=%d Duplicate=%d Unique=%d\n",index,duplicate,index-duplicate);
804 amb 110 fflush(stdout);
805     }
806    
807    
808     /*++++++++++++++++++++++++++++++++++++++
809 amb 209 Create the real segments data.
810    
811     SegmentsX* segmentsx The set of segments to use.
812    
813     WaysX* waysx The set of ways to use.
814     ++++++++++++++++++++++++++++++++++++++*/
815    
816     void CreateRealSegments(SegmentsX *segmentsx,WaysX *waysx)
817     {
818 amb 214 index_t i;
819 amb 209
820 amb 275 /* Check the start conditions */
821    
822 amb 243 assert(!segmentsx->sdata); /* Must not have sdata filled in => no real segments */
823 amb 213
824 amb 275 /* Print the start message */
825    
826 amb 227 printf("Creating Real Segments: Segments=0");
827     fflush(stdout);
828    
829 amb 275 /* Map into memory */
830 amb 209
831 amb 275 if(!option_slim)
832     {
833     segmentsx->xdata=MapFile(segmentsx->filename);
834     waysx->xdata=MapFile(waysx->filename);
835     }
836    
837     /* Deallocate and allocate the memory */
838    
839     free(segmentsx->idata);
840     segmentsx->idata=NULL;
841    
842 amb 209 segmentsx->sdata=(Segment*)malloc(segmentsx->number*sizeof(Segment));
843    
844 amb 243 assert(segmentsx->sdata); /* Check malloc() worked */
845    
846 amb 275 /* Loop through and fill */
847 amb 209
848     for(i=0;i<segmentsx->number;i++)
849     {
850 amb 275 SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
851 amb 262 WayX *wayx=LookupWayX(waysx,IndexWayX(waysx,segmentx->way),1);
852 amb 209
853     segmentsx->sdata[i].node1=0;
854     segmentsx->sdata[i].node2=0;
855     segmentsx->sdata[i].next2=NO_NODE;
856 amb 262 segmentsx->sdata[i].way=wayx->cid;
857 amb 256 segmentsx->sdata[i].distance=segmentx->distance;
858 amb 209
859     if(!((i+1)%10000))
860     {
861     printf("\rCreating Real Segments: Segments=%d",i+1);
862     fflush(stdout);
863     }
864     }
865    
866 amb 275 /* Unmap from memory */
867    
868     if(!option_slim)
869     {
870     segmentsx->xdata=UnmapFile(segmentsx->filename);
871     waysx->xdata=UnmapFile(waysx->filename);
872     }
873    
874     /* Print the final message */
875    
876 amb 209 printf("\rCreating Real Segments: Segments=%d \n",segmentsx->number);
877     fflush(stdout);
878     }
879    
880    
881     /*++++++++++++++++++++++++++++++++++++++
882 amb 110 Assign the nodes indexes to the segments.
883    
884     SegmentsX* segmentsx The set of segments to process.
885    
886     NodesX *nodesx The list of nodes to use.
887     ++++++++++++++++++++++++++++++++++++++*/
888    
889     void IndexSegments(SegmentsX* segmentsx,NodesX *nodesx)
890     {
891 amb 214 index_t i;
892 amb 110
893 amb 275 /* Check the start conditions */
894    
895 amb 243 assert(segmentsx->sdata); /* Must have sdata filled in => real segments */
896     assert(nodesx->gdata); /* Must have gdata filled in => sorted geographically */
897 amb 110
898 amb 275 /* Print the start message */
899    
900 amb 227 printf("Indexing Nodes: Nodes=0");
901     fflush(stdout);
902    
903 amb 275 /* Map into memory */
904    
905     if(!option_slim)
906     segmentsx->xdata=MapFile(segmentsx->filename);
907    
908 amb 110 /* Index the segments */
909    
910     for(i=0;i<nodesx->number;i++)
911     {
912 amb 257 Node *node =&nodesx->ndata[nodesx->gdata[i]];
913 amb 212 index_t index=SEGMENT(node->firstseg);
914 amb 110
915     do
916     {
917 amb 275 SegmentX *segmentx=LookupSegmentX(segmentsx,index,1);
918 amb 256
919 amb 257 if(segmentx->node1==nodesx->idata[nodesx->gdata[i]])
920 amb 110 {
921 amb 209 segmentsx->sdata[index].node1=i;
922 amb 110
923 amb 209 index++;
924 amb 128
925 amb 256 if(index>=segmentsx->number)
926 amb 209 break;
927 amb 256
928 amb 275 segmentx=LookupSegmentX(segmentsx,index,1);
929 amb 256
930 amb 257 if(segmentx->node1!=nodesx->idata[nodesx->gdata[i]])
931 amb 256 break;
932 amb 110 }
933     else
934     {
935 amb 209 segmentsx->sdata[index].node2=i;
936 amb 110
937 amb 209 if(segmentsx->sdata[index].next2==NO_NODE)
938     break;
939 amb 110 else
940 amb 209 index=segmentsx->sdata[index].next2;
941 amb 110 }
942     }
943 amb 209 while(1);
944 amb 110
945     if(!((i+1)%10000))
946     {
947     printf("\rIndexing Nodes: Nodes=%d",i+1);
948     fflush(stdout);
949     }
950     }
951    
952 amb 275 /* Unmap from memory */
953    
954     if(!option_slim)
955     segmentsx->xdata=UnmapFile(segmentsx->filename);
956    
957     /* Print the final message */
958    
959 amb 110 printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number);
960     fflush(stdout);
961     }
962    
963    
964     /*++++++++++++++++++++++++++++++++++++++
965     Calculate the distance between two nodes.
966    
967     distance_t DistanceX Returns the distance between the extended nodes.
968    
969     NodeX *nodex1 The starting node.
970    
971     NodeX *nodex2 The end node.
972     ++++++++++++++++++++++++++++++++++++++*/
973    
974 amb 228 static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
975 amb 110 {
976 amb 223 double dlon = latlong_to_radians(nodex1->longitude) - latlong_to_radians(nodex2->longitude);
977     double dlat = latlong_to_radians(nodex1->latitude) - latlong_to_radians(nodex2->latitude);
978     double lat1 = latlong_to_radians(nodex1->latitude);
979     double lat2 = latlong_to_radians(nodex2->latitude);
980 amb 110
981 amb 219 double a1,a2,a,sa,c,d;
982 amb 110
983     if(dlon==0 && dlat==0)
984     return 0;
985    
986 amb 219 a1 = sin (dlat / 2);
987     a2 = sin (dlon / 2);
988     a = (a1 * a1) + cos (lat1) * cos (lat2) * a2 * a2;
989     sa = sqrt (a);
990 amb 110 if (sa <= 1.0)
991 amb 219 {c = 2 * asin (sa);}
992 amb 110 else
993 amb 219 {c = 2 * asin (1.0);}
994 amb 110 d = 6378.137 * c;
995    
996     return km_to_distance(d);
997     }

Properties

Name Value
cvs:description Extended segments functions.