7d21c10fc9ac3bebbf44503c669d02cea5cc94b9
[kopensolaris-gnu/glibc.git] / stdlib / msort.c
1 /* An alternative to qsort, with an identical interface.
2    This file is part of the GNU C Library.
3    Copyright (C) 1992, 1995-1997, 1999, 2000, 2001, 2002
4    Free Software Foundation, Inc.
5    Original Implementation by Mike Haertel, September 1988.
6    Towers of Hanoi Mergesort by Roger Sayle, January 2002.
7
8    The GNU C Library is free software; you can redistribute it and/or
9    modify it under the terms of the GNU Lesser General Public
10    License as published by the Free Software Foundation; either
11    version 2.1 of the License, or (at your option) any later version.
12
13    The GNU C Library 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 GNU
16    Lesser General Public License for more details.
17
18    You should have received a copy of the GNU Lesser General Public
19    License along with the GNU C Library; if not, write to the Free
20    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21    02111-1307 USA.  */
22
23 #include <alloca.h>
24 #include <limits.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <unistd.h>
28 #include <memcopy.h>
29 #include <errno.h>
30
31
32 /* Check whether pointer P is aligned for access by type T. */
33 #define TYPE_ALIGNED(P,T)  (((char *) (P) - (char *) 0) % __alignof__ (T) == 0)
34
35
36 static int hanoi_sort (char *b, size_t n, size_t s,
37                         __compar_fn_t cmp, char *t);
38 static int hanoi_sort_int (int *b, size_t n,
39                            __compar_fn_t cmp, int *t);
40 #if INT_MAX != LONG_MAX
41 static int hanoi_sort_long (long int *b, size_t n,
42                             __compar_fn_t cmp, long int *t);
43 #endif
44 static void msort_with_tmp (void *b, size_t n, size_t s,
45                             __compar_fn_t cmp, void *t);
46
47
48 /* This routine implements "Towers of Hanoi Mergesort".  The algorithm
49    sorts the n elements of size s pointed to by array b using comparison
50    function cmp.  The argument t points to a suitable temporary buffer.
51    If the return value is zero, the sorted array is returned in b, and
52    for non-zero return values the sorted array is returned in t.  */
53 static int
54 hanoi_sort (char *b, size_t n, size_t s, __compar_fn_t cmp, char *t)
55 {
56   size_t n1, n2;
57   char *b1,*b2;
58   char *t1,*t2;
59   char *s1,*s2;
60   size_t size;
61   int result;
62   char *ptr;
63
64   if (n <= 1)
65     return 0;
66
67   if (n == 2)
68     {
69       b2 = b + s;
70       if ((*cmp) (b, b2) <= 0)
71         return 0;
72       memcpy (__mempcpy (t, b2, s), b, s);
73       return 1;
74     }
75
76   n1 = n/2;
77   n2 = n - n1;
78   /* n1 < n2!  */
79
80   size = n1 * s;
81   b1 = b;
82   b2 = b + size;
83
84   t1 = t;
85   t2 = t + size;
86
87   /* Recursively call hanoi_sort to sort the two halves of the array.
88      Depending upon the return values, determine the values s1 and s2
89      the locations of the two sorted subarrays, ptr, the location to
90      contain the sorted array and result, the return value for this
91      function.  Note that "ptr = result? t : b".  */
92   if (hanoi_sort (b1, n1, s, cmp, t1))
93     {
94       if (hanoi_sort (b2, n2, s, cmp, t2))
95         {
96           result = 0;
97           ptr = b;
98           s1 = t1;
99           s2 = t2;
100         }
101       else
102         {
103           result = 0;
104           ptr = b;
105           s1 = t1;
106           s2 = b2;
107         }
108     }
109   else
110     {
111       if (hanoi_sort (b2, n2, s, cmp, t2))
112         {
113           result = 1;
114           ptr = t;
115           s1 = b1;
116           s2 = t2;
117         }
118       else
119         {
120           result = 1;
121           ptr = t;
122           s1 = b1;
123           s2 = b2;
124         }
125     }
126
127   /*  Merge the two sorted arrays s1 and s2 of n1 and n2 elements
128       respectively, placing the result in ptr.  On entry, n1 > 0
129       && n2 > 0, and with each iteration either n1 or n2 is decreased
130       until either reaches zero, and the loop terminates via return.  */
131   for (;;)
132     {
133       if ((*cmp) (s1, s2) <= 0)
134         {
135           ptr = (char *) __mempcpy (ptr, s1, s);
136           s1 += s;
137           --n1;
138           if (n1 == 0)
139             {
140               if (ptr != s2)
141                 memcpy (ptr, s2, n2 * s);
142               return result;
143             }
144         }
145       else
146         {
147           ptr = (char *) __mempcpy (ptr, s2, s);
148           s2 += s;
149           --n2;
150           if (n2 == 0)
151             {
152               memcpy (ptr, s1, n1 * s);
153               return result;
154             }
155         }
156     }
157 }
158
159
160 /* This routine is a variant of hanoi_sort that is optimized for the
161    case where items to be sorted are the size of ints, and both b and
162    t are suitably aligned.  The parameter s in not needed as it is
163    known to be sizeof(int).  */
164 static int
165 hanoi_sort_int (int *b, size_t n, __compar_fn_t cmp, int *t)
166 {
167   size_t n1, n2;
168   int *b1,*b2;
169   int *t1,*t2;
170   int *s1,*s2;
171   int result;
172   int *ptr;
173
174   if (n <= 1)
175     return 0;
176
177   if (n == 2)
178     {
179       if ((*cmp) (b, b + 1) <= 0)
180         return 0;
181       t[0] = b[1];
182       t[1] = b[0];
183       return 1;
184     }
185
186   n1 = n/2;
187   n2 = n - n1;
188   /* n1 < n2!  */
189
190   b1 = b;
191   b2 = b + n1;
192
193   t1 = t;
194   t2 = t + n1;
195
196   /* Recursively call hanoi_sort_int to sort the two halves.  */
197   if (hanoi_sort_int (b1, n1, cmp, t1))
198     {
199       if (hanoi_sort_int (b2, n2, cmp, t2))
200         {
201           result = 0;
202           ptr = b;
203           s1 = t1;
204           s2 = t2;
205         }
206       else
207         {
208           result = 0;
209           ptr = b;
210           s1 = t1;
211           s2 = b2;
212         }
213     }
214   else
215     {
216       if (hanoi_sort_int (b2, n2, cmp, t2))
217         {
218           result = 1;
219           ptr = t;
220           s1 = b1;
221           s2 = t2;
222         }
223       else
224         {
225           result = 1;
226           ptr = t;
227           s1 = b1;
228           s2 = b2;
229         }
230     }
231
232   /*  Merge n1 elements from s1 and n2 elements from s2 into ptr.  */
233   for (;;)
234     {
235       if ((*cmp) (s1, s2) <= 0)
236         {
237           *ptr++ = *s1++;
238           --n1;
239           if (n1 == 0)
240             {
241               if (ptr != s2)
242                 memcpy (ptr, s2, n2 * sizeof (int));
243               return result;
244             }
245         }
246       else
247         {
248           *ptr++ = *s2++;
249           --n2;
250           if (n2 == 0)
251             {
252               memcpy (ptr, s1, n1 * sizeof (int));
253               return result;
254             }
255         }
256     }
257 }
258
259
260 #if INT_MAX != LONG_MAX
261 /* This routine is a variant of hanoi_sort that is optimized for the
262    case where items to be sorted are the size of longs, and both b and
263    t are suitably aligned.  The parameter s in not needed as it is
264    known to be sizeof(long).  In case sizeof(int)== sizeof(long) we
265    do not need this code since it would be the same as hanoi_sort_int.  */
266 static int
267 hanoi_sort_long (long int *b, size_t n, __compar_fn_t cmp, long int *t)
268 {
269   size_t n1, n2;
270   long int *b1,*b2;
271   long int *t1,*t2;
272   long int *s1,*s2;
273   int result;
274   long int *ptr;
275
276   if (n <= 1)
277     return 0;
278
279   if (n == 2)
280     {
281       if ((*cmp) (b, b + 1) <= 0)
282         return 0;
283       t[0] = b[1];
284       t[1] = b[0];
285       return 1;
286     }
287
288   n1 = n/2;
289   n2 = n - n1;
290   /* n1 < n2!  */
291
292   b1 = b;
293   b2 = b + n1;
294
295   t1 = t;
296   t2 = t + n1;
297
298   /* Recursively call hanoi_sort_long to sort the two halves.  */
299   if (hanoi_sort_long (b1, n1, cmp, t1))
300     {
301       if (hanoi_sort_long (b2, n2, cmp, t2))
302         {
303           result = 0;
304           ptr = b;
305           s1 = t1;
306           s2 = t2;
307         }
308       else
309         {
310           result = 0;
311           ptr = b;
312           s1 = t1;
313           s2 = b2;
314         }
315     }
316   else
317     {
318       if (hanoi_sort_long (b2, n2, cmp, t2))
319         {
320           result = 1;
321           ptr = t;
322           s1 = b1;
323           s2 = t2;
324         }
325       else
326         {
327           result = 1;
328           ptr = t;
329           s1 = b1;
330           s2 = b2;
331         }
332     }
333
334   /*  Merge n1 elements from s1 and n2 elements from s2 into ptr.  */
335   for (;;)
336     {
337       if ((*cmp) (s1, s2) <= 0)
338         {
339           *ptr++ = *s1++;
340           --n1;
341           if (n1 == 0)
342             {
343               if (ptr != s2)
344                 memcpy (ptr, s2, n2 * sizeof (long));
345               return result;
346             }
347         }
348       else
349         {
350           *ptr++ = *s2++;
351           --n2;
352           if (n2 == 0)
353             {
354               memcpy (ptr, s1, n1 * sizeof (long));
355               return result;
356             }
357         }
358     }
359 }
360 #endif
361
362
363 /* This routine preserves the original interface to msort_with_tmp and
364    determines which variant of hanoi_sort to call, based upon item size
365    and alignment.  */
366
367 static void
368 msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp, void *t)
369 {
370   const size_t size = n * s;
371
372   if (s == sizeof (int) && TYPE_ALIGNED (b, int))
373     {
374       if (hanoi_sort_int (b, n, cmp, t))
375         memcpy (b, t, size);
376     }
377 #if INT_MAX != LONG_MAX
378   else if (s == sizeof (long int) && TYPE_ALIGNED (b, long int))
379     {
380       if (hanoi_sort_long (b, n, cmp, t))
381         memcpy (b, t, size);
382     }
383 #endif
384   else
385     {
386       /* Call the generic implementation.  */
387       if (hanoi_sort (b, n, s, cmp, t))
388         memcpy (b, t, size);
389     }
390 }
391
392 void
393 qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
394 {
395   const size_t size = n * s;
396
397   if (size < 1024)
398     {
399       void *buf = __alloca (size);
400
401       /* The temporary array is small, so put it on the stack.  */
402       msort_with_tmp (b, n, s, cmp, buf);
403     }
404   else
405     {
406       /* We should avoid allocating too much memory since this might
407          have to be backed up by swap space.  */
408       static long int phys_pages;
409       static int pagesize;
410
411       if (phys_pages == 0)
412         {
413           phys_pages = __sysconf (_SC_PHYS_PAGES);
414
415           if (phys_pages == -1)
416             /* Error while determining the memory size.  So let's
417                assume there is enough memory.  Otherwise the
418                implementer should provide a complete implementation of
419                the `sysconf' function.  */
420             phys_pages = (long int) (~0ul >> 1);
421
422           /* The following determines that we will never use more than
423              a quarter of the physical memory.  */
424           phys_pages /= 4;
425
426           pagesize = __sysconf (_SC_PAGESIZE);
427         }
428
429       /* Just a comment here.  We cannot compute
430            phys_pages * pagesize
431            and compare the needed amount of memory against this value.
432            The problem is that some systems might have more physical
433            memory then can be represented with a `size_t' value (when
434            measured in bytes.  */
435
436       /* If the memory requirements are too high don't allocate memory.  */
437       if ((long int) (size / pagesize) > phys_pages)
438         _quicksort (b, n, s, cmp);
439       else
440         {
441           /* It's somewhat large, so malloc it.  */
442           int save = errno;
443           char *tmp = malloc (size);
444           if (tmp == NULL)
445             {
446               /* Couldn't get space, so use the slower algorithm
447                  that doesn't need a temporary array.  */
448               __set_errno (save);
449               _quicksort (b, n, s, cmp);
450             }
451           else
452             {
453               __set_errno (save);
454               msort_with_tmp (b, n, s, cmp, tmp);
455               free (tmp);
456             }
457         }
458     }
459 }