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 1208 - (show annotations) (download) (as text)
Sat Dec 15 16:43:03 2012 UTC (12 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 18242 byte(s)
Stop planetsplitter crashing out in unusual ways if there is no data.

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

Properties

Name Value
cvs:description Extended ways functions.