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

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