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 532 - (show annotations) (download) (as text)
Sat Nov 27 14:56:37 2010 UTC (14 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 14923 byte(s) 
Split functions.h into fakes.h, sorting.h and the remainder in functions.h.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.56 2010-11-27 14:56:37 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,nfd;
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 and re-open it (finished appending) */
190
191 CloseFile(waysx->fd);
192 waysx->fd=ReOpenFile(waysx->filename);
193
194 DeleteFile(waysx->filename);
195
196 fd=OpenFileNew(waysx->filename);
197
198 /* Sort the ways to allow separating the names */
199
200 filesort_vary(waysx->fd,fd,(int (*)(const void*,const void*))sort_by_name_and_id,NULL);
201
202 /* Close the files */
203
204 CloseFile(waysx->fd);
205 CloseFile(fd);
206
207 /* Print the final message */
208
209 printf_last("Sorted Ways by Name: Ways=%d",waysx->xnumber);
210
211
212 /* Print the start message */
213
214 printf_first("Separating Way Names: Ways=0 Names=0");
215
216 /* Open the files */
217
218 waysx->fd=ReOpenFile(waysx->filename);
219
220 DeleteFile(waysx->filename);
221
222 fd=OpenFileNew(waysx->filename);
223 nfd=OpenFileNew(waysx->nfilename);
224
225 /* Copy from the single file into two files */
226
227 for(i=0;i<waysx->xnumber;i++)
228 {
229 WayX wayx;
230 FILESORT_VARINT size;
231
232 ReadFile(waysx->fd,&size,FILESORT_VARSIZE);
233
234 if(namelen[nnames%2]<size)
235 names[nnames%2]=(char*)realloc((void*)names[nnames%2],namelen[nnames%2]=size);
236
237 ReadFile(waysx->fd,&wayx,sizeof(WayX));
238 ReadFile(waysx->fd,names[nnames%2],size-sizeof(WayX));
239
240 if(nnames==0 || strcmp(names[0],names[1]))
241 {
242 WriteFile(nfd,names[nnames%2],size-sizeof(WayX));
243
244 lastlength=waysx->nlength;
245 waysx->nlength+=size-sizeof(WayX);
246
247 nnames++;
248 }
249
250 wayx.way.name=lastlength;
251
252 WriteFile(fd,&wayx,sizeof(WayX));
253
254 if(!((i+1)%10000))
255 printf_middle("Separating Way Names: Ways=%d Names=%d",i+1,nnames);
256 }
257
258 if(names[0]) free(names[0]);
259 if(names[1]) free(names[1]);
260
261 /* Close the files */
262
263 CloseFile(waysx->fd);
264 CloseFile(fd);
265
266 waysx->fd=ReOpenFile(waysx->filename);
267
268 CloseFile(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 /* Open the files */
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 and re-open them */
302
303 CloseFile(waysx->fd);
304 CloseFile(fd);
305
306 waysx->fd=ReOpenFile(waysx->filename);
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 /* Close the file and re-open it */
331
332 CloseFile(waysx->fd);
333 waysx->fd=ReOpenFile(waysx->filename);
334
335 DeleteFile(waysx->filename);
336
337 fd=OpenFileNew(waysx->filename);
338
339 /* Sort the ways to allow compacting according to he properties */
340
341 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_name_and_prop_and_id,NULL);
342
343 /* Close the files */
344
345 CloseFile(waysx->fd);
346 CloseFile(fd);
347
348 /* Print the final message */
349
350 printf_last("Sorted Ways by Properties: Ways=%d",waysx->number);
351
352
353 /* Print the start message */
354
355 printf_first("Compacting Ways: Ways=0 Properties=0");
356
357 /* Open the files */
358
359 waysx->fd=ReOpenFile(waysx->filename);
360
361 DeleteFile(waysx->filename);
362
363 fd=OpenFileNew(waysx->filename);
364
365 /* Update the way as we go using the sorted index */
366
367 waysx->cnumber=0;
368
369 for(i=0;i<waysx->number;i++)
370 {
371 WayX wayx;
372
373 ReadFile(waysx->fd,&wayx,sizeof(WayX));
374
375 if(waysx->cnumber==0 || wayx.way.name!=lastway.name || WaysCompare(&lastway,&wayx.way))
376 {
377 lastway=wayx.way;
378
379 waysx->cnumber++;
380 }
381
382 wayx.prop=waysx->cnumber-1;
383
384 WriteFile(fd,&wayx,sizeof(WayX));
385
386 if(!((i+1)%10000))
387 printf_middle("Compacting Ways: Ways=%d Properties=%d",i+1,waysx->cnumber);
388 }
389
390 /* Close the files */
391
392 CloseFile(waysx->fd);
393 CloseFile(fd);
394
395 /* Print the final message */
396
397 printf_last("Compacted Ways: Ways=%d Properties=%d ",waysx->number,waysx->cnumber);
398
399
400 /* Print the start message */
401
402 printf_first("Sorting Ways");
403
404 /* Open the files */
405
406 waysx->fd=ReOpenFile(waysx->filename);
407
408 DeleteFile(waysx->filename);
409
410 fd=OpenFileNew(waysx->filename);
411
412 /* Sort the ways by index */
413
414 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_id,NULL);
415
416 /* Close the files and re-open them */
417
418 CloseFile(waysx->fd);
419 CloseFile(fd);
420
421 waysx->fd=ReOpenFile(waysx->filename);
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 and 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 Deduplicate the extended ways using the id after sorting and create the index.
510
511 int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise zero.
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,nfd;
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 */
619
620 #if !SLIM
621 waysx->xdata=MapFile(waysx->filename);
622 #endif
623
624 /* Write out the ways data */
625
626 fd=OpenFileNew(filename);
627
628 SeekFile(fd,sizeof(WaysFile));
629
630 for(i=0;i<waysx->number;i++)
631 {
632 WayX *wayx=LookupWayX(waysx,i,1);
633
634 highways|=HIGHWAYS(wayx->way.type);
635 allow |=wayx->way.allow;
636 props |=wayx->way.props;
637
638 SeekFile(fd,sizeof(WaysFile)+(off_t)wayx->prop*sizeof(Way));
639 WriteFile(fd,&wayx->way,sizeof(Way));
640
641 if(!((i+1)%10000))
642 printf_middle("Writing Ways: Ways=%d",i+1);
643 }
644
645 /* Unmap from memory */
646
647 #if !SLIM
648 waysx->xdata=UnmapFile(waysx->filename);
649 #endif
650
651 /* Write out the ways names */
652
653 SeekFile(fd,sizeof(WaysFile)+(off_t)waysx->cnumber*sizeof(Way));
654
655 nfd=ReOpenFile(waysx->nfilename);
656
657 while(position<waysx->nlength)
658 {
659 int len=1024;
660 char temp[1024];
661
662 if((waysx->nlength-position)<1024)
663 len=waysx->nlength-position;
664
665 ReadFile(nfd,temp,len);
666 WriteFile(fd,temp,len);
667
668 position+=len;
669 }
670
671 CloseFile(nfd);
672
673 /* Write out the header structure */
674
675 waysfile.number =waysx->cnumber;
676 waysfile.onumber=waysx->number;
677
678 waysfile.highways=highways;
679 waysfile.allow =allow;
680 waysfile.props =props;
681
682 SeekFile(fd,0);
683 WriteFile(fd,&waysfile,sizeof(WaysFile));
684
685 CloseFile(fd);
686
687 /* Print the final message */
688
689 printf_last("Wrote Ways: Ways=%d",waysx->number);
690 }

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