Routino SVN Repository Browser

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

ViewVC logotype

Contents of /trunk/src/nodesx.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1161 - (show annotations) (download) (as text)
Tue Nov 20 14:16:58 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 18614 byte(s)
Tidy up all of the recent code changes - change the name of a few of the
functions.

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

Properties

Name Value
cvs:description Extended nodes functions.