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

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