1 /***************************************
2 $Header: /home/amb/routino/src/RCS/nodesx.c,v 1.56 2010/04/28 17:27:02 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 ***************************************/
32 #include "functions.h"
34 #include "segmentsx.h"
42 /*+ The command line '--slim' option. +*/
43 extern int option_slim;
45 /*+ The command line '--tmpdir' option or its default value. +*/
46 extern char *option_tmpdirname;
48 /*+ A temporary file-local variable for use by the sort functions. +*/
49 static NodesX *sortnodesx;
53 static int sort_by_id(NodeX *a,NodeX *b);
54 static int index_by_id(NodeX *nodex,index_t index);
56 static int sort_by_lat_long(NodeX *a,NodeX *b);
57 static int index_by_lat_long(NodeX *nodex,index_t index);
60 /*++++++++++++++++++++++++++++++++++++++
61 Allocate a new node list (create a new file or open an existing one).
63 NodesX *NewNodeList Returns the node list.
65 int append Set to 1 if the file is to be opened for appending (now or later).
66 ++++++++++++++++++++++++++++++++++++++*/
68 NodesX *NewNodeList(int append)
72 nodesx=(NodesX*)calloc(1,sizeof(NodesX));
74 assert(nodesx); /* Check calloc() worked */
76 nodesx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
79 sprintf(nodesx->filename,"%s/nodes.input.tmp",option_tmpdirname);
81 sprintf(nodesx->filename,"%s/nodes.%p.tmp",option_tmpdirname,nodesx);
87 nodesx->fd=AppendFile(nodesx->filename);
89 size=SizeFile(nodesx->filename);
91 nodesx->xnumber=size/sizeof(NodeX);
94 nodesx->fd=OpenFile(nodesx->filename);
100 /*++++++++++++++++++++++++++++++++++++++
103 NodesX *nodesx The list to be freed.
105 int keep Set to 1 if the file is to be kept.
106 ++++++++++++++++++++++++++++++++++++++*/
108 void FreeNodeList(NodesX *nodesx,int keep)
111 DeleteFile(nodesx->filename);
113 free(nodesx->filename);
125 free(nodesx->offsets);
131 /*++++++++++++++++++++++++++++++++++++++
132 Append a node to a newly created node list (unsorted).
134 NodesX* nodesx The set of nodes to process.
136 node_t id The node identification.
138 double latitude The latitude of the node.
140 double longitude The longitude of the node.
141 ++++++++++++++++++++++++++++++++++++++*/
143 void AppendNode(NodesX* nodesx,node_t id,double latitude,double longitude)
147 assert(!nodesx->idata); /* Must not have idata filled in => unsorted */
150 nodex.latitude =radians_to_latlong(latitude);
151 nodex.longitude=radians_to_latlong(longitude);
153 WriteFile(nodesx->fd,&nodex,sizeof(NodeX));
159 /*++++++++++++++++++++++++++++++++++++++
160 Sort the node list (i.e. create the sortable indexes).
162 NodesX* nodesx The set of nodes to process.
163 ++++++++++++++++++++++++++++++++++++++*/
165 void SortNodeList(NodesX* nodesx)
169 /* Check the start conditions */
171 assert(!nodesx->idata); /* Must not have idata filled in => unsorted */
173 /* Print the start message */
175 printf("Sorting Nodes");
178 /* Close the files and re-open them (finished appending) */
180 CloseFile(nodesx->fd);
181 nodesx->fd=ReOpenFile(nodesx->filename);
183 DeleteFile(nodesx->filename);
185 fd=OpenFile(nodesx->filename);
187 /* Allocate the array of indexes */
189 nodesx->idata=(node_t*)malloc(nodesx->xnumber*sizeof(node_t));
191 assert(nodesx->idata); /* Check malloc() worked */
193 /* Sort by node indexes */
197 filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))index_by_id);
199 /* Close the files and re-open them */
201 CloseFile(nodesx->fd);
204 nodesx->fd=ReOpenFile(nodesx->filename);
206 /* Print the final message */
208 printf("\rSorted Nodes: Nodes=%d Duplicates=%d\n",nodesx->xnumber,nodesx->xnumber-nodesx->number);
213 /*++++++++++++++++++++++++++++++++++++++
214 Sort the nodes into id order.
216 int sort_by_id Returns the comparison of the id fields.
218 NodeX *a The first extended node.
220 NodeX *b The second extended node.
221 ++++++++++++++++++++++++++++++++++++++*/
223 static int sort_by_id(NodeX *a,NodeX *b)
237 /*++++++++++++++++++++++++++++++++++++++
238 Index the nodes after sorting.
240 int index_by_id Return 1 if the value is to be kept, otherwise zero.
242 NodeX *nodex The extended node.
244 index_t index The index of this node in the total.
245 ++++++++++++++++++++++++++++++++++++++*/
247 static int index_by_id(NodeX *nodex,index_t index)
249 if(index==0 || sortnodesx->idata[index-1]!=nodex->id)
251 sortnodesx->idata[index]=nodex->id;
253 sortnodesx->number++;
262 /*++++++++++++++++++++++++++++++++++++++
263 Sort the node list geographically.
265 NodesX* nodesx The set of nodes to process.
266 ++++++++++++++++++++++++++++++++++++++*/
268 void SortNodeListGeographically(NodesX* nodesx)
272 /* Print the start message */
274 printf("Sorting Nodes Geographically");
277 /* Allocate the memory for the geographical offsets array */
279 nodesx->offsets=(index_t*)malloc((nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
283 /* Close the files and re-open them */
285 CloseFile(nodesx->fd);
286 nodesx->fd=ReOpenFile(nodesx->filename);
288 DeleteFile(nodesx->filename);
290 fd=OpenFile(nodesx->filename);
292 /* Sort geographically */
296 filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_lat_long,(int (*)(void*,index_t))index_by_lat_long);
298 /* Close the files and re-open them */
300 CloseFile(nodesx->fd);
303 nodesx->fd=ReOpenFile(nodesx->filename);
305 /* Finish off the indexing */
307 for(;nodesx->latlonbin<=(nodesx->latbins*nodesx->lonbins);nodesx->latlonbin++)
308 nodesx->offsets[nodesx->latlonbin]=nodesx->number;
310 /* Print the final message */
312 printf("\rSorted Nodes Geographically \n");
317 /*++++++++++++++++++++++++++++++++++++++
318 Sort the nodes into latitude and longitude order.
320 int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
322 NodeX *a The first extended node.
324 NodeX *b The second extended node.
325 ++++++++++++++++++++++++++++++++++++++*/
327 static int sort_by_lat_long(NodeX *a,NodeX *b)
329 ll_bin_t a_lon=latlong_to_bin(a->longitude);
330 ll_bin_t b_lon=latlong_to_bin(b->longitude);
338 ll_bin_t a_lat=latlong_to_bin(a->latitude);
339 ll_bin_t b_lat=latlong_to_bin(b->latitude);
347 #ifdef REGRESSION_TESTING
348 // Need this for regression testing because heapsort() is not order
349 // preserving like qsort() is (or was when tested).
366 /*++++++++++++++++++++++++++++++++++++++
367 Index the nodes after sorting.
369 int index_by_lat_long Return 1 if the value is to be kept, otherwise zero.
371 NodeX *nodex The extended node.
373 index_t index The index of this node in the total.
374 ++++++++++++++++++++++++++++++++++++++*/
376 static int index_by_lat_long(NodeX *nodex,index_t index)
378 /* Work out the offsets */
380 ll_bin_t latbin=latlong_to_bin(nodex->latitude )-sortnodesx->latzero;
381 ll_bin_t lonbin=latlong_to_bin(nodex->longitude)-sortnodesx->lonzero;
382 int llbin=lonbin*sortnodesx->latbins+latbin;
384 for(;sortnodesx->latlonbin<=llbin;sortnodesx->latlonbin++)
385 sortnodesx->offsets[sortnodesx->latlonbin]=index;
391 /*++++++++++++++++++++++++++++++++++++++
392 Find a particular node index.
394 index_t IndexNodeX Returns the index of the extended node with the specified id.
396 NodesX* nodesx The set of nodes to process.
398 node_t id The node id to look for.
399 ++++++++++++++++++++++++++++++++++++++*/
401 index_t IndexNodeX(NodesX* nodesx,node_t id)
404 int end=nodesx->number-1;
407 assert(nodesx->idata); /* Must have idata filled in => sorted by id */
409 /* Binary search - search key exact match only is required.
411 * # <- start | Check mid and move start or end if it doesn't match
413 * # | Since an exact match is wanted we can set end=mid-1
414 * # <- mid | or start=mid+1 because we know that mid doesn't match.
416 * # | Eventually either end=start or end=start+1 and one of
417 * # <- end | start or end is the wanted one.
420 if(end<start) /* There are no nodes */
422 else if(id<nodesx->idata[start]) /* Check key is not before start */
424 else if(id>nodesx->idata[end]) /* Check key is not after end */
430 mid=(start+end)/2; /* Choose mid point */
432 if(nodesx->idata[mid]<id) /* Mid point is too low */
434 else if(nodesx->idata[mid]>id) /* Mid point is too high */
436 else /* Mid point is correct */
439 while((end-start)>1);
441 if(nodesx->idata[start]==id) /* Start is correct */
444 if(nodesx->idata[end]==id) /* End is correct */
452 /*++++++++++++++++++++++++++++++++++++++
453 Lookup a particular node.
455 NodeX *LookupNodeX Returns a pointer to the extended node with the specified id.
457 NodesX* nodesx The set of nodes to process.
459 index_t index The node index to look for.
461 int position The position in the cache to use.
462 ++++++++++++++++++++++++++++++++++++++*/
464 NodeX *LookupNodeX(NodesX* nodesx,index_t index,int position)
466 assert(index!=NO_NODE); /* Must be a valid node */
470 SeekFile(nodesx->fd,index*sizeof(NodeX));
472 ReadFile(nodesx->fd,&nodesx->cached[position-1],sizeof(NodeX));
474 return(&nodesx->cached[position-1]);
478 return(&nodesx->xdata[index]);
483 /*++++++++++++++++++++++++++++++++++++++
484 Remove any nodes that are not part of a highway.
486 NodesX *nodesx The complete node list.
488 SegmentsX *segmentsx The list of segments.
489 ++++++++++++++++++++++++++++++++++++++*/
491 void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
494 int total=0,highway=0,nothighway=0;
495 ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
496 latlong_t lat_min,lat_max,lon_min,lon_max;
499 /* Check the start conditions */
501 assert(nodesx->idata); /* Must have idata filled in => data sorted */
503 /* Print the start message */
505 printf("Checking: Nodes=0");
508 /* While we are here we can work out the range of data */
510 lat_min=radians_to_latlong( 2);
511 lat_max=radians_to_latlong(-2);
512 lon_min=radians_to_latlong( 4);
513 lon_max=radians_to_latlong(-4);
515 /* Modify the on-disk image */
517 DeleteFile(nodesx->filename);
519 fd=OpenFile(nodesx->filename);
520 SeekFile(nodesx->fd,0);
522 while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
524 if(IndexFirstSegmentX(segmentsx,nodex.id)==NO_SEGMENT)
530 WriteFile(fd,&nodex,sizeof(NodeX));
532 nodesx->idata[highway]=nodesx->idata[total];
535 if(nodex.latitude<lat_min)
536 lat_min=nodex.latitude;
537 if(nodex.latitude>lat_max)
538 lat_max=nodex.latitude;
539 if(nodex.longitude<lon_min)
540 lon_min=nodex.longitude;
541 if(nodex.longitude>lon_max)
542 lon_max=nodex.longitude;
549 printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
554 /* Close the files and re-open them */
556 CloseFile(nodesx->fd);
559 nodesx->fd=ReOpenFile(nodesx->filename);
561 nodesx->number=highway;
563 /* Work out the number of bins */
565 lat_min_bin=latlong_to_bin(lat_min);
566 lon_min_bin=latlong_to_bin(lon_min);
567 lat_max_bin=latlong_to_bin(lat_max);
568 lon_max_bin=latlong_to_bin(lon_max);
570 nodesx->latzero=lat_min_bin;
571 nodesx->lonzero=lon_min_bin;
573 nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
574 nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;
576 /* Allocate and clear the super-node markers */
578 nodesx->super=(uint8_t*)calloc(nodesx->number,sizeof(uint8_t));
580 assert(nodesx->super); /* Check calloc() worked */
582 /* Print the final message */
584 printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",total,highway,nothighway);
589 /*++++++++++++++++++++++++++++++++++++++
590 Create the real node data.
592 NodesX *nodesx The set of nodes to use.
594 int iteration The final super-node iteration.
595 ++++++++++++++++++++++++++++++++++++++*/
597 void CreateRealNodes(NodesX *nodesx,int iteration)
601 /* Check the start conditions */
603 assert(!nodesx->ndata); /* Must not have ndata filled in => no real nodes */
605 /* Print the start message */
607 printf("Creating Real Nodes: Nodes=0");
610 /* Map into memory */
613 nodesx->xdata=MapFile(nodesx->filename);
615 /* Allocate the memory */
617 nodesx->ndata=(Node*)malloc(nodesx->number*sizeof(Node));
619 assert(nodesx->ndata); /* Check malloc() worked */
621 /* Loop through and allocate. */
623 for(i=0;i<nodesx->number;i++)
625 NodeX *nodex=LookupNodeX(nodesx,i,1);
627 nodesx->ndata[nodex->id].latoffset=latlong_to_off(nodex->latitude);
628 nodesx->ndata[nodex->id].lonoffset=latlong_to_off(nodex->longitude);
629 nodesx->ndata[nodex->id].firstseg=SEGMENT(NO_SEGMENT);
631 if(nodesx->super[nodex->id]==iteration)
632 nodesx->ndata[nodex->id].firstseg|=NODE_SUPER;
636 printf("\rCreating Real Nodes: Nodes=%d",i+1);
641 /* Free the unneeded memory */
646 /* Unmap from memory */
649 nodesx->xdata=UnmapFile(nodesx->filename);
651 /* Print the final message */
653 printf("\rCreating Real Nodes: Nodes=%d \n",nodesx->number);
658 /*++++++++++++++++++++++++++++++++++++++
659 Assign the segment indexes to the nodes.
661 NodesX *nodesx The list of nodes to process.
663 SegmentsX* segmentsx The set of segments to use.
664 ++++++++++++++++++++++++++++++++++++++*/
666 void IndexNodes(NodesX *nodesx,SegmentsX *segmentsx)
670 /* Check the start conditions */
672 assert(nodesx->ndata); /* Must have ndata filled in => real nodes exist */
673 assert(segmentsx->sdata); /* Must have sdata filled in => real segments exist */
675 /* Print the start message */
677 printf("Indexing Segments: Segments=0");
680 /* Map into memory */
684 nodesx->xdata=MapFile(nodesx->filename);
685 segmentsx->xdata=MapFile(segmentsx->filename);
688 /* Index the nodes */
690 for(i=0;i<segmentsx->number;i++)
692 SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
693 node_t id1=segmentx->node1;
694 node_t id2=segmentx->node2;
695 Node *node1=&nodesx->ndata[id1];
696 Node *node2=&nodesx->ndata[id2];
700 if(SEGMENT(node1->firstseg)==SEGMENT(NO_SEGMENT))
702 node1->firstseg^=SEGMENT(NO_SEGMENT);
707 index_t index=SEGMENT(node1->firstseg);
711 segmentx=LookupSegmentX(segmentsx,index,1);
713 if(segmentx->node1==id1)
717 if(index>=segmentsx->number)
720 segmentx=LookupSegmentX(segmentsx,index,1);
722 if(segmentx->node1!=id1)
727 if(segmentsx->sdata[index].next2==NO_NODE)
729 segmentsx->sdata[index].next2=i;
733 index=segmentsx->sdata[index].next2;
741 if(SEGMENT(node2->firstseg)==SEGMENT(NO_SEGMENT))
743 node2->firstseg^=SEGMENT(NO_SEGMENT);
748 index_t index=SEGMENT(node2->firstseg);
752 segmentx=LookupSegmentX(segmentsx,index,1);
754 if(segmentx->node1==id2)
758 if(index>=segmentsx->number)
761 segmentx=LookupSegmentX(segmentsx,index,1);
763 if(segmentx->node1!=id2)
768 if(segmentsx->sdata[index].next2==NO_NODE)
770 segmentsx->sdata[index].next2=i;
774 index=segmentsx->sdata[index].next2;
782 printf("\rIndexing Segments: Segments=%d",i+1);
787 /* Unmap from memory */
791 nodesx->xdata=UnmapFile(nodesx->filename);
792 segmentsx->xdata=UnmapFile(segmentsx->filename);
795 /* Print the final message */
797 printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
802 /*++++++++++++++++++++++++++++++++++++++
803 Save the node list to a file.
805 NodesX* nodesx The set of nodes to save.
807 const char *filename The name of the file to save.
808 ++++++++++++++++++++++++++++++++++++++*/
810 void SaveNodeList(NodesX* nodesx,const char *filename)
817 /* Check the start conditions */
819 assert(nodesx->ndata); /* Must have ndata filled in => real nodes exist */
821 /* Print the start message */
823 printf("Writing Nodes: Nodes=0");
826 /* Map into memory */
829 nodesx->xdata=MapFile(nodesx->filename);
831 /* Count the number of super-nodes */
833 for(i=0;i<nodesx->number;i++)
834 if(nodesx->ndata[i].firstseg&NODE_SUPER)
837 /* Fill in a Nodes structure with the offset of the real data in the file after
838 the Node structure itself. */
840 nodes=calloc(1,sizeof(Nodes));
842 assert(nodes); /* Check calloc() worked */
844 nodes->number=nodesx->number;
845 nodes->snumber=super_number;
847 nodes->latbins=nodesx->latbins;
848 nodes->lonbins=nodesx->lonbins;
850 nodes->latzero=nodesx->latzero;
851 nodes->lonzero=nodesx->lonzero;
857 /* Write out the Nodes structure and then the real data. */
859 fd=OpenFile(filename);
861 WriteFile(fd,nodes,sizeof(Nodes));
863 WriteFile(fd,nodesx->offsets,(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
865 for(i=0;i<nodes->number;i++)
867 NodeX *nodex=LookupNodeX(nodesx,i,1);
868 Node *node=&nodesx->ndata[nodex->id];
870 WriteFile(fd,node,sizeof(Node));
874 printf("\rWriting Nodes: Nodes=%d",i+1);
881 /* Unmap from memory */
884 nodesx->xdata=UnmapFile(nodesx->filename);
886 /* Print the final message */
888 printf("\rWrote Nodes: Nodes=%d \n",nodes->number);
891 /* Free the fake Nodes */