Re: PATCH: New libiberty sorting routine

[Mark Mitchell <mark at codesourcery dot com>]

>>>>> "Richard" == Richard Henderson <rth@cygnus.com> writes:

    Richard> On Sun, Apr 23, 2000 at 06:01:30PM -0700, Mark Mitchell
    Richard> wrote:
    >> + /* Figure out the endianness of the machine.  */ + for (i =
    >> 0; i < sizeof (size_t); ++i) + ((char *)&j)[i] = i; +
    >> big_endian_p = (((char *)&j)[0] == 0);

    Richard> This is always false.

Fixed thusly, I hope.  (I still only have a little-endian machine to
test on -- if I've still biffed it shout.  I'd appreciate it if
someone with a big-endian machine would do:

  gcc -DUNIT_TEST -I../include sort.c
  ./a.out

and verify that the output contains first an unsorted list of
pointers, and then a sorted list.  The program should exit with a
successful exit code if everything worked.

Thanks,

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com

2000-04-23  Mark Mitchell  <mark@codesourcery.com>

	* sort.c (sort_pointers): Fix endianness bugs.

Index: sort.c
===================================================================
RCS file: /cvs/gcc/egcs/libiberty/sort.c,v
retrieving revision 1.1
diff -c -p -r1.1 sort.c
*** sort.c	2000/04/24 00:51:08	1.1
--- sort.c	2000/04/24 05:51:41
*************** Boston, MA 02111-1307, USA.  */
*** 29,37 ****
  #include <stdlib.h>
  #endif
  
! /* POINTERSP and WORKP both point to arrays of N pointers.  When
!    this function returns POINTERSP will point to a sorted version of
!    the original array pointed to by POINTERSP.  */
  
  void sort_pointers (n, pointers, work)
       size_t n;
--- 29,36 ----
  #include <stdlib.h>
  #endif
  
! /* POINTERS and WORK are both arrays of N pointers.  When this
!    function returns POINTERS will be sorted in ascending order.  */
  
  void sort_pointers (n, pointers, work)
       size_t n;
*************** void sort_pointers (n, pointers, work)
*** 63,70 ****
      abort ();
  
    /* Figure out the endianness of the machine.  */
!   for (i = 0; i < sizeof (size_t); ++i)
!     ((char *)&j)[i] = i;
    big_endian_p = (((char *)&j)[0] == 0);
  
    /* Move through the pointer values from least significant to most
--- 62,72 ----
      abort ();
  
    /* Figure out the endianness of the machine.  */
!   for (i = 0, j = 0; i < sizeof (size_t); ++i)
!     {
!       j *= (UCHAR_MAX + 1);
!       j += i;
!     }
    big_endian_p = (((char *)&j)[0] == 0);
  
    /* Move through the pointer values from least significant to most
*************** void sort_pointers (n, pointers, work)
*** 91,98 ****
        /* Compute the address of the appropriate digit in the first and
  	 one-past-the-end elements of the array.  On a little-endian
  	 machine, the least-significant digit is closest to the front.  */
!       bias = ((digit_t *) pointers) + i;
!       top = ((digit_t *) (pointers + n)) + i;
  
        /* Count how many there are of each value.  At the end of this
  	 loop, COUNT[K] will contain the number of pointers whose Ith
--- 93,100 ----
        /* Compute the address of the appropriate digit in the first and
  	 one-past-the-end elements of the array.  On a little-endian
  	 machine, the least-significant digit is closest to the front.  */
!       bias = ((digit_t *) pointers) + j;
!       top = ((digit_t *) (pointers + n)) + j;
  
        /* Count how many there are of each value.  At the end of this
  	 loop, COUNT[K] will contain the number of pointers whose Ith
*************** void sort_pointers (n, pointers, work)
*** 109,115 ****
  
        /* Now, drop the pointers into their correct locations.  */
        for (pointerp = pointers + n - 1; pointerp >= pointers; --pointerp)
! 	work[--count[((digit_t *) pointerp)[i]]] = *pointerp;
  
        /* Swap WORK and POINTERS so that POINTERS contains the sorted
  	 array.  */
--- 111,117 ----
  
        /* Now, drop the pointers into their correct locations.  */
        for (pointerp = pointers + n - 1; pointerp >= pointers; --pointerp)
! 	work[--count[((digit_t *) pointerp)[j]]] = *pointerp;
  
        /* Swap WORK and POINTERS so that POINTERS contains the sorted
  	 array.  */