sort.c revision 256281
1284345Ssjg/* Sorting algorithms. 2284345Ssjg Copyright (C) 2000 Free Software Foundation, Inc. 3284345Ssjg Contributed by Mark Mitchell <mark@codesourcery.com>. 4284345Ssjg 5290816SsjgThis file is part of GNU CC. 6284345Ssjg 7284349SsjgGNU CC is free software; you can redistribute it and/or modify it 8284349Ssjgunder the terms of the GNU General Public License as published by 9284349Ssjgthe Free Software Foundation; either version 2, or (at your option) 10287898Sbdreweryany later version. 11287869Sbdrewery 12284345SsjgGNU CC is distributed in the hope that it will be useful, but 13287898SbdreweryWITHOUT ANY WARRANTY; without even the implied warranty of 14284650SsjgMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15287898SbdreweryGeneral Public License for more details. 16287636Ssjg 17287636SsjgYou should have received a copy of the GNU General Public License 18287636Ssjgalong with GNU CC; see the file COPYING. If not, write to 19287867Sbdrewerythe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20284650SsjgBoston, MA 02110-1301, USA. */ 21287867Sbdrewery 22284650Ssjg#ifdef HAVE_CONFIG_H 23287636Ssjg#include "config.h" 24287887Sbdrewery#endif 25287887Sbdrewery#include "libiberty.h" 26284650Ssjg#include "sort.h" 27284345Ssjg#ifdef HAVE_LIMITS_H 28284345Ssjg#include <limits.h> 29284345Ssjg#endif 30284345Ssjg#ifdef HAVE_SYS_PARAM_H 31284345Ssjg#include <sys/param.h> 32287966Sbdrewery#endif 33284345Ssjg#ifdef HAVE_STDLIB_H 34287871Sbdrewery#include <stdlib.h> 35284345Ssjg#endif 36284345Ssjg#ifdef HAVE_STRING_H 37284345Ssjg#include <string.h> 38284345Ssjg#endif 39284345Ssjg 40284345Ssjg#ifndef UCHAR_MAX 41284345Ssjg#define UCHAR_MAX ((unsigned char)(-1)) 42284345Ssjg#endif 43284345Ssjg 44284345Ssjg/* POINTERS and WORK are both arrays of N pointers. When this 45284345Ssjg function returns POINTERS will be sorted in ascending order. */ 46287885Sbdrewery 47287885Sbdreweryvoid sort_pointers (size_t n, void **pointers, void **work) 48287885Sbdrewery{ 49284345Ssjg /* The type of a single digit. This can be any unsigned integral 50284345Ssjg type. When changing this, DIGIT_MAX should be changed as 51284345Ssjg well. */ 52284345Ssjg typedef unsigned char digit_t; 53284345Ssjg 54284345Ssjg /* The maximum value a single digit can have. */ 55284345Ssjg#define DIGIT_MAX (UCHAR_MAX + 1) 56284345Ssjg 57291086Sbdrewery /* The Ith entry is the number of elements in *POINTERSP that have I 58284345Ssjg in the digit on which we are currently sorting. */ 59284345Ssjg unsigned int count[DIGIT_MAX]; 60284345Ssjg /* Nonzero if we are running on a big-endian machine. */ 61284345Ssjg int big_endian_p; 62284345Ssjg size_t i; 63284345Ssjg size_t j; 64284345Ssjg 65284345Ssjg /* The algorithm used here is radix sort which takes time linear in 66284345Ssjg the number of elements in the array. */ 67284345Ssjg 68284345Ssjg /* The algorithm here depends on being able to swap the two arrays 69284345Ssjg an even number of times. */ 70284345Ssjg if ((sizeof (void *) / sizeof (digit_t)) % 2 != 0) 71284345Ssjg abort (); 72284345Ssjg 73284345Ssjg /* Figure out the endianness of the machine. */ 74284345Ssjg for (i = 0, j = 0; i < sizeof (size_t); ++i) 75284345Ssjg { 76284345Ssjg j *= (UCHAR_MAX + 1); 77284345Ssjg j += i; 78284345Ssjg } 79284345Ssjg big_endian_p = (((char *)&j)[0] == 0); 80284345Ssjg 81284345Ssjg /* Move through the pointer values from least significant to most 82284345Ssjg significant digits. */ 83284345Ssjg for (i = 0; i < sizeof (void *) / sizeof (digit_t); ++i) 84284345Ssjg { 85284345Ssjg digit_t *digit; 86284345Ssjg digit_t *bias; 87284345Ssjg digit_t *top; 88284345Ssjg unsigned int *countp; 89284345Ssjg void **pointerp; 90284345Ssjg 91284345Ssjg /* The offset from the start of the pointer will depend on the 92284345Ssjg endianness of the machine. */ 93284345Ssjg if (big_endian_p) 94284345Ssjg j = sizeof (void *) / sizeof (digit_t) - i; 95284345Ssjg else 96284345Ssjg j = i; 97284345Ssjg 98284345Ssjg /* Now, perform a stable sort on this digit. We use counting 99284345Ssjg sort. */ 100284345Ssjg memset (count, 0, DIGIT_MAX * sizeof (unsigned int)); 101284345Ssjg 102284345Ssjg /* Compute the address of the appropriate digit in the first and 103284345Ssjg one-past-the-end elements of the array. On a little-endian 104284345Ssjg machine, the least-significant digit is closest to the front. */ 105284345Ssjg bias = ((digit_t *) pointers) + j; 106284345Ssjg top = ((digit_t *) (pointers + n)) + j; 107284345Ssjg 108284345Ssjg /* Count how many there are of each value. At the end of this 109287869Sbdrewery loop, COUNT[K] will contain the number of pointers whose Ith 110287869Sbdrewery digit is K. */ 111287869Sbdrewery for (digit = bias; 112287869Sbdrewery digit < top; 113287869Sbdrewery digit += sizeof (void *) / sizeof (digit_t)) 114287869Sbdrewery ++count[*digit]; 115284345Ssjg 116284345Ssjg /* Now, make COUNT[K] contain the number of pointers whose Ith 117284345Ssjg digit is less than or equal to K. */ 118284345Ssjg for (countp = count + 1; countp < count + DIGIT_MAX; ++countp) 119284345Ssjg *countp += countp[-1]; 120284345Ssjg 121284345Ssjg /* Now, drop the pointers into their correct locations. */ 122284345Ssjg for (pointerp = pointers + n - 1; pointerp >= pointers; --pointerp) 123284345Ssjg work[--count[((digit_t *) pointerp)[j]]] = *pointerp; 124284345Ssjg 125284345Ssjg /* Swap WORK and POINTERS so that POINTERS contains the sorted 126284345Ssjg array. */ 127284345Ssjg pointerp = pointers; 128284345Ssjg pointers = work; 129284345Ssjg work = pointerp; 130284345Ssjg } 131284345Ssjg} 132284345Ssjg 133284345Ssjg/* Everything below here is a unit test for the routines in this 134284345Ssjg file. */ 135284345Ssjg 136284345Ssjg#ifdef UNIT_TEST 137284345Ssjg 138284345Ssjg#include <stdio.h> 139284345Ssjg 140284345Ssjgvoid *xmalloc (size_t n) 141284345Ssjg{ 142284345Ssjg return malloc (n); 143284345Ssjg} 144284345Ssjg 145284345Ssjgint main (int argc, char **argv) 146284345Ssjg{ 147284345Ssjg int k; 148284345Ssjg int result; 149284345Ssjg size_t i; 150284345Ssjg void **pointers; 151284345Ssjg void **work; 152284345Ssjg 153284345Ssjg if (argc > 1) 154284345Ssjg k = atoi (argv[1]); 155284345Ssjg else 156284345Ssjg k = 10; 157284345Ssjg 158284345Ssjg pointers = XNEWVEC (void*, k); 159284345Ssjg work = XNEWVEC (void*, k); 160284345Ssjg 161284345Ssjg for (i = 0; i < k; ++i) 162288156Sbdrewery { 163284345Ssjg pointers[i] = (void *) random (); 164284345Ssjg printf ("%x\n", pointers[i]); 165284345Ssjg } 166284345Ssjg 167284345Ssjg sort_pointers (k, pointers, work); 168284345Ssjg 169284345Ssjg printf ("\nSorted\n\n"); 170284345Ssjg 171284345Ssjg result = 0; 172284345Ssjg 173284345Ssjg for (i = 0; i < k; ++i) 174284345Ssjg { 175284345Ssjg printf ("%x\n", pointers[i]); 176284345Ssjg if (i > 0 && (char*) pointers[i] < (char*) pointers[i - 1]) 177284345Ssjg result = 1; 178284345Ssjg } 179284345Ssjg 180284345Ssjg free (pointers); 181284345Ssjg free (work); 182284345Ssjg 183284345Ssjg return result; 184284345Ssjg} 185284345Ssjg 186284345Ssjg#endif 187284345Ssjg