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 612 - (show annotations) (download) (as text)
Sat Jan 29 19:23:15 2011 UTC (14 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 15145 byte(s) 
Ensure that record of closed file descriptors are erased.
1 /***************************************
2 Extended Way data type functions.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2008-2011 Andrew M. Bishop
7
8 This program is free software: you can redistribute it and/or modify
9 it under the terms of the GNU Affero General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU Affero General Public License for more details.
17
18 You should have received a copy of the GNU Affero General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>.
20 ***************************************/
21
22
23 #include <assert.h>
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <string.h>
27 #include <sys/stat.h>
28
29 #include "ways.h"
30
31 #include "waysx.h"
32
33 #include "files.h"
34 #include "logging.h"
35 #include "sorting.h"
36
37
38 /* Variables */
39
40 /*+ The command line '--tmpdir' option or its default value. +*/
41 extern char *option_tmpdirname;
42
43 /*+ A temporary file-local variable for use by the sort functions. +*/
44 static WaysX *sortwaysx;
45
46 /* Functions */
47
48 static int sort_by_id(WayX *a,WayX *b);
49 static int sort_by_name_and_id(WayX *a,WayX *b);
50 static int sort_by_name_and_prop_and_id(WayX *a,WayX *b);
51
52 static int deduplicate_and_index_by_id(WayX *wayx,index_t index);
53
54
55 /*++++++++++++++++++++++++++++++++++++++
56 Allocate a new way list (create a new file or open an existing one).
57
58 WaysX *NewWayList Returns the way list.
59
60 int append Set to 1 if the file is to be opened for appending (now or later).
61 ++++++++++++++++++++++++++++++++++++++*/
62
63 WaysX *NewWayList(int append)
64 {
65 WaysX *waysx;
66
67 waysx=(WaysX*)calloc(1,sizeof(WaysX));
68
69 assert(waysx); /* Check calloc() worked */
70
71 waysx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
72
73 if(append)
74 sprintf(waysx->filename,"%s/waysx.input.tmp",option_tmpdirname);
75 else
76 sprintf(waysx->filename,"%s/waysx.%p.tmp",option_tmpdirname,waysx);
77
78 if(append)
79 {
80 off_t size,position=0;
81
82 waysx->fd=OpenFileAppend(waysx->filename);
83
84 size=SizeFile(waysx->filename);
85
86 while(position<size)
87 {
88 FILESORT_VARINT waysize;
89
90 SeekFile(waysx->fd,position);
91 ReadFile(waysx->fd,&waysize,FILESORT_VARSIZE);
92
93 waysx->xnumber++;
94 position+=waysize+FILESORT_VARSIZE;
95 }
96
97 SeekFile(waysx->fd,size);
98 }
99 else
100 waysx->fd=OpenFileNew(waysx->filename);
101
102 waysx->nfilename=(char*)malloc(strlen(option_tmpdirname)+32);
103 sprintf(waysx->nfilename,"%s/waynames.%p.tmp",option_tmpdirname,waysx);
104
105 return(waysx);
106 }
107
108
109 /*++++++++++++++++++++++++++++++++++++++
110 Free a way list.
111
112 WaysX *waysx The list to be freed.
113
114 int keep Set to 1 if the file is to be kept.
115 ++++++++++++++++++++++++++++++++++++++*/
116
117 void FreeWayList(WaysX *waysx,int keep)
118 {
119 if(!keep)
120 DeleteFile(waysx->filename);
121
122 free(waysx->filename);
123
124 if(waysx->idata)
125 free(waysx->idata);
126
127 DeleteFile(waysx->nfilename);
128
129 free(waysx->nfilename);
130
131 free(waysx);
132 }
133
134
135 /*++++++++++++++++++++++++++++++++++++++
136 Append a single way to an unsorted way list.
137
138 WaysX* waysx The set of ways to process.
139
140 way_t id The ID of the way.
141
142 Way *way The way data itself.
143
144 const char *name The name or reference of the way.
145 ++++++++++++++++++++++++++++++++++++++*/
146
147 void AppendWay(WaysX* waysx,way_t id,Way *way,const char *name)
148 {
149 WayX wayx;
150 FILESORT_VARINT size;
151
152 wayx.id=id;
153 wayx.prop=0;
154 wayx.way=*way;
155
156 size=sizeof(WayX)+strlen(name)+1;
157
158 WriteFile(waysx->fd,&size,FILESORT_VARSIZE);
159 WriteFile(waysx->fd,&wayx,sizeof(WayX));
160 WriteFile(waysx->fd,name,strlen(name)+1);
161
162 waysx->xnumber++;
163
164 assert(!(waysx->xnumber==0)); /* Zero marks the high-water mark for ways. */
165 }
166
167
168 /*++++++++++++++++++++++++++++++++++++++
169 Sort the list of ways.
170
171 WaysX* waysx The set of ways to process.
172 ++++++++++++++++++++++++++++++++++++++*/
173
174 void SortWayList(WaysX* waysx)
175 {
176 index_t i;
177 int fd;
178 char *names[2]={NULL,NULL};
179 int namelen[2]={0,0};
180 int nnames=0;
181 uint32_t lastlength=0;
182
183 /* Print the start message */
184
185 printf_first("Sorting Ways by Name");
186
187 /* Close the file (finished appending) */
188
189 waysx->fd=CloseFile(waysx->fd);
190
191 /* Re-open the file read-only and a new file writeable */
192
193 waysx->fd=ReOpenFile(waysx->filename);
194
195 DeleteFile(waysx->filename);
196
197 fd=OpenFileNew(waysx->filename);
198
199 /* Sort the ways to allow separating the names */
200
201 filesort_vary(waysx->fd,fd,(int (*)(const void*,const void*))sort_by_name_and_id,NULL);
202
203 /* Close the files */
204
205 waysx->fd=CloseFile(waysx->fd);
206 CloseFile(fd);
207
208 /* Print the final message */
209
210 printf_last("Sorted Ways by Name: Ways=%d",waysx->xnumber);
211
212
213 /* Print the start message */
214
215 printf_first("Separating Way Names: Ways=0 Names=0");
216
217 /* Re-open the file read-only and new files writeable */
218
219 waysx->fd=ReOpenFile(waysx->filename);
220
221 DeleteFile(waysx->filename);
222
223 fd=OpenFileNew(waysx->filename);
224
225 waysx->nfd=OpenFileNew(waysx->nfilename);
226
227 /* Copy from the single file into two files */
228
229 for(i=0;i<waysx->xnumber;i++)
230 {
231 WayX wayx;
232 FILESORT_VARINT size;
233
234 ReadFile(waysx->fd,&size,FILESORT_VARSIZE);
235
236 if(namelen[nnames%2]<size)
237 names[nnames%2]=(char*)realloc((void*)names[nnames%2],namelen[nnames%2]=size);
238
239 ReadFile(waysx->fd,&wayx,sizeof(WayX));
240 ReadFile(waysx->fd,names[nnames%2],size-sizeof(WayX));
241
242 if(nnames==0 || strcmp(names[0],names[1]))
243 {
244 WriteFile(waysx->nfd,names[nnames%2],size-sizeof(WayX));
245
246 lastlength=waysx->nlength;
247 waysx->nlength+=size-sizeof(WayX);
248
249 nnames++;
250 }
251
252 wayx.way.name=lastlength;
253
254 WriteFile(fd,&wayx,sizeof(WayX));
255
256 if(!((i+1)%10000))
257 printf_middle("Separating Way Names: Ways=%d Names=%d",i+1,nnames);
258 }
259
260 if(names[0]) free(names[0]);
261 if(names[1]) free(names[1]);
262
263 /* Close the files */
264
265 waysx->fd=CloseFile(waysx->fd);
266 CloseFile(fd);
267
268 waysx->nfd=CloseFile(waysx->nfd);
269
270 /* Print the final message */
271
272 printf_last("Separated Way Names: Ways=%d Names=%d ",waysx->xnumber,nnames);
273
274
275 /* Print the start message */
276
277 printf_first("Sorting Ways");
278
279 /* Re-open the file read-only and a new file writeable */
280
281 waysx->fd=ReOpenFile(waysx->filename);
282
283 DeleteFile(waysx->filename);
284
285 fd=OpenFileNew(waysx->filename);
286
287 /* Allocate the array of indexes */
288
289 waysx->idata=(way_t*)malloc(waysx->xnumber*sizeof(way_t));
290
291 assert(waysx->idata); /* Check malloc() worked */
292
293 /* Sort the ways by index and index them */
294
295 waysx->number=0;
296
297 sortwaysx=waysx;
298
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);
300
301 /* Close the files */
302
303 waysx->fd=CloseFile(waysx->fd);
304 CloseFile(fd);
305
306 /* Print the final message */
307
308 printf_last("Sorted Ways: Ways=%d Duplicates=%d",waysx->number,waysx->xnumber-waysx->number);
309 }
310
311
312 /*++++++++++++++++++++++++++++++++++++++
313 Compact the list of ways.
314
315 WaysX* waysx The set of ways to process.
316 ++++++++++++++++++++++++++++++++++++++*/
317
318 void CompactWayList(WaysX* waysx)
319 {
320 index_t i;
321 int fd;
322 Way lastway;
323
324 /* Print the start message */
325
326 printf_first("Sorting Ways by Properties");
327
328 /* Re-open the file read-only and a new file writeable */
329
330 waysx->fd=ReOpenFile(waysx->filename);
331
332 DeleteFile(waysx->filename);
333
334 fd=OpenFileNew(waysx->filename);
335
336 /* Sort the ways to allow compacting according to he properties */
337
338 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_name_and_prop_and_id,NULL);
339
340 /* Close the files */
341
342 waysx->fd=CloseFile(waysx->fd);
343 CloseFile(fd);
344
345 /* Print the final message */
346
347 printf_last("Sorted Ways by Properties: Ways=%d",waysx->number);
348
349
350 /* Print the start message */
351
352 printf_first("Compacting Ways: Ways=0 Properties=0");
353
354 /* Re-open the file read-only and a new file writeable */
355
356 waysx->fd=ReOpenFile(waysx->filename);
357
358 DeleteFile(waysx->filename);
359
360 fd=OpenFileNew(waysx->filename);
361
362 /* Update the way as we go using the sorted index */
363
364 waysx->cnumber=0;
365
366 for(i=0;i<waysx->number;i++)
367 {
368 WayX wayx;
369
370 ReadFile(waysx->fd,&wayx,sizeof(WayX));
371
372 if(waysx->cnumber==0 || wayx.way.name!=lastway.name || WaysCompare(&lastway,&wayx.way))
373 {
374 lastway=wayx.way;
375
376 waysx->cnumber++;
377 }
378
379 wayx.prop=waysx->cnumber-1;
380
381 WriteFile(fd,&wayx,sizeof(WayX));
382
383 if(!((i+1)%10000))
384 printf_middle("Compacting Ways: Ways=%d Properties=%d",i+1,waysx->cnumber);
385 }
386
387 /* Close the files */
388
389 waysx->fd=CloseFile(waysx->fd);
390 CloseFile(fd);
391
392 /* Print the final message */
393
394 printf_last("Compacted Ways: Ways=%d Properties=%d ",waysx->number,waysx->cnumber);
395
396
397 /* Print the start message */
398
399 printf_first("Sorting Ways");
400
401 /* Re-open the file read-only and a new file writeable */
402
403 waysx->fd=ReOpenFile(waysx->filename);
404
405 DeleteFile(waysx->filename);
406
407 fd=OpenFileNew(waysx->filename);
408
409 /* Sort the ways by index */
410
411 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_id,NULL);
412
413 /* Close the files */
414
415 waysx->fd=CloseFile(waysx->fd);
416 CloseFile(fd);
417
418 /* Print the final message */
419
420 printf_last("Sorted Ways: Ways=%d",waysx->number);
421 }
422
423
424 /*++++++++++++++++++++++++++++++++++++++
425 Sort the ways into id order.
426
427 int sort_by_id Returns the comparison of the id fields.
428
429 WayX *a The first extended way.
430
431 WayX *b The second extended way.
432 ++++++++++++++++++++++++++++++++++++++*/
433
434 static int sort_by_id(WayX *a,WayX *b)
435 {
436 way_t a_id=a->id;
437 way_t b_id=b->id;
438
439 if(a_id<b_id)
440 return(-1);
441 else if(a_id>b_id)
442 return(1);
443 else
444 return(0);
445 }
446
447
448 /*++++++++++++++++++++++++++++++++++++++
449 Sort the ways into name and id order.
450
451 int sort_by_name_and_id Returns the comparison of the name and id fields.
452
453 WayX *a The first extended Way.
454
455 WayX *b The second extended Way.
456 ++++++++++++++++++++++++++++++++++++++*/
457
458 static int sort_by_name_and_id(WayX *a,WayX *b)
459 {
460 int compare;
461 char *a_name=(char*)a+sizeof(WayX);
462 char *b_name=(char*)b+sizeof(WayX);
463
464 compare=strcmp(a_name,b_name);
465
466 if(compare)
467 return(compare);
468
469 return(sort_by_id(a,b));
470 }
471
472
473 /*++++++++++++++++++++++++++++++++++++++
474 Sort the ways into name, properties and id order.
475
476 int sort_by_name_and_prop_and_id Returns the comparison of the name, properties and id fields.
477
478 WayX *a The first extended Way.
479
480 WayX *b The second extended Way.
481 ++++++++++++++++++++++++++++++++++++++*/
482
483 static int sort_by_name_and_prop_and_id(WayX *a,WayX *b)
484 {
485 int compare;
486 index_t a_name=a->way.name;
487 index_t b_name=b->way.name;
488
489 if(a_name<b_name)
490 return(-1);
491 else if(a_name>b_name)
492 return(1);
493
494 compare=WaysCompare(&a->way,&b->way);
495
496 if(compare)
497 return(compare);
498
499 return(sort_by_id(a,b));
500 }
501
502
503 /*++++++++++++++++++++++++++++++++++++++
504 Deduplicate the extended ways using the id after sorting and create the index.
505
506 int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise zero.
507
508 WayX *wayx The extended way.
509
510 index_t index The index of this way in the total.
511 ++++++++++++++++++++++++++++++++++++++*/
512
513 static int deduplicate_and_index_by_id(WayX *wayx,index_t index)
514 {
515 static way_t previd;
516
517 if(index==0 || wayx->id!=previd)
518 {
519 previd=wayx->id;
520
521 sortwaysx->number++;
522
523 sortwaysx->idata[index]=wayx->id;
524
525 return(1);
526 }
527
528 return(0);
529 }
530
531
532 /*++++++++++++++++++++++++++++++++++++++
533 Find a particular way index.
534
535 index_t IndexWayX Returns the index of the extended way with the specified id.
536
537 WaysX* waysx The set of ways to process.
538
539 way_t id The way id to look for.
540 ++++++++++++++++++++++++++++++++++++++*/
541
542 index_t IndexWayX(WaysX* waysx,way_t id)
543 {
544 int start=0;
545 int end=waysx->number-1;
546 int mid;
547
548 /* Binary search - search key exact match only is required.
549 *
550 * # <- start | Check mid and move start or end if it doesn't match
551 * # |
552 * # | Since an exact match is wanted we can set end=mid-1
553 * # <- mid | or start=mid+1 because we know that mid doesn't match.
554 * # |
555 * # | Eventually either end=start or end=start+1 and one of
556 * # <- end | start or end is the wanted one.
557 */
558
559 if(end<start) /* There are no ways */
560 return(NO_WAY);
561 else if(id<waysx->idata[start]) /* Check key is not before start */
562 return(NO_WAY);
563 else if(id>waysx->idata[end]) /* Check key is not after end */
564 return(NO_WAY);
565 else
566 {
567 do
568 {
569 mid=(start+end)/2; /* Choose mid point */
570
571 if(waysx->idata[mid]<id) /* Mid point is too low */
572 start=mid+1;
573 else if(waysx->idata[mid]>id) /* Mid point is too high */
574 end=mid-1;
575 else /* Mid point is correct */
576 return(mid);
577 }
578 while((end-start)>1);
579
580 if(waysx->idata[start]==id) /* Start is correct */
581 return(start);
582
583 if(waysx->idata[end]==id) /* End is correct */
584 return(end);
585 }
586
587 return(NO_WAY);
588 }
589
590
591 /*++++++++++++++++++++++++++++++++++++++
592 Save the way list to a file.
593
594 WaysX* waysx The set of ways to save.
595
596 const char *filename The name of the file to save.
597 ++++++++++++++++++++++++++++++++++++++*/
598
599 void SaveWayList(WaysX* waysx,const char *filename)
600 {
601 index_t i;
602 int fd;
603 int position=0;
604 WaysFile waysfile={0};
605 highways_t highways=0;
606 transports_t allow=0;
607 properties_t props=0;
608
609 /* Print the start message */
610
611 printf_first("Writing Ways: Ways=0");
612
613 /* Map into memory / open the file */
614
615 #if !SLIM
616 waysx->xdata=MapFile(waysx->filename);
617 #else
618 waysx->fd=ReOpenFile(waysx->filename);
619 #endif
620
621 /* Write out the ways data */
622
623 fd=OpenFileNew(filename);
624
625 SeekFile(fd,sizeof(WaysFile));
626
627 for(i=0;i<waysx->number;i++)
628 {
629 WayX *wayx=LookupWayX(waysx,i,1);
630
631 highways|=HIGHWAYS(wayx->way.type);
632 allow |=wayx->way.allow;
633 props |=wayx->way.props;
634
635 SeekFile(fd,sizeof(WaysFile)+(off_t)wayx->prop*sizeof(Way));
636 WriteFile(fd,&wayx->way,sizeof(Way));
637
638 if(!((i+1)%10000))
639 printf_middle("Writing Ways: Ways=%d",i+1);
640 }
641
642 /* Unmap from memory / close the file */
643
644 #if !SLIM
645 waysx->xdata=UnmapFile(waysx->filename);
646 #else
647 waysx->fd=CloseFile(waysx->fd);
648 #endif
649
650 /* Write out the ways names */
651
652 SeekFile(fd,sizeof(WaysFile)+(off_t)waysx->cnumber*sizeof(Way));
653
654 waysx->nfd=ReOpenFile(waysx->nfilename);
655
656 while(position<waysx->nlength)
657 {
658 int len=1024;
659 char temp[1024];
660
661 if((waysx->nlength-position)<1024)
662 len=waysx->nlength-position;
663
664 ReadFile(waysx->nfd,temp,len);
665 WriteFile(fd,temp,len);
666
667 position+=len;
668 }
669
670 /* Close the file */
671
672 waysx->nfd=CloseFile(waysx->nfd);
673
674 /* Write out the header structure */
675
676 waysfile.number =waysx->cnumber;
677 waysfile.onumber=waysx->number;
678
679 waysfile.highways=highways;
680 waysfile.allow =allow;
681 waysfile.props =props;
682
683 SeekFile(fd,0);
684 WriteFile(fd,&waysfile,sizeof(WaysFile));
685
686 CloseFile(fd);
687
688 /* Print the final message */
689
690 printf_last("Wrote Ways: Ways=%d",waysx->number);
691 }

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