Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/nodes.c
Parent Directory
| 
Revision Log
Revision 17 -
(show annotations)
(download)
(as text)
Wed Jan 7 19:21:06 2009 UTC (16 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 5627 byte(s)
Wed Jan 7 19:21:06 2009 UTC (16 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 5627 byte(s)
Lots of modifications: Two data structures - in memory (pointers) and in file (array). Data is hashed into multiple bins. Each function takes a nodes structure as an argument.
| 1 | /*************************************** |
| 2 | $Header: /home/amb/CVS/routino/src/nodes.c,v 1.4 2009-01-07 19:21:06 amb Exp $ |
| 3 | |
| 4 | Node data type functions. |
| 5 | ******************/ /****************** |
| 6 | Written by Andrew M. Bishop |
| 7 | |
| 8 | This file Copyright 2008,2009 Andrew M. Bishop |
| 9 | It may be distributed under the GNU Public License, version 2, or |
| 10 | any higher version. See section COPYING of the GNU Public license |
| 11 | for conditions under which this file may be redistributed. |
| 12 | ***************************************/ |
| 13 | |
| 14 | |
| 15 | #include <assert.h> |
| 16 | #include <stdlib.h> |
| 17 | |
| 18 | #include "functions.h" |
| 19 | #include "nodes.h" |
| 20 | |
| 21 | |
| 22 | /* Functions */ |
| 23 | |
| 24 | static int sort_by_id(Node *a,Node *b); |
| 25 | |
| 26 | |
| 27 | /*++++++++++++++++++++++++++++++++++++++ |
| 28 | Allocate a new node list. |
| 29 | |
| 30 | NodesMem *NewNodeList Returns the node list. |
| 31 | ++++++++++++++++++++++++++++++++++++++*/ |
| 32 | |
| 33 | NodesMem *NewNodeList(void) |
| 34 | { |
| 35 | NodesMem *nodes; |
| 36 | int i; |
| 37 | |
| 38 | nodes=(NodesMem*)calloc(sizeof(NodesMem),1); |
| 39 | |
| 40 | nodes->alloced=INCREMENT_NODES; |
| 41 | |
| 42 | for(i=0;i<NBINS_NODES;i++) |
| 43 | nodes->bins[i]=(Node*)malloc(nodes->alloced*sizeof(Node)); |
| 44 | |
| 45 | return(nodes); |
| 46 | } |
| 47 | |
| 48 | |
| 49 | /*++++++++++++++++++++++++++++++++++++++ |
| 50 | Load in a node list from a file. |
| 51 | |
| 52 | NodesFile* LoadNodeList Returns the node list. |
| 53 | |
| 54 | const char *filename The name of the file to load. |
| 55 | ++++++++++++++++++++++++++++++++++++++*/ |
| 56 | |
| 57 | NodesFile *LoadNodeList(const char *filename) |
| 58 | { |
| 59 | return((NodesFile*)MapFile(filename)); |
| 60 | } |
| 61 | |
| 62 | |
| 63 | /*++++++++++++++++++++++++++++++++++++++ |
| 64 | Save the node list to a file. |
| 65 | |
| 66 | NodesFile* SaveNodeList Returns the node list that has just been saved. |
| 67 | |
| 68 | NodesMem* nodesm The set of nodes to save. |
| 69 | |
| 70 | const char *filename The name of the file to save. |
| 71 | ++++++++++++++++++++++++++++++++++++++*/ |
| 72 | |
| 73 | NodesFile *SaveNodeList(NodesMem* nodesm,const char *filename) |
| 74 | { |
| 75 | NodesFile nodesf; |
| 76 | int i; |
| 77 | |
| 78 | assert(nodesm->sorted); /* Must be sorted */ |
| 79 | |
| 80 | nodesf.offset[0]=0; |
| 81 | for(i=1;i<=NBINS_NODES;i++) |
| 82 | nodesf.offset[i]=nodesf.offset[i-1]+nodesm->number[i-1]; |
| 83 | |
| 84 | if(WriteFile(filename,(void*)&nodesf,sizeof(nodesf.offset),0)) |
| 85 | assert(0); |
| 86 | |
| 87 | for(i=0;i<NBINS_NODES;i++) |
| 88 | if(WriteFile(filename,(void*)nodesm->bins[i],nodesm->number[i]*sizeof(Node),1)) |
| 89 | assert(0); |
| 90 | |
| 91 | for(i=0;i<NBINS_NODES;i++) |
| 92 | free(nodesm->bins[i]); |
| 93 | |
| 94 | free(nodesm); |
| 95 | |
| 96 | return(LoadNodeList(filename)); |
| 97 | } |
| 98 | |
| 99 | |
| 100 | /*++++++++++++++++++++++++++++++++++++++ |
| 101 | Find a particular node. |
| 102 | |
| 103 | Node *FindNode Returns a pointer to the node with the specified id. |
| 104 | |
| 105 | NodesFile* nodes The set of nodes to process. |
| 106 | |
| 107 | node_t id The node id to look for. |
| 108 | ++++++++++++++++++++++++++++++++++++++*/ |
| 109 | |
| 110 | Node *FindNode(NodesFile* nodes,node_t id) |
| 111 | { |
| 112 | int bin=id%NBINS_NODES; |
| 113 | int start=nodes->offset[bin]; |
| 114 | int end=nodes->offset[bin+1]-1; |
| 115 | int mid; |
| 116 | |
| 117 | /* Binary search - search key exact match only is required. |
| 118 | * |
| 119 | * # <- start | Check mid and move start or end if it doesn't match |
| 120 | * # | |
| 121 | * # | Since an exact match is wanted we can set end=mid-1 |
| 122 | * # <- mid | or start=mid+1 because we know that mid doesn't match. |
| 123 | * # | |
| 124 | * # | Eventually either end=start or end=start+1 and one of |
| 125 | * # <- end | start or end is the wanted one. |
| 126 | */ |
| 127 | |
| 128 | if(end<start) /* There are no nodes */ |
| 129 | return(NULL); |
| 130 | else if(id<nodes->nodes[start].id) /* Check key is not before start */ |
| 131 | return(NULL); |
| 132 | else if(id>nodes->nodes[end].id) /* Check key is not after end */ |
| 133 | return(NULL); |
| 134 | else |
| 135 | { |
| 136 | do |
| 137 | { |
| 138 | mid=(start+end)/2; /* Choose mid point */ |
| 139 | |
| 140 | if(nodes->nodes[mid].id<id) /* Mid point is too low */ |
| 141 | start=mid+1; |
| 142 | else if(nodes->nodes[mid].id>id) /* Mid point is too high */ |
| 143 | end=mid-1; |
| 144 | else /* Mid point is correct */ |
| 145 | return(&nodes->nodes[mid]); |
| 146 | } |
| 147 | while((end-start)>1); |
| 148 | |
| 149 | if(nodes->nodes[start].id==id) /* Start is correct */ |
| 150 | return(&nodes->nodes[start]); |
| 151 | |
| 152 | if(nodes->nodes[end].id==id) /* End is correct */ |
| 153 | return(&nodes->nodes[end]); |
| 154 | } |
| 155 | |
| 156 | return(NULL); |
| 157 | } |
| 158 | |
| 159 | |
| 160 | /*++++++++++++++++++++++++++++++++++++++ |
| 161 | Append a node to a newly created node list (unsorted). |
| 162 | |
| 163 | NodesMem* nodes The set of nodes to process. |
| 164 | |
| 165 | node_t id The node identification. |
| 166 | |
| 167 | latlong_t latitude The latitude of the node. |
| 168 | |
| 169 | latlong_t longitude The longitude of the node. |
| 170 | ++++++++++++++++++++++++++++++++++++++*/ |
| 171 | |
| 172 | void AppendNode(NodesMem* nodes,node_t id,latlong_t latitude,latlong_t longitude) |
| 173 | { |
| 174 | int i; |
| 175 | int bin=id%NBINS_NODES; |
| 176 | |
| 177 | /* Check that the arrays have enough space. */ |
| 178 | |
| 179 | if(nodes->number[bin]==nodes->alloced) |
| 180 | { |
| 181 | nodes->alloced+=INCREMENT_NODES; |
| 182 | |
| 183 | for(i=0;i<NBINS_NODES;i++) |
| 184 | nodes->bins[i]=(Node*)realloc((void*)nodes->bins[i],nodes->alloced*sizeof(Node)); |
| 185 | } |
| 186 | |
| 187 | /* Insert the node */ |
| 188 | |
| 189 | nodes->bins[bin][nodes->number[bin]].id=id; |
| 190 | nodes->bins[bin][nodes->number[bin]].latitude=latitude; |
| 191 | nodes->bins[bin][nodes->number[bin]].longitude=longitude; |
| 192 | |
| 193 | nodes->number[bin]++; |
| 194 | |
| 195 | nodes->sorted=0; |
| 196 | } |
| 197 | |
| 198 | |
| 199 | /*++++++++++++++++++++++++++++++++++++++ |
| 200 | Sort the node list. |
| 201 | |
| 202 | NodesMem* nodes The set of nodes to process. |
| 203 | ++++++++++++++++++++++++++++++++++++++*/ |
| 204 | |
| 205 | void SortNodeList(NodesMem* nodes) |
| 206 | { |
| 207 | int i; |
| 208 | |
| 209 | for(i=0;i<NBINS_NODES;i++) |
| 210 | qsort(nodes->bins[i],nodes->number[i],sizeof(Node),(int (*)(const void*,const void*))sort_by_id); |
| 211 | |
| 212 | nodes->sorted=1; |
| 213 | } |
| 214 | |
| 215 | |
| 216 | /*++++++++++++++++++++++++++++++++++++++ |
| 217 | Sort the nodes into id order. |
| 218 | |
| 219 | int sort_by_id Returns the comparison of the id fields. |
| 220 | |
| 221 | Node *a The first Node. |
| 222 | |
| 223 | Node *b The second Node. |
| 224 | ++++++++++++++++++++++++++++++++++++++*/ |
| 225 | |
| 226 | static int sort_by_id(Node *a,Node *b) |
| 227 | { |
| 228 | node_t a_id=a->id; |
| 229 | node_t b_id=b->id; |
| 230 | |
| 231 | return(a_id-b_id); |
| 232 | } |
Properties
| Name | Value |
|---|---|
| cvs:description | Node data type. |