Routino SVN Repository Browser

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

ViewVC logotype

Contents of /trunk/src/nodesx.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1151 - (show annotations) (download) (as text)
Sun Nov 18 17:24:50 2012 UTC (12 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 18610 byte(s)
Using --parse-only and --preserve must sort the data so that it is ready to
apply the changes.

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

Properties

Name Value
cvs:description Extended nodes functions.