trunk/src/sorting.c

/***************************************
 $Header: /home/amb/CVS/routino/src/sorting.c,v 1.12 2010-11-27 14:56:37 amb Exp $

 Merge sort functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2009-2010 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"


/* 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;

    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(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);

    heap[i]=i;

    index=i;

    /* Bubble up the new value */

    while(index>0 &&
          compare(datap[heap[index]],datap[heap[(index-1)/2]])<0)
      {
       int newindex;
       int temp;

       newindex=(index-1)/2;

       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=0;

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

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

    /* Bubble down the new value */

    while((2*index+2)<ndata &&
          (compare(datap[heap[index]],datap[heap[2*index+1]])>0 ||
           compare(datap[heap[index]],datap[heap[2*index+2]])>0))
      {
       int newindex;
       int temp;

       if(compare(datap[heap[2*index+1]],datap[heap[2*index+2]])<0)
          newindex=2*index+1;
       else
          newindex=2*index+2;

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

       index=newindex;
      }

    if((2*index+2)==ndata &&
       compare(datap[heap[index]],datap[heap[2*index+1]])>0)
      {
       int newindex;
       int temp;

       newindex=2*index+1;

       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 2 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;
         }
      }

    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(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);

    heap[i]=i;

    index=i;

    /* Bubble up the new value */

    while(index>0 &&
          compare(datap[heap[index]],datap[heap[(index-1)/2]])<0)
      {
       int newindex;
       int temp;

       newindex=(index-1)/2;

       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=0;
    FILESORT_VARINT itemsize;

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

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

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

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

    /* Bubble down the new value */

    while((2*index+2)<ndata &&
          (compare(datap[heap[index]],datap[heap[2*index+1]])>0 ||
           compare(datap[heap[index]],datap[heap[2*index+2]])>0))
      {
       int newindex;
       int temp;

       if(compare(datap[heap[2*index+1]],datap[heap[2*index+2]])<0)
          newindex=2*index+1;
       else
          newindex=2*index+2;

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

       index=newindex;
      }

    if((2*index+2)==ndata &&
       compare(datap[heap[index]],datap[heap[2*index+1]])>0)
      {
       int newindex;
       int temp;

       newindex=2*index+1;

       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 an this 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*))
{
 int i;

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

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

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

    while(index>0 &&
          compare(datap[index],datap[(index-1)/2])>0) /* reversed compared to filesort() above */
      {
       int newindex;
       void *temp;

       newindex=(index-1)/2;

       temp=datap[index];
       datap[index]=datap[newindex];
       datap[newindex]=temp;

       index=newindex;
      }
   }

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

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

    temp=datap[index];
    datap[index]=datap[i];
    datap[i]=temp;

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

    while((2*index+2)<i &&
          (compare(datap[index],datap[2*index+1])<0 || /* reversed compared to filesort() above */
           compare(datap[index],datap[2*index+2])<0))  /* reversed compared to filesort() above */
      {
       int newindex;
       void *temp;

       if(compare(datap[2*index+1],datap[2*index+2])>0) /* reversed compared to filesort() above */
          newindex=2*index+1;
       else
          newindex=2*index+2;

       temp=datap[newindex];
       datap[newindex]=datap[index];
       datap[index]=temp;

       index=newindex;
      }

    if((2*index+2)==i &&
       compare(datap[index],datap[2*index+1])<0) /* reversed compared to filesort() above */
      {
       int newindex;
       void *temp;

       newindex=2*index+1;

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