12e0724c7Sespie /* Sorting algorithms.
22e0724c7Sespie Copyright (C) 2000 Free Software Foundation, Inc.
32e0724c7Sespie Contributed by Mark Mitchell <mark@codesourcery.com>.
42e0724c7Sespie
52e0724c7Sespie This file is part of GNU CC.
62e0724c7Sespie
72e0724c7Sespie GNU CC is free software; you can redistribute it and/or modify it
82e0724c7Sespie under the terms of the GNU General Public License as published by
92e0724c7Sespie the Free Software Foundation; either version 2, or (at your option)
102e0724c7Sespie any later version.
112e0724c7Sespie
122e0724c7Sespie GNU CC is distributed in the hope that it will be useful, but
132e0724c7Sespie WITHOUT ANY WARRANTY; without even the implied warranty of
142e0724c7Sespie MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
152e0724c7Sespie General Public License for more details.
162e0724c7Sespie
172e0724c7Sespie You should have received a copy of the GNU General Public License
182e0724c7Sespie along with GNU CC; see the file COPYING. If not, write to
19*20fce977Smiod the Free Software Foundation, 51 Franklin Street - Fifth Floor,
20*20fce977Smiod Boston, MA 02110-1301, USA. */
212e0724c7Sespie
222e0724c7Sespie #ifdef HAVE_CONFIG_H
232e0724c7Sespie #include "config.h"
242e0724c7Sespie #endif
252e0724c7Sespie #include "libiberty.h"
262e0724c7Sespie #include "sort.h"
272e0724c7Sespie #ifdef HAVE_LIMITS_H
282e0724c7Sespie #include <limits.h>
292e0724c7Sespie #endif
302e0724c7Sespie #ifdef HAVE_SYS_PARAM_H
312e0724c7Sespie #include <sys/param.h>
322e0724c7Sespie #endif
332e0724c7Sespie #ifdef HAVE_STDLIB_H
342e0724c7Sespie #include <stdlib.h>
352e0724c7Sespie #endif
362e0724c7Sespie #ifdef HAVE_STRING_H
372e0724c7Sespie #include <string.h>
382e0724c7Sespie #endif
392e0724c7Sespie
402e0724c7Sespie #ifndef UCHAR_MAX
412e0724c7Sespie #define UCHAR_MAX ((unsigned char)(-1))
422e0724c7Sespie #endif
432e0724c7Sespie
442e0724c7Sespie /* POINTERS and WORK are both arrays of N pointers. When this
452e0724c7Sespie function returns POINTERS will be sorted in ascending order. */
462e0724c7Sespie
sort_pointers(size_t n,void ** pointers,void ** work)47*20fce977Smiod void sort_pointers (size_t n, void **pointers, void **work)
482e0724c7Sespie {
492e0724c7Sespie /* The type of a single digit. This can be any unsigned integral
502e0724c7Sespie type. When changing this, DIGIT_MAX should be changed as
512e0724c7Sespie well. */
522e0724c7Sespie typedef unsigned char digit_t;
532e0724c7Sespie
542e0724c7Sespie /* The maximum value a single digit can have. */
552e0724c7Sespie #define DIGIT_MAX (UCHAR_MAX + 1)
562e0724c7Sespie
572e0724c7Sespie /* The Ith entry is the number of elements in *POINTERSP that have I
582e0724c7Sespie in the digit on which we are currently sorting. */
592e0724c7Sespie unsigned int count[DIGIT_MAX];
602e0724c7Sespie /* Nonzero if we are running on a big-endian machine. */
612e0724c7Sespie int big_endian_p;
622e0724c7Sespie size_t i;
632e0724c7Sespie size_t j;
642e0724c7Sespie
652e0724c7Sespie /* The algorithm used here is radix sort which takes time linear in
662e0724c7Sespie the number of elements in the array. */
672e0724c7Sespie
682e0724c7Sespie /* The algorithm here depends on being able to swap the two arrays
692e0724c7Sespie an even number of times. */
702e0724c7Sespie if ((sizeof (void *) / sizeof (digit_t)) % 2 != 0)
712e0724c7Sespie abort ();
722e0724c7Sespie
732e0724c7Sespie /* Figure out the endianness of the machine. */
742e0724c7Sespie for (i = 0, j = 0; i < sizeof (size_t); ++i)
752e0724c7Sespie {
762e0724c7Sespie j *= (UCHAR_MAX + 1);
772e0724c7Sespie j += i;
782e0724c7Sespie }
792e0724c7Sespie big_endian_p = (((char *)&j)[0] == 0);
802e0724c7Sespie
812e0724c7Sespie /* Move through the pointer values from least significant to most
822e0724c7Sespie significant digits. */
832e0724c7Sespie for (i = 0; i < sizeof (void *) / sizeof (digit_t); ++i)
842e0724c7Sespie {
852e0724c7Sespie digit_t *digit;
862e0724c7Sespie digit_t *bias;
872e0724c7Sespie digit_t *top;
882e0724c7Sespie unsigned int *countp;
892e0724c7Sespie void **pointerp;
902e0724c7Sespie
912e0724c7Sespie /* The offset from the start of the pointer will depend on the
922e0724c7Sespie endianness of the machine. */
932e0724c7Sespie if (big_endian_p)
942e0724c7Sespie j = sizeof (void *) / sizeof (digit_t) - i;
952e0724c7Sespie else
962e0724c7Sespie j = i;
972e0724c7Sespie
982e0724c7Sespie /* Now, perform a stable sort on this digit. We use counting
992e0724c7Sespie sort. */
1002e0724c7Sespie memset (count, 0, DIGIT_MAX * sizeof (unsigned int));
1012e0724c7Sespie
1022e0724c7Sespie /* Compute the address of the appropriate digit in the first and
1032e0724c7Sespie one-past-the-end elements of the array. On a little-endian
1042e0724c7Sespie machine, the least-significant digit is closest to the front. */
1052e0724c7Sespie bias = ((digit_t *) pointers) + j;
1062e0724c7Sespie top = ((digit_t *) (pointers + n)) + j;
1072e0724c7Sespie
1082e0724c7Sespie /* Count how many there are of each value. At the end of this
1092e0724c7Sespie loop, COUNT[K] will contain the number of pointers whose Ith
1102e0724c7Sespie digit is K. */
1112e0724c7Sespie for (digit = bias;
1122e0724c7Sespie digit < top;
1132e0724c7Sespie digit += sizeof (void *) / sizeof (digit_t))
1142e0724c7Sespie ++count[*digit];
1152e0724c7Sespie
1162e0724c7Sespie /* Now, make COUNT[K] contain the number of pointers whose Ith
1172e0724c7Sespie digit is less than or equal to K. */
1182e0724c7Sespie for (countp = count + 1; countp < count + DIGIT_MAX; ++countp)
1192e0724c7Sespie *countp += countp[-1];
1202e0724c7Sespie
1212e0724c7Sespie /* Now, drop the pointers into their correct locations. */
1222e0724c7Sespie for (pointerp = pointers + n - 1; pointerp >= pointers; --pointerp)
1232e0724c7Sespie work[--count[((digit_t *) pointerp)[j]]] = *pointerp;
1242e0724c7Sespie
1252e0724c7Sespie /* Swap WORK and POINTERS so that POINTERS contains the sorted
1262e0724c7Sespie array. */
1272e0724c7Sespie pointerp = pointers;
1282e0724c7Sespie pointers = work;
1292e0724c7Sespie work = pointerp;
1302e0724c7Sespie }
1312e0724c7Sespie }
1322e0724c7Sespie
1332e0724c7Sespie /* Everything below here is a unit test for the routines in this
1342e0724c7Sespie file. */
1352e0724c7Sespie
1362e0724c7Sespie #ifdef UNIT_TEST
1372e0724c7Sespie
1382e0724c7Sespie #include <stdio.h>
1392e0724c7Sespie
xmalloc(size_t n)140*20fce977Smiod void *xmalloc (size_t n)
1412e0724c7Sespie {
1422e0724c7Sespie return malloc (n);
1432e0724c7Sespie }
1442e0724c7Sespie
main(int argc,char ** argv)1452e0724c7Sespie int main (int argc, char **argv)
1462e0724c7Sespie {
1472e0724c7Sespie int k;
1482e0724c7Sespie int result;
1492e0724c7Sespie size_t i;
1502e0724c7Sespie void **pointers;
1512e0724c7Sespie void **work;
1522e0724c7Sespie
1532e0724c7Sespie if (argc > 1)
1542e0724c7Sespie k = atoi (argv[1]);
1552e0724c7Sespie else
1562e0724c7Sespie k = 10;
1572e0724c7Sespie
158*20fce977Smiod pointers = XNEWVEC (void*, k);
159*20fce977Smiod work = XNEWVEC (void*, k);
1602e0724c7Sespie
1612e0724c7Sespie for (i = 0; i < k; ++i)
1622e0724c7Sespie {
1632e0724c7Sespie pointers[i] = (void *) random ();
1642e0724c7Sespie printf ("%x\n", pointers[i]);
1652e0724c7Sespie }
1662e0724c7Sespie
1672e0724c7Sespie sort_pointers (k, pointers, work);
1682e0724c7Sespie
1692e0724c7Sespie printf ("\nSorted\n\n");
1702e0724c7Sespie
1712e0724c7Sespie result = 0;
1722e0724c7Sespie
1732e0724c7Sespie for (i = 0; i < k; ++i)
1742e0724c7Sespie {
1752e0724c7Sespie printf ("%x\n", pointers[i]);
1762e0724c7Sespie if (i > 0 && (char*) pointers[i] < (char*) pointers[i - 1])
1772e0724c7Sespie result = 1;
1782e0724c7Sespie }
1792e0724c7Sespie
1802e0724c7Sespie free (pointers);
1812e0724c7Sespie free (work);
1822e0724c7Sespie
1832e0724c7Sespie return result;
1842e0724c7Sespie }
1852e0724c7Sespie
1862e0724c7Sespie #endif
187