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

   1 /***************************************
   2  $Header: /home/amb/routino/src/RCS/waysx.c,v 1.52 2010/11/13 14:22:28 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 "functions.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  allow_t allow=0;
 611  wayprop_t  props=0;
 612
 613  /* Print the start message */
 614
 615  printf_first("Writing Ways: Ways=0");
 616
 617  /* Map into memory */
 618
 619 #if !SLIM
 620  waysx->xdata=MapFile(waysx->filename);
 621 #endif
 622
 623  /* Write out the ways data */
 624
 625  fd=OpenFileNew(filename);
 626
 627  SeekFile(fd,sizeof(WaysFile));
 628
 629  for(i=0;i<waysx->number;i++)
 630    {
 631     WayX *wayx=LookupWayX(waysx,i,1);
 632
 633     allow|=wayx->way.allow;
 634     props|=wayx->way.props;
 635
 636     SeekFile(fd,sizeof(WaysFile)+(off_t)wayx->prop*sizeof(Way));
 637     WriteFile(fd,&wayx->way,sizeof(Way));
 638
 639     if(!((i+1)%10000))
 640        printf_middle("Writing Ways: Ways=%d",i+1);
 641    }
 642
 643  /* Unmap from memory */
 644
 645 #if !SLIM
 646  waysx->xdata=UnmapFile(waysx->filename);
 647 #endif
 648
 649  /* Write out the ways names */
 650
 651  SeekFile(fd,sizeof(WaysFile)+(off_t)waysx->cnumber*sizeof(Way));
 652
 653  nfd=ReOpenFile(waysx->nfilename);
 654
 655  while(position<waysx->nlength)
 656    {
 657     int len=1024;
 658     char temp[1024];
 659
 660     if((waysx->nlength-position)<1024)
 661        len=waysx->nlength-position;
 662
 663     ReadFile(nfd,temp,len);
 664     WriteFile(fd,temp,len);
 665
 666     position+=len;
 667    }
 668
 669  CloseFile(nfd);
 670
 671  /* Write out the header structure */
 672
 673  waysfile.number=waysx->cnumber;
 674  waysfile.onumber=waysx->number;
 675
 676  waysfile.allow=allow;
 677  waysfile.props=props;
 678
 679  SeekFile(fd,0);
 680  WriteFile(fd,&waysfile,sizeof(WaysFile));
 681
 682  CloseFile(fd);
 683
 684  /* Print the final message */
 685
 686  printf_last("Wrote Ways: Ways=%d",waysx->number);
 687 }