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

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