Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Annotation of /trunk/src/nodesx.c
Parent Directory
|
Revision Log
Revision 1165 -
(hide annotations)
(download)
(as text)
Tue Nov 20 15:30:13 2012 UTC (12 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 18620 byte(s)
Tue Nov 20 15:30:13 2012 UTC (12 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 18620 byte(s)
Use a specific type for the node flags instead of a generic uint16_t.
1 | amb | 110 | /*************************************** |
2 | Extented Node data type functions. | ||
3 | amb | 151 | |
4 | Part of the Routino routing software. | ||
5 | amb | 110 | ******************/ /****************** |
6 | amb | 947 | This file Copyright 2008-2012 Andrew M. Bishop |
7 | amb | 110 | |
8 | amb | 151 | This program is free software: you can redistribute it and/or modify |
9 | it under the terms of the GNU Affero General Public License as published by | ||
10 | the Free Software Foundation, either version 3 of the License, or | ||
11 | (at your option) any later version. | ||
12 | |||
13 | This program is distributed in the hope that it will be useful, | ||
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
16 | GNU Affero General Public License for more details. | ||
17 | |||
18 | You should have received a copy of the GNU Affero General Public License | ||
19 | along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
20 | amb | 110 | ***************************************/ |
21 | |||
22 | |||
23 | #include <assert.h> | ||
24 | #include <stdlib.h> | ||
25 | amb | 249 | #include <string.h> |
26 | amb | 110 | |
27 | #include "types.h" | ||
28 | amb | 449 | #include "nodes.h" |
29 | |||
30 | amb | 955 | #include "typesx.h" |
31 | amb | 110 | #include "nodesx.h" |
32 | #include "segmentsx.h" | ||
33 | amb | 204 | #include "waysx.h" |
34 | amb | 110 | |
35 | amb | 449 | #include "files.h" |
36 | amb | 519 | #include "logging.h" |
37 | amb | 532 | #include "sorting.h" |
38 | amb | 110 | |
39 | amb | 449 | |
40 | amb | 1146 | /* Global variables */ |
41 | amb | 110 | |
42 | amb | 289 | /*+ The command line '--tmpdir' option or its default value. +*/ |
43 | amb | 284 | extern char *option_tmpdirname; |
44 | amb | 110 | |
45 | amb | 1146 | /*+ The option to apply changes (needed to suppress some error log messages) +*/ |
46 | extern int option_changes; | ||
47 | |||
48 | /* Local variables */ | ||
49 | |||
50 | amb | 1109 | /*+ Temporary file-local variables for use by the sort functions. +*/ |
51 | amb | 284 | static NodesX *sortnodesx; |
52 | amb | 1109 | static latlong_t lat_min,lat_max,lon_min,lon_max; |
53 | amb | 284 | |
54 | amb | 1146 | /* Local functions */ |
55 | amb | 110 | |
56 | amb | 271 | static int sort_by_id(NodeX *a,NodeX *b); |
57 | amb | 680 | static int deduplicate_and_index_by_id(NodeX *nodex,index_t index); |
58 | amb | 271 | |
59 | amb | 281 | static int sort_by_lat_long(NodeX *a,NodeX *b); |
60 | amb | 1098 | static int index_by_lat_long(NodeX *nodex,index_t index); |
61 | amb | 110 | |
62 | |||
63 | /*++++++++++++++++++++++++++++++++++++++ | ||
64 | amb | 326 | Allocate a new node list (create a new file or open an existing one). |
65 | amb | 110 | |
66 | amb | 680 | NodesX *NewNodeList Returns a pointer to the node list. |
67 | amb | 326 | |
68 | amb | 1123 | int append Set to 1 if the file is to be opened for appending. |
69 | |||
70 | amb | 1139 | int readonly Set to 1 if the file is to be opened for reading. |
71 | amb | 110 | ++++++++++++++++++++++++++++++++++++++*/ |
72 | |||
73 | amb | 1123 | NodesX *NewNodeList(int append,int readonly) |
74 | amb | 110 | { |
75 | NodesX *nodesx; | ||
76 | |||
77 | amb | 213 | nodesx=(NodesX*)calloc(1,sizeof(NodesX)); |
78 | amb | 110 | |
79 | amb | 243 | assert(nodesx); /* Check calloc() worked */ |
80 | |||
81 | amb | 1120 | nodesx->filename =(char*)malloc(strlen(option_tmpdirname)+32); |
82 | nodesx->filename_tmp=(char*)malloc(strlen(option_tmpdirname)+32); | ||
83 | amb | 216 | |
84 | amb | 1120 | sprintf(nodesx->filename ,"%s/nodesx.parsed.mem",option_tmpdirname); |
85 | sprintf(nodesx->filename_tmp,"%s/nodesx.%p.tmp" ,option_tmpdirname,(void*)nodesx); | ||
86 | amb | 249 | |
87 | amb | 1123 | if(append || readonly) |
88 | if(ExistsFile(nodesx->filename)) | ||
89 | { | ||
90 | off_t size; | ||
91 | amb | 326 | |
92 | amb | 1123 | size=SizeFile(nodesx->filename); |
93 | amb | 326 | |
94 | amb | 1123 | nodesx->number=size/sizeof(NodeX); |
95 | amb | 1139 | |
96 | RenameFile(nodesx->filename,nodesx->filename_tmp); | ||
97 | amb | 1123 | } |
98 | amb | 326 | |
99 | amb | 1123 | if(append) |
100 | amb | 1139 | nodesx->fd=OpenFileAppend(nodesx->filename_tmp); |
101 | amb | 1123 | else if(!readonly) |
102 | amb | 1139 | nodesx->fd=OpenFileNew(nodesx->filename_tmp); |
103 | amb | 326 | else |
104 | amb | 1123 | nodesx->fd=-1; |
105 | amb | 326 | |
106 | amb | 110 | return(nodesx); |
107 | } | ||
108 | |||
109 | |||
110 | /*++++++++++++++++++++++++++++++++++++++ | ||
111 | amb | 226 | Free a node list. |
112 | |||
113 | amb | 681 | NodesX *nodesx The set of nodes to be freed. |
114 | amb | 1151 | |
115 | int preserve If set then the results file is to be preserved. | ||
116 | amb | 226 | ++++++++++++++++++++++++++++++++++++++*/ |
117 | |||
118 | amb | 1151 | void FreeNodeList(NodesX *nodesx,int preserve) |
119 | amb | 226 | { |
120 | amb | 1151 | if(preserve) |
121 | RenameFile(nodesx->filename_tmp,nodesx->filename); | ||
122 | else | ||
123 | DeleteFile(nodesx->filename_tmp); | ||
124 | amb | 1120 | |
125 | amb | 283 | free(nodesx->filename); |
126 | amb | 1120 | free(nodesx->filename_tmp); |
127 | amb | 226 | |
128 | if(nodesx->idata) | ||
129 | free(nodesx->idata); | ||
130 | |||
131 | amb | 552 | if(nodesx->gdata) |
132 | free(nodesx->gdata); | ||
133 | amb | 226 | |
134 | amb | 1101 | if(nodesx->pdata) |
135 | free(nodesx->pdata); | ||
136 | |||
137 | amb | 283 | if(nodesx->super) |
138 | free(nodesx->super); | ||
139 | |||
140 | amb | 226 | free(nodesx); |
141 | } | ||
142 | |||
143 | |||
144 | /*++++++++++++++++++++++++++++++++++++++ | ||
145 | amb | 493 | Append a single node to an unsorted node list. |
146 | amb | 243 | |
147 | amb | 681 | NodesX *nodesx The set of nodes to modify. |
148 | amb | 243 | |
149 | amb | 680 | node_t id The node identifier from the original OSM data. |
150 | amb | 110 | |
151 | amb | 252 | double latitude The latitude of the node. |
152 | amb | 110 | |
153 | amb | 252 | double longitude The longitude of the node. |
154 | amb | 469 | |
155 | amb | 529 | transports_t allow The allowed traffic types through the node. |
156 | amb | 537 | |
157 | amb | 1165 | nodeflags_t flags The flags to set for this node. |
158 | amb | 252 | ++++++++++++++++++++++++++++++++++++++*/ |
159 | amb | 110 | |
160 | amb | 1165 | void AppendNodeList(NodesX *nodesx,node_t id,double latitude,double longitude,transports_t allow,nodeflags_t flags) |
161 | amb | 252 | { |
162 | NodeX nodex; | ||
163 | amb | 249 | |
164 | amb | 252 | nodex.id=id; |
165 | nodex.latitude =radians_to_latlong(latitude); | ||
166 | nodex.longitude=radians_to_latlong(longitude); | ||
167 | amb | 469 | nodex.allow=allow; |
168 | amb | 538 | nodex.flags=flags; |
169 | amb | 252 | |
170 | WriteFile(nodesx->fd,&nodex,sizeof(NodeX)); | ||
171 | |||
172 | amb | 650 | nodesx->number++; |
173 | amb | 466 | |
174 | amb | 650 | assert(nodesx->number<NODE_FAKE); /* NODE_FAKE marks the high-water mark for real nodes. */ |
175 | amb | 110 | } |
176 | |||
177 | |||
178 | /*++++++++++++++++++++++++++++++++++++++ | ||
179 | amb | 1120 | Finish appending nodes and change the filename over. |
180 | |||
181 | NodesX *nodesx The nodes that have been appended. | ||
182 | ++++++++++++++++++++++++++++++++++++++*/ | ||
183 | |||
184 | amb | 1151 | void FinishNodeList(NodesX *nodesx) |
185 | amb | 1120 | { |
186 | amb | 1136 | if(nodesx->fd!=-1) |
187 | nodesx->fd=CloseFile(nodesx->fd); | ||
188 | amb | 1120 | } |
189 | |||
190 | |||
191 | /*++++++++++++++++++++++++++++++++++++++ | ||
192 | amb | 1160 | Find a particular node index. |
193 | |||
194 | index_t IndexNodeX Returns the index of the extended node with the specified id. | ||
195 | |||
196 | NodesX *nodesx The set of nodes to use. | ||
197 | |||
198 | node_t id The node id to look for. | ||
199 | ++++++++++++++++++++++++++++++++++++++*/ | ||
200 | |||
201 | index_t IndexNodeX(NodesX *nodesx,node_t id) | ||
202 | { | ||
203 | index_t start=0; | ||
204 | index_t end=nodesx->number-1; | ||
205 | index_t mid; | ||
206 | |||
207 | /* Binary search - search key exact match only is required. | ||
208 | * | ||
209 | * # <- start | Check mid and move start or end if it doesn't match | ||
210 | * # | | ||
211 | * # | Since an exact match is wanted we can set end=mid-1 | ||
212 | * # <- mid | or start=mid+1 because we know that mid doesn't match. | ||
213 | * # | | ||
214 | * # | Eventually either end=start or end=start+1 and one of | ||
215 | * # <- end | start or end is the wanted one. | ||
216 | */ | ||
217 | |||
218 | if(end<start) /* There are no nodes */ | ||
219 | return(NO_NODE); | ||
220 | else if(id<nodesx->idata[start]) /* Check key is not before start */ | ||
221 | return(NO_NODE); | ||
222 | else if(id>nodesx->idata[end]) /* Check key is not after end */ | ||
223 | return(NO_NODE); | ||
224 | else | ||
225 | { | ||
226 | do | ||
227 | { | ||
228 | mid=(start+end)/2; /* Choose mid point */ | ||
229 | |||
230 | if(nodesx->idata[mid]<id) /* Mid point is too low */ | ||
231 | start=mid+1; | ||
232 | else if(nodesx->idata[mid]>id) /* Mid point is too high */ | ||
233 | end=mid?(mid-1):mid; | ||
234 | else /* Mid point is correct */ | ||
235 | return(mid); | ||
236 | } | ||
237 | while((end-start)>1); | ||
238 | |||
239 | if(nodesx->idata[start]==id) /* Start is correct */ | ||
240 | return(start); | ||
241 | |||
242 | if(nodesx->idata[end]==id) /* End is correct */ | ||
243 | return(end); | ||
244 | } | ||
245 | |||
246 | return(NO_NODE); | ||
247 | } | ||
248 | |||
249 | |||
250 | /*++++++++++++++++++++++++++++++++++++++ | ||
251 | amb | 680 | Sort the node list. |
252 | amb | 110 | |
253 | amb | 681 | NodesX *nodesx The set of nodes to modify. |
254 | amb | 110 | ++++++++++++++++++++++++++++++++++++++*/ |
255 | |||
256 | amb | 681 | void SortNodeList(NodesX *nodesx) |
257 | amb | 110 | { |
258 | amb | 263 | int fd; |
259 | amb | 650 | index_t xnumber; |
260 | amb | 110 | |
261 | amb | 263 | /* Print the start message */ |
262 | |||
263 | amb | 519 | printf_first("Sorting Nodes"); |
264 | amb | 132 | |
265 | amb | 555 | /* Re-open the file read-only and a new file writeable */ |
266 | |||
267 | amb | 1120 | nodesx->fd=ReOpenFile(nodesx->filename_tmp); |
268 | amb | 260 | |
269 | amb | 1120 | DeleteFile(nodesx->filename_tmp); |
270 | amb | 271 | |
271 | amb | 1120 | fd=OpenFileNew(nodesx->filename_tmp); |
272 | amb | 271 | |
273 | amb | 252 | /* Allocate the array of indexes */ |
274 | amb | 249 | |
275 | amb | 650 | nodesx->idata=(node_t*)malloc(nodesx->number*sizeof(node_t)); |
276 | amb | 249 | |
277 | amb | 252 | assert(nodesx->idata); /* Check malloc() worked */ |
278 | amb | 249 | |
279 | amb | 1097 | /* Sort the nodes by ID and index them */ |
280 | amb | 249 | |
281 | amb | 650 | xnumber=nodesx->number; |
282 | |||
283 | amb | 271 | sortnodesx=nodesx; |
284 | amb | 110 | |
285 | amb | 1106 | nodesx->number=filesort_fixed(nodesx->fd,fd,sizeof(NodeX),NULL, |
286 | (int (*)(const void*,const void*))sort_by_id, | ||
287 | (int (*)(void*,index_t))deduplicate_and_index_by_id); | ||
288 | amb | 252 | |
289 | amb | 555 | /* Close the files */ |
290 | amb | 260 | |
291 | amb | 612 | nodesx->fd=CloseFile(nodesx->fd); |
292 | amb | 257 | CloseFile(fd); |
293 | amb | 252 | |
294 | amb | 263 | /* Print the final message */ |
295 | |||
296 | amb | 790 | printf_last("Sorted Nodes: Nodes=%"Pindex_t" Duplicates=%"Pindex_t,xnumber,xnumber-nodesx->number); |
297 | amb | 110 | } |
298 | |||
299 | |||
300 | /*++++++++++++++++++++++++++++++++++++++ | ||
301 | Sort the nodes into id order. | ||
302 | |||
303 | int sort_by_id Returns the comparison of the id fields. | ||
304 | |||
305 | amb | 271 | NodeX *a The first extended node. |
306 | amb | 110 | |
307 | amb | 271 | NodeX *b The second extended node. |
308 | amb | 110 | ++++++++++++++++++++++++++++++++++++++*/ |
309 | |||
310 | amb | 271 | static int sort_by_id(NodeX *a,NodeX *b) |
311 | amb | 110 | { |
312 | amb | 271 | node_t a_id=a->id; |
313 | node_t b_id=b->id; | ||
314 | amb | 252 | |
315 | if(a_id<b_id) | ||
316 | return(-1); | ||
317 | else if(a_id>b_id) | ||
318 | amb | 249 | return(1); |
319 | amb | 110 | else |
320 | amb | 1140 | return(-FILESORT_PRESERVE_ORDER(a,b)); /* latest version first */ |
321 | amb | 110 | } |
322 | |||
323 | |||
324 | amb | 271 | /*++++++++++++++++++++++++++++++++++++++ |
325 | amb | 680 | Create the index of identifiers and discard duplicate nodes. |
326 | amb | 252 | |
327 | amb | 680 | int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise 0. |
328 | amb | 273 | |
329 | amb | 271 | NodeX *nodex The extended node. |
330 | amb | 252 | |
331 | amb | 1106 | index_t index The number of sorted nodes that have already been written to the output file. |
332 | amb | 271 | ++++++++++++++++++++++++++++++++++++++*/ |
333 | |||
334 | amb | 680 | static int deduplicate_and_index_by_id(NodeX *nodex,index_t index) |
335 | amb | 271 | { |
336 | amb | 1140 | static node_t previd=NO_NODE_ID; |
337 | |||
338 | if(nodex->id!=previd) | ||
339 | amb | 273 | { |
340 | amb | 1140 | previd=nodex->id; |
341 | amb | 271 | |
342 | amb | 1140 | if(nodex->flags&NODE_DELETED) |
343 | return(0); | ||
344 | else | ||
345 | { | ||
346 | sortnodesx->idata[index]=nodex->id; | ||
347 | |||
348 | return(1); | ||
349 | } | ||
350 | amb | 273 | } |
351 | amb | 812 | else |
352 | { | ||
353 | amb | 1146 | if(!option_changes) |
354 | logerror("Node %"Pnode_t" is duplicated\n",nodex->id); | ||
355 | amb | 273 | |
356 | amb | 812 | return(0); |
357 | } | ||
358 | amb | 271 | } |
359 | |||
360 | |||
361 | amb | 110 | /*++++++++++++++++++++++++++++++++++++++ |
362 | amb | 1160 | Remove any nodes that are not part of a highway. |
363 | |||
364 | NodesX *nodesx The set of nodes to modify. | ||
365 | |||
366 | SegmentsX *segmentsx The set of segments to use. | ||
367 | |||
368 | int preserve If set to 1 then keep the old data file otherwise delete it. | ||
369 | ++++++++++++++++++++++++++++++++++++++*/ | ||
370 | |||
371 | void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx,int preserve) | ||
372 | { | ||
373 | NodeX nodex; | ||
374 | index_t total=0,highway=0,nothighway=0; | ||
375 | int fd; | ||
376 | |||
377 | /* Print the start message */ | ||
378 | |||
379 | printf_first("Checking Nodes: Nodes=0"); | ||
380 | |||
381 | /* Re-open the file read-only and a new file writeable */ | ||
382 | |||
383 | nodesx->fd=ReOpenFile(nodesx->filename_tmp); | ||
384 | |||
385 | if(preserve) | ||
386 | RenameFile(nodesx->filename_tmp,nodesx->filename); | ||
387 | else | ||
388 | DeleteFile(nodesx->filename_tmp); | ||
389 | |||
390 | fd=OpenFileNew(nodesx->filename_tmp); | ||
391 | |||
392 | /* Modify the on-disk image */ | ||
393 | |||
394 | while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX))) | ||
395 | { | ||
396 | if(!IsBitSet(segmentsx->usednode,total)) | ||
397 | nothighway++; | ||
398 | else | ||
399 | { | ||
400 | nodex.id=highway; | ||
401 | nodesx->idata[highway]=nodesx->idata[total]; | ||
402 | |||
403 | WriteFile(fd,&nodex,sizeof(NodeX)); | ||
404 | |||
405 | highway++; | ||
406 | } | ||
407 | |||
408 | total++; | ||
409 | |||
410 | if(!(total%10000)) | ||
411 | printf_middle("Checking Nodes: Nodes=%"Pindex_t" Highway=%"Pindex_t" not-Highway=%"Pindex_t,total,highway,nothighway); | ||
412 | } | ||
413 | |||
414 | nodesx->number=highway; | ||
415 | |||
416 | /* Close the files */ | ||
417 | |||
418 | nodesx->fd=CloseFile(nodesx->fd); | ||
419 | CloseFile(fd); | ||
420 | |||
421 | /* Free the now-unneeded index */ | ||
422 | |||
423 | free(segmentsx->usednode); | ||
424 | segmentsx->usednode=NULL; | ||
425 | |||
426 | /* Print the final message */ | ||
427 | |||
428 | printf_last("Checked Nodes: Nodes=%"Pindex_t" Highway=%"Pindex_t" not-Highway=%"Pindex_t,total,highway,nothighway); | ||
429 | } | ||
430 | |||
431 | |||
432 | /*++++++++++++++++++++++++++++++++++++++ | ||
433 | Remove any nodes that have been pruned. | ||
434 | |||
435 | NodesX *nodesx The set of nodes to prune. | ||
436 | |||
437 | SegmentsX *segmentsx The set of segments to use. | ||
438 | ++++++++++++++++++++++++++++++++++++++*/ | ||
439 | |||
440 | void RemovePrunedNodes(NodesX *nodesx,SegmentsX *segmentsx) | ||
441 | { | ||
442 | NodeX nodex; | ||
443 | index_t total=0,pruned=0,notpruned=0; | ||
444 | int fd; | ||
445 | |||
446 | /* Print the start message */ | ||
447 | |||
448 | printf_first("Deleting Pruned Nodes: Nodes=0 Pruned=0"); | ||
449 | |||
450 | /* Allocate the array of indexes */ | ||
451 | |||
452 | nodesx->pdata=(index_t*)malloc(nodesx->number*sizeof(index_t)); | ||
453 | |||
454 | assert(nodesx->pdata); /* Check malloc() worked */ | ||
455 | |||
456 | /* Re-open the file read-only and a new file writeable */ | ||
457 | |||
458 | nodesx->fd=ReOpenFile(nodesx->filename_tmp); | ||
459 | |||
460 | DeleteFile(nodesx->filename_tmp); | ||
461 | |||
462 | fd=OpenFileNew(nodesx->filename_tmp); | ||
463 | |||
464 | /* Modify the on-disk image */ | ||
465 | |||
466 | while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX))) | ||
467 | { | ||
468 | if(segmentsx->firstnode[total]==NO_SEGMENT) | ||
469 | { | ||
470 | pruned++; | ||
471 | |||
472 | nodesx->pdata[total]=NO_NODE; | ||
473 | } | ||
474 | else | ||
475 | { | ||
476 | nodex.id=notpruned; | ||
477 | nodesx->pdata[total]=notpruned; | ||
478 | |||
479 | WriteFile(fd,&nodex,sizeof(NodeX)); | ||
480 | |||
481 | notpruned++; | ||
482 | } | ||
483 | |||
484 | total++; | ||
485 | |||
486 | if(!(total%10000)) | ||
487 | printf_middle("Deleting Pruned Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,total,pruned); | ||
488 | } | ||
489 | |||
490 | nodesx->number=notpruned; | ||
491 | |||
492 | /* Close the files */ | ||
493 | |||
494 | nodesx->fd=CloseFile(nodesx->fd); | ||
495 | CloseFile(fd); | ||
496 | |||
497 | /* Print the final message */ | ||
498 | |||
499 | printf_last("Deleted Pruned Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,total,pruned); | ||
500 | } | ||
501 | |||
502 | |||
503 | /*++++++++++++++++++++++++++++++++++++++ | ||
504 | amb | 212 | Sort the node list geographically. |
505 | |||
506 | amb | 681 | NodesX *nodesx The set of nodes to modify. |
507 | amb | 212 | ++++++++++++++++++++++++++++++++++++++*/ |
508 | |||
509 | amb | 681 | void SortNodeListGeographically(NodesX *nodesx) |
510 | amb | 212 | { |
511 | amb | 281 | int fd; |
512 | amb | 1109 | ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin; |
513 | amb | 212 | |
514 | amb | 1109 | /* While we are here we can work out the range of data */ |
515 | |||
516 | lat_min=radians_to_latlong( 2); | ||
517 | lat_max=radians_to_latlong(-2); | ||
518 | lon_min=radians_to_latlong( 4); | ||
519 | lon_max=radians_to_latlong(-4); | ||
520 | |||
521 | amb | 263 | /* Print the start message */ |
522 | |||
523 | amb | 1101 | printf_first("Sorting Nodes Geographically"); |
524 | amb | 212 | |
525 | amb | 552 | /* Allocate the memory for the geographical index array */ |
526 | |||
527 | nodesx->gdata=(index_t*)malloc(nodesx->number*sizeof(index_t)); | ||
528 | |||
529 | assert(nodesx->gdata); /* Check malloc() worked */ | ||
530 | |||
531 | amb | 555 | /* Re-open the file read-only and a new file writeable */ |
532 | amb | 212 | |
533 | amb | 1120 | nodesx->fd=ReOpenFile(nodesx->filename_tmp); |
534 | amb | 243 | |
535 | amb | 1120 | DeleteFile(nodesx->filename_tmp); |
536 | amb | 212 | |
537 | amb | 1120 | fd=OpenFileNew(nodesx->filename_tmp); |
538 | amb | 212 | |
539 | amb | 1097 | /* Sort nodes geographically and index them */ |
540 | amb | 252 | |
541 | amb | 281 | sortnodesx=nodesx; |
542 | amb | 257 | |
543 | amb | 1106 | filesort_fixed(nodesx->fd,fd,sizeof(NodeX),NULL, |
544 | (int (*)(const void*,const void*))sort_by_lat_long, | ||
545 | (int (*)(void*,index_t))index_by_lat_long); | ||
546 | amb | 257 | |
547 | amb | 555 | /* Close the files */ |
548 | amb | 257 | |
549 | amb | 612 | nodesx->fd=CloseFile(nodesx->fd); |
550 | amb | 281 | CloseFile(fd); |
551 | amb | 257 | |
552 | amb | 1109 | /* Free the memory */ |
553 | |||
554 | free(nodesx->super); | ||
555 | nodesx->super=NULL; | ||
556 | |||
557 | /* Work out the number of bins */ | ||
558 | |||
559 | lat_min_bin=latlong_to_bin(lat_min); | ||
560 | lon_min_bin=latlong_to_bin(lon_min); | ||
561 | lat_max_bin=latlong_to_bin(lat_max); | ||
562 | lon_max_bin=latlong_to_bin(lon_max); | ||
563 | |||
564 | nodesx->latzero=lat_min_bin; | ||
565 | nodesx->lonzero=lon_min_bin; | ||
566 | |||
567 | nodesx->latbins=(lat_max_bin-lat_min_bin)+1; | ||
568 | nodesx->lonbins=(lon_max_bin-lon_min_bin)+1; | ||
569 | |||
570 | amb | 263 | /* Print the final message */ |
571 | amb | 257 | |
572 | amb | 1101 | printf_last("Sorted Nodes Geographically: Nodes=%"Pindex_t,nodesx->number); |
573 | amb | 212 | } |
574 | |||
575 | |||
576 | /*++++++++++++++++++++++++++++++++++++++ | ||
577 | amb | 680 | Sort the nodes into latitude and longitude order (first by longitude bin |
578 | number, then by latitude bin number and then by exact longitude and then by | ||
579 | exact latitude). | ||
580 | amb | 110 | |
581 | int sort_by_lat_long Returns the comparison of the latitude and longitude fields. | ||
582 | |||
583 | amb | 281 | NodeX *a The first extended node. |
584 | amb | 110 | |
585 | amb | 281 | NodeX *b The second extended node. |
586 | amb | 110 | ++++++++++++++++++++++++++++++++++++++*/ |
587 | |||
588 | amb | 281 | static int sort_by_lat_long(NodeX *a,NodeX *b) |
589 | amb | 110 | { |
590 | amb | 1098 | ll_bin_t a_lon=latlong_to_bin(a->longitude); |
591 | ll_bin_t b_lon=latlong_to_bin(b->longitude); | ||
592 | amb | 110 | |
593 | amb | 1098 | if(a_lon<b_lon) |
594 | return(-1); | ||
595 | else if(a_lon>b_lon) | ||
596 | amb | 949 | return(1); |
597 | amb | 110 | else |
598 | { | ||
599 | amb | 1098 | ll_bin_t a_lat=latlong_to_bin(a->latitude); |
600 | ll_bin_t b_lat=latlong_to_bin(b->latitude); | ||
601 | amb | 110 | |
602 | amb | 1098 | if(a_lat<b_lat) |
603 | amb | 110 | return(-1); |
604 | amb | 1098 | else if(a_lat>b_lat) |
605 | amb | 110 | return(1); |
606 | else | ||
607 | amb | 281 | { |
608 | amb | 1098 | if(a->longitude<b->longitude) |
609 | amb | 281 | return(-1); |
610 | amb | 1098 | else if(a->longitude>b->longitude) |
611 | amb | 281 | return(1); |
612 | else | ||
613 | amb | 664 | { |
614 | amb | 1098 | if(a->latitude<b->latitude) |
615 | amb | 664 | return(-1); |
616 | amb | 1098 | else if(a->latitude>b->latitude) |
617 | amb | 664 | return(1); |
618 | amb | 1098 | } |
619 | amb | 949 | |
620 | amb | 1118 | return(FILESORT_PRESERVE_ORDER(a,b)); |
621 | amb | 281 | } |
622 | amb | 110 | } |
623 | } | ||
624 | |||
625 | |||
626 | /*++++++++++++++++++++++++++++++++++++++ | ||
627 | amb | 1098 | Create the index between the sorted and unsorted nodes. |
628 | amb | 281 | |
629 | amb | 1098 | int index_by_lat_long Return 1 if the value is to be kept, otherwise 0. |
630 | amb | 281 | |
631 | NodeX *nodex The extended node. | ||
632 | |||
633 | amb | 1106 | index_t index The number of sorted nodes that have already been written to the output file. |
634 | amb | 281 | ++++++++++++++++++++++++++++++++++++++*/ |
635 | |||
636 | amb | 1098 | static int index_by_lat_long(NodeX *nodex,index_t index) |
637 | amb | 281 | { |
638 | amb | 552 | sortnodesx->gdata[nodex->id]=index; |
639 | |||
640 | amb | 1109 | if(IsBitSet(sortnodesx->super,nodex->id)) |
641 | nodex->flags|=NODE_SUPER; | ||
642 | |||
643 | if(nodex->latitude<lat_min) | ||
644 | lat_min=nodex->latitude; | ||
645 | if(nodex->latitude>lat_max) | ||
646 | lat_max=nodex->latitude; | ||
647 | if(nodex->longitude<lon_min) | ||
648 | lon_min=nodex->longitude; | ||
649 | if(nodex->longitude>lon_max) | ||
650 | lon_max=nodex->longitude; | ||
651 | |||
652 | amb | 281 | return(1); |
653 | } | ||
654 | |||
655 | |||
656 | /*++++++++++++++++++++++++++++++++++++++ | ||
657 | amb | 680 | Save the final node list database to a file. |
658 | amb | 285 | |
659 | amb | 681 | NodesX *nodesx The set of nodes to save. |
660 | amb | 285 | |
661 | const char *filename The name of the file to save. | ||
662 | amb | 1109 | |
663 | SegmentsX *segmentsx The set of segments to use. | ||
664 | amb | 285 | ++++++++++++++++++++++++++++++++++++++*/ |
665 | |||
666 | amb | 1109 | void SaveNodeList(NodesX *nodesx,const char *filename,SegmentsX *segmentsx) |
667 | amb | 285 | { |
668 | index_t i; | ||
669 | int fd; | ||
670 | amb | 500 | NodesFile nodesfile={0}; |
671 | amb | 780 | index_t super_number=0; |
672 | amb | 788 | ll_bin2_t latlonbin=0,maxlatlonbins; |
673 | amb | 780 | index_t *offsets; |
674 | amb | 285 | |
675 | /* Print the start message */ | ||
676 | |||
677 | amb | 519 | printf_first("Writing Nodes: Nodes=0"); |
678 | amb | 285 | |
679 | amb | 553 | /* Allocate the memory for the geographical offsets array */ |
680 | |||
681 | offsets=(index_t*)malloc((nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t)); | ||
682 | |||
683 | assert(offsets); /* Check malloc() worked */ | ||
684 | |||
685 | latlonbin=0; | ||
686 | |||
687 | amb | 556 | /* Re-open the file */ |
688 | amb | 285 | |
689 | amb | 1120 | nodesx->fd=ReOpenFile(nodesx->filename_tmp); |
690 | amb | 285 | |
691 | amb | 461 | /* Write out the nodes data */ |
692 | amb | 285 | |
693 | amb | 502 | fd=OpenFileNew(filename); |
694 | amb | 285 | |
695 | amb | 553 | SeekFile(fd,sizeof(NodesFile)+(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t)); |
696 | amb | 285 | |
697 | amb | 461 | for(i=0;i<nodesx->number;i++) |
698 | amb | 285 | { |
699 | amb | 556 | NodeX nodex; |
700 | amb | 944 | Node node={0}; |
701 | amb | 553 | ll_bin_t latbin,lonbin; |
702 | amb | 780 | ll_bin2_t llbin; |
703 | amb | 285 | |
704 | amb | 556 | ReadFile(nodesx->fd,&nodex,sizeof(NodeX)); |
705 | |||
706 | amb | 553 | /* Create the Node */ |
707 | |||
708 | amb | 556 | node.latoffset=latlong_to_off(nodex.latitude); |
709 | node.lonoffset=latlong_to_off(nodex.longitude); | ||
710 | amb | 1109 | node.firstseg=segmentsx->firstnode[nodesx->gdata[nodex.id]]; |
711 | amb | 556 | node.allow=nodex.allow; |
712 | node.flags=nodex.flags; | ||
713 | amb | 552 | |
714 | if(node.flags&NODE_SUPER) | ||
715 | amb | 461 | super_number++; |
716 | |||
717 | amb | 553 | /* Work out the offsets */ |
718 | |||
719 | amb | 556 | latbin=latlong_to_bin(nodex.latitude )-nodesx->latzero; |
720 | lonbin=latlong_to_bin(nodex.longitude)-nodesx->lonzero; | ||
721 | amb | 553 | llbin=lonbin*nodesx->latbins+latbin; |
722 | |||
723 | for(;latlonbin<=llbin;latlonbin++) | ||
724 | offsets[latlonbin]=i; | ||
725 | |||
726 | /* Write the data */ | ||
727 | |||
728 | amb | 552 | WriteFile(fd,&node,sizeof(Node)); |
729 | amb | 285 | |
730 | if(!((i+1)%10000)) | ||
731 | amb | 790 | printf_middle("Writing Nodes: Nodes=%"Pindex_t,i+1); |
732 | amb | 285 | } |
733 | |||
734 | amb | 556 | /* Close the file */ |
735 | |||
736 | amb | 612 | nodesx->fd=CloseFile(nodesx->fd); |
737 | amb | 556 | |
738 | amb | 553 | /* Finish off the offset indexing and write them out */ |
739 | |||
740 | amb | 788 | maxlatlonbins=nodesx->latbins*nodesx->lonbins; |
741 | |||
742 | for(;latlonbin<=maxlatlonbins;latlonbin++) | ||
743 | amb | 553 | offsets[latlonbin]=nodesx->number; |
744 | |||
745 | SeekFile(fd,sizeof(NodesFile)); | ||
746 | WriteFile(fd,offsets,(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t)); | ||
747 | |||
748 | amb | 795 | free(offsets); |
749 | |||
750 | amb | 461 | /* Write out the header structure */ |
751 | |||
752 | nodesfile.number=nodesx->number; | ||
753 | nodesfile.snumber=super_number; | ||
754 | |||
755 | nodesfile.latbins=nodesx->latbins; | ||
756 | nodesfile.lonbins=nodesx->lonbins; | ||
757 | |||
758 | nodesfile.latzero=nodesx->latzero; | ||
759 | nodesfile.lonzero=nodesx->lonzero; | ||
760 | |||
761 | SeekFile(fd,0); | ||
762 | WriteFile(fd,&nodesfile,sizeof(NodesFile)); | ||
763 | |||
764 | amb | 285 | CloseFile(fd); |
765 | |||
766 | /* Print the final message */ | ||
767 | |||
768 | amb | 790 | printf_last("Wrote Nodes: Nodes=%"Pindex_t,nodesx->number); |
769 | amb | 285 | } |
Properties
Name | Value |
---|---|
cvs:description | Extended nodes functions. |