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 1109 - (show annotations) (download) (as text)
Sun Oct 21 18:23:01 2012 UTC (12 years, 5 months ago) by amb
File MIME type: text/x-csrc
File size: 17431 byte(s) 
Move the UpdateNodes() work into the callback for SortNodeListGeographically()
and use firstnode when saving the nodes.
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 /*+ Temporary file-local variables for use by the sort functions. +*/
46 static NodesX *sortnodesx;
47 static latlong_t lat_min,lat_max,lon_min,lon_max;
48
49 /* Functions */
50
51 static int sort_by_id(NodeX *a,NodeX *b);
52 static int deduplicate_and_index_by_id(NodeX *nodex,index_t index);
53
54 static int sort_by_lat_long(NodeX *a,NodeX *b);
55 static int index_by_lat_long(NodeX *nodex,index_t index);
56
57
58 /*++++++++++++++++++++++++++++++++++++++
59 Allocate a new node list (create a new file or open an existing one).
60
61 NodesX *NewNodeList Returns a pointer to the node list.
62
63 int append Set to 1 if the file is to be opened for appending (now or later).
64 ++++++++++++++++++++++++++++++++++++++*/
65
66 NodesX *NewNodeList(int append)
67 {
68 NodesX *nodesx;
69
70 nodesx=(NodesX*)calloc(1,sizeof(NodesX));
71
72 assert(nodesx); /* Check calloc() worked */
73
74 nodesx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
75
76 if(append)
77 sprintf(nodesx->filename,"%s/nodesx.input.tmp",option_tmpdirname);
78 else
79 sprintf(nodesx->filename,"%s/nodesx.%p.tmp",option_tmpdirname,(void*)nodesx);
80
81 if(append)
82 {
83 off_t size;
84
85 nodesx->fd=OpenFileAppend(nodesx->filename);
86
87 size=SizeFile(nodesx->filename);
88
89 nodesx->number=size/sizeof(NodeX);
90 }
91 else
92 nodesx->fd=OpenFileNew(nodesx->filename);
93
94 return(nodesx);
95 }
96
97
98 /*++++++++++++++++++++++++++++++++++++++
99 Free a node list.
100
101 NodesX *nodesx The set of nodes to be freed.
102
103 int keep Set to 1 if the file is to be kept (for appending later).
104 ++++++++++++++++++++++++++++++++++++++*/
105
106 void FreeNodeList(NodesX *nodesx,int keep)
107 {
108 if(!keep)
109 DeleteFile(nodesx->filename);
110
111 free(nodesx->filename);
112
113 if(nodesx->idata)
114 free(nodesx->idata);
115
116 if(nodesx->gdata)
117 free(nodesx->gdata);
118
119 if(nodesx->pdata)
120 free(nodesx->pdata);
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 the nodes by ID and index them */
197
198 xnumber=nodesx->number;
199 nodesx->number=0;
200
201 sortnodesx=nodesx;
202
203 nodesx->number=filesort_fixed(nodesx->fd,fd,sizeof(NodeX),NULL,
204 (int (*)(const void*,const void*))sort_by_id,
205 (int (*)(void*,index_t))deduplicate_and_index_by_id);
206
207 /* Close the files */
208
209 nodesx->fd=CloseFile(nodesx->fd);
210 CloseFile(fd);
211
212 /* Print the final message */
213
214 printf_last("Sorted Nodes: Nodes=%"Pindex_t" Duplicates=%"Pindex_t,xnumber,xnumber-nodesx->number);
215 }
216
217
218 /*++++++++++++++++++++++++++++++++++++++
219 Sort the nodes into id order.
220
221 int sort_by_id Returns the comparison of the id fields.
222
223 NodeX *a The first extended node.
224
225 NodeX *b The second extended node.
226 ++++++++++++++++++++++++++++++++++++++*/
227
228 static int sort_by_id(NodeX *a,NodeX *b)
229 {
230 node_t a_id=a->id;
231 node_t b_id=b->id;
232
233 if(a_id<b_id)
234 return(-1);
235 else if(a_id>b_id)
236 return(1);
237 else
238 return(0);
239 }
240
241
242 /*++++++++++++++++++++++++++++++++++++++
243 Create the index of identifiers and discard duplicate nodes.
244
245 int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise 0.
246
247 NodeX *nodex The extended node.
248
249 index_t index The number of sorted nodes that have already been written to the output file.
250 ++++++++++++++++++++++++++++++++++++++*/
251
252 static int deduplicate_and_index_by_id(NodeX *nodex,index_t index)
253 {
254 if(index==0 || sortnodesx->idata[index-1]!=nodex->id)
255 {
256 sortnodesx->idata[index]=nodex->id;
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 ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
279
280 /* While we are here we can work out the range of data */
281
282 lat_min=radians_to_latlong( 2);
283 lat_max=radians_to_latlong(-2);
284 lon_min=radians_to_latlong( 4);
285 lon_max=radians_to_latlong(-4);
286
287 /* Print the start message */
288
289 printf_first("Sorting Nodes Geographically");
290
291 /* Allocate the memory for the geographical index array */
292
293 nodesx->gdata=(index_t*)malloc(nodesx->number*sizeof(index_t));
294
295 assert(nodesx->gdata); /* Check malloc() worked */
296
297 /* Re-open the file read-only and a new file writeable */
298
299 nodesx->fd=ReOpenFile(nodesx->filename);
300
301 DeleteFile(nodesx->filename);
302
303 fd=OpenFileNew(nodesx->filename);
304
305 /* Sort nodes geographically and index them */
306
307 sortnodesx=nodesx;
308
309 filesort_fixed(nodesx->fd,fd,sizeof(NodeX),NULL,
310 (int (*)(const void*,const void*))sort_by_lat_long,
311 (int (*)(void*,index_t))index_by_lat_long);
312
313 /* Close the files */
314
315 nodesx->fd=CloseFile(nodesx->fd);
316 CloseFile(fd);
317
318 /* Free the memory */
319
320 free(nodesx->super);
321 nodesx->super=NULL;
322
323 /* Work out the number of bins */
324
325 lat_min_bin=latlong_to_bin(lat_min);
326 lon_min_bin=latlong_to_bin(lon_min);
327 lat_max_bin=latlong_to_bin(lat_max);
328 lon_max_bin=latlong_to_bin(lon_max);
329
330 nodesx->latzero=lat_min_bin;
331 nodesx->lonzero=lon_min_bin;
332
333 nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
334 nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;
335
336 /* Print the final message */
337
338 printf_last("Sorted Nodes Geographically: Nodes=%"Pindex_t,nodesx->number);
339 }
340
341
342 /*++++++++++++++++++++++++++++++++++++++
343 Sort the nodes into latitude and longitude order (first by longitude bin
344 number, then by latitude bin number and then by exact longitude and then by
345 exact latitude).
346
347 int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
348
349 NodeX *a The first extended node.
350
351 NodeX *b The second extended node.
352 ++++++++++++++++++++++++++++++++++++++*/
353
354 static int sort_by_lat_long(NodeX *a,NodeX *b)
355 {
356 ll_bin_t a_lon=latlong_to_bin(a->longitude);
357 ll_bin_t b_lon=latlong_to_bin(b->longitude);
358
359 if(a_lon<b_lon)
360 return(-1);
361 else if(a_lon>b_lon)
362 return(1);
363 else
364 {
365 ll_bin_t a_lat=latlong_to_bin(a->latitude);
366 ll_bin_t b_lat=latlong_to_bin(b->latitude);
367
368 if(a_lat<b_lat)
369 return(-1);
370 else if(a_lat>b_lat)
371 return(1);
372 else
373 {
374 if(a->longitude<b->longitude)
375 return(-1);
376 else if(a->longitude>b->longitude)
377 return(1);
378 else
379 {
380 if(a->latitude<b->latitude)
381 return(-1);
382 else if(a->latitude>b->latitude)
383 return(1);
384 }
385
386 return(0);
387 }
388 }
389 }
390
391
392 /*++++++++++++++++++++++++++++++++++++++
393 Create the index between the sorted and unsorted nodes.
394
395 int index_by_lat_long Return 1 if the value is to be kept, otherwise 0.
396
397 NodeX *nodex The extended node.
398
399 index_t index The number of sorted nodes that have already been written to the output file.
400 ++++++++++++++++++++++++++++++++++++++*/
401
402 static int index_by_lat_long(NodeX *nodex,index_t index)
403 {
404 sortnodesx->gdata[nodex->id]=index;
405
406 if(IsBitSet(sortnodesx->super,nodex->id))
407 nodex->flags|=NODE_SUPER;
408
409 if(nodex->latitude<lat_min)
410 lat_min=nodex->latitude;
411 if(nodex->latitude>lat_max)
412 lat_max=nodex->latitude;
413 if(nodex->longitude<lon_min)
414 lon_min=nodex->longitude;
415 if(nodex->longitude>lon_max)
416 lon_max=nodex->longitude;
417
418 return(1);
419 }
420
421
422 /*++++++++++++++++++++++++++++++++++++++
423 Find a particular node index.
424
425 index_t IndexNodeX Returns the index of the extended node with the specified id.
426
427 NodesX *nodesx The set of nodes to use.
428
429 node_t id The node id to look for.
430 ++++++++++++++++++++++++++++++++++++++*/
431
432 index_t IndexNodeX(NodesX *nodesx,node_t id)
433 {
434 index_t start=0;
435 index_t end=nodesx->number-1;
436 index_t mid;
437
438 /* Binary search - search key exact match only is required.
439 *
440 * # <- start | Check mid and move start or end if it doesn't match
441 * # |
442 * # | Since an exact match is wanted we can set end=mid-1
443 * # <- mid | or start=mid+1 because we know that mid doesn't match.
444 * # |
445 * # | Eventually either end=start or end=start+1 and one of
446 * # <- end | start or end is the wanted one.
447 */
448
449 if(end<start) /* There are no nodes */
450 return(NO_NODE);
451 else if(id<nodesx->idata[start]) /* Check key is not before start */
452 return(NO_NODE);
453 else if(id>nodesx->idata[end]) /* Check key is not after end */
454 return(NO_NODE);
455 else
456 {
457 do
458 {
459 mid=(start+end)/2; /* Choose mid point */
460
461 if(nodesx->idata[mid]<id) /* Mid point is too low */
462 start=mid+1;
463 else if(nodesx->idata[mid]>id) /* Mid point is too high */
464 end=mid?(mid-1):mid;
465 else /* Mid point is correct */
466 return(mid);
467 }
468 while((end-start)>1);
469
470 if(nodesx->idata[start]==id) /* Start is correct */
471 return(start);
472
473 if(nodesx->idata[end]==id) /* End is correct */
474 return(end);
475 }
476
477 return(NO_NODE);
478 }
479
480
481 /*++++++++++++++++++++++++++++++++++++++
482 Remove any nodes that are not part of a highway.
483
484 NodesX *nodesx The set of nodes to modify.
485
486 SegmentsX *segmentsx The set of segments to use.
487 ++++++++++++++++++++++++++++++++++++++*/
488
489 void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
490 {
491 NodeX nodex;
492 index_t total=0,highway=0,nothighway=0;
493 int fd;
494
495 /* Print the start message */
496
497 printf_first("Checking Nodes: Nodes=0");
498
499 /* Re-open the file read-only and a new file writeable */
500
501 nodesx->fd=ReOpenFile(nodesx->filename);
502
503 DeleteFile(nodesx->filename);
504
505 fd=OpenFileNew(nodesx->filename);
506
507 /* Modify the on-disk image */
508
509 while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
510 {
511 if(!IsBitSet(segmentsx->usednode,total))
512 nothighway++;
513 else
514 {
515 nodex.id=highway;
516 nodesx->idata[highway]=nodesx->idata[total];
517
518 WriteFile(fd,&nodex,sizeof(NodeX));
519
520 highway++;
521 }
522
523 total++;
524
525 if(!(total%10000))
526 printf_middle("Checking Nodes: Nodes=%"Pindex_t" Highway=%"Pindex_t" not-Highway=%"Pindex_t,total,highway,nothighway);
527 }
528
529 nodesx->number=highway;
530
531 /* Close the files */
532
533 nodesx->fd=CloseFile(nodesx->fd);
534 CloseFile(fd);
535
536 /* Free the now-unneeded index */
537
538 free(segmentsx->usednode);
539 segmentsx->usednode=NULL;
540
541 /* Print the final message */
542
543 printf_last("Checked Nodes: Nodes=%"Pindex_t" Highway=%"Pindex_t" not-Highway=%"Pindex_t,total,highway,nothighway);
544 }
545
546
547 /*++++++++++++++++++++++++++++++++++++++
548 Remove any nodes that have been pruned.
549
550 NodesX *nodesx The set of nodes to prune.
551
552 SegmentsX *segmentsx The set of segments to use.
553 ++++++++++++++++++++++++++++++++++++++*/
554
555 void RemovePrunedNodes(NodesX *nodesx,SegmentsX *segmentsx)
556 {
557 NodeX nodex;
558 index_t total=0,pruned=0,notpruned=0;
559 int fd;
560
561 /* Print the start message */
562
563 printf_first("Deleting Pruned Nodes: Nodes=0 Pruned=0");
564
565 /* Allocate the array of indexes */
566
567 nodesx->pdata=(index_t*)malloc(nodesx->number*sizeof(index_t));
568
569 assert(nodesx->pdata); /* Check malloc() worked */
570
571 /* Re-open the file read-only and a new file writeable */
572
573 nodesx->fd=ReOpenFile(nodesx->filename);
574
575 DeleteFile(nodesx->filename);
576
577 fd=OpenFileNew(nodesx->filename);
578
579 /* Modify the on-disk image */
580
581 while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
582 {
583 if(segmentsx->firstnode[total]==NO_SEGMENT)
584 {
585 pruned++;
586
587 nodesx->pdata[total]=NO_NODE;
588 }
589 else
590 {
591 nodex.id=notpruned;
592 nodesx->pdata[total]=notpruned;
593
594 WriteFile(fd,&nodex,sizeof(NodeX));
595
596 notpruned++;
597 }
598
599 total++;
600
601 if(!(total%10000))
602 printf_middle("Deleting Pruned Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,total,pruned);
603 }
604
605 nodesx->number=notpruned;
606
607 /* Close the files */
608
609 nodesx->fd=CloseFile(nodesx->fd);
610 CloseFile(fd);
611
612 /* Print the final message */
613
614 printf_last("Deleted Pruned Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,total,pruned);
615 }
616
617
618 /*++++++++++++++++++++++++++++++++++++++
619 Save the final node list database to a file.
620
621 NodesX *nodesx The set of nodes to save.
622
623 const char *filename The name of the file to save.
624
625 SegmentsX *segmentsx The set of segments to use.
626 ++++++++++++++++++++++++++++++++++++++*/
627
628 void SaveNodeList(NodesX *nodesx,const char *filename,SegmentsX *segmentsx)
629 {
630 index_t i;
631 int fd;
632 NodesFile nodesfile={0};
633 index_t super_number=0;
634 ll_bin2_t latlonbin=0,maxlatlonbins;
635 index_t *offsets;
636
637 /* Print the start message */
638
639 printf_first("Writing Nodes: Nodes=0");
640
641 /* Allocate the memory for the geographical offsets array */
642
643 offsets=(index_t*)malloc((nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
644
645 assert(offsets); /* Check malloc() worked */
646
647 latlonbin=0;
648
649 /* Re-open the file */
650
651 nodesx->fd=ReOpenFile(nodesx->filename);
652
653 /* Write out the nodes data */
654
655 fd=OpenFileNew(filename);
656
657 SeekFile(fd,sizeof(NodesFile)+(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
658
659 for(i=0;i<nodesx->number;i++)
660 {
661 NodeX nodex;
662 Node node={0};
663 ll_bin_t latbin,lonbin;
664 ll_bin2_t llbin;
665
666 ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
667
668 /* Create the Node */
669
670 node.latoffset=latlong_to_off(nodex.latitude);
671 node.lonoffset=latlong_to_off(nodex.longitude);
672 node.firstseg=segmentsx->firstnode[nodesx->gdata[nodex.id]];
673 node.allow=nodex.allow;
674 node.flags=nodex.flags;
675
676 if(node.flags&NODE_SUPER)
677 super_number++;
678
679 /* Work out the offsets */
680
681 latbin=latlong_to_bin(nodex.latitude )-nodesx->latzero;
682 lonbin=latlong_to_bin(nodex.longitude)-nodesx->lonzero;
683 llbin=lonbin*nodesx->latbins+latbin;
684
685 for(;latlonbin<=llbin;latlonbin++)
686 offsets[latlonbin]=i;
687
688 /* Write the data */
689
690 WriteFile(fd,&node,sizeof(Node));
691
692 if(!((i+1)%10000))
693 printf_middle("Writing Nodes: Nodes=%"Pindex_t,i+1);
694 }
695
696 /* Close the file */
697
698 nodesx->fd=CloseFile(nodesx->fd);
699
700 /* Finish off the offset indexing and write them out */
701
702 maxlatlonbins=nodesx->latbins*nodesx->lonbins;
703
704 for(;latlonbin<=maxlatlonbins;latlonbin++)
705 offsets[latlonbin]=nodesx->number;
706
707 SeekFile(fd,sizeof(NodesFile));
708 WriteFile(fd,offsets,(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
709
710 free(offsets);
711
712 /* Write out the header structure */
713
714 nodesfile.number=nodesx->number;
715 nodesfile.snumber=super_number;
716
717 nodesfile.latbins=nodesx->latbins;
718 nodesfile.lonbins=nodesx->lonbins;
719
720 nodesfile.latzero=nodesx->latzero;
721 nodesfile.lonzero=nodesx->lonzero;
722
723 SeekFile(fd,0);
724 WriteFile(fd,&nodesfile,sizeof(NodesFile));
725
726 CloseFile(fd);
727
728 /* Print the final message */
729
730 printf_last("Wrote Nodes: Nodes=%"Pindex_t,nodesx->number);
731 }

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