1*fae548d3Szrj /* Sorting algorithms.
2*fae548d3Szrj Copyright (C) 2000-2020 Free Software Foundation, Inc.
3*fae548d3Szrj Contributed by Mark Mitchell <mark@codesourcery.com>.
4*fae548d3Szrj
5*fae548d3Szrj This file is part of GNU CC.
6*fae548d3Szrj
7*fae548d3Szrj GNU CC is free software; you can redistribute it and/or modify it
8*fae548d3Szrj under the terms of the GNU General Public License as published by
9*fae548d3Szrj the Free Software Foundation; either version 2, or (at your option)
10*fae548d3Szrj any later version.
11*fae548d3Szrj
12*fae548d3Szrj GNU CC is distributed in the hope that it will be useful, but
13*fae548d3Szrj WITHOUT ANY WARRANTY; without even the implied warranty of
14*fae548d3Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15*fae548d3Szrj General Public License for more details.
16*fae548d3Szrj
17*fae548d3Szrj You should have received a copy of the GNU General Public License
18*fae548d3Szrj along with GNU CC; see the file COPYING. If not, write to
19*fae548d3Szrj the Free Software Foundation, 51 Franklin Street - Fifth Floor,
20*fae548d3Szrj Boston, MA 02110-1301, USA. */
21*fae548d3Szrj
22*fae548d3Szrj #ifdef HAVE_CONFIG_H
23*fae548d3Szrj #include "config.h"
24*fae548d3Szrj #endif
25*fae548d3Szrj #include "libiberty.h"
26*fae548d3Szrj #include "sort.h"
27*fae548d3Szrj #ifdef HAVE_LIMITS_H
28*fae548d3Szrj #include <limits.h>
29*fae548d3Szrj #endif
30*fae548d3Szrj #ifdef HAVE_SYS_PARAM_H
31*fae548d3Szrj #include <sys/param.h>
32*fae548d3Szrj #endif
33*fae548d3Szrj #ifdef HAVE_STDLIB_H
34*fae548d3Szrj #include <stdlib.h>
35*fae548d3Szrj #endif
36*fae548d3Szrj #ifdef HAVE_STRING_H
37*fae548d3Szrj #include <string.h>
38*fae548d3Szrj #endif
39*fae548d3Szrj
40*fae548d3Szrj #ifndef UCHAR_MAX
41*fae548d3Szrj #define UCHAR_MAX ((unsigned char)(-1))
42*fae548d3Szrj #endif
43*fae548d3Szrj
44*fae548d3Szrj /* POINTERS and WORK are both arrays of N pointers. When this
45*fae548d3Szrj function returns POINTERS will be sorted in ascending order. */
46*fae548d3Szrj
sort_pointers(size_t n,void ** pointers,void ** work)47*fae548d3Szrj void sort_pointers (size_t n, void **pointers, void **work)
48*fae548d3Szrj {
49*fae548d3Szrj /* The type of a single digit. This can be any unsigned integral
50*fae548d3Szrj type. When changing this, DIGIT_MAX should be changed as
51*fae548d3Szrj well. */
52*fae548d3Szrj typedef unsigned char digit_t;
53*fae548d3Szrj
54*fae548d3Szrj /* The maximum value a single digit can have. */
55*fae548d3Szrj #define DIGIT_MAX (UCHAR_MAX + 1)
56*fae548d3Szrj
57*fae548d3Szrj /* The Ith entry is the number of elements in *POINTERSP that have I
58*fae548d3Szrj in the digit on which we are currently sorting. */
59*fae548d3Szrj unsigned int count[DIGIT_MAX];
60*fae548d3Szrj /* Nonzero if we are running on a big-endian machine. */
61*fae548d3Szrj int big_endian_p;
62*fae548d3Szrj size_t i;
63*fae548d3Szrj size_t j;
64*fae548d3Szrj
65*fae548d3Szrj /* The algorithm used here is radix sort which takes time linear in
66*fae548d3Szrj the number of elements in the array. */
67*fae548d3Szrj
68*fae548d3Szrj /* The algorithm here depends on being able to swap the two arrays
69*fae548d3Szrj an even number of times. */
70*fae548d3Szrj if ((sizeof (void *) / sizeof (digit_t)) % 2 != 0)
71*fae548d3Szrj abort ();
72*fae548d3Szrj
73*fae548d3Szrj /* Figure out the endianness of the machine. */
74*fae548d3Szrj for (i = 0, j = 0; i < sizeof (size_t); ++i)
75*fae548d3Szrj {
76*fae548d3Szrj j *= (UCHAR_MAX + 1);
77*fae548d3Szrj j += i;
78*fae548d3Szrj }
79*fae548d3Szrj big_endian_p = (((char *)&j)[0] == 0);
80*fae548d3Szrj
81*fae548d3Szrj /* Move through the pointer values from least significant to most
82*fae548d3Szrj significant digits. */
83*fae548d3Szrj for (i = 0; i < sizeof (void *) / sizeof (digit_t); ++i)
84*fae548d3Szrj {
85*fae548d3Szrj digit_t *digit;
86*fae548d3Szrj digit_t *bias;
87*fae548d3Szrj digit_t *top;
88*fae548d3Szrj unsigned int *countp;
89*fae548d3Szrj void **pointerp;
90*fae548d3Szrj
91*fae548d3Szrj /* The offset from the start of the pointer will depend on the
92*fae548d3Szrj endianness of the machine. */
93*fae548d3Szrj if (big_endian_p)
94*fae548d3Szrj j = sizeof (void *) / sizeof (digit_t) - i;
95*fae548d3Szrj else
96*fae548d3Szrj j = i;
97*fae548d3Szrj
98*fae548d3Szrj /* Now, perform a stable sort on this digit. We use counting
99*fae548d3Szrj sort. */
100*fae548d3Szrj memset (count, 0, DIGIT_MAX * sizeof (unsigned int));
101*fae548d3Szrj
102*fae548d3Szrj /* Compute the address of the appropriate digit in the first and
103*fae548d3Szrj one-past-the-end elements of the array. On a little-endian
104*fae548d3Szrj machine, the least-significant digit is closest to the front. */
105*fae548d3Szrj bias = ((digit_t *) pointers) + j;
106*fae548d3Szrj top = ((digit_t *) (pointers + n)) + j;
107*fae548d3Szrj
108*fae548d3Szrj /* Count how many there are of each value. At the end of this
109*fae548d3Szrj loop, COUNT[K] will contain the number of pointers whose Ith
110*fae548d3Szrj digit is K. */
111*fae548d3Szrj for (digit = bias;
112*fae548d3Szrj digit < top;
113*fae548d3Szrj digit += sizeof (void *) / sizeof (digit_t))
114*fae548d3Szrj ++count[*digit];
115*fae548d3Szrj
116*fae548d3Szrj /* Now, make COUNT[K] contain the number of pointers whose Ith
117*fae548d3Szrj digit is less than or equal to K. */
118*fae548d3Szrj for (countp = count + 1; countp < count + DIGIT_MAX; ++countp)
119*fae548d3Szrj *countp += countp[-1];
120*fae548d3Szrj
121*fae548d3Szrj /* Now, drop the pointers into their correct locations. */
122*fae548d3Szrj for (pointerp = pointers + n - 1; pointerp >= pointers; --pointerp)
123*fae548d3Szrj work[--count[((digit_t *) pointerp)[j]]] = *pointerp;
124*fae548d3Szrj
125*fae548d3Szrj /* Swap WORK and POINTERS so that POINTERS contains the sorted
126*fae548d3Szrj array. */
127*fae548d3Szrj pointerp = pointers;
128*fae548d3Szrj pointers = work;
129*fae548d3Szrj work = pointerp;
130*fae548d3Szrj }
131*fae548d3Szrj }
132*fae548d3Szrj
133*fae548d3Szrj /* Everything below here is a unit test for the routines in this
134*fae548d3Szrj file. */
135*fae548d3Szrj
136*fae548d3Szrj #ifdef UNIT_TEST
137*fae548d3Szrj
138*fae548d3Szrj #include <stdio.h>
139*fae548d3Szrj
xmalloc(size_t n)140*fae548d3Szrj void *xmalloc (size_t n)
141*fae548d3Szrj {
142*fae548d3Szrj return malloc (n);
143*fae548d3Szrj }
144*fae548d3Szrj
main(int argc,char ** argv)145*fae548d3Szrj int main (int argc, char **argv)
146*fae548d3Szrj {
147*fae548d3Szrj int k;
148*fae548d3Szrj int result;
149*fae548d3Szrj size_t i;
150*fae548d3Szrj void **pointers;
151*fae548d3Szrj void **work;
152*fae548d3Szrj
153*fae548d3Szrj if (argc > 1)
154*fae548d3Szrj k = atoi (argv[1]);
155*fae548d3Szrj else
156*fae548d3Szrj k = 10;
157*fae548d3Szrj
158*fae548d3Szrj pointers = XNEWVEC (void*, k);
159*fae548d3Szrj work = XNEWVEC (void*, k);
160*fae548d3Szrj
161*fae548d3Szrj for (i = 0; i < k; ++i)
162*fae548d3Szrj {
163*fae548d3Szrj pointers[i] = (void *) random ();
164*fae548d3Szrj printf ("%x\n", pointers[i]);
165*fae548d3Szrj }
166*fae548d3Szrj
167*fae548d3Szrj sort_pointers (k, pointers, work);
168*fae548d3Szrj
169*fae548d3Szrj printf ("\nSorted\n\n");
170*fae548d3Szrj
171*fae548d3Szrj result = 0;
172*fae548d3Szrj
173*fae548d3Szrj for (i = 0; i < k; ++i)
174*fae548d3Szrj {
175*fae548d3Szrj printf ("%x\n", pointers[i]);
176*fae548d3Szrj if (i > 0 && (char*) pointers[i] < (char*) pointers[i - 1])
177*fae548d3Szrj result = 1;
178*fae548d3Szrj }
179*fae548d3Szrj
180*fae548d3Szrj free (pointers);
181*fae548d3Szrj free (work);
182*fae548d3Szrj
183*fae548d3Szrj return result;
184*fae548d3Szrj }
185*fae548d3Szrj
186*fae548d3Szrj #endif
187