New approach to including locale data in the rpm.
[glibc.git] / stdlib / msort.c
blobe69b4011c48cacbaca48bcee7485d10780ac5440
1 /* An alternative to qsort, with an identical interface.
2 This file is part of the GNU C Library.
3 Copyright (C) 1992,95-97,99,2000,01,02,04 Free Software Foundation, Inc.
4 Written by Mike Haertel, September 1988.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, write to the Free
18 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19 02111-1307 USA. */
21 #include <alloca.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <unistd.h>
25 #include <memcopy.h>
26 #include <errno.h>
28 static void msort_with_tmp (void *b, size_t n, size_t s,
29 __compar_fn_t cmp, char *t);
31 static void
32 msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp,
33 char *t)
35 char *tmp;
36 char *b1, *b2;
37 size_t n1, n2;
39 if (n <= 1)
40 return;
42 n1 = n / 2;
43 n2 = n - n1;
44 b1 = b;
45 b2 = (char *) b + (n1 * s);
47 msort_with_tmp (b1, n1, s, cmp, t);
48 msort_with_tmp (b2, n2, s, cmp, t);
50 tmp = t;
52 if (s == OPSIZ && (b1 - (char *) 0) % OPSIZ == 0)
53 /* We are operating on aligned words. Use direct word stores. */
54 while (n1 > 0 && n2 > 0)
56 if ((*cmp) (b1, b2) <= 0)
58 --n1;
59 *((op_t *) tmp) = *((op_t *) b1);
60 tmp += sizeof (op_t);
61 b1 += sizeof (op_t);
63 else
65 --n2;
66 *((op_t *) tmp) = *((op_t *) b2);
67 tmp += sizeof (op_t);
68 b2 += sizeof (op_t);
71 else
72 while (n1 > 0 && n2 > 0)
74 if ((*cmp) (b1, b2) <= 0)
76 tmp = (char *) __mempcpy (tmp, b1, s);
77 b1 += s;
78 --n1;
80 else
82 tmp = (char *) __mempcpy (tmp, b2, s);
83 b2 += s;
84 --n2;
87 if (n1 > 0)
88 memcpy (tmp, b1, n1 * s);
89 memcpy (b, t, (n - n2) * s);
92 void
93 qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
95 const size_t size = n * s;
97 if (size < 1024)
99 void *buf = __alloca (size);
101 /* The temporary array is small, so put it on the stack. */
102 msort_with_tmp (b, n, s, cmp, buf);
104 else
106 /* We should avoid allocating too much memory since this might
107 have to be backed up by swap space. */
108 static long int phys_pages;
109 static int pagesize;
111 if (phys_pages == 0)
113 phys_pages = __sysconf (_SC_PHYS_PAGES);
115 if (phys_pages == -1)
116 /* Error while determining the memory size. So let's
117 assume there is enough memory. Otherwise the
118 implementer should provide a complete implementation of
119 the `sysconf' function. */
120 phys_pages = (long int) (~0ul >> 1);
122 /* The following determines that we will never use more than
123 a quarter of the physical memory. */
124 phys_pages /= 4;
126 pagesize = __sysconf (_SC_PAGESIZE);
129 /* Just a comment here. We cannot compute
130 phys_pages * pagesize
131 and compare the needed amount of memory against this value.
132 The problem is that some systems might have more physical
133 memory then can be represented with a `size_t' value (when
134 measured in bytes. */
136 /* If the memory requirements are too high don't allocate memory. */
137 if (size / pagesize > (size_t) phys_pages)
138 _quicksort (b, n, s, cmp);
139 else
141 /* It's somewhat large, so malloc it. */
142 int save = errno;
143 char *tmp = malloc (size);
144 if (tmp == NULL)
146 /* Couldn't get space, so use the slower algorithm
147 that doesn't need a temporary array. */
148 __set_errno (save);
149 _quicksort (b, n, s, cmp);
151 else
153 __set_errno (save);
154 msort_with_tmp (b, n, s, cmp, tmp);
155 free (tmp);
160 libc_hidden_def (qsort)