Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /branches/MS-Windows/src/segmentsx.c
Parent Directory
|
Revision Log
Revision 1698 -
(show annotations)
(download)
(as text)
Sun May 31 16:34:57 2015 UTC (9 years, 9 months ago) by amb
File MIME type: text/x-csrc
File size: 25637 byte(s)
Sun May 31 16:34:57 2015 UTC (9 years, 9 months ago) by amb
File MIME type: text/x-csrc
File size: 25637 byte(s)
Merge changes from trunk: remove -Wfloat-conversion option, change web/Makefile order, ensure allocated strings are long enough.
1 | /*************************************** |
2 | Extended Segment data type functions. |
3 | |
4 | Part of the Routino routing software. |
5 | ******************/ /****************** |
6 | This file Copyright 2008-2015 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_id(SegmentX *a,SegmentX *b); |
56 | |
57 | static int delete_pruned(SegmentX *segmentx,index_t index); |
58 | |
59 | static int deduplicate_super(SegmentX *segmentx,index_t index); |
60 | |
61 | static int geographically_index(SegmentX *segmentx,index_t index); |
62 | |
63 | static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2); |
64 | |
65 | |
66 | /*++++++++++++++++++++++++++++++++++++++ |
67 | Allocate a new segment list (create a new file or open an existing one). |
68 | |
69 | SegmentsX *NewSegmentList Returns the segment list. |
70 | ++++++++++++++++++++++++++++++++++++++*/ |
71 | |
72 | SegmentsX *NewSegmentList(void) |
73 | { |
74 | SegmentsX *segmentsx; |
75 | |
76 | segmentsx=(SegmentsX*)calloc(1,sizeof(SegmentsX)); |
77 | |
78 | logassert(segmentsx,"Failed to allocate memory (try using slim mode?)"); /* Check calloc() worked */ |
79 | |
80 | segmentsx->filename_tmp=(char*)malloc(strlen(option_tmpdirname)+40); /* allow %p to be up to 20 bytes */ |
81 | |
82 | sprintf(segmentsx->filename_tmp,"%s/segmentsx.%p.tmp",option_tmpdirname,(void*)segmentsx); |
83 | |
84 | segmentsx->fd=OpenFileBufferedNew(segmentsx->filename_tmp); |
85 | |
86 | #if SLIM |
87 | segmentsx->cache=NewSegmentXCache(); |
88 | log_malloc(segmentsx->cache,sizeof(*segmentsx->cache)); |
89 | #endif |
90 | |
91 | return(segmentsx); |
92 | } |
93 | |
94 | |
95 | /*++++++++++++++++++++++++++++++++++++++ |
96 | Free a segment list. |
97 | |
98 | SegmentsX *segmentsx The set of segments to be freed. |
99 | ++++++++++++++++++++++++++++++++++++++*/ |
100 | |
101 | void FreeSegmentList(SegmentsX *segmentsx) |
102 | { |
103 | DeleteFile(segmentsx->filename_tmp); |
104 | |
105 | free(segmentsx->filename_tmp); |
106 | |
107 | if(segmentsx->usedway) |
108 | { |
109 | log_free(segmentsx->usedway); |
110 | free(segmentsx->usedway); |
111 | } |
112 | |
113 | if(segmentsx->firstnode) |
114 | { |
115 | log_free(segmentsx->firstnode); |
116 | free(segmentsx->firstnode); |
117 | } |
118 | |
119 | if(segmentsx->next1) |
120 | { |
121 | log_free(segmentsx->next1); |
122 | free(segmentsx->next1); |
123 | } |
124 | |
125 | #if SLIM |
126 | log_free(segmentsx->cache); |
127 | DeleteSegmentXCache(segmentsx->cache); |
128 | #endif |
129 | |
130 | free(segmentsx); |
131 | } |
132 | |
133 | |
134 | /*++++++++++++++++++++++++++++++++++++++ |
135 | Append a single segment to an unsorted segment list. |
136 | |
137 | SegmentsX *segmentsx The set of segments to modify. |
138 | |
139 | index_t way The index of the way that the segment belongs to. |
140 | |
141 | index_t node1 The index of the first node in the segment. |
142 | |
143 | index_t node2 The index of the second node in the segment. |
144 | |
145 | distance_t distance The distance between the nodes (or just the flags). |
146 | ++++++++++++++++++++++++++++++++++++++*/ |
147 | |
148 | void AppendSegmentList(SegmentsX *segmentsx,index_t way,index_t node1,index_t node2,distance_t distance) |
149 | { |
150 | SegmentX segmentx; |
151 | |
152 | if(node1>node2) |
153 | { |
154 | index_t temp; |
155 | |
156 | temp=node1; |
157 | node1=node2; |
158 | node2=temp; |
159 | |
160 | if(distance&(ONEWAY_2TO1|ONEWAY_1TO2)) |
161 | distance^=ONEWAY_2TO1|ONEWAY_1TO2; |
162 | } |
163 | |
164 | segmentx.node1=node1; |
165 | segmentx.node2=node2; |
166 | segmentx.next2=NO_SEGMENT; |
167 | segmentx.way=way; |
168 | segmentx.distance=distance; |
169 | |
170 | WriteFileBuffered(segmentsx->fd,&segmentx,sizeof(SegmentX)); |
171 | |
172 | segmentsx->number++; |
173 | |
174 | 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 | } |
176 | |
177 | |
178 | /*++++++++++++++++++++++++++++++++++++++ |
179 | Finish appending segments and change the filename over. |
180 | |
181 | SegmentsX *segmentsx The segments that have been appended. |
182 | ++++++++++++++++++++++++++++++++++++++*/ |
183 | |
184 | void FinishSegmentList(SegmentsX *segmentsx) |
185 | { |
186 | if(segmentsx->fd!=-1) |
187 | segmentsx->fd=CloseFileBuffered(segmentsx->fd); |
188 | } |
189 | |
190 | |
191 | /*++++++++++++++++++++++++++++++++++++++ |
192 | 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 | if(segmentsx->next1) |
238 | { |
239 | index_t index=IndexSegmentX(segmentsx,segmentx); |
240 | |
241 | if(segmentsx->next1[index]==NO_SEGMENT) |
242 | return(NULL); |
243 | |
244 | segmentx=LookupSegmentX(segmentsx,segmentsx->next1[index],position); |
245 | |
246 | return(segmentx); |
247 | } |
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 | |
268 | return(segmentx); |
269 | } |
270 | } |
271 | else |
272 | { |
273 | if(segmentx->next2==NO_SEGMENT) |
274 | return(NULL); |
275 | |
276 | return(LookupSegmentX(segmentsx,segmentx->next2,position)); |
277 | } |
278 | } |
279 | |
280 | |
281 | /*++++++++++++++++++++++++++++++++++++++ |
282 | Sort the segment list. |
283 | |
284 | SegmentsX *segmentsx The set of segments to sort. |
285 | ++++++++++++++++++++++++++++++++++++++*/ |
286 | |
287 | void SortSegmentList(SegmentsX *segmentsx) |
288 | { |
289 | int fd; |
290 | |
291 | /* Print the start message */ |
292 | |
293 | printf_first("Sorting Segments"); |
294 | |
295 | /* Re-open the file read-only and a new file writeable */ |
296 | |
297 | fd=ReplaceFileBuffered(segmentsx->filename_tmp,&segmentsx->fd); |
298 | |
299 | /* Sort by node indexes */ |
300 | |
301 | segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),NULL, |
302 | (int (*)(const void*,const void*))sort_by_id, |
303 | NULL); |
304 | |
305 | /* Close the files */ |
306 | |
307 | segmentsx->fd=CloseFileBuffered(segmentsx->fd); |
308 | CloseFileBuffered(fd); |
309 | |
310 | /* Print the final message */ |
311 | |
312 | printf_last("Sorted Segments: Segments=%"Pindex_t,segmentsx->number); |
313 | } |
314 | |
315 | |
316 | /*++++++++++++++++++++++++++++++++++++++ |
317 | Sort the segments into id order, first by node1 then by node2, finally by distance. |
318 | |
319 | int sort_by_id Returns the comparison of the node fields. |
320 | |
321 | SegmentX *a The first segment. |
322 | |
323 | SegmentX *b The second segment. |
324 | ++++++++++++++++++++++++++++++++++++++*/ |
325 | |
326 | static int sort_by_id(SegmentX *a,SegmentX *b) |
327 | { |
328 | index_t a_id1=a->node1; |
329 | index_t b_id1=b->node1; |
330 | |
331 | 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 | { |
337 | index_t a_id2=a->node2; |
338 | index_t b_id2=b->node2; |
339 | |
340 | if(a_id2<b_id2) |
341 | return(-1); |
342 | else if(a_id2>b_id2) |
343 | return(1); |
344 | else |
345 | { |
346 | distance_t a_distance=DISTANCE(a->distance); |
347 | distance_t b_distance=DISTANCE(b->distance); |
348 | |
349 | if(a_distance<b_distance) |
350 | return(-1); |
351 | else if(a_distance>b_distance) |
352 | return(1); |
353 | else |
354 | { |
355 | distance_t a_distflag=DISTFLAG(a->distance); |
356 | distance_t b_distflag=DISTFLAG(b->distance); |
357 | |
358 | if(a_distflag<b_distflag) |
359 | return(-1); |
360 | else if(a_distflag>b_distflag) |
361 | return(1); |
362 | else |
363 | return(FILESORT_PRESERVE_ORDER(a,b)); /* preserve order */ |
364 | } |
365 | } |
366 | } |
367 | } |
368 | |
369 | |
370 | /*++++++++++++++++++++++++++++++++++++++ |
371 | Process segments (non-trivial duplicates). |
372 | |
373 | SegmentsX *segmentsx The set of segments to modify. |
374 | |
375 | NodesX *nodesx The set of nodes to use. |
376 | |
377 | WaysX *waysx The set of ways to use. |
378 | ++++++++++++++++++++++++++++++++++++++*/ |
379 | |
380 | void ProcessSegments(SegmentsX *segmentsx,NodesX *nodesx,WaysX *waysx) |
381 | { |
382 | index_t duplicate=0,good=0,total=0; |
383 | index_t prevnode1=NO_NODE,prevnode2=NO_NODE; |
384 | index_t prevway=NO_WAY; |
385 | distance_t prevdist=0; |
386 | SegmentX segmentx; |
387 | int fd; |
388 | |
389 | /* Print the start message */ |
390 | |
391 | printf_first("Processing Segments: Segments=0 Duplicates=0"); |
392 | |
393 | /* Map into memory / open the file */ |
394 | |
395 | #if !SLIM |
396 | nodesx->data=MapFile(nodesx->filename_tmp); |
397 | #else |
398 | nodesx->fd=SlimMapFile(nodesx->filename_tmp); |
399 | |
400 | InvalidateNodeXCache(nodesx->cache); |
401 | #endif |
402 | |
403 | /* Allocate the way usage bitmask */ |
404 | |
405 | segmentsx->usedway=AllocBitMask(waysx->number); |
406 | log_malloc(segmentsx->usedway,LengthBitMask(waysx->number)*sizeof(BitMask)); |
407 | |
408 | logassert(segmentsx->usedway,"Failed to allocate memory (try using slim mode?)"); /* Check AllocBitMask() worked */ |
409 | |
410 | /* Re-open the file read-only and a new file writeable */ |
411 | |
412 | fd=ReplaceFileBuffered(segmentsx->filename_tmp,&segmentsx->fd); |
413 | |
414 | /* Modify the on-disk image */ |
415 | |
416 | while(!ReadFileBuffered(segmentsx->fd,&segmentx,sizeof(SegmentX))) |
417 | { |
418 | if(prevnode1==segmentx.node1 && prevnode2==segmentx.node2) |
419 | { |
420 | node_t id1=nodesx->idata[segmentx.node1]; |
421 | node_t id2=nodesx->idata[segmentx.node2]; |
422 | |
423 | if(prevway==segmentx.way) |
424 | { |
425 | way_t id=waysx->idata[segmentx.way]; |
426 | |
427 | 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 | } |
429 | else |
430 | { |
431 | if(!(prevdist&SEGMENT_AREA) && !(segmentx.distance&SEGMENT_AREA)) |
432 | logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated.\n",logerror_node(id1),logerror_node(id2)); |
433 | |
434 | if(!(prevdist&SEGMENT_AREA) && (segmentx.distance&SEGMENT_AREA)) |
435 | logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (discarded the area).\n",logerror_node(id1),logerror_node(id2)); |
436 | |
437 | if((prevdist&SEGMENT_AREA) && !(segmentx.distance&SEGMENT_AREA)) |
438 | logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (discarded the non-area).\n",logerror_node(id1),logerror_node(id2)); |
439 | |
440 | if((prevdist&SEGMENT_AREA) && (segmentx.distance&SEGMENT_AREA)) |
441 | logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (both are areas).\n",logerror_node(id1),logerror_node(id2)); |
442 | } |
443 | |
444 | duplicate++; |
445 | } |
446 | else |
447 | { |
448 | NodeX *nodex1=LookupNodeX(nodesx,segmentx.node1,1); |
449 | NodeX *nodex2=LookupNodeX(nodesx,segmentx.node2,2); |
450 | |
451 | prevnode1=segmentx.node1; |
452 | prevnode2=segmentx.node2; |
453 | prevway=segmentx.way; |
454 | prevdist=DISTANCE(segmentx.distance); |
455 | |
456 | /* 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 | WriteFileBuffered(fd,&segmentx,sizeof(SegmentX)); |
468 | |
469 | good++; |
470 | } |
471 | |
472 | total++; |
473 | |
474 | if(!(total%10000)) |
475 | printf_middle("Processing Segments: Segments=%"Pindex_t" Duplicates=%"Pindex_t,total,duplicate); |
476 | } |
477 | |
478 | segmentsx->number=good; |
479 | |
480 | /* Close the files */ |
481 | |
482 | segmentsx->fd=CloseFileBuffered(segmentsx->fd); |
483 | CloseFileBuffered(fd); |
484 | |
485 | /* Unmap from memory / close the file */ |
486 | |
487 | #if !SLIM |
488 | nodesx->data=UnmapFile(nodesx->data); |
489 | #else |
490 | nodesx->fd=SlimUnmapFile(nodesx->fd); |
491 | #endif |
492 | |
493 | /* Print the final message */ |
494 | |
495 | printf_last("Processed Segments: Segments=%"Pindex_t" Duplicates=%"Pindex_t,total,duplicate); |
496 | } |
497 | |
498 | |
499 | /*++++++++++++++++++++++++++++++++++++++ |
500 | Index the segments by creating the firstnode index and filling in the segment next2 parameter. |
501 | |
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 | index_t index,start=0,i; |
512 | SegmentX *segmentx_list=NULL; |
513 | #if SLIM |
514 | index_t length=0; |
515 | #endif |
516 | |
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 | log_malloc(segmentsx->firstnode,nodesx->number*sizeof(index_t)); |
528 | |
529 | logassert(segmentsx->firstnode,"Failed to allocate memory (try using slim mode?)"); /* Check malloc() worked */ |
530 | |
531 | for(i=0;i<nodesx->number;i++) |
532 | segmentsx->firstnode[i]=NO_SEGMENT; |
533 | |
534 | /* Map into memory / open the files */ |
535 | |
536 | #if !SLIM |
537 | segmentsx->data=MapFileWriteable(segmentsx->filename_tmp); |
538 | #else |
539 | segmentsx->fd=SlimMapFileWriteable(segmentsx->filename_tmp); |
540 | |
541 | segmentx_list=(SegmentX*)malloc(1024*sizeof(SegmentX)); |
542 | #endif |
543 | |
544 | /* Read through the segments in reverse order (in chunks to help slim mode) */ |
545 | |
546 | for(index=segmentsx->number-1;index!=NO_SEGMENT;index--) |
547 | { |
548 | SegmentX *segmentx; |
549 | |
550 | if((index%1024)==1023 || index==(segmentsx->number-1)) |
551 | { |
552 | start=1024*(index/1024); |
553 | |
554 | #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 | if(nodesx->pdata) |
566 | { |
567 | segmentx->node1=nodesx->pdata[segmentx->node1]; |
568 | segmentx->node2=nodesx->pdata[segmentx->node2]; |
569 | } |
570 | |
571 | if(waysx->cdata) |
572 | segmentx->way=waysx->cdata[segmentx->way]; |
573 | |
574 | segmentx->next2=segmentsx->firstnode[segmentx->node2]; |
575 | |
576 | segmentsx->firstnode[segmentx->node1]=index; |
577 | segmentsx->firstnode[segmentx->node2]=index; |
578 | |
579 | if(!(index%10000)) |
580 | printf_middle("Indexing Segments: Segments=%"Pindex_t,segmentsx->number-index); |
581 | |
582 | #if SLIM |
583 | if(index==start) |
584 | SlimReplace(segmentsx->fd,segmentx_list,length*sizeof(SegmentX),start*sizeof(SegmentX)); |
585 | #endif |
586 | } |
587 | |
588 | /* Unmap from memory / close the files */ |
589 | |
590 | #if !SLIM |
591 | segmentsx->data=UnmapFile(segmentsx->data); |
592 | #else |
593 | segmentsx->fd=SlimUnmapFile(segmentsx->fd); |
594 | |
595 | free(segmentx_list); |
596 | #endif |
597 | |
598 | /* Free the memory */ |
599 | |
600 | if(nodesx->pdata) |
601 | { |
602 | log_free(nodesx->pdata); |
603 | free(nodesx->pdata); |
604 | nodesx->pdata=NULL; |
605 | } |
606 | |
607 | if(waysx->cdata) |
608 | { |
609 | log_free(waysx->cdata); |
610 | 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 | if(segmentsx->number==0) |
634 | return; |
635 | |
636 | /* 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 | log_malloc(segmentsx->usedway,LengthBitMask(waysx->number)*sizeof(BitMask)); |
644 | |
645 | logassert(segmentsx->usedway,"Failed to allocate memory (try using slim mode?)"); /* Check AllocBitMask() worked */ |
646 | |
647 | /* Re-open the file read-only and a new file writeable */ |
648 | |
649 | fd=ReplaceFileBuffered(segmentsx->filename_tmp,&segmentsx->fd); |
650 | |
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 | segmentsx->fd=CloseFileBuffered(segmentsx->fd); |
664 | CloseFileBuffered(fd); |
665 | |
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 | Remove the duplicate super-segments. |
695 | |
696 | SegmentsX *segmentsx The set of super-segments to modify. |
697 | |
698 | WaysX *waysx The set of ways to use. |
699 | ++++++++++++++++++++++++++++++++++++++*/ |
700 | |
701 | void DeduplicateSuperSegments(SegmentsX *segmentsx,WaysX *waysx) |
702 | { |
703 | int fd; |
704 | index_t xnumber; |
705 | |
706 | if(waysx->number==0) |
707 | return; |
708 | |
709 | /* Print the start message */ |
710 | |
711 | printf_first("Sorting and Deduplicating Super-Segments"); |
712 | |
713 | /* Map into memory / open the file */ |
714 | |
715 | #if !SLIM |
716 | waysx->data=MapFile(waysx->filename_tmp); |
717 | #else |
718 | waysx->fd=SlimMapFile(waysx->filename_tmp); |
719 | |
720 | InvalidateWayXCache(waysx->cache); |
721 | #endif |
722 | |
723 | /* Re-open the file read-only and a new file writeable */ |
724 | |
725 | fd=ReplaceFileBuffered(segmentsx->filename_tmp,&segmentsx->fd); |
726 | |
727 | /* Sort by node indexes */ |
728 | |
729 | xnumber=segmentsx->number; |
730 | |
731 | sortsegmentsx=segmentsx; |
732 | sortwaysx=waysx; |
733 | |
734 | 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 | |
738 | /* Close the files */ |
739 | |
740 | segmentsx->fd=CloseFileBuffered(segmentsx->fd); |
741 | CloseFileBuffered(fd); |
742 | |
743 | /* Unmap from memory / close the file */ |
744 | |
745 | #if !SLIM |
746 | waysx->data=UnmapFile(waysx->data); |
747 | #else |
748 | waysx->fd=SlimUnmapFile(waysx->fd); |
749 | #endif |
750 | |
751 | /* Print the final message */ |
752 | |
753 | printf_last("Sorted and Deduplicated Super-Segments: Super-Segments=%"Pindex_t" Duplicate=%"Pindex_t,xnumber,xnumber-segmentsx->number); |
754 | } |
755 | |
756 | |
757 | /*++++++++++++++++++++++++++++++++++++++ |
758 | 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 | static int nprev=0; |
770 | static index_t prevnode1=NO_NODE,prevnode2=NO_NODE; |
771 | static SegmentX prevsegx[MAX_SEG_PER_NODE]; |
772 | static Way prevway[MAX_SEG_PER_NODE]; |
773 | |
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 | if(DISTFLAG(segmentx->distance)==DISTFLAG(prevsegx[offset].distance)) |
792 | 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 | 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 | |
813 | prevsegx[nprev]=*segmentx; |
814 | prevway[nprev] =wayx->way; |
815 | |
816 | nprev++; |
817 | } |
818 | } |
819 | |
820 | return(!isduplicate); |
821 | } |
822 | |
823 | |
824 | /*++++++++++++++++++++++++++++++++++++++ |
825 | 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 | fd=ReplaceFileBuffered(segmentsx->filename_tmp,&segmentsx->fd); |
846 | |
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 | Save the segment list to a file. |
898 | |
899 | SegmentsX *segmentsx The set of segments to save. |
900 | |
901 | const char *filename The name of the file to save. |
902 | ++++++++++++++++++++++++++++++++++++++*/ |
903 | |
904 | void SaveSegmentList(SegmentsX *segmentsx,const char *filename) |
905 | { |
906 | index_t i; |
907 | int fd; |
908 | SegmentsFile segmentsfile={0}; |
909 | index_t super_number=0,normal_number=0; |
910 | |
911 | /* Print the start message */ |
912 | |
913 | printf_first("Writing Segments: Segments=0"); |
914 | |
915 | /* Re-open the file */ |
916 | |
917 | segmentsx->fd=ReOpenFileBuffered(segmentsx->filename_tmp); |
918 | |
919 | /* Write out the segments data */ |
920 | |
921 | fd=OpenFileBufferedNew(filename); |
922 | |
923 | SeekFileBuffered(fd,sizeof(SegmentsFile)); |
924 | |
925 | for(i=0;i<segmentsx->number;i++) |
926 | { |
927 | SegmentX segmentx; |
928 | Segment segment={0}; |
929 | |
930 | ReadFileBuffered(segmentsx->fd,&segmentx,sizeof(SegmentX)); |
931 | |
932 | 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 | |
938 | if(IsSuperSegment(&segment)) |
939 | super_number++; |
940 | if(IsNormalSegment(&segment)) |
941 | normal_number++; |
942 | |
943 | WriteFileBuffered(fd,&segment,sizeof(Segment)); |
944 | |
945 | if(!((i+1)%10000)) |
946 | printf_middle("Writing Segments: Segments=%"Pindex_t,i+1); |
947 | } |
948 | |
949 | /* Write out the header structure */ |
950 | |
951 | segmentsfile.number=segmentsx->number; |
952 | segmentsfile.snumber=super_number; |
953 | segmentsfile.nnumber=normal_number; |
954 | |
955 | SeekFileBuffered(fd,0); |
956 | WriteFileBuffered(fd,&segmentsfile,sizeof(SegmentsFile)); |
957 | |
958 | CloseFileBuffered(fd); |
959 | |
960 | /* Close the file */ |
961 | |
962 | segmentsx->fd=CloseFileBuffered(segmentsx->fd); |
963 | |
964 | /* Print the final message */ |
965 | |
966 | printf_last("Wrote Segments: Segments=%"Pindex_t,segmentsx->number); |
967 | } |
968 | |
969 | |
970 | /*++++++++++++++++++++++++++++++++++++++ |
971 | Calculate the distance between two nodes. |
972 | |
973 | distance_t DistanceX Returns the distance between the extended nodes. |
974 | |
975 | NodeX *nodex1 The starting node. |
976 | |
977 | NodeX *nodex2 The end node. |
978 | ++++++++++++++++++++++++++++++++++++++*/ |
979 | |
980 | static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2) |
981 | { |
982 | 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 | |
987 | double a1,a2,a,sa,c,d; |
988 | |
989 | if(dlon==0 && dlat==0) |
990 | return 0; |
991 | |
992 | a1 = sin (dlat / 2); |
993 | a2 = sin (dlon / 2); |
994 | a = a1 * a1 + cos (lat1) * cos (lat2) * a2 * a2; |
995 | sa = sqrt (a); |
996 | if (sa <= 1.0) |
997 | {c = 2 * asin (sa);} |
998 | else |
999 | {c = 2 * asin (1.0);} |
1000 | d = 6378.137 * c; |
1001 | |
1002 | return km_to_distance(d); |
1003 | } |
Properties
Name | Value |
---|---|
cvs:description | Extended segments functions. |