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