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

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.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