1 /***************************************
2 $Header: /home/amb/routino/src/RCS/waysx.c,v 1.52 2010/11/13 14:22:28 amb Exp $
4 Extended Way data type functions.
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008-2010 Andrew M. Bishop
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.
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.
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 ***************************************/
37 #include "functions.h"
42 /*+ The command line '--tmpdir' option or its default value. +*/
43 extern char *option_tmpdirname;
45 /*+ A temporary file-local variable for use by the sort functions. +*/
46 static WaysX *sortwaysx;
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);
54 static int deduplicate_and_index_by_id(WayX *wayx,index_t index);
57 /*++++++++++++++++++++++++++++++++++++++
58 Allocate a new way list (create a new file or open an existing one).
60 WaysX *NewWayList Returns the way list.
62 int append Set to 1 if the file is to be opened for appending (now or later).
63 ++++++++++++++++++++++++++++++++++++++*/
65 WaysX *NewWayList(int append)
69 waysx=(WaysX*)calloc(1,sizeof(WaysX));
71 assert(waysx); /* Check calloc() worked */
73 waysx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
76 sprintf(waysx->filename,"%s/waysx.input.tmp",option_tmpdirname);
78 sprintf(waysx->filename,"%s/waysx.%p.tmp",option_tmpdirname,waysx);
82 off_t size,position=0;
84 waysx->fd=OpenFileAppend(waysx->filename);
86 size=SizeFile(waysx->filename);
90 FILESORT_VARINT waysize;
92 SeekFile(waysx->fd,position);
93 ReadFile(waysx->fd,&waysize,FILESORT_VARSIZE);
96 position+=waysize+FILESORT_VARSIZE;
99 SeekFile(waysx->fd,size);
102 waysx->fd=OpenFileNew(waysx->filename);
104 waysx->nfilename=(char*)malloc(strlen(option_tmpdirname)+32);
105 sprintf(waysx->nfilename,"%s/waynames.%p.tmp",option_tmpdirname,waysx);
111 /*++++++++++++++++++++++++++++++++++++++
114 WaysX *waysx The list to be freed.
116 int keep Set to 1 if the file is to be kept.
117 ++++++++++++++++++++++++++++++++++++++*/
119 void FreeWayList(WaysX *waysx,int keep)
122 DeleteFile(waysx->filename);
124 free(waysx->filename);
129 DeleteFile(waysx->nfilename);
131 free(waysx->nfilename);
137 /*++++++++++++++++++++++++++++++++++++++
138 Append a single way to an unsorted way list.
140 WaysX* waysx The set of ways to process.
142 way_t id The ID of the way.
144 Way *way The way data itself.
146 const char *name The name or reference of the way.
147 ++++++++++++++++++++++++++++++++++++++*/
149 void AppendWay(WaysX* waysx,way_t id,Way *way,const char *name)
152 FILESORT_VARINT size;
158 size=sizeof(WayX)+strlen(name)+1;
160 WriteFile(waysx->fd,&size,FILESORT_VARSIZE);
161 WriteFile(waysx->fd,&wayx,sizeof(WayX));
162 WriteFile(waysx->fd,name,strlen(name)+1);
166 assert(!(waysx->xnumber==0)); /* Zero marks the high-water mark for ways. */
170 /*++++++++++++++++++++++++++++++++++++++
171 Sort the list of ways.
173 WaysX* waysx The set of ways to process.
174 ++++++++++++++++++++++++++++++++++++++*/
176 void SortWayList(WaysX* waysx)
180 char *names[2]={NULL,NULL};
181 int namelen[2]={0,0};
183 uint32_t lastlength=0;
185 /* Print the start message */
187 printf_first("Sorting Ways by Name");
189 /* Close the file and re-open it (finished appending) */
191 CloseFile(waysx->fd);
192 waysx->fd=ReOpenFile(waysx->filename);
194 DeleteFile(waysx->filename);
196 fd=OpenFileNew(waysx->filename);
198 /* Sort the ways to allow separating the names */
200 filesort_vary(waysx->fd,fd,(int (*)(const void*,const void*))sort_by_name_and_id,NULL);
202 /* Close the files */
204 CloseFile(waysx->fd);
207 /* Print the final message */
209 printf_last("Sorted Ways by Name: Ways=%d",waysx->xnumber);
212 /* Print the start message */
214 printf_first("Separating Way Names: Ways=0 Names=0");
218 waysx->fd=ReOpenFile(waysx->filename);
220 DeleteFile(waysx->filename);
222 fd=OpenFileNew(waysx->filename);
223 nfd=OpenFileNew(waysx->nfilename);
225 /* Copy from the single file into two files */
227 for(i=0;i<waysx->xnumber;i++)
230 FILESORT_VARINT size;
232 ReadFile(waysx->fd,&size,FILESORT_VARSIZE);
234 if(namelen[nnames%2]<size)
235 names[nnames%2]=(char*)realloc((void*)names[nnames%2],namelen[nnames%2]=size);
237 ReadFile(waysx->fd,&wayx,sizeof(WayX));
238 ReadFile(waysx->fd,names[nnames%2],size-sizeof(WayX));
240 if(nnames==0 || strcmp(names[0],names[1]))
242 WriteFile(nfd,names[nnames%2],size-sizeof(WayX));
244 lastlength=waysx->nlength;
245 waysx->nlength+=size-sizeof(WayX);
250 wayx.way.name=lastlength;
252 WriteFile(fd,&wayx,sizeof(WayX));
255 printf_middle("Separating Way Names: Ways=%d Names=%d",i+1,nnames);
258 if(names[0]) free(names[0]);
259 if(names[1]) free(names[1]);
261 /* Close the files */
263 CloseFile(waysx->fd);
266 waysx->fd=ReOpenFile(waysx->filename);
270 /* Print the final message */
272 printf_last("Separated Way Names: Ways=%d Names=%d ",waysx->xnumber,nnames);
275 /* Print the start message */
277 printf_first("Sorting Ways");
281 waysx->fd=ReOpenFile(waysx->filename);
283 DeleteFile(waysx->filename);
285 fd=OpenFileNew(waysx->filename);
287 /* Allocate the array of indexes */
289 waysx->idata=(way_t*)malloc(waysx->xnumber*sizeof(way_t));
291 assert(waysx->idata); /* Check malloc() worked */
293 /* Sort the ways by index and index them */
299 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))deduplicate_and_index_by_id);
301 /* Close the files and re-open them */
303 CloseFile(waysx->fd);
306 waysx->fd=ReOpenFile(waysx->filename);
308 /* Print the final message */
310 printf_last("Sorted Ways: Ways=%d Duplicates=%d",waysx->number,waysx->xnumber-waysx->number);
314 /*++++++++++++++++++++++++++++++++++++++
315 Compact the list of ways.
317 WaysX* waysx The set of ways to process.
318 ++++++++++++++++++++++++++++++++++++++*/
320 void CompactWayList(WaysX* waysx)
326 /* Print the start message */
328 printf_first("Sorting Ways by Properties");
330 /* Close the file and re-open it */
332 CloseFile(waysx->fd);
333 waysx->fd=ReOpenFile(waysx->filename);
335 DeleteFile(waysx->filename);
337 fd=OpenFileNew(waysx->filename);
339 /* Sort the ways to allow compacting according to he properties */
341 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_name_and_prop_and_id,NULL);
343 /* Close the files */
345 CloseFile(waysx->fd);
348 /* Print the final message */
350 printf_last("Sorted Ways by Properties: Ways=%d",waysx->number);
353 /* Print the start message */
355 printf_first("Compacting Ways: Ways=0 Properties=0");
359 waysx->fd=ReOpenFile(waysx->filename);
361 DeleteFile(waysx->filename);
363 fd=OpenFileNew(waysx->filename);
365 /* Update the way as we go using the sorted index */
369 for(i=0;i<waysx->number;i++)
373 ReadFile(waysx->fd,&wayx,sizeof(WayX));
375 if(waysx->cnumber==0 || wayx.way.name!=lastway.name || WaysCompare(&lastway,&wayx.way))
382 wayx.prop=waysx->cnumber-1;
384 WriteFile(fd,&wayx,sizeof(WayX));
387 printf_middle("Compacting Ways: Ways=%d Properties=%d",i+1,waysx->cnumber);
390 /* Close the files */
392 CloseFile(waysx->fd);
395 /* Print the final message */
397 printf_last("Compacted Ways: Ways=%d Properties=%d ",waysx->number,waysx->cnumber);
400 /* Print the start message */
402 printf_first("Sorting Ways");
406 waysx->fd=ReOpenFile(waysx->filename);
408 DeleteFile(waysx->filename);
410 fd=OpenFileNew(waysx->filename);
412 /* Sort the ways by index */
414 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_id,NULL);
416 /* Close the files and re-open them */
418 CloseFile(waysx->fd);
421 waysx->fd=ReOpenFile(waysx->filename);
423 /* Print the final message */
425 printf_last("Sorted Ways: Ways=%d",waysx->number);
429 /*++++++++++++++++++++++++++++++++++++++
430 Sort the ways into id order.
432 int sort_by_id Returns the comparison of the id fields.
434 WayX *a The first extended way.
436 WayX *b The second extended way.
437 ++++++++++++++++++++++++++++++++++++++*/
439 static int sort_by_id(WayX *a,WayX *b)
453 /*++++++++++++++++++++++++++++++++++++++
454 Sort the ways into name and id order.
456 int sort_by_name_and_id Returns the comparison of the name and id fields.
458 WayX *a The first extended Way.
460 WayX *b The second extended Way.
461 ++++++++++++++++++++++++++++++++++++++*/
463 static int sort_by_name_and_id(WayX *a,WayX *b)
466 char *a_name=(char*)a+sizeof(WayX);
467 char *b_name=(char*)b+sizeof(WayX);
469 compare=strcmp(a_name,b_name);
474 return(sort_by_id(a,b));
478 /*++++++++++++++++++++++++++++++++++++++
479 Sort the ways into name, properties and id order.
481 int sort_by_name_and_prop_and_id Returns the comparison of the name, properties and id fields.
483 WayX *a The first extended Way.
485 WayX *b The second extended Way.
486 ++++++++++++++++++++++++++++++++++++++*/
488 static int sort_by_name_and_prop_and_id(WayX *a,WayX *b)
491 index_t a_name=a->way.name;
492 index_t b_name=b->way.name;
496 else if(a_name>b_name)
499 compare=WaysCompare(&a->way,&b->way);
504 return(sort_by_id(a,b));
508 /*++++++++++++++++++++++++++++++++++++++
509 Deduplicate the extended ways using the id after sorting and create the index.
511 int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise zero.
513 WayX *wayx The extended way.
515 index_t index The index of this way in the total.
516 ++++++++++++++++++++++++++++++++++++++*/
518 static int deduplicate_and_index_by_id(WayX *wayx,index_t index)
522 if(index==0 || wayx->id!=previd)
528 sortwaysx->idata[index]=wayx->id;
537 /*++++++++++++++++++++++++++++++++++++++
538 Find a particular way index.
540 index_t IndexWayX Returns the index of the extended way with the specified id.
542 WaysX* waysx The set of ways to process.
544 way_t id The way id to look for.
545 ++++++++++++++++++++++++++++++++++++++*/
547 index_t IndexWayX(WaysX* waysx,way_t id)
550 int end=waysx->number-1;
553 /* Binary search - search key exact match only is required.
555 * # <- start | Check mid and move start or end if it doesn't match
557 * # | Since an exact match is wanted we can set end=mid-1
558 * # <- mid | or start=mid+1 because we know that mid doesn't match.
560 * # | Eventually either end=start or end=start+1 and one of
561 * # <- end | start or end is the wanted one.
564 if(end<start) /* There are no ways */
566 else if(id<waysx->idata[start]) /* Check key is not before start */
568 else if(id>waysx->idata[end]) /* Check key is not after end */
574 mid=(start+end)/2; /* Choose mid point */
576 if(waysx->idata[mid]<id) /* Mid point is too low */
578 else if(waysx->idata[mid]>id) /* Mid point is too high */
580 else /* Mid point is correct */
583 while((end-start)>1);
585 if(waysx->idata[start]==id) /* Start is correct */
588 if(waysx->idata[end]==id) /* End is correct */
596 /*++++++++++++++++++++++++++++++++++++++
597 Save the way list to a file.
599 WaysX* waysx The set of ways to save.
601 const char *filename The name of the file to save.
602 ++++++++++++++++++++++++++++++++++++++*/
604 void SaveWayList(WaysX* waysx,const char *filename)
609 WaysFile waysfile={0};
613 /* Print the start message */
615 printf_first("Writing Ways: Ways=0");
617 /* Map into memory */
620 waysx->xdata=MapFile(waysx->filename);
623 /* Write out the ways data */
625 fd=OpenFileNew(filename);
627 SeekFile(fd,sizeof(WaysFile));
629 for(i=0;i<waysx->number;i++)
631 WayX *wayx=LookupWayX(waysx,i,1);
633 allow|=wayx->way.allow;
634 props|=wayx->way.props;
636 SeekFile(fd,sizeof(WaysFile)+(off_t)wayx->prop*sizeof(Way));
637 WriteFile(fd,&wayx->way,sizeof(Way));
640 printf_middle("Writing Ways: Ways=%d",i+1);
643 /* Unmap from memory */
646 waysx->xdata=UnmapFile(waysx->filename);
649 /* Write out the ways names */
651 SeekFile(fd,sizeof(WaysFile)+(off_t)waysx->cnumber*sizeof(Way));
653 nfd=ReOpenFile(waysx->nfilename);
655 while(position<waysx->nlength)
660 if((waysx->nlength-position)<1024)
661 len=waysx->nlength-position;
663 ReadFile(nfd,temp,len);
664 WriteFile(fd,temp,len);
671 /* Write out the header structure */
673 waysfile.number=waysx->cnumber;
674 waysfile.onumber=waysx->number;
676 waysfile.allow=allow;
677 waysfile.props=props;
680 WriteFile(fd,&waysfile,sizeof(WaysFile));
684 /* Print the final message */
686 printf_last("Wrote Ways: Ways=%d",waysx->number);