destination-access/src/sorting.c

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

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

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

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

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


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

#include "types.h"

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


/* Global variables */

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

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


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

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

  index_t filesort_fixed Returns the number of objects kept.

  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 (*keep)(void *,index_t) If non-NULL then this function is called for each item, if it
                              returns 1 then the object is kept and written to the output file.
  ++++++++++++++++++++++++++++++++++++++*/

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

 /* Allocate the RAM buffer and other bits */

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

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

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

 do
   {
    int fd,n=0;

    /* Read in the data and create pointers */

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

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

       total++;
      }

    n=i;

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

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

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

    if(n==0)
       break;

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

    filesort_heapsort(datap,n,compare);

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

    if(nfiles==0 && !more)
      {
       for(i=0;i<n;i++)
         {
          if(!keep || keep(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(!keep || keep(datap[i],count))
         {
          WriteFile(fd_out,datap[i],itemsize);
          count++;
         }
      }

    DeleteFile(filename);

    goto tidy_and_exit;
   }

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

 assert(nfiles<nitems);

 /* Open all of the temporary files */

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

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

    fds[i]=ReOpenFile(filename);

    DeleteFile(filename);
   }

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

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

 /* Fill the heap to start with */

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

    datap[i]=data+i*itemsize;

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

    index=i+1;

    heap[index]=i;

    /* Bubble up the new value */

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

       newindex=index/2;

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

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

       index=newindex;
      }
   }

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

 ndata=nfiles;

 do
   {
    int index=1;

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

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

    /* Bubble down the new value */

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

       newindex=2*index;

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

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

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

       index=newindex;
      }

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

       newindex=2*index;

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

 /* Tidy up */

 tidy_and_exit:

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

 if(heap)
    free(heap);

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

 return(count);
}


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

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

  index_t filesort_vary Returns the number of objects kept.

  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 (*keep)(void *,index_t) If non-NULL then this function is called for each item, if it
                              returns 1 then the object is kept and written to the output file.
  ++++++++++++++++++++++++++++++++++++++*/

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

 /* Allocate the RAM buffer and other bits */

 data=malloc(option_filesort_ramsize);

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

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

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

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

    datap=data+option_filesort_ramsize;

    /* Read in the data and create pointers */

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

       if(itemsize>largestitemsize)
          largestitemsize=itemsize;

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

       ramused+=FILESORT_VARSIZE;

       ReadFile(fd_in,data+ramused,itemsize);

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

       ramused+=itemsize;

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

       total++;
       n++;

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

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

    if(n==0)
       break;

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

    filesort_heapsort(datap,n,compare);

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

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

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

       goto tidy_and_exit;
      }

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

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

    fd=OpenFileNew(filename);

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

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

    CloseFile(fd);

    nfiles++;
   }
 while(more);

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

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

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

 /* Open all of the temporary files */

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

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

    fds[i]=ReOpenFile(filename);

    DeleteFile(filename);
   }

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

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

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

 /* Fill the heap to start with */

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

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

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

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

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

    index=i+1;

    heap[index]=i;

    /* Bubble up the new value */

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

       newindex=index/2;

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

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

       index=newindex;
      }
   }

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

 ndata=nfiles;

 do
   {
    int index=1;
    FILESORT_VARINT itemsize;

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

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

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

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

    /* Bubble down the new value */

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

       newindex=2*index;

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

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

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

       index=newindex;
      }

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

       newindex=2*index;

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

 /* Tidy up */

 tidy_and_exit:

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

 if(heap)
    free(heap);

 free(data);
 free(filename);

 return(count);
}


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

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

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

  size_t nitems The number of items of data to sort.

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

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

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

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

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

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

       newindex=index/2;

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

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

       index=newindex;
      }
   }

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

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

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

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

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

       newindex=2*index;

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

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

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

       index=newindex;
      }

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

       newindex=2*index;

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