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

   1 /***************************************
   2  $Header: /home/amb/routino/src/RCS/sorting.c,v 1.8 2010/04/09 15:15:02 amb Exp $
   3
   4  Merge sort functions.
   5
   6  Part of the Routino routing software.
   7  ******************/ /******************
   8  This file Copyright 2009 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 <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <assert.h>
  29
  30 #include "functions.h"
  31
  32
  33 /* Variables */
  34
  35 /*+ The command line '--tmpdir' option or its default value. +*/
  36 extern char *option_tmpdirname;
  37
  38 /*+ The amount of RAM to use for filesorting. +*/
  39 extern size_t option_filesort_ramsize;
  40
  41
  42 /*++++++++++++++++++++++++++++++++++++++
  43   A function to sort the contents of a file of fixed length objects using a
  44   limited amount of RAM.
  45
  46   The data is sorted using a "Merge sort" http://en.wikipedia.org/wiki/Merge_sort
  47   and in particular an "external sort" http://en.wikipedia.org/wiki/External_sorting.
  48   The individual sort steps and the merge step both use a "Heap sort"
  49   http://en.wikipedia.org/wiki/Heapsort.  The combination of the two should work well
  50   if the data is already partially sorted.
  51
  52   int fd_in The file descriptor of the input file (opened for reading and at the beginning).
  53
  54   int fd_out The file descriptor of the output file (opened for writing and empty).
  55
  56   size_t itemsize The size of each item in the file that needs sorting.
  57
  58   int (*compare)(const void*, const void*) The comparison function (identical to qsort if the
  59                                            data to be sorted is an array of things not pointers).
  60
  61   int (*buildindex)(void *,index_t) If non-NULL then this function is called for each item, if it
  62                                     returns 1 then it is written to the output file.
  63   ++++++++++++++++++++++++++++++++++++++*/
  64
  65 void filesort_fixed(int fd_in,int fd_out,size_t itemsize,int (*compare)(const void*,const void*),int (*buildindex)(void*,index_t))
  66 {
  67  int *fds=NULL,*heap=NULL;
  68  int nfiles=0,ndata=0;
  69  index_t count=0,total=0;
  70  size_t nitems=option_filesort_ramsize/(itemsize+sizeof(void*));
  71  void *data=NULL,**datap=NULL;
  72  char *filename;
  73  int i,more=1;
  74
  75  /* Allocate the RAM buffer and other bits */
  76
  77  data=malloc(nitems*itemsize);
  78  datap=malloc(nitems*sizeof(void*));
  79
  80  filename=(char*)malloc(strlen(option_tmpdirname)+24);
  81
  82  /* Loop around, fill the buffer, sort the data and write a temporary file */
  83
  84  do
  85    {
  86     int fd,n=0;
  87
  88     /* Read in the data and create pointers */
  89
  90     for(i=0;i<nitems;i++)
  91       {
  92        datap[i]=data+i*itemsize;
  93
  94        if(ReadFile(fd_in,datap[i],itemsize))
  95          {
  96           more=0;
  97           break;
  98          }
  99
 100        total++;
 101       }
 102
 103     n=i;
 104
 105     if(n==0)
 106        break;
 107
 108     /* Sort the data pointers using a heap sort */
 109
 110     heapsort(datap,n,compare);
 111
 112     /* Shortcut if all read in and sorted at once */
 113
 114     if(nfiles==0 && !more)
 115       {
 116        for(i=0;i<n;i++)
 117          {
 118           if(!buildindex || buildindex(datap[i],count))
 119             {
 120              WriteFile(fd_out,datap[i],itemsize);
 121              count++;
 122             }
 123          }
 124
 125        goto tidy_and_exit;
 126       }
 127
 128     /* Create a temporary file and write the result */
 129
 130     sprintf(filename,"%s/filesort.%d.tmp",option_tmpdirname,nfiles);
 131
 132     fd=OpenFile(filename);
 133
 134     for(i=0;i<n;i++)
 135        WriteFile(fd,datap[i],itemsize);
 136
 137     CloseFile(fd);
 138
 139     nfiles++;
 140    }
 141  while(more);
 142
 143  /* Shortcut if only one file (unlucky for us there must have been exactly
 144     nitems, lucky for us we still have the data in RAM) */
 145
 146  if(nfiles==1)
 147    {
 148     for(i=0;i<nitems;i++)
 149       {
 150        if(!buildindex || buildindex(datap[i],count))
 151          {
 152           WriteFile(fd_out,datap[i],itemsize);
 153           count++;
 154          }
 155       }
 156
 157     DeleteFile(filename);
 158
 159     goto tidy_and_exit;
 160    }
 161
 162  /* Check that number of files is less than file size */
 163
 164  assert(nfiles<nitems);
 165
 166  /* Open all of the temporary files */
 167
 168  fds=(int*)malloc(nfiles*sizeof(int));
 169
 170  for(i=0;i<nfiles;i++)
 171    {
 172     sprintf(filename,"%s/filesort.%d.tmp",option_tmpdirname,i);
 173
 174     fds[i]=ReOpenFile(filename);
 175
 176     DeleteFile(filename);
 177    }
 178
 179  /* Perform an n-way merge using a binary heap */
 180
 181  heap=(int*)malloc(nfiles*sizeof(int));
 182
 183  /* Fill the heap to start with */
 184
 185  for(i=0;i<nfiles;i++)
 186    {
 187     int index;
 188
 189     datap[i]=data+i*itemsize;
 190
 191     ReadFile(fds[i],datap[i],itemsize);
 192
 193     heap[i]=i;
 194
 195     index=i;
 196
 197     /* Bubble up the new value */
 198
 199     while(index>0 &&
 200           compare(datap[heap[index]],datap[heap[(index-1)/2]])<0)
 201       {
 202        int newindex;
 203        int temp;
 204
 205        newindex=(index-1)/2;
 206
 207        temp=heap[index];
 208        heap[index]=heap[newindex];
 209        heap[newindex]=temp;
 210
 211        index=newindex;
 212       }
 213    }
 214
 215  /* Repeatedly pull out the root of the heap and refill from the same file */
 216
 217  ndata=nfiles;
 218
 219  do
 220    {
 221     int index=0;
 222
 223     if(!buildindex || buildindex(datap[heap[0]],count))
 224       {
 225        WriteFile(fd_out,datap[heap[0]],itemsize);
 226        count++;
 227       }
 228
 229     if(ReadFile(fds[heap[0]],datap[heap[0]],itemsize))
 230       {
 231        ndata--;
 232        heap[0]=heap[ndata];
 233       }
 234
 235     /* Bubble down the new value */
 236
 237     while((2*index+2)<ndata &&
 238           (compare(datap[heap[index]],datap[heap[2*index+1]])>0 ||
 239            compare(datap[heap[index]],datap[heap[2*index+2]])>0))
 240       {
 241        int newindex;
 242        int temp;
 243
 244        if(compare(datap[heap[2*index+1]],datap[heap[2*index+2]])<0)
 245           newindex=2*index+1;
 246        else
 247           newindex=2*index+2;
 248
 249        temp=heap[newindex];
 250        heap[newindex]=heap[index];
 251        heap[index]=temp;
 252
 253        index=newindex;
 254       }
 255
 256     if((2*index+2)==ndata &&
 257        compare(datap[heap[index]],datap[heap[2*index+1]])>0)
 258       {
 259        int newindex;
 260        int temp;
 261
 262        newindex=2*index+1;
 263
 264        temp=heap[newindex];
 265        heap[newindex]=heap[index];
 266        heap[index]=temp;
 267       }
 268    }
 269  while(ndata>0);
 270
 271  /* Tidy up */
 272
 273  tidy_and_exit:
 274
 275  if(fds)
 276    {
 277     for(i=0;i<nfiles;i++)
 278        CloseFile(fds[i]);
 279     free(fds);
 280    }
 281
 282  if(heap)
 283     free(heap);
 284
 285  free(data);
 286  free(datap);
 287  free(filename);
 288 }
 289
 290
 291 /*++++++++++++++++++++++++++++++++++++++
 292   A function to sort the contents of a file of variable length objects (each
 293   preceded by its length in 2 bytes) using a limited amount of RAM.
 294
 295   The data is sorted using a "Merge sort" http://en.wikipedia.org/wiki/Merge_sort
 296   and in particular an "external sort" http://en.wikipedia.org/wiki/External_sorting.
 297   The individual sort steps and the merge step both use a "Heap sort"
 298   http://en.wikipedia.org/wiki/Heapsort.  The combination of the two should work well
 299   if the data is already partially sorted.
 300
 301   int fd_in The file descriptor of the input file (opened for reading and at the beginning).
 302
 303   int fd_out The file descriptor of the output file (opened for writing and empty).
 304
 305   int (*compare)(const void*, const void*) The comparison function (identical to qsort if the
 306                                            data to be sorted is an array of things not pointers).
 307
 308   int (*buildindex)(void *,index_t) If non-NULL then this function is called for each item, if it
 309                                     returns 1 then it is written to the output file.
 310   ++++++++++++++++++++++++++++++++++++++*/
 311
 312 void filesort_vary(int fd_in,int fd_out,int (*compare)(const void*,const void*),int (*buildindex)(void*,index_t))
 313 {
 314  int *fds=NULL,*heap=NULL;
 315  int nfiles=0,ndata=0;
 316  index_t count=0,total=0;
 317  FILESORT_VARINT nextitemsize,largestitemsize=0;
 318  void *data=NULL,**datap=NULL;
 319  char *filename;
 320  int i,more=1;
 321
 322  /* Allocate the RAM buffer and other bits */
 323
 324  data=malloc(option_filesort_ramsize);
 325
 326  filename=(char*)malloc(strlen(option_tmpdirname)+24);
 327
 328  /* Loop around, fill the buffer, sort the data and write a temporary file */
 329
 330  if(ReadFile(fd_in,&nextitemsize,FILESORT_VARSIZE))    /* Always have the next item size known in advance */
 331     goto tidy_and_exit;
 332
 333  do
 334    {
 335     int fd,n=0;
 336     size_t ramused=FILESORT_VARALIGN-FILESORT_VARSIZE;
 337
 338     datap=data+option_filesort_ramsize;
 339
 340     /* Read in the data and create pointers */
 341
 342     while((ramused+FILESORT_VARSIZE+nextitemsize)<=((void*)datap-sizeof(void*)-data))
 343       {
 344        FILESORT_VARINT itemsize=nextitemsize;
 345
 346        if(itemsize>largestitemsize)
 347           largestitemsize=itemsize;
 348
 349        *(FILESORT_VARINT*)(data+ramused)=itemsize;
 350
 351        ramused+=FILESORT_VARSIZE;
 352
 353        ReadFile(fd_in,data+ramused,itemsize);
 354
 355        *--datap=data+ramused; /* points to real data */
 356
 357        ramused+=itemsize;
 358
 359        ramused =FILESORT_VARALIGN*((ramused+FILESORT_VARSIZE-1)/FILESORT_VARALIGN);
 360        ramused+=FILESORT_VARALIGN-FILESORT_VARSIZE;
 361
 362        total++;
 363        n++;
 364
 365        if(ReadFile(fd_in,&nextitemsize,FILESORT_VARSIZE))
 366          {
 367           more=0;
 368           break;
 369          }
 370       }
 371
 372     if(n==0)
 373        break;
 374
 375     /* Sort the data pointers using a heap sort */
 376
 377     heapsort(datap,n,compare);
 378
 379     /* Shortcut if all read in and sorted at once */
 380
 381     if(nfiles==0 && !more)
 382       {
 383        for(i=0;i<n;i++)
 384          {
 385           if(!buildindex || buildindex(datap[i],count))
 386             {
 387              FILESORT_VARINT itemsize=*(FILESORT_VARINT*)(datap[i]-FILESORT_VARSIZE);
 388
 389              WriteFile(fd_out,datap[i]-FILESORT_VARSIZE,itemsize+FILESORT_VARSIZE);
 390              count++;
 391             }
 392          }
 393
 394        goto tidy_and_exit;
 395       }
 396
 397     /* Create a temporary file and write the result */
 398
 399     sprintf(filename,"%s/filesort.%d.tmp",option_tmpdirname,nfiles);
 400
 401     fd=OpenFile(filename);
 402
 403     for(i=0;i<n;i++)
 404       {
 405        FILESORT_VARINT itemsize=*(FILESORT_VARINT*)(datap[i]-FILESORT_VARSIZE);
 406
 407        WriteFile(fd,datap[i]-FILESORT_VARSIZE,itemsize+FILESORT_VARSIZE);
 408       }
 409
 410     CloseFile(fd);
 411
 412     nfiles++;
 413    }
 414  while(more);
 415
 416  /* Check that number of files is less than file size */
 417
 418  largestitemsize=FILESORT_VARALIGN*(1+(largestitemsize+FILESORT_VARALIGN-FILESORT_VARSIZE)/FILESORT_VARALIGN);
 419
 420  assert(nfiles<((option_filesort_ramsize-nfiles*sizeof(void*))/largestitemsize));
 421
 422  /* Open all of the temporary files */
 423
 424  fds=(int*)malloc(nfiles*sizeof(int));
 425
 426  for(i=0;i<nfiles;i++)
 427    {
 428     sprintf(filename,"%s/filesort.%d.tmp",option_tmpdirname,i);
 429
 430     fds[i]=ReOpenFile(filename);
 431
 432     DeleteFile(filename);
 433    }
 434
 435  /* Perform an n-way merge using a binary heap */
 436
 437  heap=(int*)malloc(nfiles*sizeof(int));
 438
 439  datap=data+option_filesort_ramsize-nfiles*sizeof(void*);
 440
 441  /* Fill the heap to start with */
 442
 443  for(i=0;i<nfiles;i++)
 444    {
 445     int index;
 446     FILESORT_VARINT itemsize;
 447
 448     datap[i]=data+FILESORT_VARALIGN-FILESORT_VARSIZE+i*largestitemsize;
 449
 450     ReadFile(fds[i],&itemsize,FILESORT_VARSIZE);
 451
 452     *(FILESORT_VARINT*)(datap[i]-FILESORT_VARSIZE)=itemsize;
 453
 454     ReadFile(fds[i],datap[i],itemsize);
 455
 456     heap[i]=i;
 457
 458     index=i;
 459
 460     /* Bubble up the new value */
 461
 462     while(index>0 &&
 463           compare(datap[heap[index]],datap[heap[(index-1)/2]])<0)
 464       {
 465        int newindex;
 466        int temp;
 467
 468        newindex=(index-1)/2;
 469
 470        temp=heap[index];
 471        heap[index]=heap[newindex];
 472        heap[newindex]=temp;
 473
 474        index=newindex;
 475       }
 476    }
 477
 478  /* Repeatedly pull out the root of the heap and refill from the same file */
 479
 480  ndata=nfiles;
 481
 482  do
 483    {
 484     int index=0;
 485     FILESORT_VARINT itemsize;
 486
 487     if(!buildindex || buildindex(datap[heap[0]],count))
 488       {
 489        itemsize=*(FILESORT_VARINT*)(datap[heap[0]]-FILESORT_VARSIZE);
 490
 491        WriteFile(fd_out,datap[heap[0]]-FILESORT_VARSIZE,itemsize+FILESORT_VARSIZE);
 492        count++;
 493       }
 494
 495     if(ReadFile(fds[heap[0]],&itemsize,FILESORT_VARSIZE))
 496       {
 497        ndata--;
 498        heap[0]=heap[ndata];
 499       }
 500     else
 501       {
 502        *(FILESORT_VARINT*)(datap[heap[0]]-FILESORT_VARSIZE)=itemsize;
 503
 504        ReadFile(fds[heap[0]],datap[heap[0]],itemsize);
 505       }
 506
 507     /* Bubble down the new value */
 508
 509     while((2*index+2)<ndata &&
 510           (compare(datap[heap[index]],datap[heap[2*index+1]])>0 ||
 511            compare(datap[heap[index]],datap[heap[2*index+2]])>0))
 512       {
 513        int newindex;
 514        int temp;
 515
 516        if(compare(datap[heap[2*index+1]],datap[heap[2*index+2]])<0)
 517           newindex=2*index+1;
 518        else
 519           newindex=2*index+2;
 520
 521        temp=heap[newindex];
 522        heap[newindex]=heap[index];
 523        heap[index]=temp;
 524
 525        index=newindex;
 526       }
 527
 528     if((2*index+2)==ndata &&
 529        compare(datap[heap[index]],datap[heap[2*index+1]])>0)
 530       {
 531        int newindex;
 532        int temp;
 533
 534        newindex=2*index+1;
 535
 536        temp=heap[newindex];
 537        heap[newindex]=heap[index];
 538        heap[index]=temp;
 539       }
 540    }
 541  while(ndata>0);
 542
 543  /* Tidy up */
 544
 545  tidy_and_exit:
 546
 547  if(fds)
 548    {
 549     for(i=0;i<nfiles;i++)
 550        CloseFile(fds[i]);
 551     free(fds);
 552    }
 553
 554  if(heap)
 555     free(heap);
 556
 557  free(data);
 558  free(filename);
 559 }
 560
 561
 562 /*++++++++++++++++++++++++++++++++++++++
 563   A function to sort an array of pointers efficiently.
 564
 565   The data is sorted using a "Heap sort" http://en.wikipedia.org/wiki/Heapsort,
 566   in particular an this good because it can operate in-place and doesn't
 567   allocate more memory like using qsort() does.
 568
 569   void **datap A pointer to the array of pointers to sort.
 570
 571   size_t nitems The number of items of data to sort.
 572
 573   int(*compare)(const void *, const void *) The comparison function (identical to qsort if the
 574                                             data to be sorted was an array of things not pointers).
 575   ++++++++++++++++++++++++++++++++++++++*/
 576
 577 void heapsort(void **datap,size_t nitems,int(*compare)(const void*, const void*))
 578 {
 579  int i;
 580
 581  /* Fill the heap by pretending to insert the data that is already there */
 582
 583  for(i=1;i<nitems;i++)
 584    {
 585     int index=i;
 586
 587     /* Bubble up the new value (upside-down, put largest at top) */
 588
 589     while(index>0 &&
 590           compare(datap[index],datap[(index-1)/2])>0) /* reversed compared to filesort() above */
 591       {
 592        int newindex;
 593        void *temp;
 594
 595        newindex=(index-1)/2;
 596
 597        temp=datap[index];
 598        datap[index]=datap[newindex];
 599        datap[newindex]=temp;
 600
 601        index=newindex;
 602       }
 603    }
 604
 605  /* Repeatedly pull out the root of the heap and swap with the bottom item */
 606
 607  for(i=nitems-1;i>0;i--)
 608    {
 609     int index=0;
 610     void *temp;
 611
 612     temp=datap[index];
 613     datap[index]=datap[i];
 614     datap[i]=temp;
 615
 616     /* Bubble down the new value (upside-down, put largest at top) */
 617
 618     while((2*index+2)<i &&
 619           (compare(datap[index],datap[2*index+1])<0 || /* reversed compared to filesort() above */
 620            compare(datap[index],datap[2*index+2])<0))  /* reversed compared to filesort() above */
 621       {
 622        int newindex;
 623        void *temp;
 624
 625        if(compare(datap[2*index+1],datap[2*index+2])>0) /* reversed compared to filesort() above */
 626           newindex=2*index+1;
 627        else
 628           newindex=2*index+2;
 629
 630        temp=datap[newindex];
 631        datap[newindex]=datap[index];
 632        datap[index]=temp;
 633
 634        index=newindex;
 635       }
 636
 637     if((2*index+2)==i &&
 638        compare(datap[index],datap[2*index+1])<0) /* reversed compared to filesort() above */
 639       {
 640        int newindex;
 641        void *temp;
 642
 643        newindex=2*index+1;
 644
 645        temp=datap[newindex];
 646        datap[newindex]=datap[index];
 647        datap[index]=temp;
 648       }
 649    }
 650 }