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 680 - (show annotations) (download) (as text)
Sun Apr 24 15:14:53 2011 UTC (13 years, 10 months ago) by amb
File MIME type: text/x-csrc
File size: 16562 byte(s) 
Update comments throughout the source code.
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 deduplicate_and_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 a pointer to 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 (for appending later).
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 identifier from the original OSM data.
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.
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))deduplicate_and_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 Create the index of identifiers and discard duplicate nodes.
242
243 int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise 0.
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 deduplicate_and_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 (first by longitude bin
312 number, then by latitude bin number and then by exact longitude and then by
313 exact latitude).
314
315 int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
316
317 NodeX *a The first extended node.
318
319 NodeX *b The second extended node.
320 ++++++++++++++++++++++++++++++++++++++*/
321
322 static int sort_by_lat_long(NodeX *a,NodeX *b)
323 {
324 ll_bin_t a_lon=latlong_to_bin(a->longitude);
325 ll_bin_t b_lon=latlong_to_bin(b->longitude);
326
327 if(a_lon<b_lon)
328 return(-1);
329 else if(a_lon>b_lon)
330 return(1);
331 else
332 {
333 ll_bin_t a_lat=latlong_to_bin(a->latitude);
334 ll_bin_t b_lat=latlong_to_bin(b->latitude);
335
336 if(a_lat<b_lat)
337 return(-1);
338 else if(a_lat>b_lat)
339 return(1);
340 else
341 {
342 if(a->longitude<b->longitude)
343 return(-1);
344 else if(a->longitude>b->longitude)
345 return(1);
346 else
347 {
348 if(a->latitude<b->latitude)
349 return(-1);
350 else if(a->latitude>b->latitude)
351 return(1);
352 }
353
354 return(0);
355 }
356 }
357 }
358
359
360 /*++++++++++++++++++++++++++++++++++++++
361 Create the index between the sorted and unsorted nodes.
362
363 int index_by_lat_long Return 1 if the value is to be kept, otherwise 0.
364
365 NodeX *nodex The extended node.
366
367 index_t index The index of this node in the total.
368 ++++++++++++++++++++++++++++++++++++++*/
369
370 static int index_by_lat_long(NodeX *nodex,index_t index)
371 {
372 /* Create the index from the previous sort to the current one */
373
374 sortnodesx->gdata[nodex->id]=index;
375
376 return(1);
377 }
378
379
380 /*++++++++++++++++++++++++++++++++++++++
381 Find a particular node index.
382
383 index_t IndexNodeX Returns the index of the extended node with the specified id.
384
385 NodesX* nodesx The set of nodes to process.
386
387 node_t id The node id to look for.
388 ++++++++++++++++++++++++++++++++++++++*/
389
390 index_t IndexNodeX(NodesX* nodesx,node_t id)
391 {
392 int start=0;
393 int end=nodesx->number-1;
394 int mid;
395
396 /* Binary search - search key exact match only is required.
397 *
398 * # <- start | Check mid and move start or end if it doesn't match
399 * # |
400 * # | Since an exact match is wanted we can set end=mid-1
401 * # <- mid | or start=mid+1 because we know that mid doesn't match.
402 * # |
403 * # | Eventually either end=start or end=start+1 and one of
404 * # <- end | start or end is the wanted one.
405 */
406
407 if(end<start) /* There are no nodes */
408 return(NO_NODE);
409 else if(id<nodesx->idata[start]) /* Check key is not before start */
410 return(NO_NODE);
411 else if(id>nodesx->idata[end]) /* Check key is not after end */
412 return(NO_NODE);
413 else
414 {
415 do
416 {
417 mid=(start+end)/2; /* Choose mid point */
418
419 if(nodesx->idata[mid]<id) /* Mid point is too low */
420 start=mid+1;
421 else if(nodesx->idata[mid]>id) /* Mid point is too high */
422 end=mid-1;
423 else /* Mid point is correct */
424 return(mid);
425 }
426 while((end-start)>1);
427
428 if(nodesx->idata[start]==id) /* Start is correct */
429 return(start);
430
431 if(nodesx->idata[end]==id) /* End is correct */
432 return(end);
433 }
434
435 return(NO_NODE);
436 }
437
438
439 /*++++++++++++++++++++++++++++++++++++++
440 Remove any nodes that are not part of a highway.
441
442 NodesX* nodesx The set of nodes to process.
443
444 SegmentsX *segmentsx The set of segments to use.
445 ++++++++++++++++++++++++++++++++++++++*/
446
447 void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
448 {
449 NodeX nodex;
450 int total=0,highway=0,nothighway=0;
451 ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
452 latlong_t lat_min,lat_max,lon_min,lon_max;
453 int fd;
454
455 /* Print the start message */
456
457 printf_first("Checking Nodes: Nodes=0");
458
459 /* While we are here we can work out the range of data */
460
461 lat_min=radians_to_latlong( 2);
462 lat_max=radians_to_latlong(-2);
463 lon_min=radians_to_latlong( 4);
464 lon_max=radians_to_latlong(-4);
465
466 /* Re-open the file read-only and a new file writeable */
467
468 nodesx->fd=ReOpenFile(nodesx->filename);
469
470 DeleteFile(nodesx->filename);
471
472 fd=OpenFileNew(nodesx->filename);
473
474 /* Modify the on-disk image */
475
476 while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
477 {
478 if(!IsBitSet(segmentsx->usednode,total))
479 nothighway++;
480 else
481 {
482 nodex.id=highway;
483
484 WriteFile(fd,&nodex,sizeof(NodeX));
485
486 nodesx->idata[highway]=nodesx->idata[total];
487 highway++;
488
489 if(nodex.latitude<lat_min)
490 lat_min=nodex.latitude;
491 if(nodex.latitude>lat_max)
492 lat_max=nodex.latitude;
493 if(nodex.longitude<lon_min)
494 lon_min=nodex.longitude;
495 if(nodex.longitude>lon_max)
496 lon_max=nodex.longitude;
497 }
498
499 total++;
500
501 if(!(total%10000))
502 printf_middle("Checking Nodes: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
503 }
504
505 nodesx->number=highway;
506
507 /* Close the files */
508
509 nodesx->fd=CloseFile(nodesx->fd);
510 CloseFile(fd);
511
512 /* Work out the number of bins */
513
514 lat_min_bin=latlong_to_bin(lat_min);
515 lon_min_bin=latlong_to_bin(lon_min);
516 lat_max_bin=latlong_to_bin(lat_max);
517 lon_max_bin=latlong_to_bin(lon_max);
518
519 nodesx->latzero=lat_min_bin;
520 nodesx->lonzero=lon_min_bin;
521
522 nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
523 nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;
524
525 /* Free the now-unneeded index */
526
527 free(segmentsx->usednode);
528 segmentsx->usednode=NULL;
529
530 /* Allocate and set the super-node markers */
531
532 nodesx->super=(uint8_t*)malloc((1+nodesx->number/8)*sizeof(uint8_t));
533
534 assert(nodesx->super); /* Check calloc() worked */
535
536 memset(nodesx->super,~0,(1+nodesx->number/8));
537
538 /* Print the final message */
539
540 printf_last("Checked Nodes: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
541 }
542
543
544 /*++++++++++++++++++++++++++++++++++++++
545 Insert the super-node flag and the first segment indexes after geographical sorting.
546
547 NodesX* nodesx The set of nodes to process.
548
549 SegmentsX *segmentsx The set of segments to use.
550 ++++++++++++++++++++++++++++++++++++++*/
551
552 void UpdateNodes(NodesX *nodesx,SegmentsX *segmentsx)
553 {
554 index_t i;
555 int fd;
556
557 /* Print the start message */
558
559 printf_first("Updating Super Nodes: Nodes=0");
560
561 /* Re-open the file read-only and a new file writeable */
562
563 nodesx->fd=ReOpenFile(nodesx->filename);
564
565 DeleteFile(nodesx->filename);
566
567 fd=OpenFileNew(nodesx->filename);
568
569 /* Modify the on-disk image */
570
571 for(i=0;i<nodesx->number;i++)
572 {
573 NodeX nodex;
574
575 ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
576
577 if(IsBitSet(nodesx->super,nodex.id))
578 nodex.flags|=NODE_SUPER;
579
580 nodex.id=segmentsx->firstnode[nodesx->gdata[nodex.id]];
581
582 WriteFile(fd,&nodex,sizeof(NodeX));
583
584 if(!((i+1)%10000))
585 printf_middle("Updating Super Nodes: Nodes=%d",i+1);
586 }
587
588 /* Close the files */
589
590 nodesx->fd=CloseFile(nodesx->fd);
591 CloseFile(fd);
592
593 /* Print the final message */
594
595 printf_last("Updated Super Nodes: Nodes=%d",nodesx->number);
596 }
597
598
599 /*++++++++++++++++++++++++++++++++++++++
600 Save the final node list database to a file.
601
602 NodesX* nodesx The set of nodes to save.
603
604 const char *filename The name of the file to save.
605 ++++++++++++++++++++++++++++++++++++++*/
606
607 void SaveNodeList(NodesX* nodesx,const char *filename)
608 {
609 index_t i;
610 int fd;
611 NodesFile nodesfile={0};
612 int super_number=0;
613 index_t latlonbin=0,*offsets;
614
615 /* Print the start message */
616
617 printf_first("Writing Nodes: Nodes=0");
618
619 /* Allocate the memory for the geographical offsets array */
620
621 offsets=(index_t*)malloc((nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
622
623 assert(offsets); /* Check malloc() worked */
624
625 latlonbin=0;
626
627 /* Re-open the file */
628
629 nodesx->fd=ReOpenFile(nodesx->filename);
630
631 /* Write out the nodes data */
632
633 fd=OpenFileNew(filename);
634
635 SeekFile(fd,sizeof(NodesFile)+(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
636
637 for(i=0;i<nodesx->number;i++)
638 {
639 NodeX nodex;
640 Node node;
641 ll_bin_t latbin,lonbin;
642 int llbin;
643
644 ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
645
646 /* Create the Node */
647
648 node.latoffset=latlong_to_off(nodex.latitude);
649 node.lonoffset=latlong_to_off(nodex.longitude);
650 node.firstseg=nodex.id;
651 node.allow=nodex.allow;
652 node.flags=nodex.flags;
653
654 if(node.flags&NODE_SUPER)
655 super_number++;
656
657 /* Work out the offsets */
658
659 latbin=latlong_to_bin(nodex.latitude )-nodesx->latzero;
660 lonbin=latlong_to_bin(nodex.longitude)-nodesx->lonzero;
661 llbin=lonbin*nodesx->latbins+latbin;
662
663 for(;latlonbin<=llbin;latlonbin++)
664 offsets[latlonbin]=i;
665
666 /* Write the data */
667
668 WriteFile(fd,&node,sizeof(Node));
669
670 if(!((i+1)%10000))
671 printf_middle("Writing Nodes: Nodes=%d",i+1);
672 }
673
674 /* Close the file */
675
676 nodesx->fd=CloseFile(nodesx->fd);
677
678 /* Finish off the offset indexing and write them out */
679
680 for(;latlonbin<=(nodesx->latbins*nodesx->lonbins);latlonbin++)
681 offsets[latlonbin]=nodesx->number;
682
683 SeekFile(fd,sizeof(NodesFile));
684 WriteFile(fd,offsets,(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
685
686 /* Write out the header structure */
687
688 nodesfile.number=nodesx->number;
689 nodesfile.snumber=super_number;
690
691 nodesfile.latbins=nodesx->latbins;
692 nodesfile.lonbins=nodesx->lonbins;
693
694 nodesfile.latzero=nodesx->latzero;
695 nodesfile.lonzero=nodesx->lonzero;
696
697 SeekFile(fd,0);
698 WriteFile(fd,&nodesfile,sizeof(NodesFile));
699
700 CloseFile(fd);
701
702 /* Print the final message */
703
704 printf_last("Wrote Nodes: Nodes=%d",nodesx->number);
705 }

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