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

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