1 /***************************************
2 $Header: /home/amb/routino/src/RCS/nodesx.c,v 1.76 2010/11/13 14:22:28 amb Exp $
4 Extented Node data type functions.
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008-2010 Andrew M. Bishop
10 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.
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.
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 ***************************************/
36 #include "segmentsx.h"
43 #include "functions.h"
48 /*+ The command line '--tmpdir' option or its default value. +*/
49 extern char *option_tmpdirname;
51 /*+ A temporary file-local variable for use by the sort functions. +*/
52 static NodesX *sortnodesx;
56 static int sort_by_id(NodeX *a,NodeX *b);
57 static int index_by_id(NodeX *nodex,index_t index);
59 static int sort_by_lat_long(NodeX *a,NodeX *b);
60 static int index_by_lat_long(NodeX *nodex,index_t index);
63 /*++++++++++++++++++++++++++++++++++++++
64 Allocate a new node list (create a new file or open an existing one).
66 NodesX *NewNodeList Returns the node list.
68 int append Set to 1 if the file is to be opened for appending (now or later).
69 ++++++++++++++++++++++++++++++++++++++*/
71 NodesX *NewNodeList(int append)
75 nodesx=(NodesX*)calloc(1,sizeof(NodesX));
77 assert(nodesx); /* Check calloc() worked */
79 nodesx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
82 sprintf(nodesx->filename,"%s/nodesx.input.tmp",option_tmpdirname);
84 sprintf(nodesx->filename,"%s/nodesx.%p.tmp",option_tmpdirname,nodesx);
87 nodesx->nfilename=(char*)malloc(strlen(option_tmpdirname)+32);
89 sprintf(nodesx->nfilename,"%s/nodes.%p.tmp",option_tmpdirname,nodesx);
96 nodesx->fd=OpenFileAppend(nodesx->filename);
98 size=SizeFile(nodesx->filename);
100 nodesx->xnumber=size/sizeof(NodeX);
103 nodesx->fd=OpenFileNew(nodesx->filename);
109 /*++++++++++++++++++++++++++++++++++++++
112 NodesX *nodesx The list to be freed.
114 int keep Set to 1 if the file is to be kept.
115 ++++++++++++++++++++++++++++++++++++++*/
117 void FreeNodeList(NodesX *nodesx,int keep)
120 DeleteFile(nodesx->filename);
122 free(nodesx->filename);
133 DeleteFile(nodesx->nfilename);
135 free(nodesx->nfilename);
142 free(nodesx->offsets);
148 /*++++++++++++++++++++++++++++++++++++++
149 Append a single node to an unsorted node list.
151 NodesX* nodesx The set of nodes to process.
153 node_t id The node identification.
155 double latitude The latitude of the node.
157 double longitude The longitude of the node.
159 allow_t allow The allowed traffic types through the node.
160 ++++++++++++++++++++++++++++++++++++++*/
162 void AppendNode(NodesX* nodesx,node_t id,double latitude,double longitude,allow_t allow)
167 nodex.latitude =radians_to_latlong(latitude);
168 nodex.longitude=radians_to_latlong(longitude);
171 WriteFile(nodesx->fd,&nodex,sizeof(NodeX));
175 assert(nodesx->xnumber<NODE_FAKE); /* NODE_FAKE marks the high-water mark for real nodes. */
179 /*++++++++++++++++++++++++++++++++++++++
180 Sort the node list (i.e. create the sortable indexes).
182 NodesX* nodesx The set of nodes to process.
183 ++++++++++++++++++++++++++++++++++++++*/
185 void SortNodeList(NodesX* nodesx)
189 /* Print the start message */
191 printf_first("Sorting Nodes");
193 /* Close the files and re-open them (finished appending) */
195 CloseFile(nodesx->fd);
196 nodesx->fd=ReOpenFile(nodesx->filename);
198 DeleteFile(nodesx->filename);
200 fd=OpenFileNew(nodesx->filename);
202 /* Allocate the array of indexes */
204 nodesx->idata=(node_t*)malloc(nodesx->xnumber*sizeof(node_t));
206 assert(nodesx->idata); /* Check malloc() worked */
208 /* Sort by node indexes */
212 filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))index_by_id);
214 /* Close the files and re-open them */
216 CloseFile(nodesx->fd);
219 nodesx->fd=ReOpenFile(nodesx->filename);
221 /* Print the final message */
223 printf_last("Sorted Nodes: Nodes=%d Duplicates=%d",nodesx->xnumber,nodesx->xnumber-nodesx->number);
227 /*++++++++++++++++++++++++++++++++++++++
228 Sort the nodes into id order.
230 int sort_by_id Returns the comparison of the id fields.
232 NodeX *a The first extended node.
234 NodeX *b The second extended node.
235 ++++++++++++++++++++++++++++++++++++++*/
237 static int sort_by_id(NodeX *a,NodeX *b)
251 /*++++++++++++++++++++++++++++++++++++++
252 Index the nodes after sorting.
254 int index_by_id Return 1 if the value is to be kept, otherwise zero.
256 NodeX *nodex The extended node.
258 index_t index The index of this node in the total.
259 ++++++++++++++++++++++++++++++++++++++*/
261 static int index_by_id(NodeX *nodex,index_t index)
263 if(index==0 || sortnodesx->idata[index-1]!=nodex->id)
265 sortnodesx->idata[index]=nodex->id;
267 sortnodesx->number++;
276 /*++++++++++++++++++++++++++++++++++++++
277 Sort the node list geographically.
279 NodesX* nodesx The set of nodes to process.
280 ++++++++++++++++++++++++++++++++++++++*/
282 void SortNodeListGeographically(NodesX* nodesx)
286 /* Print the start message */
288 printf_first("Sorting Nodes Geographically");
290 /* Allocate the memory for the geographical offsets array */
292 nodesx->offsets=(index_t*)malloc((nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
296 /* Close the files and re-open them */
298 CloseFile(nodesx->fd);
299 nodesx->fd=ReOpenFile(nodesx->filename);
301 DeleteFile(nodesx->filename);
303 fd=OpenFileNew(nodesx->filename);
305 /* Sort geographically */
309 filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_lat_long,(int (*)(void*,index_t))index_by_lat_long);
311 /* Close the files and re-open them */
313 CloseFile(nodesx->fd);
316 nodesx->fd=ReOpenFile(nodesx->filename);
318 /* Finish off the indexing */
320 for(;nodesx->latlonbin<=(nodesx->latbins*nodesx->lonbins);nodesx->latlonbin++)
321 nodesx->offsets[nodesx->latlonbin]=nodesx->number;
323 /* Print the final message */
325 printf_last("Sorted Nodes Geographically");
329 /*++++++++++++++++++++++++++++++++++++++
330 Sort the nodes into latitude and longitude order.
332 int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
334 NodeX *a The first extended node.
336 NodeX *b The second extended node.
337 ++++++++++++++++++++++++++++++++++++++*/
339 static int sort_by_lat_long(NodeX *a,NodeX *b)
341 ll_bin_t a_lon=latlong_to_bin(a->longitude);
342 ll_bin_t b_lon=latlong_to_bin(b->longitude);
350 ll_bin_t a_lat=latlong_to_bin(a->latitude);
351 ll_bin_t b_lat=latlong_to_bin(b->latitude);
359 #ifdef REGRESSION_TESTING
360 // Need this for regression testing because filesort_heapsort() is not order
361 // preserving like qsort() is (or was when tested).
378 /*++++++++++++++++++++++++++++++++++++++
379 Index the nodes after sorting.
381 int index_by_lat_long Return 1 if the value is to be kept, otherwise zero.
383 NodeX *nodex The extended node.
385 index_t index The index of this node in the total.
386 ++++++++++++++++++++++++++++++++++++++*/
388 static int index_by_lat_long(NodeX *nodex,index_t index)
390 /* Work out the offsets */
392 ll_bin_t latbin=latlong_to_bin(nodex->latitude )-sortnodesx->latzero;
393 ll_bin_t lonbin=latlong_to_bin(nodex->longitude)-sortnodesx->lonzero;
394 int llbin=lonbin*sortnodesx->latbins+latbin;
396 for(;sortnodesx->latlonbin<=llbin;sortnodesx->latlonbin++)
397 sortnodesx->offsets[sortnodesx->latlonbin]=index;
403 /*++++++++++++++++++++++++++++++++++++++
404 Find a particular node index.
406 index_t IndexNodeX Returns the index of the extended node with the specified id.
408 NodesX* nodesx The set of nodes to process.
410 node_t id The node id to look for.
411 ++++++++++++++++++++++++++++++++++++++*/
413 index_t IndexNodeX(NodesX* nodesx,node_t id)
416 int end=nodesx->number-1;
419 /* Binary search - search key exact match only is required.
421 * # <- start | Check mid and move start or end if it doesn't match
423 * # | Since an exact match is wanted we can set end=mid-1
424 * # <- mid | or start=mid+1 because we know that mid doesn't match.
426 * # | Eventually either end=start or end=start+1 and one of
427 * # <- end | start or end is the wanted one.
430 if(end<start) /* There are no nodes */
432 else if(id<nodesx->idata[start]) /* Check key is not before start */
434 else if(id>nodesx->idata[end]) /* Check key is not after end */
440 mid=(start+end)/2; /* Choose mid point */
442 if(nodesx->idata[mid]<id) /* Mid point is too low */
444 else if(nodesx->idata[mid]>id) /* Mid point is too high */
446 else /* Mid point is correct */
449 while((end-start)>1);
451 if(nodesx->idata[start]==id) /* Start is correct */
454 if(nodesx->idata[end]==id) /* End is correct */
462 /*++++++++++++++++++++++++++++++++++++++
463 Remove any nodes that are not part of a highway.
465 NodesX *nodesx The complete node list.
467 SegmentsX *segmentsx The list of segments.
468 ++++++++++++++++++++++++++++++++++++++*/
470 void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
473 int total=0,highway=0,nothighway=0;
474 ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
475 latlong_t lat_min,lat_max,lon_min,lon_max;
478 /* Print the start message */
480 printf_first("Checking: Nodes=0");
482 /* While we are here we can work out the range of data */
484 lat_min=radians_to_latlong( 2);
485 lat_max=radians_to_latlong(-2);
486 lon_min=radians_to_latlong( 4);
487 lon_max=radians_to_latlong(-4);
489 /* Modify the on-disk image */
491 DeleteFile(nodesx->filename);
493 fd=OpenFileNew(nodesx->filename);
494 SeekFile(nodesx->fd,0);
496 while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
498 if(IndexFirstSegmentX(segmentsx,nodex.id)==NO_SEGMENT)
504 WriteFile(fd,&nodex,sizeof(NodeX));
506 nodesx->idata[highway]=nodesx->idata[total];
509 if(nodex.latitude<lat_min)
510 lat_min=nodex.latitude;
511 if(nodex.latitude>lat_max)
512 lat_max=nodex.latitude;
513 if(nodex.longitude<lon_min)
514 lon_min=nodex.longitude;
515 if(nodex.longitude>lon_max)
516 lon_max=nodex.longitude;
522 printf_middle("Checking: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
525 /* Close the files and re-open them */
527 CloseFile(nodesx->fd);
530 nodesx->fd=ReOpenFile(nodesx->filename);
532 nodesx->number=highway;
534 /* Work out the number of bins */
536 lat_min_bin=latlong_to_bin(lat_min);
537 lon_min_bin=latlong_to_bin(lon_min);
538 lat_max_bin=latlong_to_bin(lat_max);
539 lon_max_bin=latlong_to_bin(lon_max);
541 nodesx->latzero=lat_min_bin;
542 nodesx->lonzero=lon_min_bin;
544 nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
545 nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;
547 /* Allocate and clear the super-node markers */
549 nodesx->super=(uint8_t*)calloc(nodesx->number,sizeof(uint8_t));
551 assert(nodesx->super); /* Check calloc() worked */
553 /* Print the final message */
555 printf_last("Checked: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
559 /*++++++++++++++++++++++++++++++++++++++
560 Create the real node data.
562 NodesX *nodesx The set of nodes to use.
564 int iteration The final super-node iteration.
565 ++++++++++++++++++++++++++++++++++++++*/
567 void CreateRealNodes(NodesX *nodesx,int iteration)
571 /* Print the start message */
573 printf_first("Creating Real Nodes: Nodes=0");
575 /* Map into memory */
578 nodesx->xdata=MapFile(nodesx->filename);
581 /* Allocate the memory (or open the file) */
584 nodesx->ndata=(Node*)malloc(nodesx->number*sizeof(Node));
586 assert(nodesx->ndata); /* Check malloc() worked */
588 nodesx->nfd=OpenFileNew(nodesx->nfilename);
591 /* Loop through and allocate. */
593 for(i=0;i<nodesx->number;i++)
595 NodeX *nodex=LookupNodeX(nodesx,i,1);
596 Node *node =LookupNodeXNode(nodesx,nodex->id,1);
598 node->latoffset=latlong_to_off(nodex->latitude);
599 node->lonoffset=latlong_to_off(nodex->longitude);
600 node->firstseg=NO_SEGMENT;
601 node->allow=nodex->allow;
604 if(nodesx->super[nodex->id]==iteration)
605 node->flags|=NODE_SUPER;
608 PutBackNodeXNode(nodesx,nodex->id,1);
612 printf_middle("Creating Real Nodes: Nodes=%d",i+1);
615 /* Free the unneeded memory */
620 /* Unmap from memory */
623 nodesx->xdata=UnmapFile(nodesx->filename);
626 /* Print the final message */
628 printf_last("Creating Real Nodes: Nodes=%d",nodesx->number);
632 /*++++++++++++++++++++++++++++++++++++++
633 Assign the segment indexes to the nodes.
635 NodesX *nodesx The list of nodes to process.
637 SegmentsX* segmentsx The set of segments to use.
638 ++++++++++++++++++++++++++++++++++++++*/
640 void IndexNodes(NodesX *nodesx,SegmentsX *segmentsx)
644 if(nodesx->number==0 || segmentsx->number==0)
647 /* Print the start message */
649 printf_first("Indexing Segments: Segments=0");
651 /* Map into memory */
654 nodesx->xdata=MapFile(nodesx->filename);
655 segmentsx->xdata=MapFile(segmentsx->filename);
658 /* Index the nodes */
660 for(i=0;i<segmentsx->number;i++)
662 SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
663 node_t id1=segmentx->node1;
664 node_t id2=segmentx->node2;
665 Node *node1=LookupNodeXNode(nodesx,id1,1);
666 Node *node2=LookupNodeXNode(nodesx,id2,2);
670 if(node1->firstseg==NO_SEGMENT)
675 PutBackNodeXNode(nodesx,id1,1);
680 index_t index=node1->firstseg;
684 segmentx=LookupSegmentX(segmentsx,index,1);
686 if(segmentx->node1==id1)
690 if(index>=segmentsx->number)
693 segmentx=LookupSegmentX(segmentsx,index,1);
695 if(segmentx->node1!=id1)
700 Segment *segment=LookupSegmentXSegment(segmentsx,index,1);
702 if(segment->next2==NO_NODE)
707 PutBackSegmentXSegment(segmentsx,index,1);
713 index=segment->next2;
721 if(node2->firstseg==NO_SEGMENT)
726 PutBackNodeXNode(nodesx,id2,2);
731 index_t index=node2->firstseg;
735 segmentx=LookupSegmentX(segmentsx,index,1);
737 if(segmentx->node1==id2)
741 if(index>=segmentsx->number)
744 segmentx=LookupSegmentX(segmentsx,index,1);
746 if(segmentx->node1!=id2)
751 Segment *segment=LookupSegmentXSegment(segmentsx,index,1);
753 if(segment->next2==NO_NODE)
758 PutBackSegmentXSegment(segmentsx,index,1);
764 index=segment->next2;
771 printf_middle("Indexing Segments: Segments=%d",i+1);
774 /* Unmap from memory */
777 nodesx->xdata=UnmapFile(nodesx->filename);
778 segmentsx->xdata=UnmapFile(segmentsx->filename);
781 /* Print the final message */
783 printf_last("Indexed Segments: Segments=%d ",segmentsx->number);
787 /*++++++++++++++++++++++++++++++++++++++
788 Save the node list to a file.
790 NodesX* nodesx The set of nodes to save.
792 const char *filename The name of the file to save.
793 ++++++++++++++++++++++++++++++++++++++*/
795 void SaveNodeList(NodesX* nodesx,const char *filename)
799 NodesFile nodesfile={0};
802 /* Print the start message */
804 printf_first("Writing Nodes: Nodes=0");
806 /* Map into memory */
809 nodesx->xdata=MapFile(nodesx->filename);
812 /* Write out the nodes data */
814 fd=OpenFileNew(filename);
816 SeekFile(fd,sizeof(NodesFile));
817 WriteFile(fd,nodesx->offsets,(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
819 for(i=0;i<nodesx->number;i++)
821 NodeX *nodex=LookupNodeX(nodesx,i,1);
822 Node *node=LookupNodeXNode(nodesx,nodex->id,1);
824 if(node->flags&NODE_SUPER)
827 WriteFile(fd,node,sizeof(Node));
830 printf_middle("Writing Nodes: Nodes=%d",i+1);
833 /* Write out the header structure */
835 nodesfile.number=nodesx->number;
836 nodesfile.snumber=super_number;
838 nodesfile.latbins=nodesx->latbins;
839 nodesfile.lonbins=nodesx->lonbins;
841 nodesfile.latzero=nodesx->latzero;
842 nodesfile.lonzero=nodesx->lonzero;
845 WriteFile(fd,&nodesfile,sizeof(NodesFile));
849 /* Unmap from memory */
852 nodesx->xdata=UnmapFile(nodesx->filename);
855 /* Print the final message */
857 printf_last("Wrote Nodes: Nodes=%d",nodesx->number);