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 1784 - (hide annotations) (download) (as text)
Sat Aug 15 13:08:37 2015 UTC (9 years, 7 months ago) by amb
File MIME type: text/x-csrc
File size: 25966 byte(s)
Merge libroutino branch back into the trunk.

1 amb 110 /***************************************
2     Extended Segment data type functions.
3 amb 151
4     Part of the Routino routing software.
5 amb 110 ******************/ /******************
6 amb 1695 This file Copyright 2008-2015 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 <math.h>
24     #include <stdlib.h>
25 amb 955 #include <string.h>
26 amb 110
27     #include "types.h"
28 amb 228 #include "segments.h"
29     #include "ways.h"
30 amb 110
31 amb 955 #include "typesx.h"
32 amb 449 #include "nodesx.h"
33     #include "segmentsx.h"
34     #include "waysx.h"
35 amb 110
36 amb 449 #include "files.h"
37 amb 519 #include "logging.h"
38 amb 532 #include "sorting.h"
39 amb 449
40    
41 amb 680 /* Global variables */
42 amb 110
43 amb 289 /*+ The command line '--tmpdir' option or its default value. +*/
44 amb 284 extern char *option_tmpdirname;
45 amb 110
46 amb 1100 /* Local variables */
47    
48 amb 1784 /*+ Temporary file-local variables for use by the sort functions (re-initialised for each sort). +*/
49 amb 1427 static NodesX *sortnodesx;
50 amb 1100 static SegmentsX *sortsegmentsx;
51 amb 1132 static WaysX *sortwaysx;
52 amb 1100
53 amb 680 /* Local functions */
54 amb 110
55 amb 275 static int sort_by_id(SegmentX *a,SegmentX *b);
56 amb 1160
57 amb 949 static int delete_pruned(SegmentX *segmentx,index_t index);
58 amb 1160
59 amb 1132 static int deduplicate_super(SegmentX *segmentx,index_t index);
60 amb 275
61 amb 1427 static int geographically_index(SegmentX *segmentx,index_t index);
62    
63 amb 1168 static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2);
64 amb 110
65    
66     /*++++++++++++++++++++++++++++++++++++++
67 amb 326 Allocate a new segment list (create a new file or open an existing one).
68 amb 110
69     SegmentsX *NewSegmentList Returns the segment list.
70     ++++++++++++++++++++++++++++++++++++++*/
71    
72 amb 1339 SegmentsX *NewSegmentList(void)
73 amb 110 {
74     SegmentsX *segmentsx;
75    
76 amb 213 segmentsx=(SegmentsX*)calloc(1,sizeof(SegmentsX));
77 amb 110
78 amb 1166 logassert(segmentsx,"Failed to allocate memory (try using slim mode?)"); /* Check calloc() worked */
79 amb 243
80 amb 1695 segmentsx->filename_tmp=(char*)malloc(strlen(option_tmpdirname)+40); /* allow %p to be up to 20 bytes */
81 amb 216
82 amb 1339 sprintf(segmentsx->filename_tmp,"%s/segmentsx.%p.tmp",option_tmpdirname,(void*)segmentsx);
83 amb 256
84 amb 1402 segmentsx->fd=OpenFileBufferedNew(segmentsx->filename_tmp);
85 amb 326
86 amb 1297 #if SLIM
87     segmentsx->cache=NewSegmentXCache();
88 amb 1598 log_malloc(segmentsx->cache,sizeof(*segmentsx->cache));
89 amb 1297 #endif
90    
91 amb 110 return(segmentsx);
92     }
93    
94    
95     /*++++++++++++++++++++++++++++++++++++++
96 amb 226 Free a segment list.
97 amb 110
98 amb 681 SegmentsX *segmentsx The set of segments to be freed.
99 amb 110 ++++++++++++++++++++++++++++++++++++++*/
100    
101 amb 1339 void FreeSegmentList(SegmentsX *segmentsx)
102 amb 110 {
103 amb 1339 DeleteFile(segmentsx->filename_tmp);
104 amb 1120
105     free(segmentsx->filename_tmp);
106 amb 256
107 amb 1593 if(segmentsx->usedway)
108 amb 1598 {
109     log_free(segmentsx->usedway);
110 amb 1593 free(segmentsx->usedway);
111 amb 1598 }
112 amb 1593
113 amb 949 if(segmentsx->firstnode)
114 amb 1598 {
115     log_free(segmentsx->firstnode);
116 amb 949 free(segmentsx->firstnode);
117 amb 1598 }
118 amb 949
119 amb 1431 if(segmentsx->next1)
120 amb 1598 {
121     log_free(segmentsx->next1);
122 amb 1431 free(segmentsx->next1);
123 amb 1598 }
124 amb 1431
125 amb 1297 #if SLIM
126 amb 1598 log_free(segmentsx->cache);
127 amb 1297 DeleteSegmentXCache(segmentsx->cache);
128     #endif
129    
130 amb 110 free(segmentsx);
131     }
132    
133    
134     /*++++++++++++++++++++++++++++++++++++++
135 amb 493 Append a single segment to an unsorted segment list.
136 amb 110
137 amb 681 SegmentsX *segmentsx The set of segments to modify.
138 amb 110
139 amb 1349 index_t way The index of the way that the segment belongs to.
140 amb 285
141 amb 1349 index_t node1 The index of the first node in the segment.
142 amb 285
143 amb 1349 index_t node2 The index of the second node in the segment.
144 amb 285
145 amb 1168 distance_t distance The distance between the nodes (or just the flags).
146 amb 110 ++++++++++++++++++++++++++++++++++++++*/
147    
148 amb 1349 void AppendSegmentList(SegmentsX *segmentsx,index_t way,index_t node1,index_t node2,distance_t distance)
149 amb 110 {
150 amb 285 SegmentX segmentx;
151 amb 110
152 amb 643 if(node1>node2)
153     {
154 amb 1349 index_t temp;
155 amb 643
156     temp=node1;
157     node1=node2;
158     node2=temp;
159    
160 amb 1168 if(distance&(ONEWAY_2TO1|ONEWAY_1TO2))
161     distance^=ONEWAY_2TO1|ONEWAY_1TO2;
162 amb 643 }
163    
164 amb 285 segmentx.node1=node1;
165     segmentx.node2=node2;
166 amb 643 segmentx.next2=NO_SEGMENT;
167 amb 285 segmentx.way=way;
168 amb 1168 segmentx.distance=distance;
169 amb 110
170 amb 1402 WriteFileBuffered(segmentsx->fd,&segmentx,sizeof(SegmentX));
171 amb 281
172 amb 650 segmentsx->number++;
173 amb 466
174 amb 1166 logassert(segmentsx->number<SEGMENT_FAKE,"Too many segments (change index_t to 64-bits?)"); /* SEGMENT_FAKE marks the high-water mark for real segments. */
175 amb 285 }
176 amb 227
177 amb 281
178 amb 285 /*++++++++++++++++++++++++++++++++++++++
179 amb 1120 Finish appending segments and change the filename over.
180    
181     SegmentsX *segmentsx The segments that have been appended.
182     ++++++++++++++++++++++++++++++++++++++*/
183    
184 amb 1151 void FinishSegmentList(SegmentsX *segmentsx)
185 amb 1120 {
186 amb 1136 if(segmentsx->fd!=-1)
187 amb 1402 segmentsx->fd=CloseFileBuffered(segmentsx->fd);
188 amb 1120 }
189    
190    
191     /*++++++++++++++++++++++++++++++++++++++
192 amb 1160 Find the first extended segment with a particular starting node index.
193    
194     SegmentX *FirstSegmentX Returns a pointer to the first extended segment with the specified id.
195    
196     SegmentsX *segmentsx The set of segments to use.
197    
198     index_t nodeindex The node index to look for.
199    
200     int position A flag to pass through.
201     ++++++++++++++++++++++++++++++++++++++*/
202    
203     SegmentX *FirstSegmentX(SegmentsX *segmentsx,index_t nodeindex,int position)
204     {
205     index_t index=segmentsx->firstnode[nodeindex];
206     SegmentX *segmentx;
207    
208     if(index==NO_SEGMENT)
209     return(NULL);
210    
211     segmentx=LookupSegmentX(segmentsx,index,position);
212    
213     return(segmentx);
214     }
215    
216    
217     /*++++++++++++++++++++++++++++++++++++++
218     Find the next segment with a particular starting node index.
219    
220     SegmentX *NextSegmentX Returns a pointer to the next segment with the same id.
221    
222     SegmentsX *segmentsx The set of segments to use.
223    
224     SegmentX *segmentx The current segment.
225    
226     index_t nodeindex The node index.
227     ++++++++++++++++++++++++++++++++++++++*/
228    
229     SegmentX *NextSegmentX(SegmentsX *segmentsx,SegmentX *segmentx,index_t nodeindex)
230     {
231     #if SLIM
232     int position=1+(segmentx-&segmentsx->cached[0]);
233     #endif
234    
235     if(segmentx->node1==nodeindex)
236     {
237 amb 1431 if(segmentsx->next1)
238     {
239     index_t index=IndexSegmentX(segmentsx,segmentx);
240 amb 1160
241 amb 1431 if(segmentsx->next1[index]==NO_SEGMENT)
242     return(NULL);
243    
244     segmentx=LookupSegmentX(segmentsx,segmentsx->next1[index],position);
245 amb 1448
246     return(segmentx);
247 amb 1431 }
248     else
249     {
250     #if SLIM
251     index_t index=IndexSegmentX(segmentsx,segmentx);
252     index++;
253    
254     if(index>=segmentsx->number)
255     return(NULL);
256    
257     segmentx=LookupSegmentX(segmentsx,index,position);
258     #else
259     segmentx++;
260    
261     if(IndexSegmentX(segmentsx,segmentx)>=segmentsx->number)
262     return(NULL);
263     #endif
264    
265     if(segmentx->node1!=nodeindex)
266     return(NULL);
267 amb 1448
268     return(segmentx);
269 amb 1432 }
270 amb 1160 }
271     else
272     {
273 amb 1448 if(segmentx->next2==NO_SEGMENT)
274     return(NULL);
275 amb 1160
276 amb 1448 return(LookupSegmentX(segmentsx,segmentx->next2,position));
277 amb 1160 }
278     }
279    
280    
281     /*++++++++++++++++++++++++++++++++++++++
282 amb 1354 Sort the segment list.
283 amb 1100
284 amb 1354 SegmentsX *segmentsx The set of segments to sort.
285 amb 285 ++++++++++++++++++++++++++++++++++++++*/
286 amb 110
287 amb 1160 void SortSegmentList(SegmentsX *segmentsx)
288 amb 285 {
289     int fd;
290 amb 243
291 amb 285 /* Print the start message */
292 amb 232
293 amb 1160 printf_first("Sorting Segments");
294 amb 110
295 amb 555 /* Re-open the file read-only and a new file writeable */
296    
297 amb 1699 fd=ReplaceFileBuffered(segmentsx->filename_tmp,&segmentsx->fd);
298 amb 110
299 amb 285 /* Sort by node indexes */
300 amb 132
301 amb 1160 segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),NULL,
302 amb 1132 (int (*)(const void*,const void*))sort_by_id,
303 amb 1354 NULL);
304 amb 1100
305 amb 555 /* Close the files */
306 amb 285
307 amb 1409 segmentsx->fd=CloseFileBuffered(segmentsx->fd);
308     CloseFileBuffered(fd);
309 amb 281
310     /* Print the final message */
311    
312 amb 1355 printf_last("Sorted Segments: Segments=%"Pindex_t,segmentsx->number);
313 amb 110 }
314    
315    
316     /*++++++++++++++++++++++++++++++++++++++
317 amb 680 Sort the segments into id order, first by node1 then by node2, finally by distance.
318 amb 110
319 amb 285 int sort_by_id Returns the comparison of the node fields.
320 amb 110
321 amb 285 SegmentX *a The first segment.
322 amb 110
323 amb 285 SegmentX *b The second segment.
324 amb 256 ++++++++++++++++++++++++++++++++++++++*/
325    
326 amb 285 static int sort_by_id(SegmentX *a,SegmentX *b)
327 amb 256 {
328 amb 1349 index_t a_id1=a->node1;
329     index_t b_id1=b->node1;
330 amb 256
331 amb 285 if(a_id1<b_id1)
332     return(-1);
333     else if(a_id1>b_id1)
334     return(1);
335     else /* if(a_id1==b_id1) */
336 amb 256 {
337 amb 1349 index_t a_id2=a->node2;
338     index_t b_id2=b->node2;
339 amb 256
340 amb 285 if(a_id2<b_id2)
341     return(-1);
342     else if(a_id2>b_id2)
343     return(1);
344     else
345     {
346 amb 1168 distance_t a_distance=DISTANCE(a->distance);
347     distance_t b_distance=DISTANCE(b->distance);
348 amb 256
349 amb 1168 if(a_distance<b_distance)
350 amb 285 return(-1);
351 amb 1168 else if(a_distance>b_distance)
352 amb 285 return(1);
353     else
354 amb 1153 {
355 amb 1168 distance_t a_distflag=DISTFLAG(a->distance);
356     distance_t b_distflag=DISTFLAG(b->distance);
357 amb 1153
358 amb 1168 if(a_distflag<b_distflag)
359 amb 1153 return(-1);
360 amb 1168 else if(a_distflag>b_distflag)
361 amb 1153 return(1);
362     else
363     return(FILESORT_PRESERVE_ORDER(a,b)); /* preserve order */
364     }
365 amb 285 }
366 amb 256 }
367     }
368    
369    
370     /*++++++++++++++++++++++++++++++++++++++
371 amb 1351 Process segments (non-trivial duplicates).
372 amb 110
373 amb 1136 SegmentsX *segmentsx The set of segments to modify.
374    
375 amb 681 NodesX *nodesx The set of nodes to use.
376 amb 195
377 amb 1140 WaysX *waysx The set of ways to use.
378 amb 110 ++++++++++++++++++++++++++++++++++++++*/
379    
380 amb 1351 void ProcessSegments(SegmentsX *segmentsx,NodesX *nodesx,WaysX *waysx)
381 amb 110 {
382 amb 1349 index_t duplicate=0,good=0,total=0;
383     index_t prevnode1=NO_NODE,prevnode2=NO_NODE;
384     index_t prevway=NO_WAY;
385 amb 1168 distance_t prevdist=0;
386 amb 275 SegmentX segmentx;
387     int fd;
388 amb 110
389 amb 275 /* Print the start message */
390    
391 amb 1351 printf_first("Processing Segments: Segments=0 Duplicates=0");
392 amb 227
393 amb 1349 /* Map into memory / open the file */
394    
395     #if !SLIM
396     nodesx->data=MapFile(nodesx->filename_tmp);
397     #else
398 amb 1414 nodesx->fd=SlimMapFile(nodesx->filename_tmp);
399 amb 1349
400     InvalidateNodeXCache(nodesx->cache);
401     #endif
402    
403 amb 1351 /* Allocate the way usage bitmask */
404    
405     segmentsx->usedway=AllocBitMask(waysx->number);
406 amb 1598 log_malloc(segmentsx->usedway,LengthBitMask(waysx->number)*sizeof(BitMask));
407 amb 1351
408     logassert(segmentsx->usedway,"Failed to allocate memory (try using slim mode?)"); /* Check AllocBitMask() worked */
409    
410 amb 555 /* Re-open the file read-only and a new file writeable */
411 amb 275
412 amb 1699 fd=ReplaceFileBuffered(segmentsx->filename_tmp,&segmentsx->fd);
413 amb 555
414     /* Modify the on-disk image */
415    
416 amb 1408 while(!ReadFileBuffered(segmentsx->fd,&segmentx,sizeof(SegmentX)))
417 amb 110 {
418 amb 1349 if(prevnode1==segmentx.node1 && prevnode2==segmentx.node2)
419 amb 812 {
420 amb 1607 node_t id1=nodesx->idata[segmentx.node1];
421     node_t id2=nodesx->idata[segmentx.node2];
422    
423 amb 1349 if(prevway==segmentx.way)
424     {
425 amb 1608 way_t id=waysx->idata[segmentx.way];
426 amb 812
427 amb 1608 logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" in way %"Pway_t" is duplicated.\n",logerror_node(id1),logerror_node(id2),logerror_way(id));
428 amb 1349 }
429 amb 1173 else
430     {
431     if(!(prevdist&SEGMENT_AREA) && !(segmentx.distance&SEGMENT_AREA))
432 amb 1607 logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated.\n",logerror_node(id1),logerror_node(id2));
433 amb 1155
434 amb 1173 if(!(prevdist&SEGMENT_AREA) && (segmentx.distance&SEGMENT_AREA))
435 amb 1607 logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (discarded the area).\n",logerror_node(id1),logerror_node(id2));
436 amb 1155
437 amb 1173 if((prevdist&SEGMENT_AREA) && !(segmentx.distance&SEGMENT_AREA))
438 amb 1607 logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (discarded the non-area).\n",logerror_node(id1),logerror_node(id2));
439 amb 1155
440 amb 1173 if((prevdist&SEGMENT_AREA) && (segmentx.distance&SEGMENT_AREA))
441 amb 1607 logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (both are areas).\n",logerror_node(id1),logerror_node(id2));
442 amb 1173 }
443 amb 1155
444     duplicate++;
445     }
446 amb 275 else
447 amb 257 {
448 amb 1607 NodeX *nodex1=LookupNodeX(nodesx,segmentx.node1,1);
449     NodeX *nodex2=LookupNodeX(nodesx,segmentx.node2,2);
450    
451 amb 1155 prevnode1=segmentx.node1;
452     prevnode2=segmentx.node2;
453 amb 1173 prevway=segmentx.way;
454 amb 1168 prevdist=DISTANCE(segmentx.distance);
455 amb 1155
456 amb 1351 /* Mark the ways which are used */
457    
458     SetBit(segmentsx->usedway,segmentx.way);
459    
460     /* Set the distance but keep the other flags except for area */
461    
462     segmentx.distance=DISTANCE(DistanceX(nodex1,nodex2))|DISTFLAG(segmentx.distance);
463     segmentx.distance&=~SEGMENT_AREA;
464    
465     /* Write the modified segment */
466    
467 amb 1408 WriteFileBuffered(fd,&segmentx,sizeof(SegmentX));
468 amb 1351
469 amb 275 good++;
470 amb 110 }
471    
472 amb 275 total++;
473 amb 256
474 amb 275 if(!(total%10000))
475 amb 1351 printf_middle("Processing Segments: Segments=%"Pindex_t" Duplicates=%"Pindex_t,total,duplicate);
476 amb 110 }
477    
478 amb 555 segmentsx->number=good;
479 amb 275
480 amb 555 /* Close the files */
481    
482 amb 1408 segmentsx->fd=CloseFileBuffered(segmentsx->fd);
483     CloseFileBuffered(fd);
484 amb 275
485 amb 1349 /* Unmap from memory / close the file */
486    
487     #if !SLIM
488     nodesx->data=UnmapFile(nodesx->data);
489     #else
490 amb 1414 nodesx->fd=SlimUnmapFile(nodesx->fd);
491 amb 1349 #endif
492    
493 amb 275 /* Print the final message */
494    
495 amb 1351 printf_last("Processed Segments: Segments=%"Pindex_t" Duplicates=%"Pindex_t,total,duplicate);
496 amb 110 }
497    
498    
499     /*++++++++++++++++++++++++++++++++++++++
500 amb 1431 Index the segments by creating the firstnode index and filling in the segment next2 parameter.
501 amb 1160
502     SegmentsX *segmentsx The set of segments to modify.
503    
504     NodesX *nodesx The set of nodes to use.
505    
506     WaysX *waysx The set of ways to use.
507     ++++++++++++++++++++++++++++++++++++++*/
508    
509     void IndexSegments(SegmentsX *segmentsx,NodesX *nodesx,WaysX *waysx)
510     {
511 amb 1431 index_t index,start=0,i;
512     SegmentX *segmentx_list=NULL;
513     #if SLIM
514     index_t length=0;
515     #endif
516 amb 1160
517     if(segmentsx->number==0)
518     return;
519    
520     /* Print the start message */
521    
522     printf_first("Indexing Segments: Segments=0");
523    
524     /* Allocate the array of indexes */
525    
526     segmentsx->firstnode=(index_t*)malloc(nodesx->number*sizeof(index_t));
527 amb 1598 log_malloc(segmentsx->firstnode,nodesx->number*sizeof(index_t));
528 amb 1160
529 amb 1166 logassert(segmentsx->firstnode,"Failed to allocate memory (try using slim mode?)"); /* Check malloc() worked */
530 amb 1160
531 amb 1431 for(i=0;i<nodesx->number;i++)
532     segmentsx->firstnode[i]=NO_SEGMENT;
533 amb 1160
534 amb 1431 /* Map into memory / open the files */
535 amb 1160
536 amb 1431 #if !SLIM
537     segmentsx->data=MapFileWriteable(segmentsx->filename_tmp);
538     #else
539     segmentsx->fd=SlimMapFileWriteable(segmentsx->filename_tmp);
540 amb 1297
541 amb 1431 segmentx_list=(SegmentX*)malloc(1024*sizeof(SegmentX));
542     #endif
543 amb 1160
544 amb 1431 /* Read through the segments in reverse order (in chunks to help slim mode) */
545 amb 1160
546 amb 1431 for(index=segmentsx->number-1;index!=NO_SEGMENT;index--)
547 amb 1160 {
548 amb 1431 SegmentX *segmentx;
549 amb 1160
550 amb 1431 if((index%1024)==1023 || index==(segmentsx->number-1))
551     {
552     start=1024*(index/1024);
553 amb 1422
554 amb 1431 #if !SLIM
555     segmentx_list=LookupSegmentX(segmentsx,start,1);
556     #else
557     length=index-start+1;
558    
559     SlimFetch(segmentsx->fd,segmentx_list,length*sizeof(SegmentX),start*sizeof(SegmentX));
560     #endif
561     }
562    
563     segmentx=segmentx_list+(index-start);
564    
565 amb 1160 if(nodesx->pdata)
566     {
567 amb 1431 segmentx->node1=nodesx->pdata[segmentx->node1];
568     segmentx->node2=nodesx->pdata[segmentx->node2];
569 amb 1160 }
570    
571     if(waysx->cdata)
572 amb 1431 segmentx->way=waysx->cdata[segmentx->way];
573 amb 1160
574 amb 1431 segmentx->next2=segmentsx->firstnode[segmentx->node2];
575 amb 1160
576 amb 1431 segmentsx->firstnode[segmentx->node1]=index;
577     segmentsx->firstnode[segmentx->node2]=index;
578 amb 1160
579     if(!(index%10000))
580     printf_middle("Indexing Segments: Segments=%"Pindex_t,segmentsx->number-index);
581 amb 1422
582 amb 1431 #if SLIM
583     if(index==start)
584     SlimReplace(segmentsx->fd,segmentx_list,length*sizeof(SegmentX),start*sizeof(SegmentX));
585     #endif
586 amb 1160 }
587    
588     /* Unmap from memory / close the files */
589    
590 amb 1431 #if !SLIM
591     segmentsx->data=UnmapFile(segmentsx->data);
592     #else
593     segmentsx->fd=SlimUnmapFile(segmentsx->fd);
594 amb 1422
595 amb 1431 free(segmentx_list);
596     #endif
597    
598 amb 1160 /* Free the memory */
599    
600     if(nodesx->pdata)
601     {
602 amb 1598 log_free(nodesx->pdata);
603 amb 1160 free(nodesx->pdata);
604     nodesx->pdata=NULL;
605     }
606    
607     if(waysx->cdata)
608     {
609 amb 1598 log_free(waysx->cdata);
610 amb 1160 free(waysx->cdata);
611     waysx->cdata=NULL;
612     }
613    
614     /* Print the final message */
615    
616     printf_last("Indexed Segments: Segments=%"Pindex_t,segmentsx->number);
617     }
618    
619    
620     /*++++++++++++++++++++++++++++++++++++++
621     Prune the deleted segments while resorting the list.
622    
623     SegmentsX *segmentsx The set of segments to sort and modify.
624    
625     WaysX *waysx The set of ways to check.
626     ++++++++++++++++++++++++++++++++++++++*/
627    
628     void RemovePrunedSegments(SegmentsX *segmentsx,WaysX *waysx)
629     {
630     int fd;
631     index_t xnumber;
632    
633 amb 1208 if(segmentsx->number==0)
634     return;
635    
636 amb 1160 /* Print the start message */
637    
638     printf_first("Sorting and Pruning Segments");
639    
640     /* Allocate the way usage bitmask */
641    
642     segmentsx->usedway=AllocBitMask(waysx->number);
643 amb 1598 log_malloc(segmentsx->usedway,LengthBitMask(waysx->number)*sizeof(BitMask));
644 amb 1160
645 amb 1166 logassert(segmentsx->usedway,"Failed to allocate memory (try using slim mode?)"); /* Check AllocBitMask() worked */
646 amb 1160
647     /* Re-open the file read-only and a new file writeable */
648    
649 amb 1699 fd=ReplaceFileBuffered(segmentsx->filename_tmp,&segmentsx->fd);
650 amb 1160
651     /* Sort by node indexes */
652    
653     xnumber=segmentsx->number;
654    
655     sortsegmentsx=segmentsx;
656    
657     segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),(int (*)(void*,index_t))delete_pruned,
658     (int (*)(const void*,const void*))sort_by_id,
659     NULL);
660    
661     /* Close the files */
662    
663 amb 1409 segmentsx->fd=CloseFileBuffered(segmentsx->fd);
664     CloseFileBuffered(fd);
665 amb 1160
666     /* Print the final message */
667    
668     printf_last("Sorted and Pruned Segments: Segments=%"Pindex_t" Deleted=%"Pindex_t,xnumber,xnumber-segmentsx->number);
669     }
670    
671    
672     /*++++++++++++++++++++++++++++++++++++++
673     Delete the pruned segments.
674    
675     int delete_pruned Return 1 if the value is to be kept, otherwise 0.
676    
677     SegmentX *segmentx The extended segment.
678    
679     index_t index The number of unsorted segments that have been read from the input file.
680     ++++++++++++++++++++++++++++++++++++++*/
681    
682     static int delete_pruned(SegmentX *segmentx,index_t index)
683     {
684     if(IsPrunedSegmentX(segmentx))
685     return(0);
686    
687     SetBit(sortsegmentsx->usedway,segmentx->way);
688    
689     return(1);
690     }
691    
692    
693     /*++++++++++++++++++++++++++++++++++++++
694 amb 1132 Remove the duplicate super-segments.
695 amb 110
696 amb 1132 SegmentsX *segmentsx The set of super-segments to modify.
697 amb 110
698 amb 680 WaysX *waysx The set of ways to use.
699 amb 110 ++++++++++++++++++++++++++++++++++++++*/
700    
701 amb 1132 void DeduplicateSuperSegments(SegmentsX *segmentsx,WaysX *waysx)
702 amb 110 {
703 amb 1132 int fd;
704     index_t xnumber;
705 amb 110
706 amb 1208 if(waysx->number==0)
707     return;
708    
709 amb 275 /* Print the start message */
710    
711 amb 1132 printf_first("Sorting and Deduplicating Super-Segments");
712 amb 227
713 amb 555 /* Map into memory / open the file */
714 amb 256
715 amb 452 #if !SLIM
716 amb 1120 waysx->data=MapFile(waysx->filename_tmp);
717 amb 555 #else
718 amb 1414 waysx->fd=SlimMapFile(waysx->filename_tmp);
719 amb 1297
720     InvalidateWayXCache(waysx->cache);
721 amb 452 #endif
722 amb 275
723 amb 555 /* Re-open the file read-only and a new file writeable */
724 amb 275
725 amb 1699 fd=ReplaceFileBuffered(segmentsx->filename_tmp,&segmentsx->fd);
726 amb 555
727 amb 1132 /* Sort by node indexes */
728 amb 555
729 amb 1132 xnumber=segmentsx->number;
730 amb 256
731 amb 1132 sortsegmentsx=segmentsx;
732     sortwaysx=waysx;
733 amb 110
734 amb 1132 segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),NULL,
735     (int (*)(const void*,const void*))sort_by_id,
736     (int (*)(void*,index_t))deduplicate_super);
737 amb 264
738 amb 555 /* Close the files */
739    
740 amb 1409 segmentsx->fd=CloseFileBuffered(segmentsx->fd);
741     CloseFileBuffered(fd);
742 amb 275
743 amb 555 /* Unmap from memory / close the file */
744 amb 275
745 amb 452 #if !SLIM
746 amb 1122 waysx->data=UnmapFile(waysx->data);
747 amb 555 #else
748 amb 1414 waysx->fd=SlimUnmapFile(waysx->fd);
749 amb 452 #endif
750 amb 275
751     /* Print the final message */
752    
753 amb 1132 printf_last("Sorted and Deduplicated Super-Segments: Super-Segments=%"Pindex_t" Duplicate=%"Pindex_t,xnumber,xnumber-segmentsx->number);
754 amb 110 }
755    
756    
757     /*++++++++++++++++++++++++++++++++++++++
758 amb 1132 De-duplicate super-segments.
759    
760     int deduplicate_super Return 1 if the value is to be kept, otherwise 0.
761    
762     SegmentX *segmentx The extended super-segment.
763    
764     index_t index The number of sorted super-segments that have already been written to the output file.
765     ++++++++++++++++++++++++++++++++++++++*/
766    
767     static int deduplicate_super(SegmentX *segmentx,index_t index)
768     {
769 amb 1784 static int nprev; /* internal variable (reset by first call in each sort; index==0) */
770     static index_t prevnode1,prevnode2; /* internal variable (reset by first call in each sort; index==0) */
771     static SegmentX prevsegx[MAX_SEG_PER_NODE]; /* internal variable (reset by first call in each sort; index==0) */
772     static Way prevway[MAX_SEG_PER_NODE]; /* internal variable (reset by first call in each sort; index==0) */
773 amb 1132
774     WayX *wayx=LookupWayX(sortwaysx,segmentx->way,1);
775     int isduplicate=0;
776    
777     if(index==0 || segmentx->node1!=prevnode1 || segmentx->node2!=prevnode2)
778     {
779     nprev=1;
780     prevnode1=segmentx->node1;
781     prevnode2=segmentx->node2;
782     prevsegx[0]=*segmentx;
783     prevway[0] =wayx->way;
784     }
785     else
786     {
787     int offset;
788    
789     for(offset=0;offset<nprev;offset++)
790     {
791 amb 1168 if(DISTFLAG(segmentx->distance)==DISTFLAG(prevsegx[offset].distance))
792 amb 1132 if(!WaysCompare(&prevway[offset],&wayx->way))
793     {
794     isduplicate=1;
795     break;
796     }
797     }
798    
799     if(isduplicate)
800     {
801     nprev--;
802    
803     for(;offset<nprev;offset++)
804     {
805     prevsegx[offset]=prevsegx[offset+1];
806     prevway[offset] =prevway[offset+1];
807     }
808     }
809     else
810     {
811 amb 1166 logassert(nprev<MAX_SEG_PER_NODE,"Too many segments for one node (increase MAX_SEG_PER_NODE?)"); /* Only a limited amount of information stored. */
812 amb 1132
813     prevsegx[nprev]=*segmentx;
814     prevway[nprev] =wayx->way;
815    
816     nprev++;
817     }
818     }
819    
820     return(!isduplicate);
821     }
822    
823    
824     /*++++++++++++++++++++++++++++++++++++++
825 amb 1427 Sort the segments geographically after updating the node indexes.
826    
827     SegmentsX *segmentsx The set of segments to modify.
828    
829     NodesX *nodesx The set of nodes to use.
830     ++++++++++++++++++++++++++++++++++++++*/
831    
832     void SortSegmentListGeographically(SegmentsX *segmentsx,NodesX *nodesx)
833     {
834     int fd;
835    
836     if(segmentsx->number==0)
837     return;
838    
839     /* Print the start message */
840    
841     printf_first("Sorting Segments Geographically");
842    
843     /* Re-open the file read-only and a new file writeable */
844    
845 amb 1699 fd=ReplaceFileBuffered(segmentsx->filename_tmp,&segmentsx->fd);
846 amb 1427
847     /* Update the segments with geographically sorted node indexes and sort them */
848    
849     sortnodesx=nodesx;
850    
851     filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),(int (*)(void*,index_t))geographically_index,
852     (int (*)(const void*,const void*))sort_by_id,
853     NULL);
854     /* Close the files */
855    
856     segmentsx->fd=CloseFileBuffered(segmentsx->fd);
857     CloseFileBuffered(fd);
858    
859     /* Print the final message */
860    
861     printf_last("Sorted Segments Geographically: Segments=%"Pindex_t,segmentsx->number);
862     }
863    
864    
865     /*++++++++++++++++++++++++++++++++++++++
866     Update the segment indexes.
867    
868     int geographically_index Return 1 if the value is to be kept, otherwise 0.
869    
870     SegmentX *segmentx The extended segment.
871    
872     index_t index The number of unsorted segments that have been read from the input file.
873     ++++++++++++++++++++++++++++++++++++++*/
874    
875     static int geographically_index(SegmentX *segmentx,index_t index)
876     {
877     segmentx->node1=sortnodesx->gdata[segmentx->node1];
878     segmentx->node2=sortnodesx->gdata[segmentx->node2];
879    
880     if(segmentx->node1>segmentx->node2)
881     {
882     index_t temp;
883    
884     temp=segmentx->node1;
885     segmentx->node1=segmentx->node2;
886     segmentx->node2=temp;
887    
888     if(segmentx->distance&(ONEWAY_2TO1|ONEWAY_1TO2))
889     segmentx->distance^=ONEWAY_2TO1|ONEWAY_1TO2;
890     }
891    
892     return(1);
893     }
894    
895    
896     /*++++++++++++++++++++++++++++++++++++++
897 amb 285 Save the segment list to a file.
898    
899 amb 681 SegmentsX *segmentsx The set of segments to save.
900 amb 285
901     const char *filename The name of the file to save.
902     ++++++++++++++++++++++++++++++++++++++*/
903    
904 amb 681 void SaveSegmentList(SegmentsX *segmentsx,const char *filename)
905 amb 285 {
906     index_t i;
907     int fd;
908 amb 500 SegmentsFile segmentsfile={0};
909 amb 780 index_t super_number=0,normal_number=0;
910 amb 285
911     /* Print the start message */
912    
913 amb 519 printf_first("Writing Segments: Segments=0");
914 amb 285
915 amb 558 /* Re-open the file */
916    
917 amb 1408 segmentsx->fd=ReOpenFileBuffered(segmentsx->filename_tmp);
918 amb 558
919 amb 461 /* Write out the segments data */
920 amb 285
921 amb 1408 fd=OpenFileBufferedNew(filename);
922 amb 461
923 amb 1408 SeekFileBuffered(fd,sizeof(SegmentsFile));
924 amb 461
925 amb 285 for(i=0;i<segmentsx->number;i++)
926     {
927 amb 643 SegmentX segmentx;
928 amb 944 Segment segment={0};
929 amb 448
930 amb 1408 ReadFileBuffered(segmentsx->fd,&segmentx,sizeof(SegmentX));
931 amb 558
932 amb 1168 segment.node1 =segmentx.node1;
933     segment.node2 =segmentx.node2;
934     segment.next2 =segmentx.next2;
935     segment.way =segmentx.way;
936     segment.distance=segmentx.distance;
937 amb 643
938 amb 558 if(IsSuperSegment(&segment))
939 amb 285 super_number++;
940 amb 558 if(IsNormalSegment(&segment))
941 amb 285 normal_number++;
942    
943 amb 1408 WriteFileBuffered(fd,&segment,sizeof(Segment));
944 amb 448
945 amb 285 if(!((i+1)%10000))
946 amb 790 printf_middle("Writing Segments: Segments=%"Pindex_t,i+1);
947 amb 285 }
948    
949 amb 461 /* Write out the header structure */
950    
951     segmentsfile.number=segmentsx->number;
952     segmentsfile.snumber=super_number;
953     segmentsfile.nnumber=normal_number;
954    
955 amb 1408 SeekFileBuffered(fd,0);
956     WriteFileBuffered(fd,&segmentsfile,sizeof(SegmentsFile));
957 amb 461
958 amb 1408 CloseFileBuffered(fd);
959 amb 285
960 amb 558 /* Close the file */
961    
962 amb 1408 segmentsx->fd=CloseFileBuffered(segmentsx->fd);
963 amb 558
964 amb 285 /* Print the final message */
965    
966 amb 790 printf_last("Wrote Segments: Segments=%"Pindex_t,segmentsx->number);
967 amb 285 }
968    
969    
970     /*++++++++++++++++++++++++++++++++++++++
971 amb 110 Calculate the distance between two nodes.
972    
973 amb 1168 distance_t DistanceX Returns the distance between the extended nodes.
974 amb 110
975     NodeX *nodex1 The starting node.
976    
977     NodeX *nodex2 The end node.
978     ++++++++++++++++++++++++++++++++++++++*/
979    
980 amb 1168 static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
981 amb 110 {
982 amb 223 double dlon = latlong_to_radians(nodex1->longitude) - latlong_to_radians(nodex2->longitude);
983     double dlat = latlong_to_radians(nodex1->latitude) - latlong_to_radians(nodex2->latitude);
984     double lat1 = latlong_to_radians(nodex1->latitude);
985     double lat2 = latlong_to_radians(nodex2->latitude);
986 amb 110
987 amb 219 double a1,a2,a,sa,c,d;
988 amb 110
989     if(dlon==0 && dlat==0)
990     return 0;
991    
992 amb 219 a1 = sin (dlat / 2);
993     a2 = sin (dlon / 2);
994 amb 1603 a = a1 * a1 + cos (lat1) * cos (lat2) * a2 * a2;
995 amb 219 sa = sqrt (a);
996 amb 110 if (sa <= 1.0)
997 amb 219 {c = 2 * asin (sa);}
998 amb 110 else
999 amb 219 {c = 2 * asin (1.0);}
1000 amb 110 d = 6378.137 * c;
1001    
1002     return km_to_distance(d);
1003     }

Properties

Name Value
cvs:description Extended segments functions.