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/waysx.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1338 - (show annotations) (download) (as text)
Wed May 22 17:31:03 2013 UTC (11 years, 9 months ago) by amb
File MIME type: text/x-csrc
File size: 18825 byte(s)
Store the list of nodes in the raw ways file for use by the errorlog functions.

1 /***************************************
2 Extended Way data type functions.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2008-2013 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 <stdlib.h>
24 #include <string.h>
25
26 #include "types.h"
27 #include "ways.h"
28
29 #include "typesx.h"
30 #include "segmentsx.h"
31 #include "waysx.h"
32
33 #include "files.h"
34 #include "logging.h"
35 #include "sorting.h"
36
37
38 /* Global variables */
39
40 /*+ The command line '--tmpdir' option or its default value. +*/
41 extern char *option_tmpdirname;
42
43 /* Local variables */
44
45 /*+ Temporary file-local variables for use by the sort functions. +*/
46 static WaysX *sortwaysx;
47 static SegmentsX *sortsegmentsx;
48
49 /* Local functions */
50
51 static int sort_by_id(WayX *a,WayX *b);
52 static int deduplicate_by_id(WayX *wayx,index_t index);
53
54 static int sort_by_name(WayX *a,WayX *b);
55 static int index_by_id(WayX *wayx,index_t index);
56
57 static int delete_unused(WayX *wayx,index_t index);
58 static int sort_by_name_and_prop_and_id(WayX *a,WayX *b);
59 static int deduplicate_and_index_by_compact_id(WayX *wayx,index_t index);
60
61
62 /*++++++++++++++++++++++++++++++++++++++
63 Allocate a new way list (create a new file or open an existing one).
64
65 WaysX *NewWayList Returns the way list.
66
67 int append Set to 1 if the file is to be opened for appending.
68
69 int readonly Set to 1 if the file is to be opened for reading.
70 ++++++++++++++++++++++++++++++++++++++*/
71
72 WaysX *NewWayList(int append,int readonly)
73 {
74 WaysX *waysx;
75
76 waysx=(WaysX*)calloc(1,sizeof(WaysX));
77
78 logassert(waysx,"Failed to allocate memory (try using slim mode?)"); /* Check calloc() worked */
79
80 waysx->filename =(char*)malloc(strlen(option_tmpdirname)+32);
81 waysx->filename_tmp=(char*)malloc(strlen(option_tmpdirname)+32);
82
83 sprintf(waysx->filename ,"%s/waysx.parsed.mem",option_tmpdirname);
84 sprintf(waysx->filename_tmp,"%s/waysx.%p.tmp" ,option_tmpdirname,(void*)waysx);
85
86 if(append || readonly)
87 if(ExistsFile(waysx->filename))
88 {
89 off_t size,position=0;
90 int fd;
91
92 size=SizeFile(waysx->filename);
93
94 fd=ReOpenFile(waysx->filename);
95
96 while(position<size)
97 {
98 FILESORT_VARINT waysize;
99
100 SeekReadFile(fd,&waysize,FILESORT_VARSIZE,position);
101
102 waysx->number++;
103 position+=waysize+FILESORT_VARSIZE;
104 }
105
106 CloseFile(fd);
107
108 RenameFile(waysx->filename,waysx->filename_tmp);
109 }
110
111 if(append)
112 waysx->fd=OpenFileAppend(waysx->filename_tmp);
113 else if(!readonly)
114 waysx->fd=OpenFileNew(waysx->filename_tmp);
115 else
116 waysx->fd=-1;
117
118 #if SLIM
119 waysx->cache=NewWayXCache();
120 #endif
121
122
123 waysx->nfilename_tmp=(char*)malloc(strlen(option_tmpdirname)+32);
124
125 sprintf(waysx->nfilename_tmp,"%s/waynames.%p.tmp",option_tmpdirname,(void*)waysx);
126
127 return(waysx);
128 }
129
130
131 /*++++++++++++++++++++++++++++++++++++++
132 Free a way list.
133
134 WaysX *waysx The set of ways to be freed.
135
136 int keep If set then the results file is to be kept.
137 ++++++++++++++++++++++++++++++++++++++*/
138
139 void FreeWayList(WaysX *waysx,int keep)
140 {
141 if(keep)
142 RenameFile(waysx->filename_tmp,waysx->filename);
143 else
144 DeleteFile(waysx->filename_tmp);
145
146 free(waysx->filename);
147 free(waysx->filename_tmp);
148
149 if(waysx->idata)
150 free(waysx->idata);
151
152 if(waysx->odata)
153 free(waysx->odata);
154
155 if(waysx->cdata)
156 free(waysx->cdata);
157
158 DeleteFile(waysx->nfilename_tmp);
159
160 free(waysx->nfilename_tmp);
161
162 #if SLIM
163 DeleteWayXCache(waysx->cache);
164 #endif
165
166 free(waysx);
167 }
168
169
170 /*++++++++++++++++++++++++++++++++++++++
171 Append a single way to an unsorted way list.
172
173 WaysX *waysx The set of ways to process.
174
175 way_t id The ID of the way.
176
177 Way *way The way data itself.
178
179 node_t *nodes The list of nodes for this way.
180
181 int nnodes The number of nodes for this way.
182
183 const char *name The name or reference of the way.
184 ++++++++++++++++++++++++++++++++++++++*/
185
186 void AppendWayList(WaysX *waysx,way_t id,Way *way,node_t *nodes,int nnodes,const char *name)
187 {
188 WayX wayx;
189 FILESORT_VARINT size;
190 node_t nonode=NO_NODE_ID;
191
192 wayx.id=id;
193 wayx.way=*way;
194
195 size=sizeof(WayX)+(nnodes+1)*sizeof(node_t)+strlen(name)+1;
196
197 WriteFile(waysx->fd,&size,FILESORT_VARSIZE);
198 WriteFile(waysx->fd,&wayx,sizeof(WayX));
199
200 WriteFile(waysx->fd,nodes ,nnodes*sizeof(node_t));
201 WriteFile(waysx->fd,&nonode, sizeof(node_t));
202
203 WriteFile(waysx->fd,name,strlen(name)+1);
204
205 waysx->number++;
206
207 logassert(waysx->number!=0,"Too many ways (change index_t to 64-bits?)"); /* Zero marks the high-water mark for ways. */
208 }
209
210
211 /*++++++++++++++++++++++++++++++++++++++
212 Finish appending ways and change the filename over.
213
214 WaysX *waysx The ways that have been appended.
215 ++++++++++++++++++++++++++++++++++++++*/
216
217 void FinishWayList(WaysX *waysx)
218 {
219 if(waysx->fd!=-1)
220 waysx->fd=CloseFile(waysx->fd);
221 }
222
223
224 /*++++++++++++++++++++++++++++++++++++++
225 Find a particular way index.
226
227 index_t IndexWayX Returns the index of the extended way with the specified id.
228
229 WaysX *waysx The set of ways to process.
230
231 way_t id The way id to look for.
232 ++++++++++++++++++++++++++++++++++++++*/
233
234 index_t IndexWayX(WaysX *waysx,way_t id)
235 {
236 index_t start=0;
237 index_t end=waysx->number-1;
238 index_t mid;
239
240 if(waysx->number==0) /* There are no ways */
241 return(NO_WAY);
242
243 if(id<waysx->idata[start]) /* Key is before start */
244 return(NO_WAY);
245
246 if(id>waysx->idata[end]) /* Key is after end */
247 return(NO_WAY);
248
249 /* Binary search - search key exact match only is required.
250 *
251 * # <- start | Check mid and move start or end if it doesn't match
252 * # |
253 * # | Since an exact match is wanted we can set end=mid-1
254 * # <- mid | or start=mid+1 because we know that mid doesn't match.
255 * # |
256 * # | Eventually either end=start or end=start+1 and one of
257 * # <- end | start or end is the wanted one.
258 */
259
260 do
261 {
262 mid=(start+end)/2; /* Choose mid point */
263
264 if(waysx->idata[mid]<id) /* Mid point is too low */
265 start=mid+1;
266 else if(waysx->idata[mid]>id) /* Mid point is too high */
267 end=mid?(mid-1):mid;
268 else /* Mid point is correct */
269 return(mid);
270 }
271 while((end-start)>1);
272
273 if(waysx->idata[start]==id) /* Start is correct */
274 return(start);
275
276 if(waysx->idata[end]==id) /* End is correct */
277 return(end);
278
279 return(NO_WAY);
280 }
281
282
283 /*++++++++++++++++++++++++++++++++++++++
284 Sort the list of ways.
285
286 WaysX *waysx The set of ways to process.
287 ++++++++++++++++++++++++++++++++++++++*/
288
289 void SortWayList(WaysX *waysx)
290 {
291 index_t xnumber;
292 int fd;
293
294 /* Print the start message */
295
296 printf_first("Sorting Ways");
297
298 /* Re-open the file read-only and a new file writeable */
299
300 waysx->fd=ReOpenFile(waysx->filename_tmp);
301
302 DeleteFile(waysx->filename_tmp);
303
304 fd=OpenFileNew(waysx->filename_tmp);
305
306 /* Sort the ways by ID and index them */
307
308 xnumber=waysx->number;
309
310 waysx->number=filesort_vary(waysx->fd,fd,NULL,
311 (int (*)(const void*,const void*))sort_by_id,
312 (int (*)(void*,index_t))deduplicate_by_id);
313
314 /* Close the files */
315
316 waysx->fd=CloseFile(waysx->fd);
317 CloseFile(fd);
318
319 /* Print the final message */
320
321 printf_last("Sorted Ways: Ways=%"Pindex_t" Duplicates=%"Pindex_t,xnumber,xnumber-waysx->number);
322 }
323
324
325 /*++++++++++++++++++++++++++++++++++++++
326 Sort the ways into id order.
327
328 int sort_by_id Returns the comparison of the id fields.
329
330 WayX *a The first extended way.
331
332 WayX *b The second extended way.
333 ++++++++++++++++++++++++++++++++++++++*/
334
335 static int sort_by_id(WayX *a,WayX *b)
336 {
337 way_t a_id=a->id;
338 way_t b_id=b->id;
339
340 if(a_id<b_id)
341 return(-1);
342 else if(a_id>b_id)
343 return(1);
344 else
345 return(-FILESORT_PRESERVE_ORDER(a,b)); /* latest version first */
346 }
347
348
349 /*++++++++++++++++++++++++++++++++++++++
350 Discard duplicate ways.
351
352 int deduplicate_by_id Return 1 if the value is to be kept, otherwise 0.
353
354 WayX *wayx The extended way.
355
356 index_t index The number of sorted ways that have already been written to the output file.
357 ++++++++++++++++++++++++++++++++++++++*/
358
359 static int deduplicate_by_id(WayX *wayx,index_t index)
360 {
361 static way_t previd=NO_WAY_ID;
362
363 if(wayx->id!=previd)
364 {
365 previd=wayx->id;
366
367 if(wayx->way.type==WAY_DELETED)
368 return(0);
369 else
370 return(1);
371 }
372 else
373 return(0);
374 }
375
376
377 /*++++++++++++++++++++++++++++++++++++++
378 Extract the way names from the ways and reference the list of names from the ways.
379
380 WaysX *waysx The set of ways to process.
381
382 int keep If set to 1 then keep the old data file otherwise delete it.
383 ++++++++++++++++++++++++++++++++++++++*/
384
385 void ExtractWayNames(WaysX *waysx,int keep)
386 {
387 index_t i;
388 int fd;
389 char *names[2]={NULL,NULL};
390 int namelen[2]={0,0};
391 int nnames=0;
392 uint32_t lastlength=0;
393
394 /* Print the start message */
395
396 printf_first("Sorting Ways by Name");
397
398 /* Re-open the file read-only and a new file writeable */
399
400 waysx->fd=ReOpenFile(waysx->filename_tmp);
401
402 if(keep)
403 RenameFile(waysx->filename_tmp,waysx->filename);
404 else
405 DeleteFile(waysx->filename_tmp);
406
407 waysx->knumber=waysx->number;
408
409 fd=OpenFileNew(waysx->filename_tmp);
410
411 /* Sort the ways to allow separating the names */
412
413 filesort_vary(waysx->fd,fd,NULL,
414 (int (*)(const void*,const void*))sort_by_name,
415 NULL);
416
417 /* Close the files */
418
419 waysx->fd=CloseFile(waysx->fd);
420 CloseFile(fd);
421
422 /* Print the final message */
423
424 printf_last("Sorted Ways by Name: Ways=%"Pindex_t,waysx->number);
425
426
427 /* Print the start message */
428
429 printf_first("Separating Way Names: Ways=0 Names=0");
430
431 /* Re-open the file read-only and new files writeable */
432
433 waysx->fd=ReOpenFile(waysx->filename_tmp);
434
435 DeleteFile(waysx->filename_tmp);
436
437 fd=OpenFileNew(waysx->filename_tmp);
438
439 waysx->nfd=OpenFileNew(waysx->nfilename_tmp);
440
441 /* Copy from the single file into two files */
442
443 for(i=0;i<waysx->number;i++)
444 {
445 WayX wayx;
446 FILESORT_VARINT size;
447 node_t node;
448
449 ReadFile(waysx->fd,&size,FILESORT_VARSIZE);
450
451 ReadFile(waysx->fd,&wayx,sizeof(WayX));
452
453 while(!ReadFile(waysx->fd,&node,sizeof(node_t)) && node!=NO_NODE_ID)
454 size-=sizeof(node_t);
455
456 size-=sizeof(node_t)+sizeof(WayX);
457
458 if(namelen[nnames%2]<size)
459 names[nnames%2]=(char*)realloc((void*)names[nnames%2],namelen[nnames%2]=size);
460
461 ReadFile(waysx->fd,names[nnames%2],size);
462
463 if(nnames==0 || strcmp(names[0],names[1]))
464 {
465 WriteFile(waysx->nfd,names[nnames%2],size);
466
467 lastlength=waysx->nlength;
468 waysx->nlength+=size;
469
470 nnames++;
471 }
472
473 wayx.way.name=lastlength;
474
475 WriteFile(fd,&wayx,sizeof(WayX));
476
477 if(!((i+1)%1000))
478 printf_middle("Separating Way Names: Ways=%"Pindex_t" Names=%"Pindex_t,i+1,nnames);
479 }
480
481 if(names[0]) free(names[0]);
482 if(names[1]) free(names[1]);
483
484 /* Close the files */
485
486 waysx->fd=CloseFile(waysx->fd);
487 CloseFile(fd);
488
489 waysx->nfd=CloseFile(waysx->nfd);
490
491 /* Print the final message */
492
493 printf_last("Separated Way Names: Ways=%"Pindex_t" Names=%"Pindex_t,waysx->number,nnames);
494
495
496 /* Print the start message */
497
498 printf_first("Sorting Ways");
499
500 /* Re-open the file read-only and a new file writeable */
501
502 waysx->fd=ReOpenFile(waysx->filename_tmp);
503
504 DeleteFile(waysx->filename_tmp);
505
506 fd=OpenFileNew(waysx->filename_tmp);
507
508 /* Allocate the array of indexes */
509
510 waysx->idata=(way_t*)malloc(waysx->number*sizeof(way_t));
511
512 logassert(waysx->idata,"Failed to allocate memory (try using slim mode?)"); /* Check malloc() worked */
513
514 /* Sort the ways by ID */
515
516 sortwaysx=waysx;
517
518 filesort_fixed(waysx->fd,fd,sizeof(WayX),NULL,
519 (int (*)(const void*,const void*))sort_by_id,
520 (int (*)(void*,index_t))index_by_id);
521
522 /* Close the files */
523
524 waysx->fd=CloseFile(waysx->fd);
525 CloseFile(fd);
526
527 /* Print the final message */
528
529 printf_last("Sorted Ways: Ways=%"Pindex_t,waysx->number);
530 }
531
532
533 /*++++++++++++++++++++++++++++++++++++++
534 Sort the ways into name order and then id order.
535
536 int sort_by_name Returns the comparison of the name fields.
537
538 WayX *a The first extended Way.
539
540 WayX *b The second extended Way.
541 ++++++++++++++++++++++++++++++++++++++*/
542
543 static int sort_by_name(WayX *a,WayX *b)
544 {
545 int compare;
546 char *a_name=(char*)a+sizeof(WayX);
547 char *b_name=(char*)b+sizeof(WayX);
548
549 compare=strcmp(a_name,b_name);
550
551 if(compare)
552 return(compare);
553 else
554 return(FILESORT_PRESERVE_ORDER(a,b));
555 }
556
557
558 /*++++++++++++++++++++++++++++++++++++++
559 Create the index of identifiers.
560
561 int index_by_id Return 1 if the value is to be kept, otherwise 0.
562
563 WayX *wayx The extended way.
564
565 index_t index The number of sorted ways that have already been written to the output file.
566 ++++++++++++++++++++++++++++++++++++++*/
567
568 static int index_by_id(WayX *wayx,index_t index)
569 {
570 sortwaysx->idata[index]=wayx->id;
571
572 return(1);
573 }
574
575
576 /*++++++++++++++++++++++++++++++++++++++
577 Compact the way list, removing duplicated ways and unused ways.
578
579 WaysX *waysx The set of ways to process.
580
581 SegmentsX *segmentsx The set of segments to check.
582 ++++++++++++++++++++++++++++++++++++++*/
583
584 void CompactWayList(WaysX *waysx,SegmentsX *segmentsx)
585 {
586 int fd;
587 index_t cnumber;
588
589 if(waysx->number==0)
590 return;
591
592 /* Print the start message */
593
594 printf_first("Sorting Ways and Compacting");
595
596 /* Allocate the array of indexes */
597
598 waysx->cdata=(index_t*)malloc(waysx->number*sizeof(index_t));
599
600 logassert(waysx->cdata,"Failed to allocate memory (try using slim mode?)"); /* Check malloc() worked */
601
602 /* Re-open the file read-only and a new file writeable */
603
604 waysx->fd=ReOpenFile(waysx->filename_tmp);
605
606 DeleteFile(waysx->filename_tmp);
607
608 fd=OpenFileNew(waysx->filename_tmp);
609
610 /* Sort the ways to allow compacting according to the properties */
611
612 sortwaysx=waysx;
613 sortsegmentsx=segmentsx;
614
615 cnumber=filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(void*,index_t))delete_unused,
616 (int (*)(const void*,const void*))sort_by_name_and_prop_and_id,
617 (int (*)(void*,index_t))deduplicate_and_index_by_compact_id);
618
619 /* Close the files */
620
621 waysx->fd=CloseFile(waysx->fd);
622 CloseFile(fd);
623
624 /* Print the final message */
625
626 printf_last("Sorted and Compacted Ways: Ways=%"Pindex_t" Unique=%"Pindex_t,waysx->number,cnumber);
627 waysx->number=cnumber;
628
629 free(segmentsx->usedway);
630 segmentsx->usedway=NULL;
631 }
632
633
634 /*++++++++++++++++++++++++++++++++++++++
635 Delete the ways that are no longer being used.
636
637 int delete_unused Return 1 if the value is to be kept, otherwise 0.
638
639 WayX *wayx The extended way.
640
641 index_t index The number of unsorted ways that have been read from the input file.
642 ++++++++++++++++++++++++++++++++++++++*/
643
644 static int delete_unused(WayX *wayx,index_t index)
645 {
646 if(sortsegmentsx && !IsBitSet(sortsegmentsx->usedway,index))
647 {
648 sortwaysx->cdata[index]=NO_WAY;
649
650 return(0);
651 }
652 else
653 {
654 wayx->id=index;
655
656 return(1);
657 }
658 }
659
660
661 /*++++++++++++++++++++++++++++++++++++++
662 Sort the ways into name, properties and id order.
663
664 int sort_by_name_and_prop_and_id Returns the comparison of the name, properties and id fields.
665
666 WayX *a The first extended Way.
667
668 WayX *b The second extended Way.
669 ++++++++++++++++++++++++++++++++++++++*/
670
671 static int sort_by_name_and_prop_and_id(WayX *a,WayX *b)
672 {
673 int compare;
674 index_t a_name=a->way.name;
675 index_t b_name=b->way.name;
676
677 if(a_name<b_name)
678 return(-1);
679 else if(a_name>b_name)
680 return(1);
681
682 compare=WaysCompare(&a->way,&b->way);
683
684 if(compare)
685 return(compare);
686
687 return(sort_by_id(a,b));
688 }
689
690
691 /*++++++++++++++++++++++++++++++++++++++
692 Create the index of compacted Way identifiers and ignore Ways with duplicated properties.
693
694 int deduplicate_and_index_by_compact_id Return 1 if the value is to be kept, otherwise 0.
695
696 WayX *wayx The extended way.
697
698 index_t index The number of sorted ways that have already been written to the output file.
699 ++++++++++++++++++++++++++++++++++++++*/
700
701 static int deduplicate_and_index_by_compact_id(WayX *wayx,index_t index)
702 {
703 static Way lastway;
704
705 if(index==0 || wayx->way.name!=lastway.name || WaysCompare(&lastway,&wayx->way))
706 {
707 lastway=wayx->way;
708
709 sortwaysx->cdata[wayx->id]=index;
710
711 wayx->id=index;
712
713 return(1);
714 }
715 else
716 {
717 sortwaysx->cdata[wayx->id]=index-1;
718
719 return(0);
720 }
721 }
722
723
724 /*++++++++++++++++++++++++++++++++++++++
725 Save the way list to a file.
726
727 WaysX *waysx The set of ways to save.
728
729 const char *filename The name of the file to save.
730 ++++++++++++++++++++++++++++++++++++++*/
731
732 void SaveWayList(WaysX *waysx,const char *filename)
733 {
734 index_t i;
735 int fd;
736 index_t position=0;
737 WayX wayx;
738 WaysFile waysfile={0};
739 highways_t highways=0;
740 transports_t allow=0;
741 properties_t props=0;
742
743 /* Print the start message */
744
745 printf_first("Writing Ways: Ways=0");
746
747 /* Re-open the files */
748
749 waysx->fd=ReOpenFile(waysx->filename_tmp);
750 waysx->nfd=ReOpenFile(waysx->nfilename_tmp);
751
752 /* Write out the ways data */
753
754 fd=OpenFileNew(filename);
755
756 SeekFile(fd,sizeof(WaysFile));
757
758 for(i=0;i<waysx->number;i++)
759 {
760 ReadFile(waysx->fd,&wayx,sizeof(WayX));
761
762 highways|=HIGHWAYS(wayx.way.type);
763 allow |=wayx.way.allow;
764 props |=wayx.way.props;
765
766 WriteFile(fd,&wayx.way,sizeof(Way));
767
768 if(!((i+1)%1000))
769 printf_middle("Writing Ways: Ways=%"Pindex_t,i+1);
770 }
771
772 /* Write out the ways names */
773
774 SeekFile(fd,sizeof(WaysFile)+(off_t)waysx->number*sizeof(Way));
775
776 while(position<waysx->nlength)
777 {
778 size_t len=1024;
779 char temp[1024];
780
781 if((waysx->nlength-position)<1024)
782 len=waysx->nlength-position;
783
784 ReadFile(waysx->nfd,temp,len);
785
786 WriteFile(fd,temp,len);
787
788 position+=len;
789 }
790
791 /* Close the files */
792
793 waysx->fd=CloseFile(waysx->fd);
794 waysx->nfd=CloseFile(waysx->nfd);
795
796 /* Write out the header structure */
797
798 waysfile.number =waysx->number;
799
800 waysfile.highways=highways;
801 waysfile.allow =allow;
802 waysfile.props =props;
803
804 SeekFile(fd,0);
805 WriteFile(fd,&waysfile,sizeof(WaysFile));
806
807 CloseFile(fd);
808
809 /* Print the final message */
810
811 printf_last("Wrote Ways: Ways=%"Pindex_t,waysx->number);
812 }

Properties

Name Value
cvs:description Extended ways functions.