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 1167 - (show annotations) (download) (as text)
Tue Nov 20 16:21:27 2012 UTC (12 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 18492 byte(s)
Rename the '--preserve' command line option to '--keep' for simplicity.

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

Properties

Name Value
cvs:description Extended ways functions.