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
|
/* Sorting algorithms.
Copyright (C) 2000-2018 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, 51 Franklin Street - Fifth Floor,
Boston, MA 02110-1301, 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 (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 (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 = XNEWVEC (void*, k);
work = XNEWVEC (void*, k);
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
|