git.maemo.org Git - routino/blob - src/nodes.h

   1 /***************************************
   2  $Header: /home/amb/routino/src/RCS/nodes.h,v 1.37 2010/08/03 18:28:30 amb Exp $
   3
   4  A header file for the nodes.
   5
   6  Part of the Routino routing software.
   7  ******************/ /******************
   8  This file Copyright 2008-2010 Andrew M. Bishop
   9
  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.
  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  ***************************************/
  23
  24
  25 #ifndef NODES_H
  26 #define NODES_H    /*+ To stop multiple inclusions. +*/
  27
  28 #include <stdint.h>
  29
  30 #include "types.h"
  31
  32 #include "files.h"
  33 #include "profiles.h"
  34
  35
  36 /* Data structures */
  37
  38
  39 /*+ A structure containing a single node. +*/
  40 struct _Node
  41 {
  42  index_t    firstseg;           /*+ The index of the first segment. +*/
  43
  44  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  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). +*/
  49 };
  50
  51
  52 /*+ A structure containing the header from the file. +*/
  53 typedef struct _NodesFile
  54 {
  55  index_t  number;               /*+ How many nodes in total? +*/
  56  index_t  snumber;              /*+ How many super-nodes? +*/
  57
  58  index_t  latbins;              /*+ The number of bins containing latitude. +*/
  59  index_t  lonbins;              /*+ The number of bins containing longitude. +*/
  60
  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. +*/
  63 }
  64  NodesFile;
  65
  66
  67 /*+ A structure containing a set of nodes (and pointers to mmap file). +*/
  68 struct _Nodes
  69 {
  70  NodesFile file;                /*+ The header data from the file. +*/
  71
  72 #if !SLIM
  73
  74  void     *data;                /*+ The memory mapped data. +*/
  75
  76  index_t  *offsets;             /*+ An array of offsets to the first node in each bin. +*/
  77
  78  Node     *nodes;               /*+ An array of nodes. +*/
  79
  80 #else
  81
  82  int       fd;                  /*+ The file descriptor for the file. +*/
  83  off_t     nodesoffset;         /*+ The offset of the nodes within the file. +*/
  84
  85  Node      cached[3];           /*+ The cached nodes. +*/
  86  index_t   incache[3];          /*+ The indexes of the cached nodes. +*/
  87
  88 #endif
  89 };
  90
  91
  92 /* Functions */
  93
  94 Nodes *LoadNodeList(const char *filename);
  95
  96 index_t FindClosestNode(Nodes* nodes,Segments *segments,Ways *ways,double latitude,double longitude,
  97                         distance_t distance,Profile *profile,distance_t *bestdist);
  98
  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);
 102
 103 void GetLatLong(Nodes *nodes,index_t index,double *latitude,double *longitude);
 104
 105
 106 /* Macros and inline functions */
 107
 108 #if !SLIM
 109
 110 /*+ Return a Node pointer given a set of nodes and an index. +*/
 111 #define LookupNode(xxx,yyy,zzz)     (&(xxx)->nodes[yyy])
 112
 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)
 115
 116 /*+ Return true if this is a super-node. +*/
 117 #define IsSuperNode(xxx,yyy)        (((xxx)->nodes[yyy].flags)&NODE_SUPER)
 118
 119 /*+ Return the offset of a geographical region given a set of nodes and an index. +*/
 120 #define LookupNodeOffset(xxx,yyy)   ((xxx)->offsets[yyy])
 121
 122 #else
 123
 124 static Node *LookupNode(Nodes *nodes,index_t index,int position);
 125
 126 #define FirstSegment(xxx,yyy,zzz)   LookupSegment((xxx),FirstSegment_internal(yyy,zzz),1)
 127
 128 static index_t FirstSegment_internal(Nodes *nodes,index_t index);
 129
 130 static int IsSuperNode(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  SeekFile(nodes->fd,nodes->nodesoffset+(off_t)index*sizeof(Node));
 150
 151  ReadFile(nodes->fd,&nodes->cached[position-1],sizeof(Node));
 152
 153  nodes->incache[position-1]=index;
 154
 155  return(&nodes->cached[position-1]);
 156 }
 157
 158
 159 /*++++++++++++++++++++++++++++++++++++++
 160   Find the index of the first segment of a node (called by FirstSegment() macro).
 161
 162   index_t FirstSegment_internal Returns the index of the first segment.
 163
 164   Nodes *nodes The nodes structure to use.
 165
 166   index_t index The index of the node.
 167   ++++++++++++++++++++++++++++++++++++++*/
 168
 169 static inline index_t FirstSegment_internal(Nodes *nodes,index_t index)
 170 {
 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);
 177  else
 178    {
 179     Node *node=LookupNode(nodes,index,3);
 180
 181     return(node->firstseg);
 182    }
 183 }
 184
 185
 186 /*++++++++++++++++++++++++++++++++++++++
 187   Decide if a node is a super-node.
 188
 189   int IsSuperNode Return true if it is a supernode.
 190
 191   Nodes *nodes The nodes structure to use.
 192
 193   index_t index The index of the node.
 194   ++++++++++++++++++++++++++++++++++++++*/
 195
 196 static inline int IsSuperNode(Nodes *nodes,index_t index)
 197 {
 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);
 204  else
 205    {
 206     Node *node=LookupNode(nodes,index,3);
 207
 208     return(node->flags&NODE_SUPER);
 209    }
 210 }
 211
 212
 213 /*++++++++++++++++++++++++++++++++++++++
 214   Find the offset of nodes in a geographical region.
 215
 216   index_t LookupNodeOffset Returns the value of the index offset.
 217
 218   Nodes *nodes The nodes structure to use.
 219
 220   index_t index The index of the offset.
 221   ++++++++++++++++++++++++++++++++++++++*/
 222
 223 static inline index_t LookupNodeOffset(Nodes *nodes,index_t index)
 224 {
 225  index_t offset;
 226
 227  SeekFile(nodes->fd,sizeof(NodesFile)+(off_t)index*sizeof(index_t));
 228
 229  ReadFile(nodes->fd,&offset,sizeof(index_t));
 230
 231  return(offset);
 232 }
 233
 234 #endif
 235
 236
 237 #endif /* NODES_H */