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 1171 - (show annotations) (download) (as text)
Tue Nov 27 19:19:01 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 18684 byte(s)
Don't log an error for duplicated nodes, ways or relations because it can only
occur when applying changes or if using multiple geographically overlapping
files and neither is a data error.

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

Properties

Name Value
cvs:description Extended nodes functions.