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 1099 - (show annotations) (download) (as text)
Sat Oct 20 13:12:44 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 18238 byte(s)
Mark pruned nodes in the node index.

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

Properties

Name Value
cvs:description Extended nodes functions.