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