Routino SVN Repository Browser

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

ViewVC logotype

Contents of /trunk/src/segmentsx.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1173 - (show annotations) (download) (as text)
Tue Nov 27 19:51:08 2012 UTC (12 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 31645 byte(s)
Log an error about duplicated segments within a way while parsing the OSM
instead of later (will have been removed by de-duplication code before tested
later in most cases).

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

Properties

Name Value
cvs:description Extended segments functions.