Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Annotation of /trunk/src/waysx.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 466 - (hide annotations) (download) (as text)
Sat Jul 31 14:56:17 2010 UTC (14 years, 7 months ago) by amb
File MIME type: text/x-csrc
File size: 12803 byte(s)
Assert if the number of nodes, segments or ways exceeds the legal range of the
index counters.

1 amb 110 /***************************************
2 amb 466 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.47 2010-07-31 14:56:17 amb Exp $
3 amb 110
4     Extended Way data type functions.
5 amb 151
6     Part of the Routino routing software.
7 amb 110 ******************/ /******************
8 amb 326 This file Copyright 2008-2010 Andrew M. Bishop
9 amb 110
10 amb 151 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 amb 110 ***************************************/
23    
24    
25     #include <assert.h>
26     #include <stdlib.h>
27 amb 449 #include <stdio.h>
28 amb 110 #include <string.h>
29 amb 326 #include <sys/stat.h>
30 amb 110
31 amb 228 #include "ways.h"
32 amb 110
33 amb 449 #include "waysx.h"
34 amb 110
35 amb 449 #include "files.h"
36     #include "functions.h"
37    
38    
39 amb 262 /* Variables */
40 amb 110
41 amb 289 /*+ The command line '--tmpdir' option or its default value. +*/
42 amb 284 extern char *option_tmpdirname;
43 amb 110
44 amb 284 /*+ A temporary file-local variable for use by the sort functions. +*/
45     static WaysX *sortwaysx;
46    
47 amb 110 /* Functions */
48    
49 amb 310 static int sort_by_name_and_prop_and_id(WayX *a,WayX *b);
50     static int deduplicate_by_id(WayX *wayx,index_t index);
51    
52 amb 272 static int sort_by_id(WayX *a,WayX *b);
53     static int index_by_id(WayX *wayx,index_t index);
54    
55 amb 110
56     /*++++++++++++++++++++++++++++++++++++++
57 amb 326 Allocate a new way list (create a new file or open an existing one).
58 amb 110
59     WaysX *NewWayList Returns the way list.
60 amb 326
61     int append Set to 1 if the file is to be opened for appending (now or later).
62 amb 110 ++++++++++++++++++++++++++++++++++++++*/
63    
64 amb 326 WaysX *NewWayList(int append)
65 amb 110 {
66     WaysX *waysx;
67    
68 amb 213 waysx=(WaysX*)calloc(1,sizeof(WaysX));
69 amb 110
70 amb 243 assert(waysx); /* Check calloc() worked */
71    
72 amb 284 waysx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
73 amb 216
74 amb 326 if(append)
75 amb 447 sprintf(waysx->filename,"%s/waysx.input.tmp",option_tmpdirname);
76 amb 326 else
77 amb 447 sprintf(waysx->filename,"%s/waysx.%p.tmp",option_tmpdirname,waysx);
78 amb 262
79 amb 326 if(append)
80     {
81 amb 331 off_t size,position=0;
82 amb 326
83     waysx->fd=AppendFile(waysx->filename);
84    
85 amb 331 size=SizeFile(waysx->filename);
86 amb 326
87 amb 331 while(position<size)
88 amb 326 {
89 amb 331 FILESORT_VARINT waysize;
90 amb 326
91     SeekFile(waysx->fd,position);
92 amb 331 ReadFile(waysx->fd,&waysize,FILESORT_VARSIZE);
93 amb 326
94     waysx->xnumber++;
95 amb 331 position+=waysize+FILESORT_VARSIZE;
96 amb 326 }
97    
98 amb 331 SeekFile(waysx->fd,size);
99 amb 326 }
100     else
101     waysx->fd=OpenFile(waysx->filename);
102    
103 amb 284 waysx->nfilename=(char*)malloc(strlen(option_tmpdirname)+32);
104     sprintf(waysx->nfilename,"%s/waynames.%p.tmp",option_tmpdirname,waysx);
105 amb 262
106 amb 110 return(waysx);
107     }
108    
109    
110     /*++++++++++++++++++++++++++++++++++++++
111 amb 226 Free a way list.
112    
113     WaysX *waysx The list to be freed.
114 amb 326
115     int keep Set to 1 if the file is to be kept.
116 amb 226 ++++++++++++++++++++++++++++++++++++++*/
117    
118 amb 326 void FreeWayList(WaysX *waysx,int keep)
119 amb 226 {
120 amb 326 if(!keep)
121     DeleteFile(waysx->filename);
122    
123 amb 283 free(waysx->filename);
124 amb 262
125 amb 226 if(waysx->idata)
126     free(waysx->idata);
127    
128 amb 262 DeleteFile(waysx->nfilename);
129 amb 326
130 amb 283 free(waysx->nfilename);
131 amb 226
132     free(waysx);
133     }
134    
135    
136     /*++++++++++++++++++++++++++++++++++++++
137 amb 262 Append a way to a way list.
138 amb 203
139 amb 262 void AppendWay Returns the newly appended way.
140 amb 243
141 amb 262 WaysX* waysx The set of ways to process.
142 amb 110
143 amb 262 way_t id The ID of the way.
144 amb 110
145 amb 262 Way *way The way data itself.
146 amb 110
147 amb 262 const char *name The name or reference of the way.
148     ++++++++++++++++++++++++++++++++++++++*/
149 amb 110
150 amb 262 void AppendWay(WaysX* waysx,way_t id,Way *way,const char *name)
151     {
152     WayX wayx;
153 amb 311 FILESORT_VARINT size;
154 amb 110
155 amb 262 wayx.id=id;
156 amb 310 wayx.prop=0;
157 amb 262 wayx.way=*way;
158    
159 amb 310 size=sizeof(WayX)+strlen(name)+1;
160    
161 amb 311 WriteFile(waysx->fd,&size,FILESORT_VARSIZE);
162 amb 262 WriteFile(waysx->fd,&wayx,sizeof(WayX));
163 amb 310 WriteFile(waysx->fd,name,strlen(name)+1);
164 amb 262
165     waysx->xnumber++;
166 amb 466
167     assert(!(waysx->xnumber==0)); /* Zero marks the high-water mark for ways. */
168 amb 110 }
169    
170    
171     /*++++++++++++++++++++++++++++++++++++++
172 amb 224 Sort the list of ways.
173 amb 110
174     WaysX* waysx The set of ways to process.
175     ++++++++++++++++++++++++++++++++++++++*/
176    
177     void SortWayList(WaysX* waysx)
178     {
179 amb 310 index_t i;
180     int fd,nfd;
181     char *names[2]={NULL,NULL};
182     int namelen[2]={0,0};
183     int nnames=0,nprops=0;
184     uint32_t lastlength=0;
185     Way lastway;
186 amb 110
187 amb 266 /* Print the start message */
188    
189 amb 227 printf("Sorting Ways");
190     fflush(stdout);
191 amb 110
192 amb 310 /* Close the file and re-open it (finished appending) */
193 amb 203
194 amb 262 CloseFile(waysx->fd);
195     waysx->fd=ReOpenFile(waysx->filename);
196 amb 216
197 amb 310 DeleteFile(waysx->filename);
198 amb 262
199 amb 310 fd=OpenFile(waysx->filename);
200    
201     /* Sort the ways to allow compacting them and remove duplicates */
202    
203     sortwaysx=waysx;
204    
205 amb 311 filesort_vary(waysx->fd,fd,(int (*)(const void*,const void*))sort_by_name_and_prop_and_id,(int (*)(void*,index_t))deduplicate_by_id);
206 amb 310
207     /* Close the files */
208    
209     CloseFile(waysx->fd);
210     CloseFile(fd);
211    
212     /* Print the final message */
213    
214     printf("\rSorted Ways: Ways=%d Duplicates=%d\n",waysx->xnumber,waysx->xnumber-waysx->number);
215     fflush(stdout);
216    
217    
218     /* Print the start message */
219    
220     printf("Compacting Ways: Ways=0 Names=0 Properties=0");
221     fflush(stdout);
222    
223     /* Open the files */
224    
225     waysx->fd=ReOpenFile(waysx->filename);
226    
227 amb 272 DeleteFile(waysx->filename);
228 amb 262
229 amb 272 fd=OpenFile(waysx->filename);
230 amb 310 nfd=OpenFile(waysx->nfilename);
231 amb 272
232 amb 310 /* Copy from the single file into two files and index as we go. */
233    
234     for(i=0;i<waysx->number;i++)
235     {
236     WayX wayx;
237 amb 311 FILESORT_VARINT size;
238 amb 310
239 amb 311 ReadFile(waysx->fd,&size,FILESORT_VARSIZE);
240 amb 310
241     if(namelen[nnames%2]<size)
242     names[nnames%2]=(char*)realloc((void*)names[nnames%2],namelen[nnames%2]=size);
243    
244     ReadFile(waysx->fd,&wayx,sizeof(WayX));
245     ReadFile(waysx->fd,names[nnames%2],size-sizeof(WayX));
246    
247     if(nnames==0 || strcmp(names[0],names[1]))
248     {
249     WriteFile(nfd,names[nnames%2],size-sizeof(WayX));
250    
251     lastlength=waysx->nlength;
252     waysx->nlength+=size-sizeof(WayX);
253    
254     nnames++;
255     }
256    
257     wayx.way.name=lastlength;
258    
259     if(nprops==0 || wayx.way.name!=lastway.name || WaysCompare(&lastway,&wayx.way))
260     {
261     lastway=wayx.way;
262    
263     waysx->cnumber++;
264    
265     nprops++;
266     }
267    
268     wayx.prop=nprops-1;
269    
270     WriteFile(fd,&wayx,sizeof(WayX));
271    
272     if(!((i+1)%10000))
273     {
274     printf("\rCompacting Ways: Ways=%d Names=%d Properties=%d",i+1,nnames,nprops);
275     fflush(stdout);
276     }
277     }
278    
279     if(names[0]) free(names[0]);
280     if(names[1]) free(names[1]);
281    
282     /* Close the files */
283    
284     CloseFile(waysx->fd);
285     CloseFile(fd);
286    
287     waysx->fd=ReOpenFile(waysx->filename);
288    
289     CloseFile(nfd);
290    
291     /* Print the final message */
292    
293     printf("\rCompacted Ways: Ways=%d Names=%d Properties=%d \n",waysx->number,nnames,nprops);
294     fflush(stdout);
295    
296    
297     /* Print the start message */
298    
299     printf("Sorting Ways");
300     fflush(stdout);
301    
302     /* Open the files */
303    
304     waysx->fd=ReOpenFile(waysx->filename);
305    
306     DeleteFile(waysx->filename);
307    
308     fd=OpenFile(waysx->filename);
309    
310 amb 272 /* Allocate the array of indexes */
311    
312 amb 310 waysx->idata=(way_t*)malloc(waysx->number*sizeof(way_t));
313 amb 262
314 amb 243 assert(waysx->idata); /* Check malloc() worked */
315    
316 amb 310 /* Sort the ways by index and index them */
317 amb 203
318 amb 272 sortwaysx=waysx;
319 amb 215
320 amb 311 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))index_by_id);
321 amb 215
322 amb 262 /* Close the files and re-open them */
323    
324     CloseFile(waysx->fd);
325     CloseFile(fd);
326    
327     waysx->fd=ReOpenFile(waysx->filename);
328    
329 amb 266 /* Print the final message */
330    
331 amb 310 printf("\rSorted Ways: Ways=%d\n",waysx->number);
332 amb 227 fflush(stdout);
333 amb 224 }
334    
335    
336     /*++++++++++++++++++++++++++++++++++++++
337 amb 262 Sort the ways into id order.
338 amb 224
339 amb 262 int sort_by_id Returns the comparison of the id fields.
340    
341 amb 272 WayX *a The first extended way.
342 amb 262
343 amb 272 WayX *b The second extended way.
344 amb 262 ++++++++++++++++++++++++++++++++++++++*/
345    
346 amb 272 static int sort_by_id(WayX *a,WayX *b)
347 amb 262 {
348 amb 272 way_t a_id=a->id;
349     way_t b_id=b->id;
350 amb 262
351     if(a_id<b_id)
352     return(-1);
353     else if(a_id>b_id)
354     return(1);
355     else
356     return(0);
357     }
358    
359    
360     /*++++++++++++++++++++++++++++++++++++++
361 amb 310 Sort the ways into name, properties and id order.
362 amb 272
363 amb 310 int sort_by_name_and_prop_and_id Returns the comparison of the name, properties and id fields.
364 amb 272
365 amb 310 WayX *a The first extended Way.
366    
367     WayX *b The second extended Way.
368     ++++++++++++++++++++++++++++++++++++++*/
369    
370     static int sort_by_name_and_prop_and_id(WayX *a,WayX *b)
371     {
372     int compare;
373     char *a_name=(char*)a+sizeof(WayX);
374     char *b_name=(char*)b+sizeof(WayX);
375    
376     compare=strcmp(a_name,b_name);
377    
378     if(compare)
379     return(compare);
380    
381     compare=WaysCompare(&a->way,&b->way);
382    
383     if(compare)
384     return(compare);
385    
386     return(sort_by_id(a,b));
387     }
388    
389    
390     /*++++++++++++++++++++++++++++++++++++++
391     Deduplicate the extended ways using the id after sorting.
392    
393     int deduplicate_by_id Return 1 if the value is to be kept, otherwise zero.
394    
395 amb 272 WayX *wayx The extended way.
396    
397     index_t index The index of this way in the total.
398     ++++++++++++++++++++++++++++++++++++++*/
399    
400 amb 310 static int deduplicate_by_id(WayX *wayx,index_t index)
401 amb 272 {
402 amb 310 static way_t previd;
403    
404     if(index==0 || wayx->id!=previd)
405 amb 272 {
406 amb 310 previd=wayx->id;
407 amb 272
408     sortwaysx->number++;
409    
410     return(1);
411     }
412    
413     return(0);
414     }
415    
416    
417     /*++++++++++++++++++++++++++++++++++++++
418 amb 310 Index the ways after sorting.
419    
420     int index_by_id Return 1 if the value is to be kept, otherwise zero.
421    
422     WayX *wayx The extended way.
423    
424     index_t index The index of this way in the total.
425     ++++++++++++++++++++++++++++++++++++++*/
426    
427     static int index_by_id(WayX *wayx,index_t index)
428     {
429     sortwaysx->idata[index]=wayx->id;
430    
431     return(1);
432     }
433    
434    
435     /*++++++++++++++++++++++++++++++++++++++
436 amb 285 Find a particular way index.
437    
438     index_t IndexWayX Returns the index of the extended way with the specified id.
439    
440     WaysX* waysx The set of ways to process.
441    
442     way_t id The way id to look for.
443     ++++++++++++++++++++++++++++++++++++++*/
444    
445     index_t IndexWayX(WaysX* waysx,way_t id)
446     {
447     int start=0;
448     int end=waysx->number-1;
449     int mid;
450    
451     /* Binary search - search key exact match only is required.
452     *
453     * # <- start | Check mid and move start or end if it doesn't match
454     * # |
455     * # | Since an exact match is wanted we can set end=mid-1
456     * # <- mid | or start=mid+1 because we know that mid doesn't match.
457     * # |
458     * # | Eventually either end=start or end=start+1 and one of
459     * # <- end | start or end is the wanted one.
460     */
461    
462     if(end<start) /* There are no ways */
463     return(NO_WAY);
464     else if(id<waysx->idata[start]) /* Check key is not before start */
465     return(NO_WAY);
466     else if(id>waysx->idata[end]) /* Check key is not after end */
467     return(NO_WAY);
468     else
469     {
470     do
471     {
472     mid=(start+end)/2; /* Choose mid point */
473    
474     if(waysx->idata[mid]<id) /* Mid point is too low */
475     start=mid+1;
476     else if(waysx->idata[mid]>id) /* Mid point is too high */
477     end=mid-1;
478     else /* Mid point is correct */
479     return(mid);
480     }
481     while((end-start)>1);
482    
483     if(waysx->idata[start]==id) /* Start is correct */
484     return(start);
485    
486     if(waysx->idata[end]==id) /* End is correct */
487     return(end);
488     }
489    
490     return(NO_WAY);
491     }
492    
493    
494     /*++++++++++++++++++++++++++++++++++++++
495     Save the way list to a file.
496    
497     WaysX* waysx The set of ways to save.
498    
499     const char *filename The name of the file to save.
500     ++++++++++++++++++++++++++++++++++++++*/
501    
502 amb 398 void SaveWayList(WaysX* waysx,const char *filename)
503 amb 285 {
504     index_t i;
505 amb 310 int fd,nfd;
506     int position=0;
507 amb 461 WaysFile waysfile;
508     wayallow_t allow=0;
509     wayprop_t props=0;
510 amb 285
511 amb 461 /* Print the start message */
512    
513 amb 285 printf("Writing Ways: Ways=0");
514     fflush(stdout);
515    
516 amb 461 /* Map into memory */
517    
518 amb 452 #if !SLIM
519     waysx->xdata=MapFile(waysx->filename);
520     #endif
521 amb 285
522 amb 461 /* Write out the ways data */
523 amb 285
524 amb 461 fd=OpenFile(filename);
525 amb 285
526 amb 461 SeekFile(fd,sizeof(WaysFile));
527 amb 285
528     for(i=0;i<waysx->number;i++)
529     {
530 amb 309 WayX *wayx=LookupWayX(waysx,i,1);
531 amb 285
532 amb 461 allow|=wayx->way.allow;
533     props|=wayx->way.props;
534 amb 398
535 amb 464 SeekFile(fd,sizeof(WaysFile)+(off_t)wayx->prop*sizeof(Way));
536 amb 309 WriteFile(fd,&wayx->way,sizeof(Way));
537    
538 amb 285 if(!((i+1)%10000))
539     {
540     printf("\rWriting Ways: Ways=%d",i+1);
541     fflush(stdout);
542     }
543     }
544    
545 amb 461 /* Unmap from memory */
546 amb 398
547 amb 452 #if !SLIM
548     waysx->xdata=UnmapFile(waysx->filename);
549     #endif
550 amb 285
551 amb 461 /* Write out the ways names */
552 amb 285
553 amb 464 SeekFile(fd,sizeof(WaysFile)+(off_t)waysx->cnumber*sizeof(Way));
554 amb 461
555 amb 310 nfd=ReOpenFile(waysx->nfilename);
556 amb 285
557 amb 309 while(position<waysx->nlength)
558     {
559     int len=1024;
560     char temp[1024];
561    
562     if((waysx->nlength-position)<1024)
563     len=waysx->nlength-position;
564    
565 amb 310 ReadFile(nfd,temp,len);
566 amb 309 WriteFile(fd,temp,len);
567    
568     position+=len;
569     }
570    
571 amb 310 CloseFile(nfd);
572 amb 309
573 amb 461 /* Write out the header structure */
574    
575     waysfile.number=waysx->cnumber;
576     waysfile.onumber=waysx->number;
577    
578     waysfile.allow=allow;
579     waysfile.props=props;
580    
581     SeekFile(fd,0);
582     WriteFile(fd,&waysfile,sizeof(WaysFile));
583    
584 amb 285 CloseFile(fd);
585    
586 amb 461 /* Print the final message */
587    
588 amb 285 printf("\rWrote Ways: Ways=%d \n",waysx->number);
589     fflush(stdout);
590     }

Properties

Name Value
cvs:description Extended ways functions.