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 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.
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.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