trunk/src/sorting.c

/***************************************
 $Header: /home/amb/CVS/routino/src/sorting.c,v 1.8 2010-04-09 15:15:02 amb Exp $

 Merge sort functions.

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

    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=OpenFile(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 */

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