trunk/src/sorting.c

/***************************************
 Merge sort functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2009-2011 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "types.h"

#include "files.h"
#include "sorting.h"


/* Global variables */

/*+ The command line '--tmpdir' option or its default value. +*/
extern char *option_tmpdirname;

/*+ The amount of RAM to use for filesorting. +*/
extern size_t option_filesort_ramsize;


/*++++++++++++++++++++++++++++++++++++++
  A function to sort the contents of a file of fixed length objects using a
  limited amount of RAM.

  The data is sorted using a "Merge sort" http://en.wikipedia.org/wiki/Merge_sort
  and in particular an "external sort" http://en.wikipedia.org/wiki/External_sorting.
  The individual sort steps and the merge step both use a "Heap sort"
  http://en.wikipedia.org/wiki/Heapsort.  The combination of the two should work well
  if the data is already partially sorted.

  int fd_in The file descriptor of the input file (opened for reading and at the beginning).

  int fd_out The file descriptor of the output file (opened for writing and empty).

  size_t itemsize The size of each item in the file that needs sorting.

  int (*compare)(const void*, const void*) The comparison function (identical to qsort if the
                                           data to be sorted is an array of things not pointers).

  int (*buildindex)(void *,index_t) If non-NULL then this function is called for each item, if it
                                    returns 1 then it is written to the output file.
  ++++++++++++++++++++++++++++++++++++++*/

void filesort_fixed(int fd_in,int fd_out,size_t itemsize,int (*compare)(const void*,const void*),int (*buildindex)(void*,index_t))
{
 int *fds=NULL,*heap=NULL;
 int nfiles=0,ndata=0;
 index_t count=0,total=0;
 size_t nitems=option_filesort_ramsize/(itemsize+sizeof(void*));
 void *data=NULL,**datap=NULL;
 char *filename;
 int i,more=1;

 /* Allocate the RAM buffer and other bits */

 data=malloc(nitems*itemsize);
 datap=malloc(nitems*sizeof(void*));

 filename=(char*)malloc(strlen(option_tmpdirname)+24);

 /* Loop around, fill the buffer, sort the data and write a temporary file */

 do
   {
    int fd,n=0;

    /* Read in the data and create pointers */

    for(i=0;i<nitems;i++)
      {
       datap[i]=data+i*itemsize;

       if(ReadFile(fd_in,datap[i],itemsize))
         {
          more=0;
          break;
         }

       total++;
      }

    n=i;

    /* Shortcut if there is no data and no previous files (i.e. no data at all) */

    if(nfiles==0 && n==0)
       goto tidy_and_exit;

    /* No new data read in this time round */

    if(n==0)
       break;

    /* Sort the data pointers using a heap sort */

    filesort_heapsort(datap,n,compare);

    /* Shortcut if all read in and sorted at once */

    if(nfiles==0 && !more)
      {
       for(i=0;i<n;i++)
         {
          if(!buildindex || buildindex(datap[i],count))
            {
             WriteFile(fd_out,datap[i],itemsize);
             count++;
            }
         }

       goto tidy_and_exit;
      }

    /* Create a temporary file and write the result */

    sprintf(filename,"%s/filesort.%d.tmp",option_tmpdirname,nfiles);

    fd=OpenFileNew(filename);

    for(i=0;i<n;i++)
       WriteFile(fd,datap[i],itemsize);

    CloseFile(fd);

    nfiles++;
   }
 while(more);

 /* Shortcut if only one file (unlucky for us there must have been exactly
    nitems, lucky for us we still have the data in RAM) */

 if(nfiles==1)
   {
    for(i=0;i<nitems;i++)
      {
       if(!buildindex || buildindex(datap[i],count))
         {
          WriteFile(fd_out,datap[i],itemsize);
          count++;
         }
      }

    DeleteFile(filename);

    goto tidy_and_exit;
   }

 /* Check that number of files is less than file size */

 assert(nfiles<nitems);

 /* Open all of the temporary files */

 fds=(int*)malloc(nfiles*sizeof(int));

 for(i=0;i<nfiles;i++)
   {
    sprintf(filename,"%s/filesort.%d.tmp",option_tmpdirname,i);

    fds[i]=ReOpenFile(filename);

    DeleteFile(filename);
   }

 /* Perform an n-way merge using a binary heap */

 heap=(int*)malloc((1+nfiles)*sizeof(int));

 /* Fill the heap to start with */

 for(i=0;i<nfiles;i++)
   {
    int index;

    datap[i]=data+i*itemsize;

    ReadFile(fds[i],datap[i],itemsize);

    index=i+1;

    heap[index]=i;

    /* Bubble up the new value */

    while(index>1)
      {
       int newindex;
       int temp;

       newindex=index/2;

       if(compare(datap[heap[index]],datap[heap[newindex]])>=0)
          break;

       temp=heap[index];
       heap[index]=heap[newindex];
       heap[newindex]=temp;

       index=newindex;
      }
   }

 /* Repeatedly pull out the root of the heap and refill from the same file */

 ndata=nfiles;

 do
   {
    int index=1;

    if(!buildindex || buildindex(datap[heap[index]],count))
      {
       WriteFile(fd_out,datap[heap[index]],itemsize);
       count++;
      }

    if(ReadFile(fds[heap[index]],datap[heap[index]],itemsize))
      {
       heap[index]=heap[ndata];
       ndata--;
      }

    /* Bubble down the new value */

    while((2*index)<ndata)
      {
       int newindex;
       int temp;

       newindex=2*index;

       if(compare(datap[heap[newindex]],datap[heap[newindex+1]])>=0)
          newindex=newindex+1;

       if(compare(datap[heap[index]],datap[heap[newindex]])<=0)
          break;

       temp=heap[newindex];
       heap[newindex]=heap[index];
       heap[index]=temp;

       index=newindex;
      }

    if((2*index)==ndata)
      {
       int newindex;
       int temp;

       newindex=2*index;

       if(compare(datap[heap[index]],datap[heap[newindex]])<=0)
          ; /* break */
       else
         {
          temp=heap[newindex];
          heap[newindex]=heap[index];
          heap[index]=temp;
         }
      }
   }
 while(ndata>0);

 /* Tidy up */

 tidy_and_exit:

 if(fds)
   {
    for(i=0;i<nfiles;i++)
       CloseFile(fds[i]);
    free(fds);
   }

 if(heap)
    free(heap);

 free(data);
 free(datap);
 free(filename);
}


/*++++++++++++++++++++++++++++++++++++++
  A function to sort the contents of a file of variable length objects (each
  preceded by its length in FILESORT_VARSIZE bytes) using a limited amount of RAM.

  The data is sorted using a "Merge sort" http://en.wikipedia.org/wiki/Merge_sort
  and in particular an "external sort" http://en.wikipedia.org/wiki/External_sorting.
  The individual sort steps and the merge step both use a "Heap sort"
  http://en.wikipedia.org/wiki/Heapsort.  The combination of the two should work well
  if the data is already partially sorted.

  int fd_in The file descriptor of the input file (opened for reading and at the beginning).

  int fd_out The file descriptor of the output file (opened for writing and empty).

  int (*compare)(const void*, const void*) The comparison function (identical to qsort if the
                                           data to be sorted is an array of things not pointers).

  int (*buildindex)(void *,index_t) If non-NULL then this function is called for each item, if it
                                    returns 1 then it is written to the output file.
  ++++++++++++++++++++++++++++++++++++++*/

void filesort_vary(int fd_in,int fd_out,int (*compare)(const void*,const void*),int (*buildindex)(void*,index_t))
{
 int *fds=NULL,*heap=NULL;
 int nfiles=0,ndata=0;
 index_t count=0,total=0;
 FILESORT_VARINT nextitemsize,largestitemsize=0;
 void *data=NULL,**datap=NULL;
 char *filename;
 int i,more=1;

 /* Allocate the RAM buffer and other bits */

 data=malloc(option_filesort_ramsize);

 filename=(char*)malloc(strlen(option_tmpdirname)+24);

 /* Loop around, fill the buffer, sort the data and write a temporary file */

 if(ReadFile(fd_in,&nextitemsize,FILESORT_VARSIZE))    /* Always have the next item size known in advance */
    goto tidy_and_exit;

 do
   {
    int fd,n=0;
    size_t ramused=FILESORT_VARALIGN-FILESORT_VARSIZE;

    datap=data+option_filesort_ramsize;

    /* Read in the data and create pointers */

    while((ramused+FILESORT_VARSIZE+nextitemsize)<=((void*)datap-sizeof(void*)-data))
      {
       FILESORT_VARINT itemsize=nextitemsize;

       if(itemsize>largestitemsize)
          largestitemsize=itemsize;

       *(FILESORT_VARINT*)(data+ramused)=itemsize;

       ramused+=FILESORT_VARSIZE;

       ReadFile(fd_in,data+ramused,itemsize);

       *--datap=data+ramused; /* points to real data */

       ramused+=itemsize;

       ramused =FILESORT_VARALIGN*((ramused+FILESORT_VARSIZE-1)/FILESORT_VARALIGN);
       ramused+=FILESORT_VARALIGN-FILESORT_VARSIZE;

       total++;
       n++;

       if(ReadFile(fd_in,&nextitemsize,FILESORT_VARSIZE))
         {
          more=0;
          break;
         }
      }

    /* No new data read in this time round */

    if(n==0)
       break;

    /* Sort the data pointers using a heap sort */

    filesort_heapsort(datap,n,compare);

    /* Shortcut if all read in and sorted at once */

    if(nfiles==0 && !more)
      {
       for(i=0;i<n;i++)
         {
          if(!buildindex || buildindex(datap[i],count))
            {
             FILESORT_VARINT itemsize=*(FILESORT_VARINT*)(datap[i]-FILESORT_VARSIZE);

             WriteFile(fd_out,datap[i]-FILESORT_VARSIZE,itemsize+FILESORT_VARSIZE);
             count++;
            }
         }

       goto tidy_and_exit;
      }

    /* Create a temporary file and write the result */

    sprintf(filename,"%s/filesort.%d.tmp",option_tmpdirname,nfiles);

    fd=OpenFileNew(filename);

    for(i=0;i<n;i++)
      {
       FILESORT_VARINT itemsize=*(FILESORT_VARINT*)(datap[i]-FILESORT_VARSIZE);

       WriteFile(fd,datap[i]-FILESORT_VARSIZE,itemsize+FILESORT_VARSIZE);
      }

    CloseFile(fd);

    nfiles++;
   }
 while(more);

 /* Check that number of files is less than file size */

 largestitemsize=FILESORT_VARALIGN*(1+(largestitemsize+FILESORT_VARALIGN-FILESORT_VARSIZE)/FILESORT_VARALIGN);

 assert(nfiles<((option_filesort_ramsize-nfiles*sizeof(void*))/largestitemsize));

 /* Open all of the temporary files */

 fds=(int*)malloc(nfiles*sizeof(int));

 for(i=0;i<nfiles;i++)
   {
    sprintf(filename,"%s/filesort.%d.tmp",option_tmpdirname,i);

    fds[i]=ReOpenFile(filename);

    DeleteFile(filename);
   }

 /* Perform an n-way merge using a binary heap */

 heap=(int*)malloc((1+nfiles)*sizeof(int));

 datap=data+option_filesort_ramsize-nfiles*sizeof(void*);

 /* Fill the heap to start with */

 for(i=0;i<nfiles;i++)
   {
    int index;
    FILESORT_VARINT itemsize;

    datap[i]=data+FILESORT_VARALIGN-FILESORT_VARSIZE+i*largestitemsize;

    ReadFile(fds[i],&itemsize,FILESORT_VARSIZE);

    *(FILESORT_VARINT*)(datap[i]-FILESORT_VARSIZE)=itemsize;

    ReadFile(fds[i],datap[i],itemsize);

    index=i+1;

    heap[index]=i;

    /* Bubble up the new value */

    while(index>1)
      {
       int newindex;
       int temp;

       newindex=index/2;

       if(compare(datap[heap[index]],datap[heap[newindex]])>=0)
          break;

       temp=heap[index];
       heap[index]=heap[newindex];
       heap[newindex]=temp;

       index=newindex;
      }
   }

 /* Repeatedly pull out the root of the heap and refill from the same file */

 ndata=nfiles;

 do
   {
    int index=1;
    FILESORT_VARINT itemsize;

    if(!buildindex || buildindex(datap[heap[index]],count))
      {
       itemsize=*(FILESORT_VARINT*)(datap[heap[index]]-FILESORT_VARSIZE);

       WriteFile(fd_out,datap[heap[index]]-FILESORT_VARSIZE,itemsize+FILESORT_VARSIZE);
       count++;
      }

    if(ReadFile(fds[heap[index]],&itemsize,FILESORT_VARSIZE))
      {
       heap[index]=heap[ndata];
       ndata--;
      }
    else
      {
       *(FILESORT_VARINT*)(datap[heap[index]]-FILESORT_VARSIZE)=itemsize;

       ReadFile(fds[heap[index]],datap[heap[index]],itemsize);
      }

    /* Bubble down the new value */

    while((2*index)<ndata)
      {
       int newindex;
       int temp;

       newindex=2*index;

       if(compare(datap[heap[newindex]],datap[heap[newindex+1]])>=0)
          newindex=newindex+1;

       if(compare(datap[heap[index]],datap[heap[newindex]])<=0)
          break;

       temp=heap[newindex];
       heap[newindex]=heap[index];
       heap[index]=temp;

       index=newindex;
      }

    if((2*index)==ndata)
      {
       int newindex;
       int temp;

       newindex=2*index;

       if(compare(datap[heap[index]],datap[heap[newindex]])<=0)
          ; /* break */
       else
         {
          temp=heap[newindex];
          heap[newindex]=heap[index];
          heap[index]=temp;
         }
      }
   }
 while(ndata>0);

 /* Tidy up */

 tidy_and_exit:

 if(fds)
   {
    for(i=0;i<nfiles;i++)
       CloseFile(fds[i]);
    free(fds);
   }

 if(heap)
    free(heap);

 free(data);
 free(filename);
}


/*++++++++++++++++++++++++++++++++++++++
  A function to sort an array of pointers efficiently.

  The data is sorted using a "Heap sort" http://en.wikipedia.org/wiki/Heapsort,
  in particular, this is good because it can operate in-place and doesn't
  allocate more memory like using qsort() does.

  void **datap A pointer to the array of pointers to sort.

  size_t nitems The number of items of data to sort.

  int(*compare)(const void *, const void *) The comparison function (identical to qsort if the
                                            data to be sorted was an array of things not pointers).
  ++++++++++++++++++++++++++++++++++++++*/

void filesort_heapsort(void **datap,size_t nitems,int(*compare)(const void*, const void*))
{
 void **datap1=&datap[-1];
 int i;

 /* Fill the heap by pretending to insert the data that is already there */

 for(i=2;i<=nitems;i++)
   {
    int index=i;

    /* Bubble up the new value (upside-down, put largest at top) */

    while(index>1)
      {
       int newindex;
       void *temp;

       newindex=index/2;

       if(compare(datap1[index],datap1[newindex])<=0) /* reversed compared to filesort_fixed() above */
          break;

       temp=datap1[index];
       datap1[index]=datap1[newindex];
       datap1[newindex]=temp;

       index=newindex;
      }
   }

 /* Repeatedly pull out the root of the heap and swap with the bottom item */

 for(i=nitems;i>1;i--)
   {
    int index=1;
    void *temp;

    temp=datap1[index];
    datap1[index]=datap1[i];
    datap1[i]=temp;

    /* Bubble down the new value (upside-down, put largest at top) */

    while((2*index)<(i-1))
      {
       int newindex;
       void *temp;

       newindex=2*index;

       if(compare(datap1[newindex],datap1[newindex+1])<=0) /* reversed compared to filesort_fixed() above */
          newindex=newindex+1;

       if(compare(datap1[index],datap1[newindex])>=0) /* reversed compared to filesort_fixed() above */
          break;

       temp=datap1[newindex];
       datap1[newindex]=datap1[index];
       datap1[index]=temp;

       index=newindex;
      }

    if((2*index)==(i-1))
      {
       int newindex;
       void *temp;

       newindex=2*index;

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