X-Git-Url: http://git.maemo.org/git/?p=routino;a=blobdiff_plain;f=src%2Fnodes.c;fp=src%2Fnodes.c;h=f04678b4c7bb8f3fcd558b13d44d2b2f780a267c;hp=7430d62d15cdb8cefde7eabf6e3e7ae615672ab5;hb=a5b34ad069a52ff6cf981f01667d102292988811;hpb=20283c6cf5c6951cc1f2787492c67a7fb72aee9a diff --git a/src/nodes.c b/src/nodes.c index 7430d62..f04678b 100644 --- a/src/nodes.c +++ b/src/nodes.c @@ -1,5 +1,5 @@ /*************************************** - $Header: /home/amb/routino/src/RCS/nodes.c,v 1.39 2010/07/08 17:54:54 amb Exp $ + $Header: /home/amb/routino/src/RCS/nodes.c,v 1.44 2010/07/26 18:17:20 amb Exp $ Node data type functions. @@ -26,11 +26,12 @@ #include #include -#include "profiles.h" #include "nodes.h" #include "segments.h" #include "ways.h" -#include "functions.h" + +#include "files.h" +#include "profiles.h" /*++++++++++++++++++++++++++++++++++++++ @@ -43,22 +44,38 @@ Nodes *LoadNodeList(const char *filename) { - void *data; Nodes *nodes; nodes=(Nodes*)malloc(sizeof(Nodes)); - data=MapFile(filename); +#if !SLIM + + nodes->data=MapFile(filename); + + /* Copy the NodesFile header structure from the loaded data */ + + nodes->file=*((NodesFile*)nodes->data); + + /* Set the pointers in the Nodes structure. */ + + nodes->offsets=(index_t*)(nodes->data+sizeof(NodesFile)); + nodes->nodes =(Node* )(nodes->data+sizeof(NodesFile)+(nodes->file.latbins*nodes->file.lonbins+1)*sizeof(index_t)); + +#else + + nodes->fd=ReOpenFile(filename); - /* Copy the Nodes structure from the loaded data */ + /* Copy the NodesFile header structure from the loaded data */ - *nodes=*((Nodes*)data); + ReadFile(nodes->fd,&nodes->file,sizeof(NodesFile)); - /* Adjust the pointers in the Nodes structure. */ + nodes->nodesoffset=sizeof(NodesFile)+(nodes->file.latbins*nodes->file.lonbins+1)*sizeof(index_t); - nodes->data=data; - nodes->offsets=(index_t*)(data+sizeof(Nodes)); - nodes->nodes=(Node*)(data+(sizeof(Nodes)+(nodes->latbins*nodes->lonbins+1)*sizeof(index_t))); + nodes->incache[0]=NO_NODE; + nodes->incache[1]=NO_NODE; + nodes->incache[2]=NO_NODE; + +#endif return(nodes); } @@ -89,10 +106,11 @@ Nodes *LoadNodeList(const char *filename) index_t FindClosestNode(Nodes* nodes,Segments *segments,Ways *ways,double latitude,double longitude, distance_t distance,Profile *profile,distance_t *bestdist) { - ll_bin_t latbin=latlong_to_bin(radians_to_latlong(latitude ))-nodes->latzero; - ll_bin_t lonbin=latlong_to_bin(radians_to_latlong(longitude))-nodes->lonzero; + ll_bin_t latbin=latlong_to_bin(radians_to_latlong(latitude ))-nodes->file.latzero; + ll_bin_t lonbin=latlong_to_bin(radians_to_latlong(longitude))-nodes->file.lonzero; int delta=0,count; - index_t i,bestn=NO_NODE; + index_t i,index1,index2; + index_t bestn=NO_NODE; distance_t bestd=INF_DISTANCE; /* Start with the bin containing the location, then spiral outwards. */ @@ -102,30 +120,30 @@ index_t FindClosestNode(Nodes* nodes,Segments *segments,Ways *ways,double latitu int latb,lonb,llbin; count=0; - + for(latb=latbin-delta;latb<=latbin+delta;latb++) { - if(latb<0 || latb>=nodes->latbins) + if(latb<0 || latb>=nodes->file.latbins) continue; for(lonb=lonbin-delta;lonb<=lonbin+delta;lonb++) { - if(lonb<0 || lonb>=nodes->lonbins) + if(lonb<0 || lonb>=nodes->file.lonbins) continue; if(abs(latb-latbin)latbins+latb; + llbin=lonb*nodes->file.latbins+latb; /* Check if this grid square has any hope of being close enough */ if(delta>0) { - double lat1=latlong_to_radians(bin_to_latlong(nodes->latzero+latb)); - double lon1=latlong_to_radians(bin_to_latlong(nodes->lonzero+lonb)); - double lat2=latlong_to_radians(bin_to_latlong(nodes->latzero+latb+1)); - double lon2=latlong_to_radians(bin_to_latlong(nodes->lonzero+lonb+1)); + double lat1=latlong_to_radians(bin_to_latlong(nodes->file.latzero+latb)); + double lon1=latlong_to_radians(bin_to_latlong(nodes->file.lonzero+lonb)); + double lat2=latlong_to_radians(bin_to_latlong(nodes->file.latzero+latb+1)); + double lon2=latlong_to_radians(bin_to_latlong(nodes->file.lonzero+lonb+1)); if(latb==latbin) { @@ -157,10 +175,14 @@ index_t FindClosestNode(Nodes* nodes,Segments *segments,Ways *ways,double latitu /* Check every node in this grid square. */ - for(i=nodes->offsets[llbin];ioffsets[llbin+1];i++) + index1=LookupNodeOffset(nodes,llbin); + index2=LookupNodeOffset(nodes,llbin+1); + + for(i=index1;ilatzero+latb)+off_to_latlong(nodes->nodes[i].latoffset)); - double lon=latlong_to_radians(bin_to_latlong(nodes->lonzero+lonb)+off_to_latlong(nodes->nodes[i].lonoffset)); + Node *node=LookupNode(nodes,i,1); + double lat=latlong_to_radians(bin_to_latlong(nodes->file.latzero+latb)+off_to_latlong(node->latoffset)); + double lon=latlong_to_radians(bin_to_latlong(nodes->file.lonzero+lonb)+off_to_latlong(node->lonoffset)); distance_t dist=Distance(lat,lon,latitude,longitude); @@ -176,7 +198,7 @@ index_t FindClosestNode(Nodes* nodes,Segments *segments,Ways *ways,double latitu do { - Way *way=LookupWay(ways,segment->way); + Way *way=LookupWay(ways,segment->way,1); if(way->allow&profile->allow) break; @@ -210,7 +232,7 @@ index_t FindClosestNode(Nodes* nodes,Segments *segments,Ways *ways,double latitu /*++++++++++++++++++++++++++++++++++++++ Find the closest segment to a latitude, longitude and optionally profile. - Segment *FindClosestSegment Returns the closest segment. + index_t FindClosestSegment Returns the closest segment index. Nodes* nodes The set of nodes to search. @@ -237,16 +259,17 @@ index_t FindClosestNode(Nodes* nodes,Segments *segments,Ways *ways,double latitu distance_t *bestdist2 Returns the distance to the best node at the other end. ++++++++++++++++++++++++++++++++++++++*/ -Segment *FindClosestSegment(Nodes* nodes,Segments *segments,Ways *ways,double latitude,double longitude, - distance_t distance,Profile *profile, distance_t *bestdist, - index_t *bestnode1,index_t *bestnode2,distance_t *bestdist1,distance_t *bestdist2) +index_t FindClosestSegment(Nodes* nodes,Segments *segments,Ways *ways,double latitude,double longitude, + distance_t distance,Profile *profile, distance_t *bestdist, + index_t *bestnode1,index_t *bestnode2,distance_t *bestdist1,distance_t *bestdist2) { - ll_bin_t latbin=latlong_to_bin(radians_to_latlong(latitude ))-nodes->latzero; - ll_bin_t lonbin=latlong_to_bin(radians_to_latlong(longitude))-nodes->lonzero; + ll_bin_t latbin=latlong_to_bin(radians_to_latlong(latitude ))-nodes->file.latzero; + ll_bin_t lonbin=latlong_to_bin(radians_to_latlong(longitude))-nodes->file.lonzero; int delta=0,count; - index_t i,bestn1=NO_NODE,bestn2=NO_NODE; + index_t i,index1,index2; + index_t bestn1=NO_NODE,bestn2=NO_NODE; distance_t bestd=INF_DISTANCE,bestd1=INF_DISTANCE,bestd2=INF_DISTANCE; - Segment *bests=NULL; + index_t bests=NO_SEGMENT; /* Start with the bin containing the location, then spiral outwards. */ @@ -255,30 +278,30 @@ Segment *FindClosestSegment(Nodes* nodes,Segments *segments,Ways *ways,double la int latb,lonb,llbin; count=0; - + for(latb=latbin-delta;latb<=latbin+delta;latb++) { - if(latb<0 || latb>=nodes->latbins) + if(latb<0 || latb>=nodes->file.latbins) continue; for(lonb=lonbin-delta;lonb<=lonbin+delta;lonb++) { - if(lonb<0 || lonb>=nodes->lonbins) + if(lonb<0 || lonb>=nodes->file.lonbins) continue; if(abs(latb-latbin)latbins+latb; + llbin=lonb*nodes->file.latbins+latb; /* Check if this grid square has any hope of being close enough */ if(delta>0) { - double lat1=latlong_to_radians(bin_to_latlong(nodes->latzero+latb)); - double lon1=latlong_to_radians(bin_to_latlong(nodes->lonzero+lonb)); - double lat2=latlong_to_radians(bin_to_latlong(nodes->latzero+latb+1)); - double lon2=latlong_to_radians(bin_to_latlong(nodes->lonzero+lonb+1)); + double lat1=latlong_to_radians(bin_to_latlong(nodes->file.latzero+latb)); + double lon1=latlong_to_radians(bin_to_latlong(nodes->file.lonzero+lonb)); + double lat2=latlong_to_radians(bin_to_latlong(nodes->file.latzero+latb+1)); + double lon2=latlong_to_radians(bin_to_latlong(nodes->file.lonzero+lonb+1)); if(latb==latbin) { @@ -310,10 +333,14 @@ Segment *FindClosestSegment(Nodes* nodes,Segments *segments,Ways *ways,double la /* Check every node in this grid square. */ - for(i=nodes->offsets[llbin];ioffsets[llbin+1];i++) + index1=LookupNodeOffset(nodes,llbin); + index2=LookupNodeOffset(nodes,llbin+1); + + for(i=index1;ilatzero+latb)+off_to_latlong(nodes->nodes[i].latoffset)); - double lon1=latlong_to_radians(bin_to_latlong(nodes->lonzero+lonb)+off_to_latlong(nodes->nodes[i].lonoffset)); + Node *node=LookupNode(nodes,i,1); + double lat1=latlong_to_radians(bin_to_latlong(nodes->file.latzero+latb)+off_to_latlong(node->latoffset)); + double lon1=latlong_to_radians(bin_to_latlong(nodes->file.lonzero+lonb)+off_to_latlong(node->lonoffset)); distance_t dist1; dist1=Distance(lat1,lon1,latitude,longitude); @@ -333,7 +360,7 @@ Segment *FindClosestSegment(Nodes* nodes,Segments *segments,Ways *ways,double la Way *way=NULL; if(profile) - way=LookupWay(ways,segment->way); + way=LookupWay(ways,segment->way,1); if(!profile || way->allow&profile->allow) { @@ -368,7 +395,7 @@ Segment *FindClosestSegment(Nodes* nodes,Segments *segments,Ways *ways,double la if(distp<(double)bestd) { - bests=segment; + bests=IndexSegment(segments,segment); bestn1=i; bestn2=OtherNode(segment,i); bestd1=(distance_t)dist3a; @@ -418,9 +445,10 @@ Segment *FindClosestSegment(Nodes* nodes,Segments *segments,Ways *ways,double la void GetLatLong(Nodes *nodes,index_t index,double *latitude,double *longitude) { - Node *node=&nodes->nodes[index]; + Node *node=LookupNode(nodes,index,2); int latbin=-1,lonbin=-1; int start,end,mid; + index_t offset; /* Binary search - search key closest below is required. * @@ -436,63 +464,73 @@ void GetLatLong(Nodes *nodes,index_t index,double *latitude,double *longitude) /* Search for longitude */ start=0; - end=nodes->lonbins-1; + end=nodes->file.lonbins-1; do { - mid=(start+end)/2; /* Choose mid point */ + mid=(start+end)/2; /* Choose mid point */ - if(nodes->offsets[nodes->latbins*mid]file.latbins*mid); + + if(offsetoffsets[nodes->latbins*mid]>index) /* Mid point is too high */ + else if(offset>index) /* Mid point is too high */ end=mid-1; - else /* Mid point is correct */ + else /* Mid point is correct */ {lonbin=mid;break;} } while((end-start)>1); if(lonbin==-1) { - if(nodes->offsets[nodes->latbins*end]>index) + offset=LookupNodeOffset(nodes,nodes->file.latbins*end); + + if(offset>index) lonbin=start; else lonbin=end; } - while(lonbinlonbins && nodes->offsets[lonbin*nodes->latbins]==nodes->offsets[(lonbin+1)*nodes->latbins]) + while(lonbinfile.lonbins && + LookupNodeOffset(nodes,lonbin*nodes->file.latbins)==LookupNodeOffset(nodes,(lonbin+1)*nodes->file.latbins)) lonbin++; /* Search for latitude */ start=0; - end=nodes->latbins-1; + end=nodes->file.latbins-1; do { - mid=(start+end)/2; /* Choose mid point */ + mid=(start+end)/2; /* Choose mid point */ - if(nodes->offsets[lonbin*nodes->latbins+mid]file.latbins+mid); + + if(offsetoffsets[lonbin*nodes->latbins+mid]>index) /* Mid point is too high */ + else if(offset>index) /* Mid point is too high */ end=mid-1; - else /* Mid point is correct */ + else /* Mid point is correct */ {latbin=mid;break;} } while((end-start)>1); if(latbin==-1) { - if(nodes->offsets[lonbin*nodes->latbins+end]>index) + offset=LookupNodeOffset(nodes,lonbin*nodes->file.latbins+end); + + if(offset>index) latbin=start; else latbin=end; } - while(latbinlatbins && nodes->offsets[lonbin*nodes->latbins+latbin]==nodes->offsets[lonbin*nodes->latbins+latbin+1]) + while(latbinfile.latbins && + LookupNodeOffset(nodes,lonbin*nodes->file.latbins+latbin)==LookupNodeOffset(nodes,lonbin*nodes->file.latbins+latbin+1)) latbin++; /* Return the values */ - *latitude =latlong_to_radians(bin_to_latlong(nodes->latzero+latbin)+off_to_latlong(node->latoffset)); - *longitude=latlong_to_radians(bin_to_latlong(nodes->lonzero+lonbin)+off_to_latlong(node->lonoffset)); + *latitude =latlong_to_radians(bin_to_latlong(nodes->file.latzero+latbin)+off_to_latlong(node->latoffset)); + *longitude=latlong_to_radians(bin_to_latlong(nodes->file.lonzero+lonbin)+off_to_latlong(node->lonoffset)); }