1 /***************************************
2 $Header: /home/amb/routino/src/RCS/nodes.h,v 1.37 2010/08/03 18:28:30 amb Exp $
4 A header file for the nodes.
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 ***************************************/
26 #define NODES_H /*+ To stop multiple inclusions. +*/
39 /*+ A structure containing a single node. +*/
42 index_t firstseg; /*+ The index of the first segment. +*/
44 ll_off_t latoffset; /*+ The node latitude offset within its bin. +*/
45 ll_off_t lonoffset; /*+ The node longitude offset within its bin. +*/
47 allow_t allow; /*+ The types of transport that are allowed through the node. +*/
48 uint16_t flags; /*+ Flags containing extra information (super-node, turn restriction). +*/
52 /*+ A structure containing the header from the file. +*/
53 typedef struct _NodesFile
55 index_t number; /*+ How many nodes in total? +*/
56 index_t snumber; /*+ How many super-nodes? +*/
58 index_t latbins; /*+ The number of bins containing latitude. +*/
59 index_t lonbins; /*+ The number of bins containing longitude. +*/
61 ll_bin_t latzero; /*+ The bin number of the furthest south bin. +*/
62 ll_bin_t lonzero; /*+ The bin number of the furthest west bin. +*/
67 /*+ A structure containing a set of nodes (and pointers to mmap file). +*/
70 NodesFile file; /*+ The header data from the file. +*/
74 void *data; /*+ The memory mapped data. +*/
76 index_t *offsets; /*+ An array of offsets to the first node in each bin. +*/
78 Node *nodes; /*+ An array of nodes. +*/
82 int fd; /*+ The file descriptor for the file. +*/
83 off_t nodesoffset; /*+ The offset of the nodes within the file. +*/
85 Node cached[3]; /*+ The cached nodes. +*/
86 index_t incache[3]; /*+ The indexes of the cached nodes. +*/
94 Nodes *LoadNodeList(const char *filename);
96 index_t FindClosestNode(Nodes* nodes,Segments *segments,Ways *ways,double latitude,double longitude,
97 distance_t distance,Profile *profile,distance_t *bestdist);
99 index_t FindClosestSegment(Nodes* nodes,Segments *segments,Ways *ways,double latitude,double longitude,
100 distance_t distance,Profile *profile, distance_t *bestdist,
101 index_t *bestnode1,index_t *bestnode2,distance_t *bestdist1,distance_t *bestdist2);
103 void GetLatLong(Nodes *nodes,index_t index,double *latitude,double *longitude);
106 /* Macros and inline functions */
110 /*+ Return a Node pointer given a set of nodes and an index. +*/
111 #define LookupNode(xxx,yyy,zzz) (&(xxx)->nodes[yyy])
113 /*+ Return a Segment points given a Node pointer and a set of segments. +*/
114 #define FirstSegment(xxx,yyy,zzz) LookupSegment((xxx),(yyy)->nodes[zzz].firstseg,1)
116 /*+ Return true if this is a super-node. +*/
117 #define IsSuperNode(xxx,yyy) (((xxx)->nodes[yyy].flags)&NODE_SUPER)
119 /*+ Return the offset of a geographical region given a set of nodes and an index. +*/
120 #define LookupNodeOffset(xxx,yyy) ((xxx)->offsets[yyy])
124 static Node *LookupNode(Nodes *nodes,index_t index,int position);
126 #define FirstSegment(xxx,yyy,zzz) LookupSegment((xxx),FirstSegment_internal(yyy,zzz),1)
128 static index_t FirstSegment_internal(Nodes *nodes,index_t index);
130 static int IsSuperNode(Nodes *nodes,index_t index);
132 static index_t LookupNodeOffset(Nodes *nodes,index_t index);
135 /*++++++++++++++++++++++++++++++++++++++
136 Find the Node information for a particular node.
138 Node *LookupNode Returns a pointer to the cached node information.
140 Nodes *nodes The nodes structure to use.
142 index_t index The index of the node.
144 int position The position in the cache to store the value.
145 ++++++++++++++++++++++++++++++++++++++*/
147 static inline Node *LookupNode(Nodes *nodes,index_t index,int position)
149 SeekFile(nodes->fd,nodes->nodesoffset+(off_t)index*sizeof(Node));
151 ReadFile(nodes->fd,&nodes->cached[position-1],sizeof(Node));
153 nodes->incache[position-1]=index;
155 return(&nodes->cached[position-1]);
159 /*++++++++++++++++++++++++++++++++++++++
160 Find the index of the first segment of a node (called by FirstSegment() macro).
162 index_t FirstSegment_internal Returns the index of the first segment.
164 Nodes *nodes The nodes structure to use.
166 index_t index The index of the node.
167 ++++++++++++++++++++++++++++++++++++++*/
169 static inline index_t FirstSegment_internal(Nodes *nodes,index_t index)
171 if(nodes->incache[0]==index)
172 return(nodes->cached[0].firstseg);
173 else if(nodes->incache[1]==index)
174 return(nodes->cached[1].firstseg);
175 else if(nodes->incache[2]==index)
176 return(nodes->cached[2].firstseg);
179 Node *node=LookupNode(nodes,index,3);
181 return(node->firstseg);
186 /*++++++++++++++++++++++++++++++++++++++
187 Decide if a node is a super-node.
189 int IsSuperNode Return true if it is a supernode.
191 Nodes *nodes The nodes structure to use.
193 index_t index The index of the node.
194 ++++++++++++++++++++++++++++++++++++++*/
196 static inline int IsSuperNode(Nodes *nodes,index_t index)
198 if(nodes->incache[0]==index)
199 return(nodes->cached[0].flags&NODE_SUPER);
200 else if(nodes->incache[1]==index)
201 return(nodes->cached[1].flags&NODE_SUPER);
202 else if(nodes->incache[2]==index)
203 return(nodes->cached[2].flags&NODE_SUPER);
206 Node *node=LookupNode(nodes,index,3);
208 return(node->flags&NODE_SUPER);
213 /*++++++++++++++++++++++++++++++++++++++
214 Find the offset of nodes in a geographical region.
216 index_t LookupNodeOffset Returns the value of the index offset.
218 Nodes *nodes The nodes structure to use.
220 index_t index The index of the offset.
221 ++++++++++++++++++++++++++++++++++++++*/
223 static inline index_t LookupNodeOffset(Nodes *nodes,index_t index)
227 SeekFile(nodes->fd,sizeof(NodesFile)+(off_t)index*sizeof(index_t));
229 ReadFile(nodes->fd,&offset,sizeof(index_t));