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