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

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