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 555 - (show annotations) (download) (as text)
Mon Dec 20 19:02:31 2010 UTC (14 years, 2 months ago) by amb
File MIME type: text/x-csrc
File size: 15125 byte(s)
Close and open the files for the slim case to match the map/unmap of files for
the non-slim case.

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

Properties

Name Value
cvs:description Extended ways functions.