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 1155 - (hide annotations) (download) (as text)
Mon Nov 19 16:15:53 2012 UTC (12 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 31103 byte(s)
De-duplicate segments when sorting only if they have the same nodes, way and
distance - i.e. the same data imported twice.

1 amb 110 /***************************************
2     Extended Segment data type functions.
3 amb 151
4     Part of the Routino routing software.
5 amb 110 ******************/ /******************
6 amb 949 This file Copyright 2008-2012 Andrew M. Bishop
7 amb 110
8 amb 151 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 amb 110 ***************************************/
21    
22    
23     #include <assert.h>
24     #include <math.h>
25     #include <stdlib.h>
26 amb 955 #include <string.h>
27 amb 110
28     #include "types.h"
29 amb 228 #include "segments.h"
30     #include "ways.h"
31 amb 110
32 amb 955 #include "typesx.h"
33 amb 449 #include "nodesx.h"
34     #include "segmentsx.h"
35     #include "waysx.h"
36 amb 110
37 amb 449 #include "files.h"
38 amb 519 #include "logging.h"
39 amb 532 #include "sorting.h"
40 amb 449
41    
42 amb 680 /* Global variables */
43 amb 110
44 amb 289 /*+ The command line '--tmpdir' option or its default value. +*/
45 amb 284 extern char *option_tmpdirname;
46 amb 110
47 amb 1146 /*+ The option to apply changes (needed to suppress some error log messages) +*/
48     extern int option_changes;
49    
50 amb 1100 /* Local variables */
51    
52 amb 1107 /*+ Temporary file-local variables for use by the sort functions. +*/
53 amb 1132 static NodesX *sortnodesx;
54 amb 1100 static SegmentsX *sortsegmentsx;
55 amb 1132 static WaysX *sortwaysx;
56 amb 1100
57 amb 680 /* Local functions */
58 amb 110
59 amb 1140 static int sort_by_way_id(SegmentX *a,SegmentX *b);
60     static int apply_changes(SegmentX *segmentx,index_t index);
61 amb 275 static int sort_by_id(SegmentX *a,SegmentX *b);
62 amb 1155 static int deduplicate(SegmentX *segmentx,index_t index);
63 amb 949 static int delete_pruned(SegmentX *segmentx,index_t index);
64 amb 1107 static int geographically_index(SegmentX *segmentx,index_t index);
65 amb 1132 static int deduplicate_super(SegmentX *segmentx,index_t index);
66 amb 275
67 amb 228 static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2);
68 amb 110
69    
70     /*++++++++++++++++++++++++++++++++++++++
71 amb 326 Allocate a new segment list (create a new file or open an existing one).
72 amb 110
73     SegmentsX *NewSegmentList Returns the segment list.
74 amb 326
75 amb 1123 int append Set to 1 if the file is to be opened for appending.
76    
77 amb 1139 int readonly Set to 1 if the file is to be opened for reading.
78 amb 110 ++++++++++++++++++++++++++++++++++++++*/
79    
80 amb 1123 SegmentsX *NewSegmentList(int append,int readonly)
81 amb 110 {
82     SegmentsX *segmentsx;
83    
84 amb 213 segmentsx=(SegmentsX*)calloc(1,sizeof(SegmentsX));
85 amb 110
86 amb 243 assert(segmentsx); /* Check calloc() worked */
87    
88 amb 1120 segmentsx->filename =(char*)malloc(strlen(option_tmpdirname)+32);
89     segmentsx->filename_tmp=(char*)malloc(strlen(option_tmpdirname)+32);
90 amb 216
91 amb 1120 sprintf(segmentsx->filename ,"%s/segmentsx.parsed.mem",option_tmpdirname);
92     sprintf(segmentsx->filename_tmp,"%s/segmentsx.%p.tmp" ,option_tmpdirname,(void*)segmentsx);
93 amb 256
94 amb 1123 if(append || readonly)
95     if(ExistsFile(segmentsx->filename))
96     {
97     off_t size;
98 amb 326
99 amb 1123 size=SizeFile(segmentsx->filename);
100 amb 326
101 amb 1123 segmentsx->number=size/sizeof(SegmentX);
102 amb 1139
103     RenameFile(segmentsx->filename,segmentsx->filename_tmp);
104 amb 1123 }
105 amb 326
106 amb 1123 if(append)
107 amb 1139 segmentsx->fd=OpenFileAppend(segmentsx->filename_tmp);
108 amb 1123 else if(!readonly)
109 amb 1139 segmentsx->fd=OpenFileNew(segmentsx->filename_tmp);
110 amb 326 else
111 amb 1123 segmentsx->fd=-1;
112 amb 326
113 amb 110 return(segmentsx);
114     }
115    
116    
117     /*++++++++++++++++++++++++++++++++++++++
118 amb 226 Free a segment list.
119 amb 110
120 amb 681 SegmentsX *segmentsx The set of segments to be freed.
121 amb 1151
122     int preserve If set then the results file is to be preserved.
123 amb 110 ++++++++++++++++++++++++++++++++++++++*/
124    
125 amb 1151 void FreeSegmentList(SegmentsX *segmentsx,int preserve)
126 amb 110 {
127 amb 1151 if(preserve)
128     RenameFile(segmentsx->filename_tmp,segmentsx->filename);
129     else
130     DeleteFile(segmentsx->filename_tmp);
131 amb 1120
132 amb 283 free(segmentsx->filename);
133 amb 1120 free(segmentsx->filename_tmp);
134 amb 256
135 amb 949 if(segmentsx->firstnode)
136     free(segmentsx->firstnode);
137    
138     if(segmentsx->next1)
139     free(segmentsx->next1);
140    
141 amb 643 if(segmentsx->usednode)
142     free(segmentsx->usednode);
143    
144 amb 110 free(segmentsx);
145     }
146    
147    
148     /*++++++++++++++++++++++++++++++++++++++
149 amb 493 Append a single segment to an unsorted segment list.
150 amb 110
151 amb 681 SegmentsX *segmentsx The set of segments to modify.
152 amb 110
153 amb 285 way_t way The way that the segment belongs to.
154    
155     node_t node1 The first node in the segment.
156    
157     node_t node2 The second node in the segment.
158    
159     distance_t distance The distance between the nodes (or just the flags).
160 amb 110 ++++++++++++++++++++++++++++++++++++++*/
161    
162 amb 681 void AppendSegment(SegmentsX *segmentsx,way_t way,node_t node1,node_t node2,distance_t distance)
163 amb 110 {
164 amb 285 SegmentX segmentx;
165 amb 110
166 amb 643 if(node1>node2)
167     {
168     node_t temp;
169    
170     temp=node1;
171     node1=node2;
172     node2=temp;
173    
174     if(distance&(ONEWAY_2TO1|ONEWAY_1TO2))
175     distance^=ONEWAY_2TO1|ONEWAY_1TO2;
176     }
177    
178 amb 285 segmentx.node1=node1;
179     segmentx.node2=node2;
180 amb 643 segmentx.next2=NO_SEGMENT;
181 amb 285 segmentx.way=way;
182     segmentx.distance=distance;
183 amb 110
184 amb 285 WriteFile(segmentsx->fd,&segmentx,sizeof(SegmentX));
185 amb 281
186 amb 650 segmentsx->number++;
187 amb 466
188 amb 650 assert(segmentsx->number<SEGMENT_FAKE); /* SEGMENT_FAKE marks the high-water mark for real segments. */
189 amb 285 }
190 amb 227
191 amb 281
192 amb 285 /*++++++++++++++++++++++++++++++++++++++
193 amb 1120 Finish appending segments and change the filename over.
194    
195     SegmentsX *segmentsx The segments that have been appended.
196     ++++++++++++++++++++++++++++++++++++++*/
197    
198 amb 1151 void FinishSegmentList(SegmentsX *segmentsx)
199 amb 1120 {
200 amb 1136 if(segmentsx->fd!=-1)
201     segmentsx->fd=CloseFile(segmentsx->fd);
202 amb 1120 }
203    
204    
205     /*++++++++++++++++++++++++++++++++++++++
206 amb 1140 Apply the changes to the segments (no unique id to use).
207    
208     SegmentsX *segmentsx The set of segments to sort and modify.
209     ++++++++++++++++++++++++++++++++++++++*/
210    
211     void ApplySegmentChanges(SegmentsX *segmentsx)
212     {
213     int fd;
214     index_t xnumber;
215    
216     /* Print the start message */
217    
218     printf_first("Applying Segment Changes");
219    
220     /* Re-open the file read-only and a new file writeable */
221    
222     segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
223    
224     DeleteFile(segmentsx->filename_tmp);
225    
226     fd=OpenFileNew(segmentsx->filename_tmp);
227    
228     /* Sort by node indexes */
229    
230     xnumber=segmentsx->number;
231    
232     segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),NULL,
233     (int (*)(const void*,const void*))sort_by_way_id,
234     (int (*)(void*,index_t))apply_changes);
235    
236     /* Close the files */
237    
238     segmentsx->fd=CloseFile(segmentsx->fd);
239     CloseFile(fd);
240    
241     /* Print the final message */
242    
243     printf_last("Applying Segment Changes: Segments=%"Pindex_t" Changed=%"Pindex_t,xnumber,xnumber-segmentsx->number);
244     }
245    
246    
247     /*++++++++++++++++++++++++++++++++++++++
248 amb 1131 Sort the segment list and deduplicate it.
249 amb 232
250 amb 949 SegmentsX *segmentsx The set of segments to sort and modify.
251 amb 1100 ++++++++++++++++++++++++++++++++++++++*/
252 amb 949
253 amb 1100 void SortSegmentList(SegmentsX *segmentsx)
254     {
255     int fd;
256 amb 1131 index_t xnumber;
257 amb 1100
258     /* Print the start message */
259    
260     printf_first("Sorting Segments");
261    
262     /* Re-open the file read-only and a new file writeable */
263    
264 amb 1120 segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
265 amb 1100
266 amb 1120 DeleteFile(segmentsx->filename_tmp);
267 amb 1100
268 amb 1120 fd=OpenFileNew(segmentsx->filename_tmp);
269 amb 1100
270     /* Sort by node indexes */
271    
272 amb 1131 xnumber=segmentsx->number;
273    
274     segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),NULL,
275     (int (*)(const void*,const void*))sort_by_id,
276 amb 1155 (int (*)(void*,index_t))deduplicate);
277 amb 1131
278     /* Close the files */
279    
280     segmentsx->fd=CloseFile(segmentsx->fd);
281     CloseFile(fd);
282    
283     /* Print the final message */
284    
285     printf_last("Sorted Segments: Segments=%"Pindex_t" Duplicates=%"Pindex_t,xnumber,xnumber-segmentsx->number);
286     }
287    
288    
289     /*++++++++++++++++++++++++++++++++++++++
290 amb 1100 Prune the deleted segments while resorting the list.
291    
292     SegmentsX *segmentsx The set of segments to sort and modify.
293    
294     WaysX *waysx The set of ways to check.
295 amb 285 ++++++++++++++++++++++++++++++++++++++*/
296 amb 110
297 amb 1100 void RemovePrunedSegments(SegmentsX *segmentsx,WaysX *waysx)
298 amb 285 {
299     int fd;
300 amb 1132 index_t xnumber;
301 amb 243
302 amb 285 /* Print the start message */
303 amb 232
304 amb 1106 printf_first("Sorting and Pruning Segments");
305 amb 110
306 amb 1100 /* Allocate the way usage bitmask */
307    
308     segmentsx->usedway=AllocBitMask(waysx->number);
309    
310     assert(segmentsx->usedway); /* Check AllocBitMask() worked */
311    
312 amb 555 /* Re-open the file read-only and a new file writeable */
313    
314 amb 1120 segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
315 amb 110
316 amb 1120 DeleteFile(segmentsx->filename_tmp);
317 amb 110
318 amb 1120 fd=OpenFileNew(segmentsx->filename_tmp);
319 amb 110
320 amb 285 /* Sort by node indexes */
321 amb 132
322 amb 1132 xnumber=segmentsx->number;
323    
324 amb 1100 sortsegmentsx=segmentsx;
325 amb 285
326 amb 1132 segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),(int (*)(void*,index_t))delete_pruned,
327     (int (*)(const void*,const void*))sort_by_id,
328     NULL);
329 amb 1100
330 amb 555 /* Close the files */
331 amb 285
332 amb 612 segmentsx->fd=CloseFile(segmentsx->fd);
333 amb 281 CloseFile(fd);
334    
335     /* Print the final message */
336    
337 amb 1132 printf_last("Sorted and Pruned Segments: Segments=%"Pindex_t" Deleted=%"Pindex_t,xnumber,xnumber-segmentsx->number);
338 amb 110 }
339    
340    
341     /*++++++++++++++++++++++++++++++++++++++
342 amb 1140 Sort the segments into way id order.
343    
344     int sort_by_way_id Returns the comparison of the way fields.
345    
346     SegmentX *a The first segment.
347    
348     SegmentX *b The second segment.
349     ++++++++++++++++++++++++++++++++++++++*/
350    
351     static int sort_by_way_id(SegmentX *a,SegmentX *b)
352     {
353     way_t a_id=a->way;
354     way_t b_id=b->way;
355    
356     if(a_id<b_id)
357     return(-1);
358     else if(a_id>b_id)
359     return(1);
360     else /* if(a_id==b_id) */
361     return(-FILESORT_PRESERVE_ORDER(a,b)); /* latest version first */
362     }
363    
364    
365     /*++++++++++++++++++++++++++++++++++++++
366 amb 680 Sort the segments into id order, first by node1 then by node2, finally by distance.
367 amb 110
368 amb 285 int sort_by_id Returns the comparison of the node fields.
369 amb 110
370 amb 285 SegmentX *a The first segment.
371 amb 110
372 amb 285 SegmentX *b The second segment.
373 amb 256 ++++++++++++++++++++++++++++++++++++++*/
374    
375 amb 285 static int sort_by_id(SegmentX *a,SegmentX *b)
376 amb 256 {
377 amb 285 node_t a_id1=a->node1;
378     node_t b_id1=b->node1;
379 amb 256
380 amb 285 if(a_id1<b_id1)
381     return(-1);
382     else if(a_id1>b_id1)
383     return(1);
384     else /* if(a_id1==b_id1) */
385 amb 256 {
386 amb 285 node_t a_id2=a->node2;
387     node_t b_id2=b->node2;
388 amb 256
389 amb 285 if(a_id2<b_id2)
390     return(-1);
391     else if(a_id2>b_id2)
392     return(1);
393     else
394     {
395 amb 914 distance_t a_distance=DISTANCE(a->distance);
396     distance_t b_distance=DISTANCE(b->distance);
397 amb 256
398 amb 285 if(a_distance<b_distance)
399     return(-1);
400     else if(a_distance>b_distance)
401     return(1);
402     else
403 amb 1153 {
404     distance_t a_distflag=DISTFLAG(a->distance);
405     distance_t b_distflag=DISTFLAG(b->distance);
406    
407     if(a_distflag<b_distflag)
408     return(-1);
409     else if(a_distflag>b_distflag)
410     return(1);
411     else
412     return(FILESORT_PRESERVE_ORDER(a,b)); /* preserve order */
413     }
414 amb 285 }
415 amb 256 }
416     }
417    
418    
419     /*++++++++++++++++++++++++++++++++++++++
420 amb 1140 Apply the changes to the segments.
421    
422     int apply_changes Return 1 if the value is to be kept, otherwise 0.
423    
424     SegmentX *segmentx The extended segment.
425    
426     index_t index The number of sorted segments that have already been written to the output file.
427     ++++++++++++++++++++++++++++++++++++++*/
428    
429     static int apply_changes(SegmentX *segmentx,index_t index)
430     {
431     static way_t prevway=NO_WAY_ID;
432     static int deleted=0;
433    
434     if(prevway!=segmentx->way)
435     {
436     prevway=segmentx->way;
437     deleted=0;
438     }
439    
440     if(!deleted)
441     if(segmentx->node1==NO_NODE_ID)
442     deleted=1;
443    
444     if(deleted)
445     return(0);
446     else
447     return(1);
448     }
449    
450    
451     /*++++++++++++++++++++++++++++++++++++++
452 amb 1155 Discard duplicate segments.
453 amb 1131
454 amb 1155 int deduplicate Return 1 if the value is to be kept, otherwise 0.
455 amb 1131
456     SegmentX *segmentx The extended segment.
457    
458     index_t index The number of sorted segments that have already been written to the output file.
459     ++++++++++++++++++++++++++++++++++++++*/
460    
461 amb 1155 static int deduplicate(SegmentX *segmentx,index_t index)
462 amb 1131 {
463     static node_t prevnode1=NO_NODE_ID,prevnode2=NO_NODE_ID;
464 amb 1155 static way_t prevway=NO_WAY_ID;
465 amb 1131 static distance_t prevdist=0;
466    
467 amb 1155 if(prevnode1!=segmentx->node1 || prevnode2!=segmentx->node2 || prevway!=segmentx->way || prevdist!=segmentx->distance)
468 amb 1131 {
469     prevnode1=segmentx->node1;
470     prevnode2=segmentx->node2;
471 amb 1155 prevway=segmentx->way;
472 amb 1137 prevdist=segmentx->distance;
473 amb 1131
474     return(1);
475     }
476     else
477     return(0);
478     }
479    
480    
481     /*++++++++++++++++++++++++++++++++++++++
482 amb 949 Delete the pruned segments.
483    
484     int delete_pruned Return 1 if the value is to be kept, otherwise 0.
485    
486     SegmentX *segmentx The extended segment.
487    
488 amb 1112 index_t index The number of unsorted segments that have been read from the input file.
489 amb 949 ++++++++++++++++++++++++++++++++++++++*/
490    
491     static int delete_pruned(SegmentX *segmentx,index_t index)
492     {
493     if(IsPrunedSegmentX(segmentx))
494     return(0);
495    
496 amb 1100 SetBit(sortsegmentsx->usedway,segmentx->way);
497    
498 amb 949 return(1);
499     }
500    
501    
502     /*++++++++++++++++++++++++++++++++++++++
503 amb 1107 Sort the segments geographically after updating the node indexes.
504    
505     SegmentsX *segmentsx The set of segments to modify.
506    
507     NodesX *nodesx The set of nodes to use.
508     ++++++++++++++++++++++++++++++++++++++*/
509    
510     void SortSegmentListGeographically(SegmentsX *segmentsx,NodesX *nodesx)
511     {
512     int fd;
513    
514     /* Print the start message */
515    
516     printf_first("Sorting Segments Geographically");
517    
518     /* Re-open the file read-only and a new file writeable */
519    
520 amb 1120 segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
521 amb 1107
522 amb 1120 DeleteFile(segmentsx->filename_tmp);
523 amb 1107
524 amb 1120 fd=OpenFileNew(segmentsx->filename_tmp);
525 amb 1107
526     /* Update the segments with geographically sorted node indexes and sort them */
527    
528     sortnodesx=nodesx;
529    
530     filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),(int (*)(void*,index_t))geographically_index,
531     (int (*)(const void*,const void*))sort_by_id,
532     NULL);
533     /* Close the files */
534    
535     segmentsx->fd=CloseFile(segmentsx->fd);
536     CloseFile(fd);
537    
538     /* Print the final message */
539    
540 amb 1110 printf_last("Sorted Segments Geographically: Segments=%"Pindex_t,segmentsx->number);
541 amb 1107 }
542    
543    
544     /*++++++++++++++++++++++++++++++++++++++
545     Update the segment indexes.
546    
547     int geographically_index Return 1 if the value is to be kept, otherwise 0.
548    
549     SegmentX *segmentx The extended segment.
550    
551 amb 1112 index_t index The number of unsorted segments that have been read from the input file.
552 amb 1107 ++++++++++++++++++++++++++++++++++++++*/
553    
554     static int geographically_index(SegmentX *segmentx,index_t index)
555     {
556     segmentx->node1=sortnodesx->gdata[segmentx->node1];
557     segmentx->node2=sortnodesx->gdata[segmentx->node2];
558    
559     if(segmentx->node1>segmentx->node2)
560     {
561     index_t temp;
562    
563     temp=segmentx->node1;
564     segmentx->node1=segmentx->node2;
565     segmentx->node2=temp;
566    
567     if(segmentx->distance&(ONEWAY_2TO1|ONEWAY_1TO2))
568     segmentx->distance^=ONEWAY_2TO1|ONEWAY_1TO2;
569     }
570    
571     return(1);
572     }
573    
574    
575     /*++++++++++++++++++++++++++++++++++++++
576 amb 643 Find the first extended segment with a particular starting node index.
577    
578 amb 646 SegmentX *FirstSegmentX Returns a pointer to the first extended segment with the specified id.
579 amb 544
580 amb 681 SegmentsX *segmentsx The set of segments to use.
581 amb 544
582 amb 643 index_t nodeindex The node index to look for.
583    
584     int position A flag to pass through.
585     ++++++++++++++++++++++++++++++++++++++*/
586    
587 amb 681 SegmentX *FirstSegmentX(SegmentsX *segmentsx,index_t nodeindex,int position)
588 amb 643 {
589     index_t index=segmentsx->firstnode[nodeindex];
590     SegmentX *segmentx;
591    
592 amb 793 if(index==NO_SEGMENT)
593     return(NULL);
594    
595 amb 643 segmentx=LookupSegmentX(segmentsx,index,position);
596    
597     return(segmentx);
598     }
599    
600    
601     /*++++++++++++++++++++++++++++++++++++++
602     Find the next segment with a particular starting node index.
603    
604 amb 646 SegmentX *NextSegmentX Returns a pointer to the next segment with the same id.
605 amb 643
606 amb 681 SegmentsX *segmentsx The set of segments to use.
607 amb 544
608 amb 643 SegmentX *segmentx The current segment.
609 amb 544
610 amb 771 index_t nodeindex The node index.
611 amb 110 ++++++++++++++++++++++++++++++++++++++*/
612    
613 amb 943 SegmentX *NextSegmentX(SegmentsX *segmentsx,SegmentX *segmentx,index_t nodeindex)
614 amb 110 {
615 amb 943 #if SLIM
616     int position=1+(segmentx-&segmentsx->cached[0]);
617     #endif
618    
619 amb 771 if(segmentx->node1==nodeindex)
620 amb 643 {
621 amb 949 if(segmentsx->next1)
622     {
623     index_t index=IndexSegmentX(segmentsx,segmentx);
624    
625 amb 952 if(segmentsx->next1[index]==NO_SEGMENT)
626 amb 949 return(NULL);
627    
628     segmentx=LookupSegmentX(segmentsx,segmentsx->next1[index],position);
629    
630     return(segmentx);
631     }
632     else
633     {
634 amb 643 #if SLIM
635 amb 949 index_t index=IndexSegmentX(segmentsx,segmentx);
636     index++;
637 amb 544
638 amb 949 if(index>=segmentsx->number)
639     return(NULL);
640    
641     segmentx=LookupSegmentX(segmentsx,index,position);
642 amb 643 #else
643 amb 949 segmentx++;
644    
645     if(IndexSegmentX(segmentsx,segmentx)>=segmentsx->number)
646     return(NULL);
647     #endif
648    
649     if(segmentx->node1!=nodeindex)
650     return(NULL);
651    
652 amb 643 return(segmentx);
653 amb 949 }
654 amb 643 }
655 amb 229 else
656 amb 643 {
657     if(segmentx->next2==NO_SEGMENT)
658     return(NULL);
659 amb 949
660     return(LookupSegmentX(segmentsx,segmentx->next2,position));
661 amb 643 }
662 amb 110 }
663    
664    
665     /*++++++++++++++++++++++++++++++++++++++
666 amb 680 Remove bad segments (duplicated, zero length or with missing nodes).
667 amb 110
668 amb 1136 SegmentsX *segmentsx The set of segments to modify.
669    
670 amb 681 NodesX *nodesx The set of nodes to use.
671 amb 195
672 amb 1140 WaysX *waysx The set of ways to use.
673    
674 amb 1136 int preserve If set to 1 then keep the old data file otherwise delete it.
675 amb 110 ++++++++++++++++++++++++++++++++++++++*/
676    
677 amb 1140 void RemoveBadSegments(SegmentsX *segmentsx,NodesX *nodesx,WaysX *waysx,int preserve)
678 amb 110 {
679 amb 1155 index_t noway=0,loop=0,nonode=0,duplicate=0,good=0,total=0;
680     node_t prevnode1=NO_NODE_ID,prevnode2=NO_NODE_ID;
681     distance_t prevdist=0;
682 amb 275 SegmentX segmentx;
683     int fd;
684 amb 110
685 amb 275 /* Print the start message */
686    
687 amb 1155 printf_first("Checking Segments: Segments=0 Loop=0 No-Way=0 No-Node=0 Duplicate=0");
688 amb 227
689 amb 1100 /* Allocate the node usage bitmask */
690 amb 643
691 amb 950 segmentsx->usednode=AllocBitMask(nodesx->number);
692 amb 643
693 amb 950 assert(segmentsx->usednode); /* Check AllocBitMask() worked */
694 amb 643
695 amb 555 /* Re-open the file read-only and a new file writeable */
696 amb 275
697 amb 1120 segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
698 amb 555
699 amb 1136 if(preserve)
700     RenameFile(segmentsx->filename_tmp,segmentsx->filename);
701     else
702     DeleteFile(segmentsx->filename_tmp);
703 amb 275
704 amb 1120 fd=OpenFileNew(segmentsx->filename_tmp);
705 amb 275
706 amb 555 /* Modify the on-disk image */
707    
708 amb 275 while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
709 amb 110 {
710 amb 643 index_t index1=IndexNodeX(nodesx,segmentx.node1);
711     index_t index2=IndexNodeX(nodesx,segmentx.node2);
712 amb 1140 index_t indexw=IndexWayX(waysx,segmentx.way);
713 amb 643
714 amb 1140 if(indexw==NO_WAY)
715 amb 812 {
716 amb 1140 logerror("Segment belongs to way %"Pway_t" but it doesn't exist.\n",segmentx.way);
717    
718     noway++;
719     }
720     else if(segmentx.node1==segmentx.node2)
721     {
722 amb 812 logerror("Segment connects node %"Pnode_t" to itself.\n",segmentx.node1);
723    
724 amb 257 loop++;
725 amb 812 }
726 amb 643 else if(index1==NO_NODE || index2==NO_NODE)
727 amb 812 {
728     if(index1==NO_NODE && index2==NO_NODE)
729     logerror("Segment connects nodes %"Pnode_t" and %"Pnode_t" but neither exist.\n",segmentx.node1,segmentx.node2);
730    
731     if(index1==NO_NODE && index2!=NO_NODE)
732     logerror("Segment connects nodes %"Pnode_t" and %"Pnode_t" but the first one does not exist.\n",segmentx.node1,segmentx.node2);
733    
734     if(index1!=NO_NODE && index2==NO_NODE)
735     logerror("Segment connects nodes %"Pnode_t" and %"Pnode_t" but the second one does not exist.\n",segmentx.node1,segmentx.node2);
736    
737 amb 761 nonode++;
738 amb 812 }
739 amb 1155 else if(prevnode1==segmentx.node1 && prevnode2==segmentx.node2)
740     {
741     if(!(prevdist&SEGMENT_AREA) && !(segmentx.distance&SEGMENT_AREA))
742     logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated.\n",segmentx.node1,segmentx.node2);
743    
744     if(!(prevdist&SEGMENT_AREA) && (segmentx.distance&SEGMENT_AREA))
745     logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (discarded the area).\n",segmentx.node1,segmentx.node2);
746    
747     if((prevdist&SEGMENT_AREA) && !(segmentx.distance&SEGMENT_AREA))
748     logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (discarded the non-area).\n",segmentx.node1,segmentx.node2);
749    
750     if((prevdist&SEGMENT_AREA) && (segmentx.distance&SEGMENT_AREA))
751     logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (both are areas).\n",segmentx.node1,segmentx.node2);
752    
753     duplicate++;
754     }
755 amb 275 else
756 amb 257 {
757 amb 275 WriteFile(fd,&segmentx,sizeof(SegmentX));
758    
759 amb 655 SetBit(segmentsx->usednode,index1);
760     SetBit(segmentsx->usednode,index2);
761 amb 643
762 amb 1155 prevnode1=segmentx.node1;
763     prevnode2=segmentx.node2;
764     prevdist=DISTANCE(segmentx.distance);
765    
766 amb 275 good++;
767 amb 110 }
768    
769 amb 275 total++;
770 amb 256
771 amb 275 if(!(total%10000))
772 amb 1155 printf_middle("Checking Segments: Segments=%"Pindex_t" Loop=%"Pindex_t" No-Way=%"Pindex_t" No-Node=%"Pindex_t" Duplicate=%"Pindex_t,total,loop,noway,nonode,duplicate);
773 amb 110 }
774    
775 amb 555 segmentsx->number=good;
776 amb 275
777 amb 555 /* Close the files */
778    
779 amb 612 segmentsx->fd=CloseFile(segmentsx->fd);
780 amb 275 CloseFile(fd);
781    
782     /* Print the final message */
783    
784 amb 1155 printf_last("Checked Segments: Segments=%"Pindex_t" Loop=%"Pindex_t" No-Way=%"Pindex_t" No-Node=%"Pindex_t" Duplicate=%"Pindex_t,total,loop,noway,nonode,duplicate);
785 amb 110 }
786    
787    
788     /*++++++++++++++++++++++++++++++++++++++
789 amb 285 Measure the segments and replace node/way ids with indexes.
790 amb 110
791 amb 681 SegmentsX *segmentsx The set of segments to process.
792 amb 110
793 amb 680 NodesX *nodesx The set of nodes to use.
794 amb 279
795 amb 680 WaysX *waysx The set of ways to use.
796 amb 110 ++++++++++++++++++++++++++++++++++++++*/
797    
798 amb 681 void MeasureSegments(SegmentsX *segmentsx,NodesX *nodesx,WaysX *waysx)
799 amb 110 {
800 amb 279 index_t index=0;
801 amb 643 int fd;
802 amb 256 SegmentX segmentx;
803 amb 110
804 amb 275 /* Print the start message */
805    
806 amb 519 printf_first("Measuring Segments: Segments=0");
807 amb 227
808 amb 555 /* Map into memory / open the file */
809 amb 257
810 amb 452 #if !SLIM
811 amb 1120 nodesx->data=MapFile(nodesx->filename_tmp);
812 amb 555 #else
813 amb 1120 nodesx->fd=ReOpenFile(nodesx->filename_tmp);
814 amb 452 #endif
815 amb 258
816 amb 1100 /* Allocate the way usage bitmask */
817    
818     segmentsx->usedway=AllocBitMask(waysx->number);
819    
820     assert(segmentsx->usedway); /* Check AllocBitMask() worked */
821    
822 amb 555 /* Re-open the file read-only and a new file writeable */
823 amb 275
824 amb 1120 segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
825 amb 555
826 amb 1120 DeleteFile(segmentsx->filename_tmp);
827 amb 256
828 amb 1120 fd=OpenFileNew(segmentsx->filename_tmp);
829 amb 256
830 amb 555 /* Modify the on-disk image */
831    
832 amb 256 while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
833 amb 110 {
834 amb 279 index_t node1=IndexNodeX(nodesx,segmentx.node1);
835     index_t node2=IndexNodeX(nodesx,segmentx.node2);
836     index_t way =IndexWayX (waysx ,segmentx.way);
837 amb 110
838 amb 279 NodeX *nodex1=LookupNodeX(nodesx,node1,1);
839     NodeX *nodex2=LookupNodeX(nodesx,node2,2);
840    
841     /* Replace the node and way ids with their indexes */
842    
843     segmentx.node1=node1;
844     segmentx.node2=node2;
845     segmentx.way =way;
846    
847 amb 1100 SetBit(segmentsx->usedway,segmentx.way);
848    
849 amb 949 /* Set the distance but preserve the other flags */
850 amb 275
851 amb 1137 segmentx.distance=DISTANCE(DistanceX(nodex1,nodex2))|DISTFLAG(segmentx.distance);
852 amb 275
853 amb 279 /* Write the modified segment */
854    
855 amb 275 WriteFile(fd,&segmentx,sizeof(SegmentX));
856    
857 amb 279 index++;
858 amb 275
859 amb 279 if(!(index%10000))
860 amb 790 printf_middle("Measuring Segments: Segments=%"Pindex_t,index);
861 amb 275 }
862 amb 110
863 amb 555 /* Close the files */
864 amb 257
865 amb 612 segmentsx->fd=CloseFile(segmentsx->fd);
866 amb 275 CloseFile(fd);
867    
868 amb 280 /* Free the other now-unneeded indexes */
869 amb 279
870     free(nodesx->idata);
871     nodesx->idata=NULL;
872    
873     free(waysx->idata);
874     waysx->idata=NULL;
875    
876 amb 555 /* Unmap from memory / close the file */
877 amb 275
878 amb 452 #if !SLIM
879 amb 1122 nodesx->data=UnmapFile(nodesx->data);
880 amb 555 #else
881 amb 612 nodesx->fd=CloseFile(nodesx->fd);
882 amb 452 #endif
883 amb 275
884     /* Print the final message */
885    
886 amb 790 printf_last("Measured Segments: Segments=%"Pindex_t,segmentsx->number);
887 amb 275 }
888    
889    
890     /*++++++++++++++++++++++++++++++++++++++
891 amb 1132 Remove the duplicate super-segments.
892 amb 110
893 amb 1132 SegmentsX *segmentsx The set of super-segments to modify.
894 amb 110
895 amb 680 WaysX *waysx The set of ways to use.
896 amb 110 ++++++++++++++++++++++++++++++++++++++*/
897    
898 amb 1132 void DeduplicateSuperSegments(SegmentsX *segmentsx,WaysX *waysx)
899 amb 110 {
900 amb 1132 int fd;
901     index_t xnumber;
902 amb 110
903 amb 275 /* Print the start message */
904    
905 amb 1132 printf_first("Sorting and Deduplicating Super-Segments");
906 amb 227
907 amb 555 /* Map into memory / open the file */
908 amb 256
909 amb 452 #if !SLIM
910 amb 1120 waysx->data=MapFile(waysx->filename_tmp);
911 amb 555 #else
912 amb 1120 waysx->fd=ReOpenFile(waysx->filename_tmp);
913 amb 452 #endif
914 amb 275
915 amb 555 /* Re-open the file read-only and a new file writeable */
916 amb 275
917 amb 1120 segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
918 amb 555
919 amb 1120 DeleteFile(segmentsx->filename_tmp);
920 amb 275
921 amb 1120 fd=OpenFileNew(segmentsx->filename_tmp);
922 amb 275
923 amb 1132 /* Sort by node indexes */
924 amb 555
925 amb 1132 xnumber=segmentsx->number;
926 amb 256
927 amb 1132 sortsegmentsx=segmentsx;
928     sortwaysx=waysx;
929 amb 110
930 amb 1132 segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),NULL,
931     (int (*)(const void*,const void*))sort_by_id,
932     (int (*)(void*,index_t))deduplicate_super);
933 amb 264
934 amb 555 /* Close the files */
935    
936 amb 612 segmentsx->fd=CloseFile(segmentsx->fd);
937 amb 275 CloseFile(fd);
938    
939 amb 555 /* Unmap from memory / close the file */
940 amb 275
941 amb 452 #if !SLIM
942 amb 1122 waysx->data=UnmapFile(waysx->data);
943 amb 555 #else
944 amb 612 waysx->fd=CloseFile(waysx->fd);
945 amb 452 #endif
946 amb 275
947     /* Print the final message */
948    
949 amb 1132 printf_last("Sorted and Deduplicated Super-Segments: Super-Segments=%"Pindex_t" Duplicate=%"Pindex_t,xnumber,xnumber-segmentsx->number);
950 amb 110 }
951    
952    
953     /*++++++++++++++++++++++++++++++++++++++
954 amb 1132 De-duplicate super-segments.
955    
956     int deduplicate_super Return 1 if the value is to be kept, otherwise 0.
957    
958     SegmentX *segmentx The extended super-segment.
959    
960     index_t index The number of sorted super-segments that have already been written to the output file.
961     ++++++++++++++++++++++++++++++++++++++*/
962    
963     static int deduplicate_super(SegmentX *segmentx,index_t index)
964     {
965     static int nprev=0;
966     static index_t prevnode1=NO_NODE,prevnode2=NO_NODE;
967     static SegmentX prevsegx[MAX_SEG_PER_NODE];
968     static Way prevway[MAX_SEG_PER_NODE];
969    
970     WayX *wayx=LookupWayX(sortwaysx,segmentx->way,1);
971     int isduplicate=0;
972    
973     if(index==0 || segmentx->node1!=prevnode1 || segmentx->node2!=prevnode2)
974     {
975     nprev=1;
976     prevnode1=segmentx->node1;
977     prevnode2=segmentx->node2;
978     prevsegx[0]=*segmentx;
979     prevway[0] =wayx->way;
980     }
981     else
982     {
983     int offset;
984    
985     for(offset=0;offset<nprev;offset++)
986     {
987     if(DISTFLAG(segmentx->distance)==DISTFLAG(prevsegx[offset].distance))
988     if(!WaysCompare(&prevway[offset],&wayx->way))
989     {
990     isduplicate=1;
991     break;
992     }
993     }
994    
995     if(isduplicate)
996     {
997     nprev--;
998    
999     for(;offset<nprev;offset++)
1000     {
1001     prevsegx[offset]=prevsegx[offset+1];
1002     prevway[offset] =prevway[offset+1];
1003     }
1004     }
1005     else
1006     {
1007     assert(nprev<MAX_SEG_PER_NODE); /* Only a limited amount of information stored. */
1008    
1009     prevsegx[nprev]=*segmentx;
1010     prevway[nprev] =wayx->way;
1011    
1012     nprev++;
1013     }
1014     }
1015    
1016     return(!isduplicate);
1017     }
1018    
1019    
1020     /*++++++++++++++++++++++++++++++++++++++
1021 amb 680 Index the segments by creating the firstnode index and filling in the segment next2 parameter.
1022 amb 209
1023 amb 681 SegmentsX *segmentsx The set of segments to modify.
1024 amb 209
1025 amb 1100 NodesX *nodesx The set of nodes to use.
1026    
1027     WaysX *waysx The set of ways to use.
1028 amb 209 ++++++++++++++++++++++++++++++++++++++*/
1029    
1030 amb 1100 void IndexSegments(SegmentsX *segmentsx,NodesX *nodesx,WaysX *waysx)
1031 amb 209 {
1032 amb 780 index_t index,i;
1033 amb 209
1034 amb 660 if(segmentsx->number==0)
1035     return;
1036    
1037 amb 275 /* Print the start message */
1038    
1039 amb 643 printf_first("Indexing Segments: Segments=0");
1040 amb 227
1041 amb 643 /* Allocate the array of indexes */
1042    
1043 amb 1102 if(segmentsx->firstnode)
1044     free(segmentsx->firstnode);
1045 amb 643
1046 amb 1102 segmentsx->firstnode=(index_t*)malloc(nodesx->number*sizeof(index_t));
1047 amb 643
1048 amb 1102 assert(segmentsx->firstnode); /* Check malloc() worked */
1049    
1050 amb 643 for(i=0;i<nodesx->number;i++)
1051     segmentsx->firstnode[i]=NO_SEGMENT;
1052    
1053 amb 555 /* Map into memory / open the files */
1054 amb 209
1055 amb 452 #if !SLIM
1056 amb 1120 segmentsx->data=MapFileWriteable(segmentsx->filename_tmp);
1057 amb 555 #else
1058 amb 1120 segmentsx->fd=ReOpenFileWriteable(segmentsx->filename_tmp);
1059 amb 452 #endif
1060 amb 275
1061 amb 643 /* Read through the segments in reverse order */
1062 amb 280
1063 amb 643 for(index=segmentsx->number-1;index!=NO_SEGMENT;index--)
1064 amb 209 {
1065 amb 643 SegmentX *segmentx=LookupSegmentX(segmentsx,index,1);
1066 amb 209
1067 amb 1098 if(nodesx->pdata)
1068     {
1069     segmentx->node1=nodesx->pdata[segmentx->node1];
1070     segmentx->node2=nodesx->pdata[segmentx->node2];
1071     }
1072    
1073 amb 1100 if(waysx->cdata)
1074     segmentx->way=waysx->cdata[segmentx->way];
1075    
1076 amb 674 segmentx->next2=segmentsx->firstnode[segmentx->node2];
1077 amb 209
1078 amb 942 PutBackSegmentX(segmentsx,segmentx);
1079 amb 448
1080 amb 643 segmentsx->firstnode[segmentx->node1]=index;
1081     segmentsx->firstnode[segmentx->node2]=index;
1082 amb 558
1083 amb 643 if(!(index%10000))
1084 amb 790 printf_middle("Indexing Segments: Segments=%"Pindex_t,segmentsx->number-index);
1085 amb 209 }
1086    
1087 amb 555 /* Unmap from memory / close the files */
1088 amb 275
1089 amb 452 #if !SLIM
1090 amb 1122 segmentsx->data=UnmapFile(segmentsx->data);
1091 amb 555 #else
1092 amb 643 segmentsx->fd=CloseFile(segmentsx->fd);
1093 amb 452 #endif
1094 amb 275
1095 amb 1100 /* Free the memory */
1096    
1097     if(nodesx->pdata)
1098     {
1099     free(nodesx->pdata);
1100     nodesx->pdata=NULL;
1101     }
1102    
1103     if(waysx->cdata)
1104     {
1105     free(waysx->cdata);
1106     waysx->cdata=NULL;
1107     }
1108    
1109 amb 275 /* Print the final message */
1110    
1111 amb 790 printf_last("Indexed Segments: Segments=%"Pindex_t,segmentsx->number);
1112 amb 209 }
1113    
1114    
1115     /*++++++++++++++++++++++++++++++++++++++
1116 amb 285 Save the segment list to a file.
1117    
1118 amb 681 SegmentsX *segmentsx The set of segments to save.
1119 amb 285
1120     const char *filename The name of the file to save.
1121     ++++++++++++++++++++++++++++++++++++++*/
1122    
1123 amb 681 void SaveSegmentList(SegmentsX *segmentsx,const char *filename)
1124 amb 285 {
1125     index_t i;
1126     int fd;
1127 amb 500 SegmentsFile segmentsfile={0};
1128 amb 780 index_t super_number=0,normal_number=0;
1129 amb 285
1130     /* Print the start message */
1131    
1132 amb 519 printf_first("Writing Segments: Segments=0");
1133 amb 285
1134 amb 558 /* Re-open the file */
1135    
1136 amb 1120 segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
1137 amb 558
1138 amb 461 /* Write out the segments data */
1139 amb 285
1140 amb 502 fd=OpenFileNew(filename);
1141 amb 461
1142     SeekFile(fd,sizeof(SegmentsFile));
1143    
1144 amb 285 for(i=0;i<segmentsx->number;i++)
1145     {
1146 amb 643 SegmentX segmentx;
1147 amb 944 Segment segment={0};
1148 amb 448
1149 amb 643 ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX));
1150 amb 558
1151 amb 643 segment.node1 =segmentx.node1;
1152     segment.node2 =segmentx.node2;
1153     segment.next2 =segmentx.next2;
1154     segment.way =segmentx.way;
1155     segment.distance=segmentx.distance;
1156    
1157 amb 558 if(IsSuperSegment(&segment))
1158 amb 285 super_number++;
1159 amb 558 if(IsNormalSegment(&segment))
1160 amb 285 normal_number++;
1161    
1162 amb 558 WriteFile(fd,&segment,sizeof(Segment));
1163 amb 448
1164 amb 285 if(!((i+1)%10000))
1165 amb 790 printf_middle("Writing Segments: Segments=%"Pindex_t,i+1);
1166 amb 285 }
1167    
1168 amb 461 /* Write out the header structure */
1169    
1170     segmentsfile.number=segmentsx->number;
1171     segmentsfile.snumber=super_number;
1172     segmentsfile.nnumber=normal_number;
1173    
1174     SeekFile(fd,0);
1175     WriteFile(fd,&segmentsfile,sizeof(SegmentsFile));
1176    
1177 amb 285 CloseFile(fd);
1178    
1179 amb 558 /* Close the file */
1180    
1181 amb 643 segmentsx->fd=CloseFile(segmentsx->fd);
1182 amb 558
1183 amb 285 /* Print the final message */
1184    
1185 amb 790 printf_last("Wrote Segments: Segments=%"Pindex_t,segmentsx->number);
1186 amb 285 }
1187    
1188    
1189     /*++++++++++++++++++++++++++++++++++++++
1190 amb 110 Calculate the distance between two nodes.
1191    
1192     distance_t DistanceX Returns the distance between the extended nodes.
1193    
1194     NodeX *nodex1 The starting node.
1195    
1196     NodeX *nodex2 The end node.
1197     ++++++++++++++++++++++++++++++++++++++*/
1198    
1199 amb 228 static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
1200 amb 110 {
1201 amb 223 double dlon = latlong_to_radians(nodex1->longitude) - latlong_to_radians(nodex2->longitude);
1202     double dlat = latlong_to_radians(nodex1->latitude) - latlong_to_radians(nodex2->latitude);
1203     double lat1 = latlong_to_radians(nodex1->latitude);
1204     double lat2 = latlong_to_radians(nodex2->latitude);
1205 amb 110
1206 amb 219 double a1,a2,a,sa,c,d;
1207 amb 110
1208     if(dlon==0 && dlat==0)
1209     return 0;
1210    
1211 amb 219 a1 = sin (dlat / 2);
1212     a2 = sin (dlon / 2);
1213     a = (a1 * a1) + cos (lat1) * cos (lat2) * a2 * a2;
1214     sa = sqrt (a);
1215 amb 110 if (sa <= 1.0)
1216 amb 219 {c = 2 * asin (sa);}
1217 amb 110 else
1218 amb 219 {c = 2 * asin (1.0);}
1219 amb 110 d = 6378.137 * c;
1220    
1221     return km_to_distance(d);
1222     }

Properties

Name Value
cvs:description Extended segments functions.