Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

/[routino]/trunk/src/waysx.c
ViewVC logotype

Contents of /trunk/src/waysx.c

Parent Directory Parent Directory | Revision Log Revision Log

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

Properties

Name Value
cvs:description Extended ways 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.2 (destination-access branch) Version 3.4.2 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