trunk/src/sorting.c

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