Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

/[routino]/trunk/src/nodesx.c
ViewVC logotype

Contents of /trunk/src/nodesx.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 212 - (show annotations) (download) (as text)
Wed Jul 1 18:23:26 2009 UTC (15 years, 8 months ago) by amb
File MIME type: text/x-csrc
File size: 14908 byte(s) 
Remove the Node structure from the NodeX structure to save memory.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.18 2009-07-01 18:23:26 amb Exp $
3
4 Extented Node data type functions.
5
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008,2009 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 #include <assert.h>
26 #include <stdlib.h>
27 #include <string.h>
28 #include <stdio.h>
29 #include <math.h>
30
31 #include "types.h"
32 #include "functions.h"
33 #include "nodesx.h"
34 #include "segmentsx.h"
35 #include "waysx.h"
36
37
38 /* Constants */
39
40 /*+ The array size increment for nodes - expect ~8,000,000 nodes. +*/
41 #define INCREMENT_NODES 1024*1024
42
43
44 /* Functions */
45
46 static int sort_by_id(NodeX **a,NodeX **b);
47 static int sort_by_lat_long(NodeX **a,NodeX **b);
48
49
50 /*++++++++++++++++++++++++++++++++++++++
51 Allocate a new node list.
52
53 NodesX *NewNodeList Returns the node list.
54 ++++++++++++++++++++++++++++++++++++++*/
55
56 NodesX *NewNodeList(void)
57 {
58 NodesX *nodesx;
59
60 nodesx=(NodesX*)malloc(sizeof(NodesX));
61
62 nodesx->alloced=INCREMENT_NODES;
63 nodesx->xnumber=0;
64 nodesx->sorted=0;
65
66 nodesx->xdata=(NodeX*)malloc(nodesx->alloced*sizeof(NodeX));
67 nodesx->gdata=NULL;
68 nodesx->idata=NULL;
69
70 nodesx->ndata=NULL;
71
72 return(nodesx);
73 }
74
75
76 /*++++++++++++++++++++++++++++++++++++++
77 Save the node list to a file.
78
79 NodesX* nodesx The set of nodes to save.
80
81 const char *filename The name of the file to save.
82 ++++++++++++++++++++++++++++++++++++++*/
83
84 void SaveNodeList(NodesX* nodesx,const char *filename)
85 {
86 int i;
87 int fd;
88 Nodes *nodes=calloc(1,sizeof(Nodes));
89 index_t *offsets;
90 int32_t lat_min,lat_max,lon_min,lon_max;
91 int latbins,lonbins,latlonbin;
92
93 assert(nodesx->sorted); /* Must be sorted */
94
95 /* Work out the offsets */
96
97 lat_min=lat_long_to_bin(nodesx->lat_min);
98 lon_min=lat_long_to_bin(nodesx->lon_min);
99 lat_max=lat_long_to_bin(nodesx->lat_max);
100 lon_max=lat_long_to_bin(nodesx->lon_max);
101
102 latbins=(lat_max-lat_min)+1;
103 lonbins=(lon_max-lon_min)+1;
104
105 offsets=malloc((latbins*lonbins+1)*sizeof(index_t));
106
107 latlonbin=0;
108
109 for(i=0;i<nodesx->number;i++)
110 {
111 int32_t latbin=lat_long_to_bin(nodesx->gdata[i]->latitude )-lat_min;
112 int32_t lonbin=lat_long_to_bin(nodesx->gdata[i]->longitude)-lon_min;
113 int llbin=lonbin*latbins+latbin;
114
115 for(;latlonbin<=llbin;latlonbin++)
116 offsets[latlonbin]=i;
117 }
118
119 for(;latlonbin<=(latbins*lonbins);latlonbin++)
120 offsets[latlonbin]=nodesx->number;
121
122 /* Fill in a Nodes structure with the offset of the real data in the file after
123 the Node structure itself. */
124
125 nodes->number=nodesx->number;
126
127 nodes->latbins=latbins;
128 nodes->lonbins=lonbins;
129
130 nodes->latzero=lat_min;
131 nodes->lonzero=lon_min;
132
133 nodes->data=NULL;
134 nodes->offsets=(void*)sizeof(Nodes);
135 nodes->nodes=(void*)sizeof(Nodes)+(latbins*lonbins+1)*sizeof(index_t);
136
137 /* Write out the Nodes structure and then the real data. */
138
139 fd=OpenFile(filename);
140
141 WriteFile(fd,nodes,sizeof(Nodes));
142
143 WriteFile(fd,offsets,(latbins*lonbins+1)*sizeof(index_t));
144
145 for(i=0;i<nodes->number;i++)
146 {
147 NodeX **nodex=FindNodeX(nodesx,nodesx->gdata[i]->id);
148 Node *node =&nodesx->ndata[nodex-nodesx->idata];
149
150 WriteFile(fd,node,sizeof(Node));
151
152 if(!((i+1)%10000))
153 {
154 printf("\rWriting Nodes: Nodes=%d",i+1);
155 fflush(stdout);
156 }
157 }
158
159 printf("\rWrote Nodes: Nodes=%d \n",nodes->number);
160 fflush(stdout);
161
162 CloseFile(fd);
163
164 /* Free the fake Nodes */
165
166 free(nodes);
167 free(offsets);
168 }
169
170
171 /*++++++++++++++++++++++++++++++++++++++
172 Find a particular node.
173
174 NodeX **FindNodeX Returns a pointer to the extended node with the specified id.
175
176 NodesX* nodesx The set of nodes to process.
177
178 node_t id The node id to look for.
179 ++++++++++++++++++++++++++++++++++++++*/
180
181 NodeX **FindNodeX(NodesX* nodesx,node_t id)
182 {
183 int start=0;
184 int end=nodesx->number-1;
185 int mid;
186
187 assert(nodesx->sorted); /* Must be sorted */
188
189 /* Binary search - search key exact match only is required.
190 *
191 * # <- start | Check mid and move start or end if it doesn't match
192 * # |
193 * # | Since an exact match is wanted we can set end=mid-1
194 * # <- mid | or start=mid+1 because we know that mid doesn't match.
195 * # |
196 * # | Eventually either end=start or end=start+1 and one of
197 * # <- end | start or end is the wanted one.
198 */
199
200 if(end<start) /* There are no nodes */
201 return(NULL);
202 else if(id<nodesx->idata[start]->id) /* Check key is not before start */
203 return(NULL);
204 else if(id>nodesx->idata[end]->id) /* Check key is not after end */
205 return(NULL);
206 else
207 {
208 do
209 {
210 mid=(start+end)/2; /* Choose mid point */
211
212 if(nodesx->idata[mid]->id<id) /* Mid point is too low */
213 start=mid+1;
214 else if(nodesx->idata[mid]->id>id) /* Mid point is too high */
215 end=mid-1;
216 else /* Mid point is correct */
217 return(&nodesx->idata[mid]);
218 }
219 while((end-start)>1);
220
221 if(nodesx->idata[start]->id==id) /* Start is correct */
222 return(&nodesx->idata[start]);
223
224 if(nodesx->idata[end]->id==id) /* End is correct */
225 return(&nodesx->idata[end]);
226 }
227
228 return(NULL);
229 }
230
231
232 /*++++++++++++++++++++++++++++++++++++++
233 Append a node to a newly created node list (unsorted).
234
235 NodesX* nodesx The set of nodes to process.
236
237 node_t id The node identification.
238
239 float latitude The latitude of the node.
240
241 float longitude The longitude of the node.
242 ++++++++++++++++++++++++++++++++++++++*/
243
244 void AppendNode(NodesX* nodesx,node_t id,float latitude,float longitude)
245 {
246 /* Check that the array has enough space. */
247
248 if(nodesx->xnumber==nodesx->alloced)
249 {
250 nodesx->alloced+=INCREMENT_NODES;
251
252 nodesx->xdata=(NodeX*)realloc((void*)nodesx->xdata,nodesx->alloced*sizeof(NodeX));
253 }
254
255 /* Insert the node */
256
257 nodesx->xdata[nodesx->xnumber].id=id;
258 nodesx->xdata[nodesx->xnumber].super=0;
259 nodesx->xdata[nodesx->xnumber].latitude =floorf(latitude *LAT_LONG_SCALE)/LAT_LONG_SCALE;
260 nodesx->xdata[nodesx->xnumber].longitude=floorf(longitude*LAT_LONG_SCALE)/LAT_LONG_SCALE;
261
262 nodesx->xnumber++;
263
264 nodesx->sorted=0;
265 }
266
267
268 /*++++++++++++++++++++++++++++++++++++++
269 Sort the node list.
270
271 NodesX* nodesx The set of nodes to process.
272 ++++++++++++++++++++++++++++++++++++++*/
273
274 void SortNodeList(NodesX* nodesx)
275 {
276 int i;
277 int duplicate;
278
279 printf("Sorting Nodes"); fflush(stdout);
280
281 /* Allocate the arrays of pointers */
282
283 if(nodesx->idata)
284 nodesx->idata=realloc(nodesx->idata,nodesx->xnumber*sizeof(NodeX*));
285 else
286 nodesx->idata=malloc(nodesx->xnumber*sizeof(NodeX*));
287
288 sort_again:
289
290 nodesx->number=0;
291
292 for(i=0;i<nodesx->xnumber;i++)
293 if(nodesx->xdata[i].id!=NO_NODE)
294 {
295 nodesx->idata[nodesx->number]=&nodesx->xdata[i];
296 nodesx->number++;
297 }
298
299 nodesx->sorted=1;
300
301 /* Sort by id */
302
303 qsort(nodesx->idata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_id);
304
305 duplicate=0;
306
307 for(i=1;i<nodesx->number;i++)
308 {
309 if(nodesx->idata[i]->id==nodesx->idata[i-1]->id &&
310 nodesx->idata[i]->id!=NO_NODE)
311 {
312 nodesx->idata[i-1]->id=NO_NODE;
313 duplicate++;
314 }
315 }
316
317 if(duplicate)
318 {
319 printf(" - %d duplicates found; trying again.\nSorting Nodes",duplicate); fflush(stdout);
320 goto sort_again;
321 }
322
323 printf("\rSorted Nodes \n"); fflush(stdout);
324 }
325
326
327 /*++++++++++++++++++++++++++++++++++++++
328 Sort the nodes into id order.
329
330 int sort_by_id Returns the comparison of the id fields.
331
332 NodeX **a The first Node.
333
334 NodeX **b The second Node.
335 ++++++++++++++++++++++++++++++++++++++*/
336
337 static int sort_by_id(NodeX **a,NodeX **b)
338 {
339 node_t a_id=(*a)->id;
340 node_t b_id=(*b)->id;
341
342 if(a_id<b_id)
343 return(-1);
344 else if(a_id>b_id)
345 return(1);
346 else
347 return(0);
348 }
349
350
351 /*++++++++++++++++++++++++++++++++++++++
352 Sort the node list geographically.
353
354 NodesX* nodesx The set of nodes to process.
355 ++++++++++++++++++++++++++++++++++++++*/
356
357 void SortNodeListGeographically(NodesX* nodesx)
358 {
359 int i;
360
361 assert(nodesx->sorted); /* Must be sorted */
362
363 printf("Sorting Nodes Geographically"); fflush(stdout);
364
365 /* Sort geographically */
366
367 nodesx->gdata=(NodeX**)malloc(nodesx->number*sizeof(NodeX*));
368
369 for(i=0;i<nodesx->number;i++)
370 nodesx->gdata[i]=nodesx->idata[i];
371
372 qsort(nodesx->gdata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_lat_long);
373
374 /* Work out the range of data */
375
376 nodesx->lat_min=2;
377 nodesx->lat_max=-2;
378 nodesx->lon_min=4;
379 nodesx->lon_max=-4;
380
381 for(i=0;i<nodesx->number;i++)
382 {
383 if(nodesx->idata[i]->latitude<nodesx->lat_min)
384 nodesx->lat_min=nodesx->idata[i]->latitude;
385 if(nodesx->idata[i]->latitude>nodesx->lat_max)
386 nodesx->lat_max=nodesx->idata[i]->latitude;
387 if(nodesx->idata[i]->longitude<nodesx->lon_min)
388 nodesx->lon_min=nodesx->idata[i]->longitude;
389 if(nodesx->idata[i]->longitude>nodesx->lon_max)
390 nodesx->lon_max=nodesx->idata[i]->longitude;
391 }
392
393 printf("\rSorted Nodes Geographically\n"); fflush(stdout);
394 }
395
396
397 /*++++++++++++++++++++++++++++++++++++++
398 Sort the nodes into latitude and longitude order.
399
400 int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
401
402 NodeX **a The first Node.
403
404 NodeX **b The second Node.
405 ++++++++++++++++++++++++++++++++++++++*/
406
407 static int sort_by_lat_long(NodeX **a,NodeX **b)
408 {
409 int32_t a_lon=lat_long_to_bin((*a)->longitude);
410 int32_t b_lon=lat_long_to_bin((*b)->longitude);
411
412 if(a_lon<b_lon)
413 return(-1);
414 else if(a_lon>b_lon)
415 return(1);
416 else
417 {
418 int32_t a_lat=lat_long_to_bin((*a)->latitude);
419 int32_t b_lat=lat_long_to_bin((*b)->latitude);
420
421 if(a_lat<b_lat)
422 return(-1);
423 else if(a_lat>b_lat)
424 return(1);
425 else
426 return(0);
427 }
428 }
429
430
431 /*++++++++++++++++++++++++++++++++++++++
432 Remove any nodes that are not part of a highway.
433
434 NodesX *nodesx The complete node list.
435
436 SegmentsX *segmentsx The list of segments.
437 ++++++++++++++++++++++++++++++++++++++*/
438
439 void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
440 {
441 int i;
442 int highway=0,nothighway=0;
443
444 for(i=0;i<nodesx->xnumber;i++)
445 {
446 if(FindFirstSegmentX(segmentsx,nodesx->xdata[i].id))
447 highway++;
448 else
449 {
450 nodesx->xdata[i].id=NO_NODE;
451 nothighway++;
452 }
453
454 if(!((i+1)%10000))
455 {
456 printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
457 fflush(stdout);
458 }
459 }
460
461 printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",nodesx->xnumber,highway,nothighway);
462 fflush(stdout);
463 }
464
465
466 /*++++++++++++++++++++++++++++++++++++++
467 Create the real node data.
468
469 NodesX *nodesx The set of nodes to use.
470
471 int iteration The final super-node iteration.
472 ++++++++++++++++++++++++++++++++++++++*/
473
474 void CreateRealNodes(NodesX *nodesx,int iteration)
475 {
476 int i;
477
478 assert(nodesx->sorted); /* Must be sorted */
479
480 /* Allocate the memory */
481
482 nodesx->ndata=(Node*)malloc(nodesx->number*sizeof(Node));
483
484 /* Loop through and allocate. */
485
486 for(i=0;i<nodesx->number;i++)
487 {
488 int32_t lat=(int32_t)(nodesx->idata[i]->latitude *LAT_LONG_SCALE);
489 int32_t lon=(int32_t)(nodesx->idata[i]->longitude*LAT_LONG_SCALE);
490
491 nodesx->ndata[i].latoffset=lat%LAT_LONG_BIN;
492 nodesx->ndata[i].lonoffset=lon%LAT_LONG_BIN;
493
494 nodesx->ndata[i].firstseg=SEGMENT(NO_SEGMENT);
495
496 if(nodesx->idata[i]->super==iteration)
497 nodesx->ndata[i].firstseg|=NODE_SUPER;
498
499 if(!((i+1)%10000))
500 {
501 printf("\rCreating Real Nodes: Nodes=%d",i+1);
502 fflush(stdout);
503 }
504 }
505
506 printf("\rCreating Real Nodes: Nodes=%d \n",nodesx->number);
507 fflush(stdout);
508 }
509
510
511 /*++++++++++++++++++++++++++++++++++++++
512 Assign the segment indexes to the nodes.
513
514 NodesX *nodesx The list of nodes to process.
515
516 SegmentsX* segmentsx The set of segments to use.
517 ++++++++++++++++++++++++++++++++++++++*/
518
519 void IndexNodes(NodesX *nodesx,SegmentsX *segmentsx)
520 {
521 int i;
522
523 assert(nodesx->sorted); /* Must be sorted */
524 assert(segmentsx->sorted); /* Must be sorted */
525 assert(segmentsx->sdata); /* Must have real segments */
526
527 /* Index the nodes */
528
529 for(i=0;i<segmentsx->number;i++)
530 {
531 NodeX **nodex1=FindNodeX(nodesx,segmentsx->ndata[i]->node1);
532 NodeX **nodex2=FindNodeX(nodesx,segmentsx->ndata[i]->node2);
533 Node *node1=&nodesx->ndata[nodex1-nodesx->idata];
534 Node *node2=&nodesx->ndata[nodex2-nodesx->idata];
535
536 /* Check node1 */
537
538 if(SEGMENT(node1->firstseg)==SEGMENT(NO_SEGMENT))
539 {
540 node1->firstseg^=SEGMENT(NO_SEGMENT);
541 node1->firstseg|=i;
542 }
543 else
544 {
545 index_t index=SEGMENT(node1->firstseg);
546
547 do
548 {
549 if(segmentsx->ndata[index]->node1==segmentsx->ndata[i]->node1)
550 {
551 index++;
552
553 if(index>=segmentsx->number || segmentsx->ndata[index]->node1!=segmentsx->ndata[i]->node1)
554 break;
555 }
556 else
557 {
558 if(segmentsx->sdata[index].next2==NO_NODE)
559 {
560 segmentsx->sdata[index].next2=i;
561 break;
562 }
563 else
564 index=segmentsx->sdata[index].next2;
565 }
566 }
567 while(1);
568 }
569
570 /* Check node2 */
571
572 if(SEGMENT(node2->firstseg)==SEGMENT(NO_SEGMENT))
573 {
574 node2->firstseg^=SEGMENT(NO_SEGMENT);
575 node2->firstseg|=i;
576 }
577 else
578 {
579 index_t index=SEGMENT(node2->firstseg);
580
581 do
582 {
583 if(segmentsx->ndata[index]->node1==segmentsx->ndata[i]->node2)
584 {
585 index++;
586
587 if(index>=segmentsx->number || segmentsx->ndata[index]->node1!=segmentsx->ndata[i]->node2)
588 break;
589 }
590 else
591 {
592 if(segmentsx->sdata[index].next2==NO_NODE)
593 {
594 segmentsx->sdata[index].next2=i;
595 break;
596 }
597 else
598 index=segmentsx->sdata[index].next2;
599 }
600 }
601 while(1);
602 }
603
604 if(!((i+1)%10000))
605 {
606 printf("\rIndexing Segments: Segments=%d",i+1);
607 fflush(stdout);
608 }
609 }
610
611 printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
612 fflush(stdout);
613 }

Properties

Name Value
cvs:description Extended nodes functions.
Index: This Site Routino Software Download Source Code Documentation XML Files Links
Index: View SVN Development Recent changes Development (destination-access branch) Version 3.4.1 (destination-access branch) Version 3.4.1 Version 3.4 (destination-access branch) Version 3.4 Version 3.3.3 (destination-access branch) Version 3.3.3 Version 3.3.2 (destination-access branch) Version 3.3.2 Version 3.3.1 (destination-access branch) Version 3.3.1 Version 3.3 (destination-access branch) Version 3.3 Version 3.2 Version 3.1.1 Version 3.1 Version 3.0 Version 2.7.3 Version 2.7.2 Version 2.7.1 Version 2.7 Version 2.6 Version 2.5.1 Version 2.5 Version 2.4.1 Version 2.4 Version 2.3.2 Version 2.3.1 Version 2.3 Version 2.2 Version 2.1.2 Version 2.1.1 Version 2.1 Version 2.0.3 Version 2.0.2 Version 2.0.1 Version 2.0 Version 1.5.1 Version 1.5 Version 1.4.1 Version 1.4 Version 1.3 Version 1.2 Version 1.1 Version 1.0
Powered by ViewVC 1.3.0-dev ViewVC Help
© Andrew M. Bishop = < amb @ ... >
Root