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

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