trunk/src/nodes.h

/***************************************
 A header file for the nodes.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2011 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#ifndef NODES_H
#define NODES_H    /*+ To stop multiple inclusions. +*/

#include <stdint.h>

#include "types.h"

#include "files.h"
#include "profiles.h"


/* Data structures */


/*+ A structure containing a single node. +*/
struct _Node
{
 index_t      firstseg;         /*+ The index of the first segment. +*/

 ll_off_t     latoffset;        /*+ The node latitude offset within its bin. +*/
 ll_off_t     lonoffset;        /*+ The node longitude offset within its bin. +*/

 transports_t allow;            /*+ The types of transport that are allowed through the node. +*/
 uint16_t     flags;            /*+ Flags containing extra information (super-node, turn restriction). +*/
};


/*+ A structure containing the header from the file. +*/
typedef struct _NodesFile
{
 index_t  number;               /*+ How many nodes in total? +*/
 index_t  snumber;              /*+ How many super-nodes? +*/

 index_t  latbins;              /*+ The number of bins containing latitude. +*/
 index_t  lonbins;              /*+ The number of bins containing longitude. +*/

 ll_bin_t latzero;              /*+ The bin number of the furthest south bin. +*/
 ll_bin_t lonzero;              /*+ The bin number of the furthest west bin. +*/
}
 NodesFile;


/*+ A structure containing a set of nodes (and pointers to mmap file). +*/
struct _Nodes
{
 NodesFile file;                /*+ The header data from the file. +*/

#if !SLIM

 void     *data;                /*+ The memory mapped data. +*/

 index_t  *offsets;             /*+ An array of offsets to the first node in each bin. +*/

 Node     *nodes;               /*+ An array of nodes. +*/

#else

 int       fd;                  /*+ The file descriptor for the file. +*/
 off_t     nodesoffset;         /*+ The offset of the nodes within the file. +*/

 Node      cached[2];           /*+ The cached nodes. +*/
 index_t   incache[2];          /*+ The indexes of the cached nodes. +*/

#endif
};


/* Functions */

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);

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);

void GetLatLong(Nodes *nodes,index_t index,double *latitude,double *longitude);


/* Macros and inline functions */

/*+ Return true if this is a super-node. +*/
#define IsSuperNode(xxx)            (((xxx)->flags)&NODE_SUPER)

/*+ Return true if this is a turn restricted node. +*/
#define IsTurnRestrictedNode(xxx)   (((xxx)->flags)&NODE_TURNRSTRCT)


#if !SLIM

/*+ Return a Node pointer given a set of nodes and an index. +*/
#define LookupNode(xxx,yyy,zzz)     (&(xxx)->nodes[yyy])

/*+ Return a Segment points given a Node pointer and a set of segments. +*/
#define FirstSegment(xxx,yyy,zzz)   LookupSegment((xxx),(yyy)->nodes[zzz].firstseg,1)

/*+ Return the offset of a geographical region given a set of nodes and an index. +*/
#define LookupNodeOffset(xxx,yyy)   ((xxx)->offsets[yyy])

#else

static Node *LookupNode(Nodes *nodes,index_t index,int position);

#define FirstSegment(xxx,yyy,zzz)   LookupSegment((xxx),FirstSegment_internal(yyy,zzz),1)

static index_t FirstSegment_internal(Nodes *nodes,index_t index);

static index_t LookupNodeOffset(Nodes *nodes,index_t index);


/*++++++++++++++++++++++++++++++++++++++
  Find the Node information for a particular node.

  Node *LookupNode Returns a pointer to the cached node information.

  Nodes *nodes The nodes structure to use.

  index_t index The index of the node.

  int position The position in the cache to store the value.
  ++++++++++++++++++++++++++++++++++++++*/

static inline Node *LookupNode(Nodes *nodes,index_t index,int position)
{
 if(nodes->incache[position-1]!=index)
   {
    SeekFile(nodes->fd,nodes->nodesoffset+(off_t)index*sizeof(Node));

    ReadFile(nodes->fd,&nodes->cached[position-1],sizeof(Node));

    nodes->incache[position-1]=index;
   }

 return(&nodes->cached[position-1]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the index of the first segment of a node (called by FirstSegment() macro).

  index_t FirstSegment_internal Returns the index of the first segment.

  Nodes *nodes The nodes structure to use.

  index_t index The index of the node.
  ++++++++++++++++++++++++++++++++++++++*/

static inline index_t FirstSegment_internal(Nodes *nodes,index_t index)
{
 if(nodes->incache[0]==index)
    return(nodes->cached[0].firstseg);
 else if(nodes->incache[1]==index)
    return(nodes->cached[1].firstseg);
 else
   {
    Node *node=LookupNode(nodes,index,3);

    return(node->firstseg);
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Find the offset of nodes in a geographical region.

  index_t LookupNodeOffset Returns the value of the index offset.

  Nodes *nodes The nodes structure to use.

  index_t index The index of the offset.
  ++++++++++++++++++++++++++++++++++++++*/

static inline index_t LookupNodeOffset(Nodes *nodes,index_t index)
{
 index_t offset;

 SeekFile(nodes->fd,sizeof(NodesFile)+(off_t)index*sizeof(index_t));

 ReadFile(nodes->fd,&offset,sizeof(index_t));

 return(offset);
}

#endif


#endif /* NODES_H */
1	/***************************************
2	A header file for the nodes.
3
4	Part of the Routino routing software.
5	****************/ /****************
6	This file Copyright 2008-2011 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	#ifndef NODES_H
24	#define NODES_H /+ To stop multiple inclusions. +/
25
26	#include <stdint.h>
27
28	#include "types.h"
29
30	#include "files.h"
31	#include "profiles.h"
32
33
34	/* Data structures */
35
36
37	/+ A structure containing a single node. +/
38	struct _Node
39	{
40	index_t firstseg; /+ The index of the first segment. +/
41
42	ll_off_t latoffset; /+ The node latitude offset within its bin. +/
43	ll_off_t lonoffset; /+ The node longitude offset within its bin. +/
44
45	transports_t allow; /+ The types of transport that are allowed through the node. +/
46	uint16_t flags; /+ Flags containing extra information (super-node, turn restriction). +/
47	};
48
49
50	/+ A structure containing the header from the file. +/
51	typedef struct _NodesFile
52	{
53	index_t number; /+ How many nodes in total? +/
54	index_t snumber; /+ How many super-nodes? +/
55
56	index_t latbins; /+ The number of bins containing latitude. +/
57	index_t lonbins; /+ The number of bins containing longitude. +/
58
59	ll_bin_t latzero; /+ The bin number of the furthest south bin. +/
60	ll_bin_t lonzero; /+ The bin number of the furthest west bin. +/
61	}
62	NodesFile;
63
64
65	/+ A structure containing a set of nodes (and pointers to mmap file). +/
66	struct _Nodes
67	{
68	NodesFile file; /+ The header data from the file. +/
69
70	#if !SLIM
71
72	void data; /+ The memory mapped data. +*/
73
74	index_t offsets; /+ An array of offsets to the first node in each bin. +*/
75
76	Node nodes; /+ An array of nodes. +*/
77
78	#else
79
80	int fd; /+ The file descriptor for the file. +/
81	off_t nodesoffset; /+ The offset of the nodes within the file. +/
82
83	Node cached[2]; /+ The cached nodes. +/
84	index_t incache[2]; /+ The indexes of the cached nodes. +/
85
86	#endif
87	};
88
89
90	/* Functions */
91
92	Nodes LoadNodeList(const char filename);
93
94	index_t FindClosestNode(Nodes* nodes,Segments segments,Ways ways,double latitude,double longitude,
95	distance_t distance,Profile profile,distance_t bestdist);
96
97	index_t FindClosestSegment(Nodes* nodes,Segments segments,Ways ways,double latitude,double longitude,
98	distance_t distance,Profile profile, distance_t bestdist,
99	index_t bestnode1,index_t bestnode2,distance_t bestdist1,distance_t bestdist2);
100
101	void GetLatLong(Nodes nodes,index_t index,double latitude,double *longitude);
102
103
104	/* Macros and inline functions */
105
106	/+ Return true if this is a super-node. +/
107	#define IsSuperNode(xxx) (((xxx)->flags)&NODE_SUPER)
108
109	/+ Return true if this is a turn restricted node. +/
110	#define IsTurnRestrictedNode(xxx) (((xxx)->flags)&NODE_TURNRSTRCT)
111
112
113	#if !SLIM
114
115	/+ Return a Node pointer given a set of nodes and an index. +/
116	#define LookupNode(xxx,yyy,zzz) (&(xxx)->nodes[yyy])
117
118	/+ Return a Segment points given a Node pointer and a set of segments. +/
119	#define FirstSegment(xxx,yyy,zzz) LookupSegment((xxx),(yyy)->nodes[zzz].firstseg,1)
120
121	/+ Return the offset of a geographical region given a set of nodes and an index. +/
122	#define LookupNodeOffset(xxx,yyy) ((xxx)->offsets[yyy])
123
124	#else
125
126	static Node LookupNode(Nodes nodes,index_t index,int position);
127
128	#define FirstSegment(xxx,yyy,zzz) LookupSegment((xxx),FirstSegment_internal(yyy,zzz),1)
129
130	static index_t FirstSegment_internal(Nodes *nodes,index_t index);
131
132	static index_t LookupNodeOffset(Nodes *nodes,index_t index);
133
134
135	/*++++++++++++++++++++++++++++++++++++++
136	Find the Node information for a particular node.
137
138	Node *LookupNode Returns a pointer to the cached node information.
139
140	Nodes *nodes The nodes structure to use.
141
142	index_t index The index of the node.
143
144	int position The position in the cache to store the value.
145	++++++++++++++++++++++++++++++++++++++*/
146
147	static inline Node LookupNode(Nodes nodes,index_t index,int position)
148	{
149	if(nodes->incache[position-1]!=index)
150	{
151	SeekFile(nodes->fd,nodes->nodesoffset+(off_t)index*sizeof(Node));
152
153	ReadFile(nodes->fd,&nodes->cached[position-1],sizeof(Node));
154
155	nodes->incache[position-1]=index;
156	}
157
158	return(&nodes->cached[position-1]);
159	}
160
161
162	/*++++++++++++++++++++++++++++++++++++++
163	Find the index of the first segment of a node (called by FirstSegment() macro).
164
165	index_t FirstSegment_internal Returns the index of the first segment.
166
167	Nodes *nodes The nodes structure to use.
168
169	index_t index The index of the node.
170	++++++++++++++++++++++++++++++++++++++*/
171
172	static inline index_t FirstSegment_internal(Nodes *nodes,index_t index)
173	{
174	if(nodes->incache[0]==index)
175	return(nodes->cached[0].firstseg);
176	else if(nodes->incache[1]==index)
177	return(nodes->cached[1].firstseg);
178	else
179	{
180	Node *node=LookupNode(nodes,index,3);
181
182	return(node->firstseg);
183	}
184	}
185
186
187	/*++++++++++++++++++++++++++++++++++++++
188	Find the offset of nodes in a geographical region.
189
190	index_t LookupNodeOffset Returns the value of the index offset.
191
192	Nodes *nodes The nodes structure to use.
193
194	index_t index The index of the offset.
195	++++++++++++++++++++++++++++++++++++++*/
196
197	static inline index_t LookupNodeOffset(Nodes *nodes,index_t index)
198	{
199	index_t offset;
200
201	SeekFile(nodes->fd,sizeof(NodesFile)+(off_t)index*sizeof(index_t));
202
203	ReadFile(nodes->fd,&offset,sizeof(index_t));
204
205	return(offset);
206	}
207
208	#endif
209
210
211	#endif /* NODES_H */