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

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.2 (destination-access branch) Version 3.4.2 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