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