trunk/src/nodes.h

/***************************************
 $Header: /home/amb/CVS/routino/src/nodes.h,v 1.32 2010-07-23 14:35:27 amb Exp $

 A header file for the nodes.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2010 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. +*/
};


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

 uint32_t latbins;              /*+ The number of bins containing latitude. +*/
 uint32_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. +*/

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

#if !SLIM

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

 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[3];           /*+ The cached nodes. +*/
 index_t   incache[3];          /*+ 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 */

#if !SLIM

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

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

/*+ Return true if this is a super-node. +*/
#define IsSuperNode(xxx,yyy)        (((xxx)->nodes[yyy].firstseg)&NODE_SUPER)

#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 int IsSuperNode(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)
{
 SeekFile(nodes->fd,nodes->nodesoffset+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(SEGMENT(nodes->cached[0].firstseg));
 else if(nodes->incache[1]==index)
    return(SEGMENT(nodes->cached[1].firstseg));
 else if(nodes->incache[2]==index)
    return(SEGMENT(nodes->cached[2].firstseg));
 else
   {
    Node *node=LookupNode(nodes,index,3);

    return(SEGMENT(node->firstseg));
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Decide if a node is a super-node.

  int IsSuperNode Return true if it is a supernode.

  Nodes *nodes The nodes structure to use.

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

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

    return(node->firstseg&NODE_SUPER);
   }
}

#endif


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