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 309 - (show annotations) (download) (as text)
Thu Dec 10 18:49:18 2009 UTC (15 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 18243 byte(s) 
Write out the list of ways without memory mapping anything.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.32 2009-12-10 18:49:18 amb Exp $
3
4 Extended Way data type functions.
5
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008,2009 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 <string.h>
28
29 #include "functions.h"
30 #include "waysx.h"
31 #include "ways.h"
32
33
34 /* Constants */
35
36 /*+ The amount of memory to use for sorting. +*/
37 #define SORT_RAMSIZE (64*1024*1024)
38
39 /* Variables */
40
41 /*+ The command line '--slim' option. +*/
42 extern int option_slim;
43
44 /*+ The command line '--tmpdir' option or its default value. +*/
45 extern char *option_tmpdirname;
46
47 /*+ A temporary file-local variable for use by the sort functions. +*/
48 static WaysX *sortwaysx;
49
50 /* Functions */
51
52 static int sort_by_id(WayX *a,WayX *b);
53 static int index_by_id(WayX *wayx,index_t index);
54
55 static int sort_by_name(char *a,char *b);
56 static index_t index_way_name(char** names,int number,char *name);
57 static int sort_by_name_and_properties(Way *a,Way *b);
58 static index_t index_way(Way** data,int number,Way *way);
59
60
61 /*++++++++++++++++++++++++++++++++++++++
62 Allocate a new way list.
63
64 WaysX *NewWayList Returns the way list.
65 ++++++++++++++++++++++++++++++++++++++*/
66
67 WaysX *NewWayList(void)
68 {
69 WaysX *waysx;
70
71 waysx=(WaysX*)calloc(1,sizeof(WaysX));
72
73 assert(waysx); /* Check calloc() worked */
74
75 waysx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
76 sprintf(waysx->filename,"%s/ways.%p.tmp",option_tmpdirname,waysx);
77
78 waysx->fd=OpenFile(waysx->filename);
79
80 waysx->nfilename=(char*)malloc(strlen(option_tmpdirname)+32);
81 sprintf(waysx->nfilename,"%s/waynames.%p.tmp",option_tmpdirname,waysx);
82
83 waysx->nfd=OpenFile(waysx->nfilename);
84
85 return(waysx);
86 }
87
88
89 /*++++++++++++++++++++++++++++++++++++++
90 Free a way list.
91
92 WaysX *waysx The list to be freed.
93 ++++++++++++++++++++++++++++++++++++++*/
94
95 void FreeWayList(WaysX *waysx)
96 {
97 DeleteFile(waysx->filename);
98 free(waysx->filename);
99
100 if(waysx->idata)
101 free(waysx->idata);
102
103 DeleteFile(waysx->nfilename);
104 free(waysx->nfilename);
105
106 free(waysx);
107 }
108
109
110 /*++++++++++++++++++++++++++++++++++++++
111 Append a way to a way list.
112
113 void AppendWay Returns the newly appended way.
114
115 WaysX* waysx The set of ways to process.
116
117 way_t id The ID of the way.
118
119 Way *way The way data itself.
120
121 const char *name The name or reference of the way.
122 ++++++++++++++++++++++++++++++++++++++*/
123
124 void AppendWay(WaysX* waysx,way_t id,Way *way,const char *name)
125 {
126 WayX wayx;
127
128 assert(!waysx->idata); /* Must not have idata filled in => unsorted */
129
130 wayx.id=id;
131 wayx.way=*way;
132 wayx.name=waysx->nlength;
133
134 WriteFile(waysx->fd,&wayx,sizeof(WayX));
135
136 waysx->xnumber++;
137
138 WriteFile(waysx->nfd,name,strlen(name)+1);
139
140 waysx->nlength+=strlen(name)+1;
141 }
142
143
144 /*++++++++++++++++++++++++++++++++++++++
145 Sort the list of ways.
146
147 WaysX* waysx The set of ways to process.
148 ++++++++++++++++++++++++++++++++++++++*/
149
150 void SortWayList(WaysX* waysx)
151 {
152 int fd;
153
154 /* Check the start conditions */
155
156 assert(!waysx->idata); /* Must not have idata filled in => unsorted */
157
158 /* Print the start message */
159
160 printf("Sorting Ways");
161 fflush(stdout);
162
163 /* Close the files and re-open them (finished appending) */
164
165 CloseFile(waysx->fd);
166 waysx->fd=ReOpenFile(waysx->filename);
167
168 CloseFile(waysx->nfd);
169 waysx->nfd=ReOpenFile(waysx->nfilename);
170
171 DeleteFile(waysx->filename);
172
173 fd=OpenFile(waysx->filename);
174
175 /* Allocate the array of indexes */
176
177 waysx->idata=(way_t*)malloc(waysx->xnumber*sizeof(way_t));
178
179 assert(waysx->idata); /* Check malloc() worked */
180
181 /* Sort the way indexes and remove duplicates */
182
183 sortwaysx=waysx;
184
185 filesort(waysx->fd,fd,sizeof(WayX),SORT_RAMSIZE,(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))index_by_id);
186
187 /* Close the files and re-open them */
188
189 CloseFile(waysx->fd);
190 CloseFile(fd);
191
192 waysx->fd=ReOpenFile(waysx->filename);
193
194 /* Print the final message */
195
196 printf("\rSorted Ways: Ways=%d Duplicates=%d\n",waysx->xnumber,waysx->xnumber-waysx->number);
197 fflush(stdout);
198 }
199
200
201 /*++++++++++++++++++++++++++++++++++++++
202 Sort the ways into id order.
203
204 int sort_by_id Returns the comparison of the id fields.
205
206 WayX *a The first extended way.
207
208 WayX *b The second extended way.
209 ++++++++++++++++++++++++++++++++++++++*/
210
211 static int sort_by_id(WayX *a,WayX *b)
212 {
213 way_t a_id=a->id;
214 way_t b_id=b->id;
215
216 if(a_id<b_id)
217 return(-1);
218 else if(a_id>b_id)
219 return(1);
220 else
221 return(0);
222 }
223
224
225 /*++++++++++++++++++++++++++++++++++++++
226 Index the ways after sorting.
227
228 int index_by_id Return 1 if the value is to be kept, otherwise zero.
229
230 WayX *wayx The extended way.
231
232 index_t index The index of this way in the total.
233 ++++++++++++++++++++++++++++++++++++++*/
234
235 static int index_by_id(WayX *wayx,index_t index)
236 {
237 if(index==0 || sortwaysx->idata[index-1]!=wayx->id)
238 {
239 sortwaysx->idata[index]=wayx->id;
240
241 sortwaysx->number++;
242
243 return(1);
244 }
245
246 return(0);
247 }
248
249
250 /*++++++++++++++++++++++++++++++++++++++
251 Find a particular way index.
252
253 index_t IndexWayX Returns the index of the extended way with the specified id.
254
255 WaysX* waysx The set of ways to process.
256
257 way_t id The way id to look for.
258 ++++++++++++++++++++++++++++++++++++++*/
259
260 index_t IndexWayX(WaysX* waysx,way_t id)
261 {
262 int start=0;
263 int end=waysx->number-1;
264 int mid;
265
266 assert(waysx->idata); /* Must have idata filled in => sorted */
267
268 /* Binary search - search key exact match only is required.
269 *
270 * # <- start | Check mid and move start or end if it doesn't match
271 * # |
272 * # | Since an exact match is wanted we can set end=mid-1
273 * # <- mid | or start=mid+1 because we know that mid doesn't match.
274 * # |
275 * # | Eventually either end=start or end=start+1 and one of
276 * # <- end | start or end is the wanted one.
277 */
278
279 if(end<start) /* There are no ways */
280 return(NO_WAY);
281 else if(id<waysx->idata[start]) /* Check key is not before start */
282 return(NO_WAY);
283 else if(id>waysx->idata[end]) /* Check key is not after end */
284 return(NO_WAY);
285 else
286 {
287 do
288 {
289 mid=(start+end)/2; /* Choose mid point */
290
291 if(waysx->idata[mid]<id) /* Mid point is too low */
292 start=mid+1;
293 else if(waysx->idata[mid]>id) /* Mid point is too high */
294 end=mid-1;
295 else /* Mid point is correct */
296 return(mid);
297 }
298 while((end-start)>1);
299
300 if(waysx->idata[start]==id) /* Start is correct */
301 return(start);
302
303 if(waysx->idata[end]==id) /* End is correct */
304 return(end);
305 }
306
307 return(NO_WAY);
308 }
309
310
311 /*++++++++++++++++++++++++++++++++++++++
312 Lookup a particular way.
313
314 WayX *LookupWayX Returns a pointer to the extended way with the specified id.
315
316 WaysX* waysx The set of ways to process.
317
318 index_t index The way index to look for.
319
320 int position The position in the cache to use.
321 ++++++++++++++++++++++++++++++++++++++*/
322
323 WayX *LookupWayX(WaysX* waysx,index_t index,int position)
324 {
325 assert(index!=NO_WAY); /* Must be a valid way */
326
327 if(option_slim)
328 {
329 SeekFile(waysx->fd,index*sizeof(WayX));
330
331 ReadFile(waysx->fd,&waysx->cached[position-1],sizeof(WayX));
332
333 return(&waysx->cached[position-1]);
334 }
335 else
336 {
337 return(&waysx->xdata[index]);
338 }
339 }
340
341
342 /*++++++++++++++++++++++++++++++++++++++
343 Compact the list of way names.
344
345 WaysX* waysx The set of ways to process.
346 ++++++++++++++++++++++++++++++++++++++*/
347
348 void CompactWayNames(WaysX* waysx)
349 {
350 index_t i,j,*offsets;
351 char **cnames;
352 WayX wayx;
353 int duplicate=0;
354 int fd,nfd;
355
356 /* Print the start message for sorting names */
357
358 printf("Sorting Way names");
359 fflush(stdout);
360
361 /* Get the uncompacted name data and create list for compacted */
362
363 waysx->xdata=MapFile(waysx->filename);
364
365 waysx->names=MapFile(waysx->nfilename);
366
367 cnames=(char**)malloc(waysx->number*sizeof(char*));
368
369 assert(cnames); /* Check malloc() worked */
370
371 /* Create the index of names, sort it and remove duplicates */
372
373 for(i=0;i<waysx->number;i++)
374 cnames[i]=&waysx->names[waysx->xdata[i].name];
375
376 heapsort((void**)cnames,waysx->number,(int (*)(const void*,const void*))sort_by_name);
377
378 j=0;
379 for(i=1;i<waysx->number;i++)
380 if(strcmp(cnames[i],cnames[j]))
381 cnames[++j]=cnames[i];
382 else
383 duplicate++;
384
385 waysx->nnumber=++j;
386
387 /* Sort the on-disk image */
388
389 DeleteFile(waysx->nfilename);
390
391 nfd=OpenFile(waysx->nfilename);
392
393 offsets=(index_t*)malloc(waysx->nnumber*sizeof(index_t));
394
395 assert(offsets); /* Check malloc() worked */
396
397 waysx->nlength=0;
398
399 for(i=0;i<waysx->nnumber;i++)
400 {
401 offsets[i]=waysx->nlength;
402 waysx->nlength+=strlen(cnames[i])+1;
403 WriteFile(nfd,cnames[i],strlen(cnames[i])+1);
404 }
405
406 CloseFile(waysx->nfd);
407 CloseFile(nfd);
408
409 waysx->nfd=ReOpenFile(waysx->nfilename);
410
411 /* Print the final message for sorting names */
412
413 printf("\rSorted Way names: Names=%d Duplicate=%d\n",waysx->number,duplicate);
414 fflush(stdout);
415
416 /* Print the start message for compacting names */
417
418 printf("Compacting Way names");
419 fflush(stdout);
420
421 /* Update the on-disk image */
422
423 DeleteFile(waysx->filename);
424
425 fd=OpenFile(waysx->filename);
426 SeekFile(waysx->fd,0);
427
428 while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
429 {
430 wayx.way.name=offsets[index_way_name(cnames,waysx->nnumber,&waysx->names[wayx.name])];
431
432 WriteFile(fd,&wayx,sizeof(WayX));
433 }
434
435 CloseFile(waysx->fd);
436 CloseFile(fd);
437
438 waysx->xdata=UnmapFile(waysx->filename);
439 waysx->names=UnmapFile(waysx->nfilename);
440
441 waysx->fd=ReOpenFile(waysx->filename);
442
443 /* Print the final message for compacting names */
444
445 printf("\rCompacted Way names: Names=%d Unique=%d\n",waysx->number,waysx->nnumber);
446 fflush(stdout);
447
448 free(cnames);
449 free(offsets);
450 }
451
452
453 /*++++++++++++++++++++++++++++++++++++++
454 Sort the way names.
455
456 int sort_by_name Returns the comparison of the name fields.
457
458 char *a The first extended Way.
459
460 char *b The second extended Way.
461 ++++++++++++++++++++++++++++++++++++++*/
462
463 static int sort_by_name(char *a,char *b)
464 {
465 return(strcmp(a,b));
466 }
467
468
469 /*++++++++++++++++++++++++++++++++++++++
470 Find a particular name within the sorted list of names.
471
472 index_t index_way_name Returns the index of the name within the list.
473
474 char **names The set of names to search.
475
476 int number The number of names.
477
478 char *name The name to look for.
479 ++++++++++++++++++++++++++++++++++++++*/
480
481 static index_t index_way_name(char** names,int number,char *name)
482 {
483 int start=0;
484 int end=number-1;
485 int mid;
486
487 /* Binary search - search key exact match only is required.
488 *
489 * # <- start | Check mid and move start or end if it doesn't match
490 * # |
491 * # | Since an exact match is wanted we can set end=mid-1
492 * # <- mid | or start=mid+1 because we know that mid doesn't match.
493 * # |
494 * # | Eventually either end=start or end=start+1 and one of
495 * # <- end | start or end is the wanted one.
496 */
497
498 do
499 {
500 mid=(start+end)/2; /* Choose mid point */
501
502 if(strcmp(name,names[mid])>0) /* Mid point is too low */
503 start=mid+1;
504 else if(strcmp(name,names[mid])<0) /* Mid point is too high */
505 end=mid-1;
506 else /* Mid point is correct */
507 return(mid);
508 }
509 while((end-start)>1);
510
511 if(strcmp(name,names[start])==0) /* Start is correct */
512 return(start);
513
514 if(strcmp(name,names[end])==0) /* End is correct */
515 return(end);
516
517 assert(0);
518
519 return(NO_WAY);
520 }
521
522
523 /*++++++++++++++++++++++++++++++++++++++
524 Compact the list of way properties.
525
526 WaysX* waysx The set of ways to process.
527 ++++++++++++++++++++++++++++++++++++++*/
528
529 void CompactWayProperties(WaysX* waysx)
530 {
531 index_t i,j;
532 WayX wayx;
533 Way **cdata;
534 int duplicate=0;
535 int fd;
536
537 /* Print the start message for sorting properties */
538
539 printf("Sorting Ways by properties");
540 fflush(stdout);
541
542 /* Get the uncompacted data and create list for compacted */
543
544 waysx->xdata=MapFile(waysx->filename);
545
546 cdata=(Way**)malloc(waysx->number*sizeof(Way*));
547
548 assert(cdata); /* Check malloc() worked */
549
550 for(i=0;i<waysx->number;i++)
551 cdata[i]=&waysx->xdata[i].way;
552
553 /* Create the index of names, sort it and remove duplicates */
554
555 heapsort((void**)cdata,waysx->number,(int (*)(const void*,const void*))sort_by_name_and_properties);
556
557 j=0;
558 for(i=1;i<waysx->number;i++)
559 if(cdata[i-1]->name!=cdata[i]->name || WaysCompare(cdata[i-1],cdata[i]))
560 cdata[++j]=cdata[i];
561 else
562 duplicate++;
563
564 waysx->cnumber=++j;
565
566 /* Print the final message for sorting properties */
567
568 printf("\rSorted Ways by properties: Properties=%d Duplicate=%d\n",waysx->number,duplicate);
569 fflush(stdout);
570
571 /* Print the start message for compacting properties */
572
573 printf("Compacting Way properties");
574 fflush(stdout);
575
576 /* Update the on-disk image */
577
578 DeleteFile(waysx->filename);
579
580 fd=OpenFile(waysx->filename);
581 SeekFile(waysx->fd,0);
582
583 while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
584 {
585 wayx.id=index_way(cdata,waysx->cnumber,&wayx.way);
586
587 WriteFile(fd,&wayx,sizeof(WayX));
588 }
589
590 CloseFile(waysx->fd);
591 CloseFile(fd);
592
593 waysx->fd=ReOpenFile(waysx->filename);
594
595 waysx->xdata=UnmapFile(waysx->filename);
596
597 /* Print the final message for compacting properties */
598
599 printf("\rCompacted Way properties: Properties=%d Unique=%d\n",waysx->number,waysx->cnumber);
600 fflush(stdout);
601
602 free(cdata);
603 }
604
605
606 /*++++++++++++++++++++++++++++++++++++++
607 Sort the ways into name and properties order.
608
609 int sort_by_name_and_properties Returns the comparison of the name and properties fields.
610
611 Way *a The first Way.
612
613 Way *b The second Way.
614 ++++++++++++++++++++++++++++++++++++++*/
615
616 static int sort_by_name_and_properties(Way *a,Way *b)
617 {
618 index_t a_name=a->name;
619 index_t b_name=b->name;
620
621 if(a_name<b_name)
622 return(-1);
623 else if(a_name>b_name)
624 return(1);
625 else
626 return(WaysCompare(a,b));
627 }
628
629
630 /*++++++++++++++++++++++++++++++++++++++
631 Find a particular Way within the sorted list of ways.
632
633 index_t index_way Returns the index of the Way within the list.
634
635 Way **data The set of Ways to search.
636
637 int number The number of Ways.
638
639 Way *way The name to look for.
640 ++++++++++++++++++++++++++++++++++++++*/
641
642 static index_t index_way(Way** data,int number,Way *way)
643 {
644 int start=0;
645 int end=number-1;
646 int mid;
647
648 /* Binary search - search key exact match only is required.
649 *
650 * # <- start | Check mid and move start or end if it doesn't match
651 * # |
652 * # | Since an exact match is wanted we can set end=mid-1
653 * # <- mid | or start=mid+1 because we know that mid doesn't match.
654 * # |
655 * # | Eventually either end=start or end=start+1 and one of
656 * # <- end | start or end is the wanted one.
657 */
658
659 do
660 {
661 mid=(start+end)/2; /* Choose mid point */
662
663 if(way->name>data[mid]->name) /* Mid point is too low */
664 start=mid+1;
665 else if(way->name<data[mid]->name) /* Mid point is too high */
666 end=mid-1;
667 else if(WaysCompare(way,data[mid])>0) /* Mid point is too low */
668 start=mid+1;
669 else if(WaysCompare(way,data[mid])<0) /* Mid point is too high */
670 end=mid-1;
671 else /* Mid point is correct */
672 return(mid);
673 }
674 while((end-start)>1);
675
676 if(way->name==data[start]->name && !WaysCompare(way,data[start])) /* Start is correct */
677 return(start);
678
679 if(way->name==data[end]->name && !WaysCompare(way,data[end])) /* End is correct */
680 return(end);
681
682 assert(0);
683
684 return(NO_WAY);
685 }
686
687
688 /*++++++++++++++++++++++++++++++++++++++
689 Save the way list to a file.
690
691 WaysX* waysx The set of ways to save.
692
693 const char *filename The name of the file to save.
694
695 Profile *profile The profile used during parsing.
696 ++++++++++++++++++++++++++++++++++++++*/
697
698 void SaveWayList(WaysX* waysx,const char *filename,Profile *profile)
699 {
700 index_t i;
701 int fd,position=0;
702 Ways *ways;
703
704 printf("Writing Ways: Ways=0");
705 fflush(stdout);
706
707 if(!option_slim)
708 waysx->xdata=MapFile(waysx->filename);
709
710 /* Fill in a Ways structure with the offset of the real data in the file after
711 the Way structure itself. */
712
713 ways=calloc(1,sizeof(Ways));
714
715 assert(ways); /* Check calloc() worked */
716
717 ways->number=waysx->cnumber;
718 ways->onumber=waysx->number;
719
720 ways->allow=profile->allow;
721
722 ways->props=0;
723 for(i=1;i<Property_Count;i++)
724 if(profile->props_yes[i])
725 ways->props|=PROPERTIES(i);
726
727 ways->data=NULL;
728
729 ways->ways=(void*)sizeof(Ways);
730 ways->names=(void*)(sizeof(Ways)+ways->number*sizeof(Way));
731
732 /* Write out the Ways structure and then the real data. */
733
734 fd=OpenFile(filename);
735
736 WriteFile(fd,ways,sizeof(Ways));
737
738 for(i=0;i<waysx->number;i++)
739 {
740 WayX *wayx=LookupWayX(waysx,i,1);
741
742 SeekFile(fd,sizeof(Ways)+wayx->id*sizeof(Way));
743 WriteFile(fd,&wayx->way,sizeof(Way));
744
745 if(!((i+1)%10000))
746 {
747 printf("\rWriting Ways: Ways=%d",i+1);
748 fflush(stdout);
749 }
750 }
751
752 if(!option_slim)
753 waysx->xdata=UnmapFile(waysx->filename);
754
755 SeekFile(fd,sizeof(Ways)+waysx->cnumber*sizeof(Way));
756
757 SeekFile(waysx->nfd,0);
758
759 while(position<waysx->nlength)
760 {
761 int len=1024;
762 char temp[1024];
763
764 if((waysx->nlength-position)<1024)
765 len=waysx->nlength-position;
766
767 ReadFile(waysx->nfd,temp,len);
768 WriteFile(fd,temp,len);
769
770 position+=len;
771 }
772
773 CloseFile(waysx->nfd);
774
775 CloseFile(fd);
776
777 printf("\rWrote Ways: Ways=%d \n",waysx->number);
778 fflush(stdout);
779
780 /* Free the fake Ways */
781
782 free(ways);
783 }

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