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