1169695Skan/* Sorting algorithms. 2169695Skan Copyright (C) 2000 Free Software Foundation, Inc. 3169695Skan Contributed by Mark Mitchell <mark@codesourcery.com>. 4169695Skan 5169695SkanThis file is part of GNU CC. 6169695Skan 7169695SkanGNU CC is free software; you can redistribute it and/or modify it 8169695Skanunder the terms of the GNU General Public License as published by 9169695Skanthe Free Software Foundation; either version 2, or (at your option) 10169695Skanany later version. 11169695Skan 12169695SkanGNU CC is distributed in the hope that it will be useful, but 13169695SkanWITHOUT ANY WARRANTY; without even the implied warranty of 14169695SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15169695SkanGeneral Public License for more details. 16169695Skan 17169695SkanYou should have received a copy of the GNU General Public License 18169695Skanalong with GNU CC; see the file COPYING. If not, write to 19169695Skanthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20169695SkanBoston, MA 02110-1301, USA. */ 21169695Skan 22169695Skan#ifdef HAVE_CONFIG_H 23169695Skan#include "config.h" 24169695Skan#endif 25169695Skan#include "libiberty.h" 26169695Skan#include "sort.h" 27169695Skan#ifdef HAVE_LIMITS_H 28169695Skan#include <limits.h> 29169695Skan#endif 30169695Skan#ifdef HAVE_SYS_PARAM_H 31169695Skan#include <sys/param.h> 32169695Skan#endif 33169695Skan#ifdef HAVE_STDLIB_H 34169695Skan#include <stdlib.h> 35169695Skan#endif 36169695Skan#ifdef HAVE_STRING_H 37169695Skan#include <string.h> 38169695Skan#endif 39169695Skan 40169695Skan#ifndef UCHAR_MAX 41169695Skan#define UCHAR_MAX ((unsigned char)(-1)) 42169695Skan#endif 43169695Skan 44169695Skan/* POINTERS and WORK are both arrays of N pointers. When this 45169695Skan function returns POINTERS will be sorted in ascending order. */ 46169695Skan 47169695Skanvoid sort_pointers (size_t n, void **pointers, void **work) 48169695Skan{ 49169695Skan /* The type of a single digit. This can be any unsigned integral 50169695Skan type. When changing this, DIGIT_MAX should be changed as 51169695Skan well. */ 52169695Skan typedef unsigned char digit_t; 53169695Skan 54169695Skan /* The maximum value a single digit can have. */ 55169695Skan#define DIGIT_MAX (UCHAR_MAX + 1) 56169695Skan 57169695Skan /* The Ith entry is the number of elements in *POINTERSP that have I 58169695Skan in the digit on which we are currently sorting. */ 59169695Skan unsigned int count[DIGIT_MAX]; 60169695Skan /* Nonzero if we are running on a big-endian machine. */ 61169695Skan int big_endian_p; 62169695Skan size_t i; 63169695Skan size_t j; 64169695Skan 65169695Skan /* The algorithm used here is radix sort which takes time linear in 66169695Skan the number of elements in the array. */ 67169695Skan 68169695Skan /* The algorithm here depends on being able to swap the two arrays 69169695Skan an even number of times. */ 70169695Skan if ((sizeof (void *) / sizeof (digit_t)) % 2 != 0) 71169695Skan abort (); 72169695Skan 73169695Skan /* Figure out the endianness of the machine. */ 74169695Skan for (i = 0, j = 0; i < sizeof (size_t); ++i) 75169695Skan { 76169695Skan j *= (UCHAR_MAX + 1); 77169695Skan j += i; 78169695Skan } 79169695Skan big_endian_p = (((char *)&j)[0] == 0); 80169695Skan 81169695Skan /* Move through the pointer values from least significant to most 82169695Skan significant digits. */ 83169695Skan for (i = 0; i < sizeof (void *) / sizeof (digit_t); ++i) 84169695Skan { 85169695Skan digit_t *digit; 86169695Skan digit_t *bias; 87169695Skan digit_t *top; 88169695Skan unsigned int *countp; 89169695Skan void **pointerp; 90169695Skan 91169695Skan /* The offset from the start of the pointer will depend on the 92169695Skan endianness of the machine. */ 93169695Skan if (big_endian_p) 94169695Skan j = sizeof (void *) / sizeof (digit_t) - i; 95169695Skan else 96169695Skan j = i; 97169695Skan 98169695Skan /* Now, perform a stable sort on this digit. We use counting 99169695Skan sort. */ 100169695Skan memset (count, 0, DIGIT_MAX * sizeof (unsigned int)); 101169695Skan 102169695Skan /* Compute the address of the appropriate digit in the first and 103169695Skan one-past-the-end elements of the array. On a little-endian 104169695Skan machine, the least-significant digit is closest to the front. */ 105169695Skan bias = ((digit_t *) pointers) + j; 106169695Skan top = ((digit_t *) (pointers + n)) + j; 107169695Skan 108169695Skan /* Count how many there are of each value. At the end of this 109169695Skan loop, COUNT[K] will contain the number of pointers whose Ith 110169695Skan digit is K. */ 111169695Skan for (digit = bias; 112169695Skan digit < top; 113169695Skan digit += sizeof (void *) / sizeof (digit_t)) 114169695Skan ++count[*digit]; 115169695Skan 116169695Skan /* Now, make COUNT[K] contain the number of pointers whose Ith 117169695Skan digit is less than or equal to K. */ 118169695Skan for (countp = count + 1; countp < count + DIGIT_MAX; ++countp) 119169695Skan *countp += countp[-1]; 120169695Skan 121169695Skan /* Now, drop the pointers into their correct locations. */ 122169695Skan for (pointerp = pointers + n - 1; pointerp >= pointers; --pointerp) 123169695Skan work[--count[((digit_t *) pointerp)[j]]] = *pointerp; 124169695Skan 125169695Skan /* Swap WORK and POINTERS so that POINTERS contains the sorted 126169695Skan array. */ 127169695Skan pointerp = pointers; 128169695Skan pointers = work; 129169695Skan work = pointerp; 130169695Skan } 131169695Skan} 132169695Skan 133169695Skan/* Everything below here is a unit test for the routines in this 134169695Skan file. */ 135169695Skan 136169695Skan#ifdef UNIT_TEST 137169695Skan 138169695Skan#include <stdio.h> 139169695Skan 140169695Skanvoid *xmalloc (size_t n) 141169695Skan{ 142169695Skan return malloc (n); 143169695Skan} 144169695Skan 145169695Skanint main (int argc, char **argv) 146169695Skan{ 147169695Skan int k; 148169695Skan int result; 149169695Skan size_t i; 150169695Skan void **pointers; 151169695Skan void **work; 152169695Skan 153169695Skan if (argc > 1) 154169695Skan k = atoi (argv[1]); 155169695Skan else 156169695Skan k = 10; 157169695Skan 158169695Skan pointers = XNEWVEC (void*, k); 159169695Skan work = XNEWVEC (void*, k); 160169695Skan 161169695Skan for (i = 0; i < k; ++i) 162169695Skan { 163169695Skan pointers[i] = (void *) random (); 164169695Skan printf ("%x\n", pointers[i]); 165169695Skan } 166169695Skan 167169695Skan sort_pointers (k, pointers, work); 168169695Skan 169169695Skan printf ("\nSorted\n\n"); 170169695Skan 171169695Skan result = 0; 172169695Skan 173169695Skan for (i = 0; i < k; ++i) 174169695Skan { 175169695Skan printf ("%x\n", pointers[i]); 176169695Skan if (i > 0 && (char*) pointers[i] < (char*) pointers[i - 1]) 177169695Skan result = 1; 178169695Skan } 179169695Skan 180169695Skan free (pointers); 181169695Skan free (work); 182169695Skan 183169695Skan return result; 184169695Skan} 185169695Skan 186169695Skan#endif 187