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

   1 /***************************************
   2  $Header: /home/amb/routino/src/RCS/waysx.c,v 1.38 2010/05/22 18:40:47 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 <string.h>
  28 #include <sys/stat.h>
  29
  30 #include "functions.h"
  31 #include "waysx.h"
  32 #include "ways.h"
  33
  34
  35 /* Variables */
  36
  37 /*+ The command line '--slim' option. +*/
  38 extern int option_slim;
  39
  40 /*+ The command line '--tmpdir' option or its default value. +*/
  41 extern char *option_tmpdirname;
  42
  43 /*+ A temporary file-local variable for use by the sort functions. +*/
  44 static WaysX *sortwaysx;
  45
  46 /* Functions */
  47
  48 static int sort_by_name_and_prop_and_id(WayX *a,WayX *b);
  49 static int deduplicate_by_id(WayX *wayx,index_t index);
  50
  51 static int sort_by_id(WayX *a,WayX *b);
  52 static int index_by_id(WayX *wayx,index_t index);
  53
  54
  55 /*++++++++++++++++++++++++++++++++++++++
  56   Allocate a new way list (create a new file or open an existing one).
  57
  58   WaysX *NewWayList Returns the way list.
  59
  60   int append Set to 1 if the file is to be opened for appending (now or later).
  61   ++++++++++++++++++++++++++++++++++++++*/
  62
  63 WaysX *NewWayList(int append)
  64 {
  65  WaysX *waysx;
  66
  67  waysx=(WaysX*)calloc(1,sizeof(WaysX));
  68
  69  assert(waysx); /* Check calloc() worked */
  70
  71  waysx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
  72
  73  if(append)
  74     sprintf(waysx->filename,"%s/ways.input.tmp",option_tmpdirname);
  75  else
  76     sprintf(waysx->filename,"%s/ways.%p.tmp",option_tmpdirname,waysx);
  77
  78  if(append)
  79    {
  80     off_t size,position=0;
  81
  82     waysx->fd=AppendFile(waysx->filename);
  83
  84     size=SizeFile(waysx->filename);
  85
  86     while(position<size)
  87       {
  88        FILESORT_VARINT waysize;
  89
  90        SeekFile(waysx->fd,position);
  91        ReadFile(waysx->fd,&waysize,FILESORT_VARSIZE);
  92
  93        waysx->xnumber++;
  94        position+=waysize+FILESORT_VARSIZE;
  95       }
  96
  97     SeekFile(waysx->fd,size);
  98    }
  99  else
 100     waysx->fd=OpenFile(waysx->filename);
 101
 102  waysx->nfilename=(char*)malloc(strlen(option_tmpdirname)+32);
 103  sprintf(waysx->nfilename,"%s/waynames.%p.tmp",option_tmpdirname,waysx);
 104
 105  return(waysx);
 106 }
 107
 108
 109 /*++++++++++++++++++++++++++++++++++++++
 110   Free a way list.
 111
 112   WaysX *waysx The list to be freed.
 113
 114   int keep Set to 1 if the file is to be kept.
 115   ++++++++++++++++++++++++++++++++++++++*/
 116
 117 void FreeWayList(WaysX *waysx,int keep)
 118 {
 119  if(!keep)
 120     DeleteFile(waysx->filename);
 121
 122  free(waysx->filename);
 123
 124  if(waysx->idata)
 125     free(waysx->idata);
 126
 127  DeleteFile(waysx->nfilename);
 128
 129  free(waysx->nfilename);
 130
 131  free(waysx);
 132 }
 133
 134
 135 /*++++++++++++++++++++++++++++++++++++++
 136   Append a way to a way list.
 137
 138   void AppendWay Returns the newly appended way.
 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  assert(!waysx->idata);       /* Must not have idata filled in => unsorted */
 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->xnumber++;
 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,nprops=0;
 183  uint32_t lastlength=0;
 184  Way lastway;
 185
 186  /* Check the start conditions */
 187
 188  assert(!waysx->idata);         /* Must not have idata filled in => unsorted */
 189
 190  /* Print the start message */
 191
 192  printf("Sorting Ways");
 193  fflush(stdout);
 194
 195  /* Close the file and re-open it (finished appending) */
 196
 197  CloseFile(waysx->fd);
 198  waysx->fd=ReOpenFile(waysx->filename);
 199
 200  DeleteFile(waysx->filename);
 201
 202  fd=OpenFile(waysx->filename);
 203
 204  /* Sort the ways to allow compacting them and remove duplicates */
 205
 206  sortwaysx=waysx;
 207
 208  filesort_vary(waysx->fd,fd,(int (*)(const void*,const void*))sort_by_name_and_prop_and_id,(int (*)(void*,index_t))deduplicate_by_id);
 209
 210  /* Close the files */
 211
 212  CloseFile(waysx->fd);
 213  CloseFile(fd);
 214
 215  /* Print the final message */
 216
 217  printf("\rSorted Ways: Ways=%d Duplicates=%d\n",waysx->xnumber,waysx->xnumber-waysx->number);
 218  fflush(stdout);
 219
 220
 221  /* Print the start message */
 222
 223  printf("Compacting Ways: Ways=0 Names=0 Properties=0");
 224  fflush(stdout);
 225
 226  /* Open the files */
 227
 228  waysx->fd=ReOpenFile(waysx->filename);
 229
 230  DeleteFile(waysx->filename);
 231
 232  fd=OpenFile(waysx->filename);
 233  nfd=OpenFile(waysx->nfilename);
 234
 235  /* Copy from the single file into two files and index as we go. */
 236
 237  for(i=0;i<waysx->number;i++)
 238    {
 239     WayX wayx;
 240     FILESORT_VARINT size;
 241
 242     ReadFile(waysx->fd,&size,FILESORT_VARSIZE);
 243
 244     if(namelen[nnames%2]<size)
 245        names[nnames%2]=(char*)realloc((void*)names[nnames%2],namelen[nnames%2]=size);
 246
 247     ReadFile(waysx->fd,&wayx,sizeof(WayX));
 248     ReadFile(waysx->fd,names[nnames%2],size-sizeof(WayX));
 249
 250     if(nnames==0 || strcmp(names[0],names[1]))
 251       {
 252        WriteFile(nfd,names[nnames%2],size-sizeof(WayX));
 253
 254        lastlength=waysx->nlength;
 255        waysx->nlength+=size-sizeof(WayX);
 256
 257        nnames++;
 258       }
 259
 260     wayx.way.name=lastlength;
 261
 262     if(nprops==0 || wayx.way.name!=lastway.name || WaysCompare(&lastway,&wayx.way))
 263       {
 264        lastway=wayx.way;
 265
 266        waysx->cnumber++;
 267
 268        nprops++;
 269       }
 270
 271     wayx.prop=nprops-1;
 272
 273     WriteFile(fd,&wayx,sizeof(WayX));
 274
 275     if(!((i+1)%10000))
 276       {
 277        printf("\rCompacting Ways: Ways=%d Names=%d Properties=%d",i+1,nnames,nprops);
 278        fflush(stdout);
 279       }
 280    }
 281
 282  if(names[0]) free(names[0]);
 283  if(names[1]) free(names[1]);
 284
 285  /* Close the files */
 286
 287  CloseFile(waysx->fd);
 288  CloseFile(fd);
 289
 290  waysx->fd=ReOpenFile(waysx->filename);
 291
 292  CloseFile(nfd);
 293
 294  /* Print the final message */
 295
 296  printf("\rCompacted Ways: Ways=%d Names=%d Properties=%d \n",waysx->number,nnames,nprops);
 297  fflush(stdout);
 298
 299
 300  /* Print the start message */
 301
 302  printf("Sorting Ways");
 303  fflush(stdout);
 304
 305  /* Open the files */
 306
 307  waysx->fd=ReOpenFile(waysx->filename);
 308
 309  DeleteFile(waysx->filename);
 310
 311  fd=OpenFile(waysx->filename);
 312
 313  /* Allocate the array of indexes */
 314
 315  waysx->idata=(way_t*)malloc(waysx->number*sizeof(way_t));
 316
 317  assert(waysx->idata); /* Check malloc() worked */
 318
 319  /* Sort the ways by index and index them */
 320
 321  sortwaysx=waysx;
 322
 323  filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))index_by_id);
 324
 325  /* Close the files and re-open them */
 326
 327  CloseFile(waysx->fd);
 328  CloseFile(fd);
 329
 330  waysx->fd=ReOpenFile(waysx->filename);
 331
 332  /* Print the final message */
 333
 334  printf("\rSorted Ways: Ways=%d\n",waysx->number);
 335  fflush(stdout);
 336 }
 337
 338
 339 /*++++++++++++++++++++++++++++++++++++++
 340   Sort the ways into id order.
 341
 342   int sort_by_id Returns the comparison of the id fields.
 343
 344   WayX *a The first extended way.
 345
 346   WayX *b The second extended way.
 347   ++++++++++++++++++++++++++++++++++++++*/
 348
 349 static int sort_by_id(WayX *a,WayX *b)
 350 {
 351  way_t a_id=a->id;
 352  way_t b_id=b->id;
 353
 354  if(a_id<b_id)
 355     return(-1);
 356  else if(a_id>b_id)
 357     return(1);
 358  else
 359     return(0);
 360 }
 361
 362
 363 /*++++++++++++++++++++++++++++++++++++++
 364   Sort the ways into name, properties and id order.
 365
 366   int sort_by_name_and_prop_and_id Returns the comparison of the name, properties and id fields.
 367
 368   WayX *a The first extended Way.
 369
 370   WayX *b The second extended Way.
 371   ++++++++++++++++++++++++++++++++++++++*/
 372
 373 static int sort_by_name_and_prop_and_id(WayX *a,WayX *b)
 374 {
 375  int compare;
 376  char *a_name=(char*)a+sizeof(WayX);
 377  char *b_name=(char*)b+sizeof(WayX);
 378
 379  compare=strcmp(a_name,b_name);
 380
 381  if(compare)
 382     return(compare);
 383
 384  compare=WaysCompare(&a->way,&b->way);
 385
 386  if(compare)
 387     return(compare);
 388
 389  return(sort_by_id(a,b));
 390 }
 391
 392
 393 /*++++++++++++++++++++++++++++++++++++++
 394   Deduplicate the extended ways using the id after sorting.
 395
 396   int deduplicate_by_id Return 1 if the value is to be kept, otherwise zero.
 397
 398   WayX *wayx The extended way.
 399
 400   index_t index The index of this way in the total.
 401   ++++++++++++++++++++++++++++++++++++++*/
 402
 403 static int deduplicate_by_id(WayX *wayx,index_t index)
 404 {
 405  static way_t previd;
 406
 407  if(index==0 || wayx->id!=previd)
 408    {
 409     previd=wayx->id;
 410
 411     sortwaysx->number++;
 412
 413     return(1);
 414    }
 415
 416  return(0);
 417 }
 418
 419
 420 /*++++++++++++++++++++++++++++++++++++++
 421   Index the ways after sorting.
 422
 423   int index_by_id Return 1 if the value is to be kept, otherwise zero.
 424
 425   WayX *wayx The extended way.
 426
 427   index_t index The index of this way in the total.
 428   ++++++++++++++++++++++++++++++++++++++*/
 429
 430 static int index_by_id(WayX *wayx,index_t index)
 431 {
 432  sortwaysx->idata[index]=wayx->id;
 433
 434  return(1);
 435 }
 436
 437
 438 /*++++++++++++++++++++++++++++++++++++++
 439   Find a particular way index.
 440
 441   index_t IndexWayX Returns the index of the extended way with the specified id.
 442
 443   WaysX* waysx The set of ways to process.
 444
 445   way_t id The way id to look for.
 446   ++++++++++++++++++++++++++++++++++++++*/
 447
 448 index_t IndexWayX(WaysX* waysx,way_t id)
 449 {
 450  int start=0;
 451  int end=waysx->number-1;
 452  int mid;
 453
 454  assert(waysx->idata);         /* Must have idata filled in => sorted */
 455
 456  /* Binary search - search key exact match only is required.
 457   *
 458   *  # <- start  |  Check mid and move start or end if it doesn't match
 459   *  #           |
 460   *  #           |  Since an exact match is wanted we can set end=mid-1
 461   *  # <- mid    |  or start=mid+1 because we know that mid doesn't match.
 462   *  #           |
 463   *  #           |  Eventually either end=start or end=start+1 and one of
 464   *  # <- end    |  start or end is the wanted one.
 465   */
 466
 467  if(end<start)                   /* There are no ways */
 468     return(NO_WAY);
 469  else if(id<waysx->idata[start]) /* Check key is not before start */
 470     return(NO_WAY);
 471  else if(id>waysx->idata[end])   /* Check key is not after end */
 472     return(NO_WAY);
 473  else
 474    {
 475     do
 476       {
 477        mid=(start+end)/2;            /* Choose mid point */
 478
 479        if(waysx->idata[mid]<id)      /* Mid point is too low */
 480           start=mid+1;
 481        else if(waysx->idata[mid]>id) /* Mid point is too high */
 482           end=mid-1;
 483        else                          /* Mid point is correct */
 484           return(mid);
 485       }
 486     while((end-start)>1);
 487
 488     if(waysx->idata[start]==id)      /* Start is correct */
 489        return(start);
 490
 491     if(waysx->idata[end]==id)        /* End is correct */
 492        return(end);
 493    }
 494
 495  return(NO_WAY);
 496 }
 497
 498
 499 /*++++++++++++++++++++++++++++++++++++++
 500   Lookup a particular way.
 501
 502   WayX *LookupWayX Returns a pointer to the extended way with the specified id.
 503
 504   WaysX* waysx The set of ways to process.
 505
 506   index_t index The way index to look for.
 507
 508   int position The position in the cache to use.
 509   ++++++++++++++++++++++++++++++++++++++*/
 510
 511 WayX *LookupWayX(WaysX* waysx,index_t index,int position)
 512 {
 513  assert(index!=NO_WAY);     /* Must be a valid way */
 514
 515  if(option_slim)
 516    {
 517     SeekFile(waysx->fd,index*sizeof(WayX));
 518
 519     ReadFile(waysx->fd,&waysx->cached[position-1],sizeof(WayX));
 520
 521     return(&waysx->cached[position-1]);
 522    }
 523  else
 524    {
 525     return(&waysx->xdata[index]);
 526    }
 527 }
 528
 529
 530 /*++++++++++++++++++++++++++++++++++++++
 531   Save the way list to a file.
 532
 533   WaysX* waysx The set of ways to save.
 534
 535   const char *filename The name of the file to save.
 536   ++++++++++++++++++++++++++++++++++++++*/
 537
 538 void SaveWayList(WaysX* waysx,const char *filename)
 539 {
 540  index_t i;
 541  int fd,nfd;
 542  int position=0;
 543  Ways *ways;
 544
 545  printf("Writing Ways: Ways=0");
 546  fflush(stdout);
 547
 548  if(!option_slim)
 549     waysx->xdata=MapFile(waysx->filename);
 550
 551  /* Fill in a Ways structure with the offset of the real data in the file after
 552     the Way structure itself. */
 553
 554  ways=calloc(1,sizeof(Ways));
 555
 556  assert(ways); /* Check calloc() worked */
 557
 558  ways->number=waysx->cnumber;
 559  ways->onumber=waysx->number;
 560
 561  ways->allow=0;
 562  ways->props=0;
 563
 564  ways->data=NULL;
 565  ways->ways=NULL;
 566  ways->names=NULL;
 567
 568  /* Write out the Ways structure and then the real data. */
 569
 570  fd=OpenFile(filename);
 571
 572  for(i=0;i<waysx->number;i++)
 573    {
 574     WayX *wayx=LookupWayX(waysx,i,1);
 575
 576     ways->allow|=wayx->way.allow;
 577     ways->props|=wayx->way.props;
 578
 579     SeekFile(fd,sizeof(Ways)+wayx->prop*sizeof(Way));
 580     WriteFile(fd,&wayx->way,sizeof(Way));
 581
 582     if(!((i+1)%10000))
 583       {
 584        printf("\rWriting Ways: Ways=%d",i+1);
 585        fflush(stdout);
 586       }
 587    }
 588
 589  SeekFile(fd,0);
 590  WriteFile(fd,ways,sizeof(Ways));
 591
 592  if(!option_slim)
 593     waysx->xdata=UnmapFile(waysx->filename);
 594
 595  SeekFile(fd,sizeof(Ways)+ways->number*sizeof(Way));
 596
 597  nfd=ReOpenFile(waysx->nfilename);
 598
 599  while(position<waysx->nlength)
 600    {
 601     int len=1024;
 602     char temp[1024];
 603
 604     if((waysx->nlength-position)<1024)
 605        len=waysx->nlength-position;
 606
 607     ReadFile(nfd,temp,len);
 608     WriteFile(fd,temp,len);
 609
 610     position+=len;
 611    }
 612
 613  CloseFile(nfd);
 614
 615  CloseFile(fd);
 616
 617  printf("\rWrote Ways: Ways=%d  \n",waysx->number);
 618  fflush(stdout);
 619
 620  /* Free the fake Ways */
 621
 622  free(ways);
 623 }