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 650 - (show annotations) (download) (as text)
Sun Feb 27 15:49:21 2011 UTC (14 years ago) by amb
File MIME type: text/x-csrc
File size: 16453 byte(s) 
Don't have both xnumber and number in the nodesx, segmentsx, waysx and
relationsx structures.
1 /***************************************
2 Extented Node data type functions.
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 #include <assert.h>
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <string.h>
27 #include <sys/stat.h>
28
29 #include "types.h"
30 #include "nodes.h"
31 #include "segments.h"
32
33 #include "nodesx.h"
34 #include "segmentsx.h"
35 #include "waysx.h"
36
37 #include "types.h"
38
39 #include "files.h"
40 #include "logging.h"
41 #include "sorting.h"
42
43
44 /* Variables */
45
46 /*+ The command line '--tmpdir' option or its default value. +*/
47 extern char *option_tmpdirname;
48
49 /*+ A temporary file-local variable for use by the sort functions. +*/
50 static NodesX *sortnodesx;
51
52 /* Functions */
53
54 static int sort_by_id(NodeX *a,NodeX *b);
55 static int index_by_id(NodeX *nodex,index_t index);
56
57 static int sort_by_lat_long(NodeX *a,NodeX *b);
58 static int index_by_lat_long(NodeX *nodex,index_t index);
59
60
61 /*++++++++++++++++++++++++++++++++++++++
62 Allocate a new node list (create a new file or open an existing one).
63
64 NodesX *NewNodeList Returns the node list.
65
66 int append Set to 1 if the file is to be opened for appending (now or later).
67 ++++++++++++++++++++++++++++++++++++++*/
68
69 NodesX *NewNodeList(int append)
70 {
71 NodesX *nodesx;
72
73 nodesx=(NodesX*)calloc(1,sizeof(NodesX));
74
75 assert(nodesx); /* Check calloc() worked */
76
77 nodesx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
78
79 if(append)
80 sprintf(nodesx->filename,"%s/nodesx.input.tmp",option_tmpdirname);
81 else
82 sprintf(nodesx->filename,"%s/nodesx.%p.tmp",option_tmpdirname,nodesx);
83
84 if(append)
85 {
86 off_t size;
87
88 nodesx->fd=OpenFileAppend(nodesx->filename);
89
90 size=SizeFile(nodesx->filename);
91
92 nodesx->number=size/sizeof(NodeX);
93 }
94 else
95 nodesx->fd=OpenFileNew(nodesx->filename);
96
97 return(nodesx);
98 }
99
100
101 /*++++++++++++++++++++++++++++++++++++++
102 Free a node list.
103
104 NodesX *nodesx The list to be freed.
105
106 int keep Set to 1 if the file is to be kept.
107 ++++++++++++++++++++++++++++++++++++++*/
108
109 void FreeNodeList(NodesX *nodesx,int keep)
110 {
111 if(!keep)
112 DeleteFile(nodesx->filename);
113
114 free(nodesx->filename);
115
116 if(nodesx->idata)
117 free(nodesx->idata);
118
119 if(nodesx->gdata)
120 free(nodesx->gdata);
121
122 if(nodesx->super)
123 free(nodesx->super);
124
125 free(nodesx);
126 }
127
128
129 /*++++++++++++++++++++++++++++++++++++++
130 Append a single node to an unsorted node list.
131
132 NodesX* nodesx The set of nodes to process.
133
134 node_t id The node identification.
135
136 double latitude The latitude of the node.
137
138 double longitude The longitude of the node.
139
140 transports_t allow The allowed traffic types through the node.
141
142 uint16_t flags The flags to set for this node.
143 ++++++++++++++++++++++++++++++++++++++*/
144
145 void AppendNode(NodesX* nodesx,node_t id,double latitude,double longitude,transports_t allow,uint16_t flags)
146 {
147 NodeX nodex;
148
149 nodex.id=id;
150 nodex.latitude =radians_to_latlong(latitude);
151 nodex.longitude=radians_to_latlong(longitude);
152 nodex.allow=allow;
153 nodex.flags=flags;
154
155 WriteFile(nodesx->fd,&nodex,sizeof(NodeX));
156
157 nodesx->number++;
158
159 assert(nodesx->number<NODE_FAKE); /* NODE_FAKE marks the high-water mark for real nodes. */
160 }
161
162
163 /*++++++++++++++++++++++++++++++++++++++
164 Sort the node list (i.e. create the sortable indexes).
165
166 NodesX* nodesx The set of nodes to process.
167 ++++++++++++++++++++++++++++++++++++++*/
168
169 void SortNodeList(NodesX* nodesx)
170 {
171 int fd;
172 index_t xnumber;
173
174 /* Print the start message */
175
176 printf_first("Sorting Nodes");
177
178 /* Close the file (finished appending) */
179
180 nodesx->fd=CloseFile(nodesx->fd);
181
182 /* Re-open the file read-only and a new file writeable */
183
184 nodesx->fd=ReOpenFile(nodesx->filename);
185
186 DeleteFile(nodesx->filename);
187
188 fd=OpenFileNew(nodesx->filename);
189
190 /* Allocate the array of indexes */
191
192 nodesx->idata=(node_t*)malloc(nodesx->number*sizeof(node_t));
193
194 assert(nodesx->idata); /* Check malloc() worked */
195
196 /* Sort by node indexes */
197
198 xnumber=nodesx->number;
199 nodesx->number=0;
200
201 sortnodesx=nodesx;
202
203 filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))index_by_id);
204
205 /* Close the files */
206
207 nodesx->fd=CloseFile(nodesx->fd);
208 CloseFile(fd);
209
210 /* Print the final message */
211
212 printf_last("Sorted Nodes: Nodes=%d Duplicates=%d",xnumber,xnumber-nodesx->number);
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 NodeX *a The first extended node.
222
223 NodeX *b The second extended node.
224 ++++++++++++++++++++++++++++++++++++++*/
225
226 static int sort_by_id(NodeX *a,NodeX *b)
227 {
228 node_t a_id=a->id;
229 node_t b_id=b->id;
230
231 if(a_id<b_id)
232 return(-1);
233 else if(a_id>b_id)
234 return(1);
235 else
236 return(0);
237 }
238
239
240 /*++++++++++++++++++++++++++++++++++++++
241 Index the nodes after sorting.
242
243 int index_by_id Return 1 if the value is to be kept, otherwise zero.
244
245 NodeX *nodex The extended node.
246
247 index_t index The index of this node in the total.
248 ++++++++++++++++++++++++++++++++++++++*/
249
250 static int index_by_id(NodeX *nodex,index_t index)
251 {
252 if(index==0 || sortnodesx->idata[index-1]!=nodex->id)
253 {
254 sortnodesx->idata[index]=nodex->id;
255
256 sortnodesx->number++;
257
258 return(1);
259 }
260
261 return(0);
262 }
263
264
265 /*++++++++++++++++++++++++++++++++++++++
266 Sort the node list geographically.
267
268 NodesX* nodesx The set of nodes to process.
269 ++++++++++++++++++++++++++++++++++++++*/
270
271 void SortNodeListGeographically(NodesX* nodesx)
272 {
273 int fd;
274
275 /* Print the start message */
276
277 printf_first("Sorting Nodes Geographically");
278
279 /* Allocate the memory for the geographical index array */
280
281 nodesx->gdata=(index_t*)malloc(nodesx->number*sizeof(index_t));
282
283 assert(nodesx->gdata); /* Check malloc() worked */
284
285 /* Re-open the file read-only and a new file writeable */
286
287 nodesx->fd=ReOpenFile(nodesx->filename);
288
289 DeleteFile(nodesx->filename);
290
291 fd=OpenFileNew(nodesx->filename);
292
293 /* Sort geographically */
294
295 sortnodesx=nodesx;
296
297 filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_lat_long,(int (*)(void*,index_t))index_by_lat_long);
298
299 /* Close the files */
300
301 nodesx->fd=CloseFile(nodesx->fd);
302 CloseFile(fd);
303
304 /* Print the final message */
305
306 printf_last("Sorted Nodes Geographically");
307 }
308
309
310 /*++++++++++++++++++++++++++++++++++++++
311 Sort the nodes into latitude and longitude order.
312
313 int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
314
315 NodeX *a The first extended node.
316
317 NodeX *b The second extended node.
318 ++++++++++++++++++++++++++++++++++++++*/
319
320 static int sort_by_lat_long(NodeX *a,NodeX *b)
321 {
322 ll_bin_t a_lon=latlong_to_bin(a->longitude);
323 ll_bin_t b_lon=latlong_to_bin(b->longitude);
324
325 if(a_lon<b_lon)
326 return(-1);
327 else if(a_lon>b_lon)
328 return(1);
329 else
330 {
331 ll_bin_t a_lat=latlong_to_bin(a->latitude);
332 ll_bin_t b_lat=latlong_to_bin(b->latitude);
333
334 if(a_lat<b_lat)
335 return(-1);
336 else if(a_lat>b_lat)
337 return(1);
338 else
339 {
340 #ifdef REGRESSION_TESTING
341 // Need this for regression testing because filesort_heapsort() is not order
342 // preserving like qsort() is (or was when tested).
343
344 index_t a_id=a->id;
345 index_t b_id=b->id;
346
347 if(a_id<b_id)
348 return(-1);
349 else if(a_id>b_id)
350 return(1);
351 else
352 #endif
353 return(0);
354 }
355 }
356 }
357
358
359 /*++++++++++++++++++++++++++++++++++++++
360 Index the nodes after sorting.
361
362 int index_by_lat_long Return 1 if the value is to be kept, otherwise zero.
363
364 NodeX *nodex The extended node.
365
366 index_t index The index of this node in the total.
367 ++++++++++++++++++++++++++++++++++++++*/
368
369 static int index_by_lat_long(NodeX *nodex,index_t index)
370 {
371 /* Create the index from the previous sort to the current one */
372
373 sortnodesx->gdata[nodex->id]=index;
374
375 return(1);
376 }
377
378
379 /*++++++++++++++++++++++++++++++++++++++
380 Find a particular node index.
381
382 index_t IndexNodeX Returns the index of the extended node with the specified id.
383
384 NodesX* nodesx The set of nodes to process.
385
386 node_t id The node id to look for.
387 ++++++++++++++++++++++++++++++++++++++*/
388
389 index_t IndexNodeX(NodesX* nodesx,node_t id)
390 {
391 int start=0;
392 int end=nodesx->number-1;
393 int mid;
394
395 /* Binary search - search key exact match only is required.
396 *
397 * # <- start | Check mid and move start or end if it doesn't match
398 * # |
399 * # | Since an exact match is wanted we can set end=mid-1
400 * # <- mid | or start=mid+1 because we know that mid doesn't match.
401 * # |
402 * # | Eventually either end=start or end=start+1 and one of
403 * # <- end | start or end is the wanted one.
404 */
405
406 if(end<start) /* There are no nodes */
407 return(NO_NODE);
408 else if(id<nodesx->idata[start]) /* Check key is not before start */
409 return(NO_NODE);
410 else if(id>nodesx->idata[end]) /* Check key is not after end */
411 return(NO_NODE);
412 else
413 {
414 do
415 {
416 mid=(start+end)/2; /* Choose mid point */
417
418 if(nodesx->idata[mid]<id) /* Mid point is too low */
419 start=mid+1;
420 else if(nodesx->idata[mid]>id) /* Mid point is too high */
421 end=mid-1;
422 else /* Mid point is correct */
423 return(mid);
424 }
425 while((end-start)>1);
426
427 if(nodesx->idata[start]==id) /* Start is correct */
428 return(start);
429
430 if(nodesx->idata[end]==id) /* End is correct */
431 return(end);
432 }
433
434 return(NO_NODE);
435 }
436
437
438 /*++++++++++++++++++++++++++++++++++++++
439 Remove any nodes that are not part of a highway.
440
441 NodesX *nodesx The complete node list.
442
443 SegmentsX *segmentsx The list of segments.
444 ++++++++++++++++++++++++++++++++++++++*/
445
446 void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
447 {
448 NodeX nodex;
449 int total=0,highway=0,nothighway=0;
450 ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
451 latlong_t lat_min,lat_max,lon_min,lon_max;
452 int fd;
453
454 /* Print the start message */
455
456 printf_first("Checking Nodes: Nodes=0");
457
458 /* While we are here we can work out the range of data */
459
460 lat_min=radians_to_latlong( 2);
461 lat_max=radians_to_latlong(-2);
462 lon_min=radians_to_latlong( 4);
463 lon_max=radians_to_latlong(-4);
464
465 /* Re-open the file read-only and a new file writeable */
466
467 nodesx->fd=ReOpenFile(nodesx->filename);
468
469 DeleteFile(nodesx->filename);
470
471 fd=OpenFileNew(nodesx->filename);
472
473 /* Modify the on-disk image */
474
475 while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
476 {
477 if(!segmentsx->usednode[total])
478 nothighway++;
479 else
480 {
481 nodex.id=highway;
482
483 WriteFile(fd,&nodex,sizeof(NodeX));
484
485 nodesx->idata[highway]=nodesx->idata[total];
486 highway++;
487
488 if(nodex.latitude<lat_min)
489 lat_min=nodex.latitude;
490 if(nodex.latitude>lat_max)
491 lat_max=nodex.latitude;
492 if(nodex.longitude<lon_min)
493 lon_min=nodex.longitude;
494 if(nodex.longitude>lon_max)
495 lon_max=nodex.longitude;
496 }
497
498 total++;
499
500 if(!(total%10000))
501 printf_middle("Checking Nodes: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
502 }
503
504 nodesx->number=highway;
505
506 /* Close the files */
507
508 nodesx->fd=CloseFile(nodesx->fd);
509 CloseFile(fd);
510
511 /* Work out the number of bins */
512
513 lat_min_bin=latlong_to_bin(lat_min);
514 lon_min_bin=latlong_to_bin(lon_min);
515 lat_max_bin=latlong_to_bin(lat_max);
516 lon_max_bin=latlong_to_bin(lon_max);
517
518 nodesx->latzero=lat_min_bin;
519 nodesx->lonzero=lon_min_bin;
520
521 nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
522 nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;
523
524 /* Free the now-unneeded index */
525
526 free(segmentsx->usednode);
527 segmentsx->usednode=NULL;
528
529 /* Allocate and clear the super-node markers */
530
531 nodesx->super=(uint8_t*)calloc(nodesx->number,sizeof(uint8_t));
532
533 assert(nodesx->super); /* Check calloc() worked */
534
535 /* Print the final message */
536
537 printf_last("Checked Nodes: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
538 }
539
540
541 /*++++++++++++++++++++++++++++++++++++++
542 Insert the super-node flag and the first segment indexes after geographical sorting.
543
544 NodesX *nodesx The list of nodes to update.
545
546 SegmentsX *segmentsx The set of segments to use.
547
548 int iteration The final super-node iteration.
549 ++++++++++++++++++++++++++++++++++++++*/
550
551 void UpdateNodes(NodesX *nodesx,SegmentsX *segmentsx,int iteration)
552 {
553 index_t i;
554 int fd;
555
556 /* Print the start message */
557
558 printf_first("Updating Super Nodes: Nodes=0");
559
560 /* Re-open the file read-only and a new file writeable */
561
562 nodesx->fd=ReOpenFile(nodesx->filename);
563
564 DeleteFile(nodesx->filename);
565
566 fd=OpenFileNew(nodesx->filename);
567
568 /* Modify the on-disk image */
569
570 for(i=0;i<nodesx->number;i++)
571 {
572 NodeX nodex;
573
574 ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
575
576 if(nodesx->super[nodex.id]==iteration)
577 nodex.flags|=NODE_SUPER;
578
579 nodex.id=segmentsx->firstnode[nodex.id];
580
581 WriteFile(fd,&nodex,sizeof(NodeX));
582
583 if(!((i+1)%10000))
584 printf_middle("Updating Super Nodes: Nodes=%d",i+1);
585 }
586
587 /* Close the files */
588
589 nodesx->fd=CloseFile(nodesx->fd);
590 CloseFile(fd);
591
592 /* Free the unneeded memory */
593
594 free(nodesx->super);
595 nodesx->super=NULL;
596
597 free(segmentsx->firstnode);
598 segmentsx->firstnode=NULL;
599
600 /* Print the final message */
601
602 printf_last("Updated Super Nodes: Nodes=%d",nodesx->number);
603 }
604
605
606 /*++++++++++++++++++++++++++++++++++++++
607 Save the node list to a file.
608
609 NodesX* nodesx The set of nodes to save.
610
611 const char *filename The name of the file to save.
612 ++++++++++++++++++++++++++++++++++++++*/
613
614 void SaveNodeList(NodesX* nodesx,const char *filename)
615 {
616 index_t i;
617 int fd;
618 NodesFile nodesfile={0};
619 int super_number=0;
620 index_t latlonbin=0,*offsets;
621
622 /* Print the start message */
623
624 printf_first("Writing Nodes: Nodes=0");
625
626 /* Allocate the memory for the geographical offsets array */
627
628 offsets=(index_t*)malloc((nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
629
630 assert(offsets); /* Check malloc() worked */
631
632 latlonbin=0;
633
634 /* Re-open the file */
635
636 nodesx->fd=ReOpenFile(nodesx->filename);
637
638 /* Write out the nodes data */
639
640 fd=OpenFileNew(filename);
641
642 SeekFile(fd,sizeof(NodesFile)+(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
643
644 for(i=0;i<nodesx->number;i++)
645 {
646 NodeX nodex;
647 Node node;
648 ll_bin_t latbin,lonbin;
649 int llbin;
650
651 ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
652
653 /* Create the Node */
654
655 node.latoffset=latlong_to_off(nodex.latitude);
656 node.lonoffset=latlong_to_off(nodex.longitude);
657 node.firstseg=nodex.id;
658 node.allow=nodex.allow;
659 node.flags=nodex.flags;
660
661 if(node.flags&NODE_SUPER)
662 super_number++;
663
664 /* Work out the offsets */
665
666 latbin=latlong_to_bin(nodex.latitude )-nodesx->latzero;
667 lonbin=latlong_to_bin(nodex.longitude)-nodesx->lonzero;
668 llbin=lonbin*nodesx->latbins+latbin;
669
670 for(;latlonbin<=llbin;latlonbin++)
671 offsets[latlonbin]=i;
672
673 /* Write the data */
674
675 WriteFile(fd,&node,sizeof(Node));
676
677 if(!((i+1)%10000))
678 printf_middle("Writing Nodes: Nodes=%d",i+1);
679 }
680
681 /* Close the file */
682
683 nodesx->fd=CloseFile(nodesx->fd);
684
685 /* Finish off the offset indexing and write them out */
686
687 for(;latlonbin<=(nodesx->latbins*nodesx->lonbins);latlonbin++)
688 offsets[latlonbin]=nodesx->number;
689
690 SeekFile(fd,sizeof(NodesFile));
691 WriteFile(fd,offsets,(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
692
693 /* Write out the header structure */
694
695 nodesfile.number=nodesx->number;
696 nodesfile.snumber=super_number;
697
698 nodesfile.latbins=nodesx->latbins;
699 nodesfile.lonbins=nodesx->lonbins;
700
701 nodesfile.latzero=nodesx->latzero;
702 nodesfile.lonzero=nodesx->lonzero;
703
704 SeekFile(fd,0);
705 WriteFile(fd,&nodesfile,sizeof(NodesFile));
706
707 CloseFile(fd);
708
709 /* Print the final message */
710
711 printf_last("Wrote Nodes: Nodes=%d",nodesx->number);
712 }

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