Formerly ../stdlib/msort.c.~4~
[kopensolaris-gnu/glibc.git] / stdlib / msort.c
1 /* msort -- an alternative to qsort, with an identical interface.
2    Copyright (C) 1988 Mike Haertel
3    Written by Mike Haertel, September 1988.  */
4
5 #include <ansidecl.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 #define MEMCPY(dst, src, s)                     \
10   ((s) == sizeof (int)                          \
11    ? (*(int *) (dst) = *(int *) (src), (dst))   \
12    : memcpy (dst, src, s))
13
14 static void
15 DEFUN(msort_with_tmp, (b, n, s, cmp, t),
16       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp AND char *t)
17 {
18   char *tmp;
19   char *b1, *b2;
20   size_t n1, n2;
21
22   if (n <= 1)
23     return;
24
25   n1 = n / 2;
26   n2 = n - n1;
27   b1 = b;
28   b2 = (char *) b + (n1 * s);
29
30   msort_with_tmp (b1, n1, s, cmp, t);
31   msort_with_tmp (b2, n2, s, cmp, t);
32
33   tmp = t;
34
35   while (n1 > 0 && n2 > 0)
36     {
37       if ((*cmp) (b1, b2) <= 0)
38         {
39           MEMCPY (tmp, b1, s);
40           b1 += s;
41           --n1;
42         }
43       else
44         {
45           MEMCPY (tmp, b2, s);
46           b2 += s;
47           --n2;
48         }
49       tmp += s;
50     }
51   if (n1 > 0)
52     memcpy (tmp, b1, n1 * s);
53   memcpy (b, t, (n - n2) * s);
54 }
55
56 void
57 DEFUN(msort, (b, n, s, cmp),
58       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp)
59 {
60   CONST size_t size = n * s;
61
62   if (size < 1024)
63     /* The temporary array is small, so put it on the stack.  */
64     msort_with_tmp (b, n, s, cmp, __alloca (size));
65   else
66     {
67       /* It's somewhat large, so malloc it.  */
68       int save = errno;
69       char *tmp = malloc (size);
70       if (tmp == NULL)
71         /* Couldn't get space, so use the slower algorithm
72            that doesn't need a temporary array.  */
73         qsort (b, n, s, cmp);
74       else
75         {
76           msort_with_tmp (b, n, s, cmp, tmp);
77           free (tmp);
78         }
79       errno = save;
80     }
81 }