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 1104 - (show annotations) (download) (as text)
Sun Oct 21 14:31:02 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 15143 byte(s)
Delete the onumber parameter from the Ways file header.
Don't map the ways file into memory when writing the 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 /* Local variables */
45
46 /*+ Temporary file-local variables for use by the sort functions. +*/
47 static WaysX *sortwaysx;
48 static SegmentsX *sortsegmentsx;
49
50 /* Local functions */
51
52 static int sort_by_id(WayX *a,WayX *b);
53 static int sort_by_name_and_id(WayX *a,WayX *b);
54 static int sort_by_name_and_prop_and_id(WayX *a,WayX *b);
55
56 static int deduplicate_and_index_by_id(WayX *wayx,index_t index);
57 static int deduplicate_and_index_by_compact_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 ID 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 way list, removing duplicated ways and unused ways.
321
322 WaysX *waysx The set of ways to process.
323
324 SegmentsX *segmentsx The set of segments to check.
325 ++++++++++++++++++++++++++++++++++++++*/
326
327 void CompactWayList(WaysX *waysx,SegmentsX *segmentsx)
328 {
329 int fd;
330 index_t cnumber;
331
332 /* Print the start message */
333
334 printf_first("Sorting Ways and Compacting");
335
336 /* Allocate the array of indexes */
337
338 waysx->cdata=(index_t*)malloc(waysx->number*sizeof(index_t));
339
340 assert(waysx->cdata); /* Check malloc() worked */
341
342 /* Re-open the file read-only and a new file writeable */
343
344 waysx->fd=ReOpenFile(waysx->filename);
345
346 DeleteFile(waysx->filename);
347
348 fd=OpenFileNew(waysx->filename);
349
350 /* Sort the ways to allow compacting according to the properties */
351
352 sortwaysx=waysx;
353 sortsegmentsx=segmentsx;
354
355 cnumber=filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_name_and_prop_and_id,(int (*)(void*,index_t))deduplicate_and_index_by_compact_id);
356
357 /* Close the files */
358
359 waysx->fd=CloseFile(waysx->fd);
360 CloseFile(fd);
361
362 /* Print the final message */
363
364 printf_last("Sorted and Compacted Ways: Ways=%"Pindex_t" Unique=%"Pindex_t,waysx->number,cnumber);
365 waysx->number=cnumber;
366
367 free(segmentsx->usedway);
368 segmentsx->usedway=NULL;
369 }
370
371
372 /*++++++++++++++++++++++++++++++++++++++
373 Sort the ways into id order.
374
375 int sort_by_id Returns the comparison of the id fields.
376
377 WayX *a The first extended way.
378
379 WayX *b The second extended way.
380 ++++++++++++++++++++++++++++++++++++++*/
381
382 static int sort_by_id(WayX *a,WayX *b)
383 {
384 way_t a_id=a->id;
385 way_t b_id=b->id;
386
387 if(a_id<b_id)
388 return(-1);
389 else if(a_id>b_id)
390 return(1);
391 else
392 return(0);
393 }
394
395
396 /*++++++++++++++++++++++++++++++++++++++
397 Sort the ways into name order and then id order.
398
399 int sort_by_name_and_id Returns the comparison of the name and id fields.
400
401 WayX *a The first extended Way.
402
403 WayX *b The second extended Way.
404 ++++++++++++++++++++++++++++++++++++++*/
405
406 static int sort_by_name_and_id(WayX *a,WayX *b)
407 {
408 int compare;
409 char *a_name=(char*)a+sizeof(WayX);
410 char *b_name=(char*)b+sizeof(WayX);
411
412 compare=strcmp(a_name,b_name);
413
414 if(compare)
415 return(compare);
416
417 return(sort_by_id(a,b));
418 }
419
420
421 /*++++++++++++++++++++++++++++++++++++++
422 Sort the ways into name, properties and id order.
423
424 int sort_by_name_and_prop_and_id Returns the comparison of the name, properties and id fields.
425
426 WayX *a The first extended Way.
427
428 WayX *b The second extended Way.
429 ++++++++++++++++++++++++++++++++++++++*/
430
431 static int sort_by_name_and_prop_and_id(WayX *a,WayX *b)
432 {
433 int compare;
434 index_t a_name=a->way.name;
435 index_t b_name=b->way.name;
436
437 if(a_name<b_name)
438 return(-1);
439 else if(a_name>b_name)
440 return(1);
441
442 compare=WaysCompare(&a->way,&b->way);
443
444 if(compare)
445 return(compare);
446
447 return(sort_by_id(a,b));
448 }
449
450
451 /*++++++++++++++++++++++++++++++++++++++
452 Create the index of identifiers and discard duplicate ways.
453
454 int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise 0.
455
456 WayX *wayx The extended way.
457
458 index_t index The index of this way in the total that have been kept.
459 ++++++++++++++++++++++++++++++++++++++*/
460
461 static int deduplicate_and_index_by_id(WayX *wayx,index_t index)
462 {
463 static way_t previd;
464
465 if(index==0 || wayx->id!=previd)
466 {
467 previd=wayx->id;
468
469 sortwaysx->idata[index]=wayx->id;
470
471 wayx->id=index;
472
473 return(1);
474 }
475 else
476 {
477 logerror("Way %"Pway_t" is duplicated.\n",wayx->id);
478
479 return(0);
480 }
481 }
482
483
484 /*++++++++++++++++++++++++++++++++++++++
485 Create the index of compacted Way identifiers and ignore Ways with duplicated properties.
486
487 int deduplicate_and_index_by_compact_id Return 1 if the value is to be kept, otherwise 0.
488
489 WayX *wayx The extended way.
490
491 index_t index The index of this way in the total that have been kept.
492 ++++++++++++++++++++++++++++++++++++++*/
493
494 static int deduplicate_and_index_by_compact_id(WayX *wayx,index_t index)
495 {
496 static Way lastway;
497
498 if(sortsegmentsx && !IsBitSet(sortsegmentsx->usedway,wayx->id))
499 {
500 sortwaysx->cdata[wayx->id]=NO_WAY;
501
502 return(0);
503 }
504
505 if(index==0 || wayx->way.name!=lastway.name || WaysCompare(&lastway,&wayx->way))
506 {
507 lastway=wayx->way;
508
509 sortwaysx->cdata[wayx->id]=index;
510
511 wayx->id=index;
512
513 return(1);
514 }
515 else
516 {
517 sortwaysx->cdata[wayx->id]=index-1;
518
519 return(0);
520 }
521 }
522
523
524 /*++++++++++++++++++++++++++++++++++++++
525 Find a particular way index.
526
527 index_t IndexWayX Returns the index of the extended way with the specified id.
528
529 WaysX *waysx The set of ways to process.
530
531 way_t id The way id to look for.
532 ++++++++++++++++++++++++++++++++++++++*/
533
534 index_t IndexWayX(WaysX *waysx,way_t id)
535 {
536 index_t start=0;
537 index_t end=waysx->number-1;
538 index_t mid;
539
540 /* Binary search - search key exact match only is required.
541 *
542 * # <- start | Check mid and move start or end if it doesn't match
543 * # |
544 * # | Since an exact match is wanted we can set end=mid-1
545 * # <- mid | or start=mid+1 because we know that mid doesn't match.
546 * # |
547 * # | Eventually either end=start or end=start+1 and one of
548 * # <- end | start or end is the wanted one.
549 */
550
551 if(end<start) /* There are no ways */
552 return(NO_WAY);
553 else if(id<waysx->idata[start]) /* Check key is not before start */
554 return(NO_WAY);
555 else if(id>waysx->idata[end]) /* Check key is not after end */
556 return(NO_WAY);
557 else
558 {
559 do
560 {
561 mid=(start+end)/2; /* Choose mid point */
562
563 if(waysx->idata[mid]<id) /* Mid point is too low */
564 start=mid+1;
565 else if(waysx->idata[mid]>id) /* Mid point is too high */
566 end=mid?(mid-1):mid;
567 else /* Mid point is correct */
568 return(mid);
569 }
570 while((end-start)>1);
571
572 if(waysx->idata[start]==id) /* Start is correct */
573 return(start);
574
575 if(waysx->idata[end]==id) /* End is correct */
576 return(end);
577 }
578
579 return(NO_WAY);
580 }
581
582
583 /*++++++++++++++++++++++++++++++++++++++
584 Save the way list to a file.
585
586 WaysX *waysx The set of ways to save.
587
588 const char *filename The name of the file to save.
589 ++++++++++++++++++++++++++++++++++++++*/
590
591 void SaveWayList(WaysX *waysx,const char *filename)
592 {
593 index_t i;
594 int fd;
595 int position=0;
596 WayX wayx;
597 WaysFile waysfile={0};
598 highways_t highways=0;
599 transports_t allow=0;
600 properties_t props=0;
601
602 /* Print the start message */
603
604 printf_first("Writing Ways: Ways=0");
605
606 /* Re-open the files */
607
608 waysx->fd=ReOpenFile(waysx->filename);
609 waysx->nfd=ReOpenFile(waysx->nfilename);
610
611 /* Write out the ways data */
612
613 fd=OpenFileNew(filename);
614
615 SeekFile(fd,sizeof(WaysFile));
616
617 for(i=0;i<waysx->number;i++)
618 {
619 ReadFile(waysx->fd,&wayx,sizeof(WayX));
620
621 highways|=HIGHWAYS(wayx.way.type);
622 allow |=wayx.way.allow;
623 props |=wayx.way.props;
624
625 WriteFile(fd,&wayx.way,sizeof(Way));
626
627 if(!((i+1)%1000))
628 printf_middle("Writing Ways: Ways=%"Pindex_t,i+1);
629 }
630
631 /* Write out the ways names */
632
633 SeekFile(fd,sizeof(WaysFile)+(off_t)waysx->number*sizeof(Way));
634
635 while(position<waysx->nlength)
636 {
637 int len=1024;
638 char temp[1024];
639
640 if((waysx->nlength-position)<1024)
641 len=waysx->nlength-position;
642
643 ReadFile(waysx->nfd,temp,len);
644
645 WriteFile(fd,temp,len);
646
647 position+=len;
648 }
649
650 /* Close the files */
651
652 waysx->fd=CloseFile(waysx->fd);
653 waysx->nfd=CloseFile(waysx->nfd);
654
655 /* Write out the header structure */
656
657 waysfile.number =waysx->number;
658
659 waysfile.highways=highways;
660 waysfile.allow =allow;
661 waysfile.props =props;
662
663 SeekFile(fd,0);
664 WriteFile(fd,&waysfile,sizeof(WaysFile));
665
666 CloseFile(fd);
667
668 /* Print the final message */
669
670 printf_last("Wrote Ways: Ways=%"Pindex_t,waysx->number);
671 }

Properties

Name Value
cvs:description Extended ways functions.