git.maemo.org Git - routino/blob - src/waysx.c

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