177298Sobrien/* Sorting algorithms. 277298Sobrien Copyright (C) 2000 Free Software Foundation, Inc. 377298Sobrien Contributed by Mark Mitchell <mark@codesourcery.com>. 477298Sobrien 577298SobrienThis file is part of GNU CC. 677298Sobrien 777298SobrienGNU CC is free software; you can redistribute it and/or modify it 877298Sobrienunder the terms of the GNU General Public License as published by 977298Sobrienthe Free Software Foundation; either version 2, or (at your option) 1077298Sobrienany later version. 1177298Sobrien 1277298SobrienGNU CC is distributed in the hope that it will be useful, but 1377298SobrienWITHOUT ANY WARRANTY; without even the implied warranty of 1477298SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1577298SobrienGeneral Public License for more details. 1677298Sobrien 1777298SobrienYou should have received a copy of the GNU General Public License 1877298Sobrienalong with GNU CC; see the file COPYING. If not, write to 19218822Sdimthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20218822SdimBoston, MA 02110-1301, USA. */ 2177298Sobrien 2277298Sobrien#ifdef HAVE_CONFIG_H 2377298Sobrien#include "config.h" 2477298Sobrien#endif 2577298Sobrien#include "libiberty.h" 2677298Sobrien#include "sort.h" 2777298Sobrien#ifdef HAVE_LIMITS_H 2877298Sobrien#include <limits.h> 2977298Sobrien#endif 3077298Sobrien#ifdef HAVE_SYS_PARAM_H 3177298Sobrien#include <sys/param.h> 3277298Sobrien#endif 3377298Sobrien#ifdef HAVE_STDLIB_H 3477298Sobrien#include <stdlib.h> 3577298Sobrien#endif 3677298Sobrien#ifdef HAVE_STRING_H 3777298Sobrien#include <string.h> 3877298Sobrien#endif 3977298Sobrien 4077298Sobrien#ifndef UCHAR_MAX 4177298Sobrien#define UCHAR_MAX ((unsigned char)(-1)) 4277298Sobrien#endif 4377298Sobrien 4477298Sobrien/* POINTERS and WORK are both arrays of N pointers. When this 4577298Sobrien function returns POINTERS will be sorted in ascending order. */ 4677298Sobrien 47218822Sdimvoid sort_pointers (size_t n, void **pointers, void **work) 4877298Sobrien{ 4977298Sobrien /* The type of a single digit. This can be any unsigned integral 5077298Sobrien type. When changing this, DIGIT_MAX should be changed as 5177298Sobrien well. */ 5277298Sobrien typedef unsigned char digit_t; 5377298Sobrien 5477298Sobrien /* The maximum value a single digit can have. */ 5577298Sobrien#define DIGIT_MAX (UCHAR_MAX + 1) 5677298Sobrien 5777298Sobrien /* The Ith entry is the number of elements in *POINTERSP that have I 5877298Sobrien in the digit on which we are currently sorting. */ 5977298Sobrien unsigned int count[DIGIT_MAX]; 6077298Sobrien /* Nonzero if we are running on a big-endian machine. */ 6177298Sobrien int big_endian_p; 6277298Sobrien size_t i; 6377298Sobrien size_t j; 6477298Sobrien 6577298Sobrien /* The algorithm used here is radix sort which takes time linear in 6677298Sobrien the number of elements in the array. */ 6777298Sobrien 6877298Sobrien /* The algorithm here depends on being able to swap the two arrays 6977298Sobrien an even number of times. */ 7077298Sobrien if ((sizeof (void *) / sizeof (digit_t)) % 2 != 0) 7177298Sobrien abort (); 7277298Sobrien 7377298Sobrien /* Figure out the endianness of the machine. */ 7477298Sobrien for (i = 0, j = 0; i < sizeof (size_t); ++i) 7577298Sobrien { 7677298Sobrien j *= (UCHAR_MAX + 1); 7777298Sobrien j += i; 7877298Sobrien } 7977298Sobrien big_endian_p = (((char *)&j)[0] == 0); 8077298Sobrien 8177298Sobrien /* Move through the pointer values from least significant to most 8277298Sobrien significant digits. */ 8377298Sobrien for (i = 0; i < sizeof (void *) / sizeof (digit_t); ++i) 8477298Sobrien { 8577298Sobrien digit_t *digit; 8677298Sobrien digit_t *bias; 8777298Sobrien digit_t *top; 8877298Sobrien unsigned int *countp; 8977298Sobrien void **pointerp; 9077298Sobrien 9177298Sobrien /* The offset from the start of the pointer will depend on the 9277298Sobrien endianness of the machine. */ 9377298Sobrien if (big_endian_p) 9477298Sobrien j = sizeof (void *) / sizeof (digit_t) - i; 9577298Sobrien else 9677298Sobrien j = i; 9777298Sobrien 9877298Sobrien /* Now, perform a stable sort on this digit. We use counting 9977298Sobrien sort. */ 10077298Sobrien memset (count, 0, DIGIT_MAX * sizeof (unsigned int)); 10177298Sobrien 10277298Sobrien /* Compute the address of the appropriate digit in the first and 10377298Sobrien one-past-the-end elements of the array. On a little-endian 10477298Sobrien machine, the least-significant digit is closest to the front. */ 10577298Sobrien bias = ((digit_t *) pointers) + j; 10677298Sobrien top = ((digit_t *) (pointers + n)) + j; 10777298Sobrien 10877298Sobrien /* Count how many there are of each value. At the end of this 10977298Sobrien loop, COUNT[K] will contain the number of pointers whose Ith 11077298Sobrien digit is K. */ 11177298Sobrien for (digit = bias; 11277298Sobrien digit < top; 11377298Sobrien digit += sizeof (void *) / sizeof (digit_t)) 11477298Sobrien ++count[*digit]; 11577298Sobrien 11677298Sobrien /* Now, make COUNT[K] contain the number of pointers whose Ith 11777298Sobrien digit is less than or equal to K. */ 11877298Sobrien for (countp = count + 1; countp < count + DIGIT_MAX; ++countp) 11977298Sobrien *countp += countp[-1]; 12077298Sobrien 12177298Sobrien /* Now, drop the pointers into their correct locations. */ 12277298Sobrien for (pointerp = pointers + n - 1; pointerp >= pointers; --pointerp) 12377298Sobrien work[--count[((digit_t *) pointerp)[j]]] = *pointerp; 12477298Sobrien 12577298Sobrien /* Swap WORK and POINTERS so that POINTERS contains the sorted 12677298Sobrien array. */ 12777298Sobrien pointerp = pointers; 12877298Sobrien pointers = work; 12977298Sobrien work = pointerp; 13077298Sobrien } 13177298Sobrien} 13277298Sobrien 13377298Sobrien/* Everything below here is a unit test for the routines in this 13477298Sobrien file. */ 13577298Sobrien 13677298Sobrien#ifdef UNIT_TEST 13777298Sobrien 13877298Sobrien#include <stdio.h> 13977298Sobrien 140218822Sdimvoid *xmalloc (size_t n) 14177298Sobrien{ 14277298Sobrien return malloc (n); 14377298Sobrien} 14477298Sobrien 14577298Sobrienint main (int argc, char **argv) 14677298Sobrien{ 14777298Sobrien int k; 14877298Sobrien int result; 14977298Sobrien size_t i; 15077298Sobrien void **pointers; 15177298Sobrien void **work; 15277298Sobrien 15377298Sobrien if (argc > 1) 15477298Sobrien k = atoi (argv[1]); 15577298Sobrien else 15677298Sobrien k = 10; 15777298Sobrien 158218822Sdim pointers = XNEWVEC (void*, k); 159218822Sdim work = XNEWVEC (void*, k); 16077298Sobrien 16177298Sobrien for (i = 0; i < k; ++i) 16277298Sobrien { 16377298Sobrien pointers[i] = (void *) random (); 16477298Sobrien printf ("%x\n", pointers[i]); 16577298Sobrien } 16677298Sobrien 16777298Sobrien sort_pointers (k, pointers, work); 16877298Sobrien 16977298Sobrien printf ("\nSorted\n\n"); 17077298Sobrien 17177298Sobrien result = 0; 17277298Sobrien 17377298Sobrien for (i = 0; i < k; ++i) 17477298Sobrien { 17577298Sobrien printf ("%x\n", pointers[i]); 17677298Sobrien if (i > 0 && (char*) pointers[i] < (char*) pointers[i - 1]) 17777298Sobrien result = 1; 17877298Sobrien } 17977298Sobrien 18077298Sobrien free (pointers); 18177298Sobrien free (work); 18277298Sobrien 18377298Sobrien return result; 18477298Sobrien} 18577298Sobrien 18677298Sobrien#endif 187