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

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