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 1113 - (show annotations) (download) (as text)
Mon Oct 22 07:54:28 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 15965 byte(s)
Use the new pre-sort function to allow CompactWays() to delete the unused
segments before sorting them.

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

Properties

Name Value
cvs:description Extended ways functions.