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