Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/nodesx.h
Parent Directory
| 
Revision Log
Revision 643 -
(show annotations)
(download)
(as text)
Sat Feb 26 16:37:14 2011 UTC (14 years ago) by amb
File MIME type: text/x-chdr
File size: 4666 byte(s)
Sat Feb 26 16:37:14 2011 UTC (14 years ago) by amb
File MIME type: text/x-chdr
File size: 4666 byte(s)
Go back to the internal structure used (but reverted) during version 1.2 development where each segment is stored only once. This halves the memory usage (mmap files or just files) for planetsplitter. This is allowed because a new algorithm to create the node to segment indexes makes it simpler now that it was. This change is required so that super-node/segment optimisation doesn't remove mutual loops. This change doesn't handle turn restrictions yet.
| 1 | /*************************************** |
| 2 | A header file for the extended 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 NODESX_H |
| 24 | #define NODESX_H /*+ To stop multiple inclusions. +*/ |
| 25 | |
| 26 | #include <stdint.h> |
| 27 | |
| 28 | #include "types.h" |
| 29 | #include "nodes.h" |
| 30 | |
| 31 | #include "typesx.h" |
| 32 | |
| 33 | #include "files.h" |
| 34 | |
| 35 | |
| 36 | /* Data structures */ |
| 37 | |
| 38 | |
| 39 | /*+ An extended structure used for processing. +*/ |
| 40 | struct _NodeX |
| 41 | { |
| 42 | node_t id; /*+ The node identifier; initially the OSM value, later the Node index, finally the first segment. +*/ |
| 43 | |
| 44 | latlong_t latitude; /*+ The node latitude. +*/ |
| 45 | latlong_t longitude; /*+ The node longitude. +*/ |
| 46 | |
| 47 | transports_t allow; /*+ The node allowed traffic. +*/ |
| 48 | |
| 49 | uint16_t flags; /*+ The node flags. +*/ |
| 50 | }; |
| 51 | |
| 52 | /*+ A structure containing a set of nodes (memory format). +*/ |
| 53 | struct _NodesX |
| 54 | { |
| 55 | char *filename; /*+ The name of the temporary file. +*/ |
| 56 | int fd; /*+ The file descriptor of the temporary file. +*/ |
| 57 | |
| 58 | index_t xnumber; /*+ The number of unsorted extended nodes. +*/ |
| 59 | |
| 60 | #if !SLIM |
| 61 | |
| 62 | NodeX *xdata; /*+ The extended node data (sorted). +*/ |
| 63 | |
| 64 | #else |
| 65 | |
| 66 | NodeX xcached[2]; /*+ Two cached nodes read from the file in slim mode. +*/ |
| 67 | |
| 68 | #endif |
| 69 | |
| 70 | index_t number; /*+ How many entries are still useful? +*/ |
| 71 | |
| 72 | node_t *idata; /*+ The extended node IDs (sorted by ID). +*/ |
| 73 | |
| 74 | node_t *gdata; /*+ The final node indexes (sorted by ID). +*/ |
| 75 | |
| 76 | uint8_t *super; /*+ A marker for super nodes (same order as sorted nodes). +*/ |
| 77 | |
| 78 | index_t latbins; /*+ The number of bins containing latitude. +*/ |
| 79 | index_t lonbins; /*+ The number of bins containing longitude. +*/ |
| 80 | |
| 81 | ll_bin_t latzero; /*+ The bin number of the furthest south bin. +*/ |
| 82 | ll_bin_t lonzero; /*+ The bin number of the furthest west bin. +*/ |
| 83 | }; |
| 84 | |
| 85 | |
| 86 | /* Functions */ |
| 87 | |
| 88 | NodesX *NewNodeList(int append); |
| 89 | void FreeNodeList(NodesX *nodesx,int keep); |
| 90 | |
| 91 | void SaveNodeList(NodesX *nodesx,const char *filename); |
| 92 | |
| 93 | index_t IndexNodeX(NodesX* nodesx,node_t id); |
| 94 | |
| 95 | void AppendNode(NodesX* nodesx,node_t id,double latitude,double longitude,transports_t allow,uint16_t flags); |
| 96 | |
| 97 | void SortNodeList(NodesX *nodesx); |
| 98 | |
| 99 | void SortNodeListGeographically(NodesX* nodesx); |
| 100 | |
| 101 | void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx); |
| 102 | |
| 103 | void UpdateNodes(NodesX *nodesx,SegmentsX *segmentsx,int iteration); |
| 104 | |
| 105 | |
| 106 | /* Macros / inline functions */ |
| 107 | |
| 108 | #if !SLIM |
| 109 | |
| 110 | #define LookupNodeX(nodesx,index,position) &(nodesx)->xdata[index] |
| 111 | |
| 112 | #define PutBackNodeX(nodesx,index,position) /* nop */ |
| 113 | |
| 114 | #else |
| 115 | |
| 116 | static NodeX *LookupNodeX(NodesX* nodesx,index_t index,int position); |
| 117 | |
| 118 | static void PutBackNodeX(NodesX* nodesx,index_t index,int position); |
| 119 | |
| 120 | |
| 121 | /*++++++++++++++++++++++++++++++++++++++ |
| 122 | Lookup a particular extended node. |
| 123 | |
| 124 | NodeX *LookupNodeX Returns a pointer to the extended node with the specified id. |
| 125 | |
| 126 | NodesX* nodesx The set of nodes to process. |
| 127 | |
| 128 | index_t index The node index to look for. |
| 129 | |
| 130 | int position The position in the cache to use. |
| 131 | ++++++++++++++++++++++++++++++++++++++*/ |
| 132 | |
| 133 | static inline NodeX *LookupNodeX(NodesX* nodesx,index_t index,int position) |
| 134 | { |
| 135 | SeekFile(nodesx->fd,(off_t)index*sizeof(NodeX)); |
| 136 | |
| 137 | ReadFile(nodesx->fd,&nodesx->xcached[position-1],sizeof(NodeX)); |
| 138 | |
| 139 | return(&nodesx->xcached[position-1]); |
| 140 | } |
| 141 | |
| 142 | |
| 143 | /*++++++++++++++++++++++++++++++++++++++ |
| 144 | Put back an extended node's data. |
| 145 | |
| 146 | NodesX* nodesx The set of nodes to process. |
| 147 | |
| 148 | index_t index The node index to put back. |
| 149 | |
| 150 | int position The position in the cache to use. |
| 151 | ++++++++++++++++++++++++++++++++++++++*/ |
| 152 | |
| 153 | static inline void PutBackNodeX(NodesX* nodesx,index_t index,int position) |
| 154 | { |
| 155 | SeekFile(nodesx->fd,(off_t)index*sizeof(NodeX)); |
| 156 | |
| 157 | WriteFile(nodesx->fd,&nodesx->xcached[position-1],sizeof(NodeX)); |
| 158 | } |
| 159 | |
| 160 | #endif /* SLIM */ |
| 161 | |
| 162 | |
| 163 | #endif /* NODESX_H */ |
Properties
| Name | Value |
|---|---|
| cvs:description | Extended nodes header. |