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

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