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

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.2 (destination-access branch) Version 3.4.2 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