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 1161 - (show annotations) (download) (as text)
Tue Nov 20 14:16:58 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 18331 byte(s)
Tidy up all of the recent code changes - change the name of a few of the
functions.

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

Properties

Name Value
cvs:description Extended ways functions.