[thirdparty/glibc.git] / stdlib / qsort.c

/* Copyright (C) 1991, 1992, 1996, 1997 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Written by Douglas C. Schmidt (schmidt@ics.uci.edu).

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public
   License along with the GNU C Library; see the file COPYING.LIB.  If not,
   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.  */

#include <stdlib.h>
#include <string.h>

extern void _quicksort __P ((void *const pbase, size_t total_elems,
			     size_t size, __compar_fn_t cmp));

/* Byte-wise swap two items of size SIZE. */
#define SWAP(a, b, size)						      \
  do									      \
    {									      \
      register size_t __size = (size);					      \
      register char *__a = (a), *__b = (b);				      \
      do								      \
	{								      \
	  char __tmp = *__a;						      \
	  *__a++ = *__b;						      \
	  *__b++ = __tmp;						      \
	} while (--__size > 0);						      \
    } while (0)

/* Discontinue quicksort algorithm when partition gets below this size.
   This particular magic number was chosen to work best on a Sun 4/260. */
#define MAX_THRESH 4

/* Stack node declarations used to store unfulfilled partition obligations. */
typedef struct
  {
    char *lo;
    char *hi;
  } stack_node;

/* The next 4 #defines implement a very fast in-line stack abstraction. */
#define STACK_SIZE	(8 * sizeof(unsigned long int))
#define PUSH(low, high)	((void) ((top->lo = (low)), (top->hi = (high)), ++top))
#define	POP(low, high)	((void) (--top, (low = top->lo), (high = top->hi)))
#define	STACK_NOT_EMPTY	(stack < top)


/* Order size using quicksort.  This implementation incorporates
   four optimizations discussed in Sedgewick:

   1. Non-recursive, using an explicit stack of pointer that store the
      next array partition to sort.  To save time, this maximum amount
      of space required to store an array of MAX_INT is allocated on the
      stack.  Assuming a 32-bit integer, this needs only 32 *
      sizeof(stack_node) == 136 bits.  Pretty cheap, actually.

   2. Chose the pivot element using a median-of-three decision tree.
      This reduces the probability of selecting a bad pivot value and
      eliminates certain extraneous comparisons.

   3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
      insertion sort to order the MAX_THRESH items within each partition.
      This is a big win, since insertion sort is faster for small, mostly
      sorted array segments.

   4. The larger of the two sub-partitions is always pushed onto the
      stack first, with the algorithm then concentrating on the
      smaller partition.  This *guarantees* no more than log (n)
      stack size is needed (actually O(1) in this case)!  */

void
_quicksort (pbase, total_elems, size, cmp)
     void *const pbase;
     size_t total_elems;
     size_t size;
     __compar_fn_t cmp;
{
  register char *base_ptr = (char *) pbase;

  /* Allocating SIZE bytes for a pivot buffer facilitates a better
     algorithm below since we can do comparisons directly on the pivot. */
  char *pivot_buffer = (char *) __alloca (size);
  const size_t max_thresh = MAX_THRESH * size;

  if (total_elems == 0)
    /* Avoid lossage with unsigned arithmetic below.  */
    return;

  if (total_elems > MAX_THRESH)
    {
      char *lo = base_ptr;
      char *hi = &lo[size * (total_elems - 1)];
      /* Largest size needed for 32-bit int!!! */
      stack_node stack[STACK_SIZE];
      stack_node *top = stack + 1;

      while (STACK_NOT_EMPTY)
        {
          char *left_ptr;
          char *right_ptr;

	  char *pivot = pivot_buffer;

	  /* Select median value from among LO, MID, and HI. Rearrange
	     LO and HI so the three values are sorted. This lowers the
	     probability of picking a pathological pivot value and
	     skips a comparison for both the LEFT_PTR and RIGHT_PTR. */

	  char *mid = lo + size * ((hi - lo) / size >> 1);

	  if ((*cmp) ((void *) mid, (void *) lo) < 0)
	    SWAP (mid, lo, size);
	  if ((*cmp) ((void *) hi, (void *) mid) < 0)
	    SWAP (mid, hi, size);
	  else
	    goto jump_over;
	  if ((*cmp) ((void *) mid, (void *) lo) < 0)
	    SWAP (mid, lo, size);
	jump_over:;
	  memcpy (pivot, mid, size);
	  pivot = pivot_buffer;

	  left_ptr  = lo + size;
	  right_ptr = hi - size;

	  /* Here's the famous ``collapse the walls'' section of quicksort.
	     Gotta like those tight inner loops!  They are the main reason
	     that this algorithm runs much faster than others. */
	  do
	    {
	      while ((*cmp) ((void *) left_ptr, (void *) pivot) < 0)
		left_ptr += size;

	      while ((*cmp) ((void *) pivot, (void *) right_ptr) < 0)
		right_ptr -= size;

	      if (left_ptr < right_ptr)
		{
		  SWAP (left_ptr, right_ptr, size);
		  left_ptr += size;
		  right_ptr -= size;
		}
	      else if (left_ptr == right_ptr)
		{
		  left_ptr += size;
		  right_ptr -= size;
		  break;
		}
	    }
	  while (left_ptr <= right_ptr);

          /* Set up pointers for next iteration.  First determine whether
             left and right partitions are below the threshold size.  If so,
             ignore one or both.  Otherwise, push the larger partition's
             bounds on the stack and continue sorting the smaller one. */

          if ((size_t) (right_ptr - lo) <= max_thresh)
            {
              if ((size_t) (hi - left_ptr) <= max_thresh)
		/* Ignore both small partitions. */
                POP (lo, hi);
              else
		/* Ignore small left partition. */
                lo = left_ptr;
            }
          else if ((size_t) (hi - left_ptr) <= max_thresh)
	    /* Ignore small right partition. */
            hi = right_ptr;
          else if ((right_ptr - lo) > (hi - left_ptr))
            {
	      /* Push larger left partition indices. */
              PUSH (lo, right_ptr);
              lo = left_ptr;
            }
          else
            {
	      /* Push larger right partition indices. */
              PUSH (left_ptr, hi);
              hi = right_ptr;
            }
        }
    }

  /* Once the BASE_PTR array is partially sorted by quicksort the rest
     is completely sorted using insertion sort, since this is efficient
     for partitions below MAX_THRESH size. BASE_PTR points to the beginning
     of the array to sort, and END_PTR points at the very last element in
     the array (*not* one beyond it!). */

#define min(x, y) ((x) < (y) ? (x) : (y))

  {
    char *const end_ptr = &base_ptr[size * (total_elems - 1)];
    char *tmp_ptr = base_ptr;
    char *thresh = min(end_ptr, base_ptr + max_thresh);
    register char *run_ptr;

    /* Find smallest element in first threshold and place it at the
       array's beginning.  This is the smallest array element,
       and the operation speeds up insertion sort's inner loop. */

    for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
      if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr) < 0)
        tmp_ptr = run_ptr;

    if (tmp_ptr != base_ptr)
      SWAP (tmp_ptr, base_ptr, size);

    /* Insertion sort, running from left-hand-side up to right-hand-side.  */

    run_ptr = base_ptr + size;
    while ((run_ptr += size) <= end_ptr)
      {
	tmp_ptr = run_ptr - size;
	while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr) < 0)
	  tmp_ptr -= size;

	tmp_ptr += size;
        if (tmp_ptr != run_ptr)
          {
            char *trav;

	    trav = run_ptr + size;
	    while (--trav >= run_ptr)
              {
                char c = *trav;
                char *hi, *lo;

                for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
                  *hi = *lo;
                *hi = c;
              }
          }
      }
  }
}
Commit	Line	Data
7cc27f44	1	/* Copyright (C) 1991, 1992, 1996, 1997 Free Software Foundation, Inc.
6d52618b UD	2	This file is part of the GNU C Library.
6d52618b UD	3	Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
28f540f4	4
6d52618b UD	5	The GNU C Library is free software; you can redistribute it and/or
	6	modify it under the terms of the GNU Library General Public License as
	7	published by the Free Software Foundation; either version 2 of the
	8	License, or (at your option) any later version.
28f540f4	9
6d52618b UD	10	The GNU C Library is distributed in the hope that it will be useful,
	11	but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	13	Library General Public License for more details.
28f540f4	14
6d52618b UD	15	You should have received a copy of the GNU Library General Public
	16	License along with the GNU C Library; see the file COPYING.LIB. If not,
	17	write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
	18	Boston, MA 02111-1307, USA. */
28f540f4	19
28f540f4 RM	20	#include <stdlib.h>
	21	#include <string.h>
	22
7434ccad UD	23	extern void _quicksort __P ((void *const pbase, size_t total_elems,
	24	size_t size, __compar_fn_t cmp));
	25
28f540f4 RM	26	/* Byte-wise swap two items of size SIZE. */
	27	#define SWAP(a, b, size) \
	28	do \
	29	{ \
	30	register size_t __size = (size); \
	31	register char __a = (a), __b = (b); \
	32	do \
	33	{ \
	34	char __tmp = *__a; \
	35	__a++ = __b; \
	36	*__b++ = __tmp; \
	37	} while (--__size > 0); \
	38	} while (0)
	39
	40	/* Discontinue quicksort algorithm when partition gets below this size.
	41	This particular magic number was chosen to work best on a Sun 4/260. */
	42	#define MAX_THRESH 4
	43
	44	/* Stack node declarations used to store unfulfilled partition obligations. */
6d52618b	45	typedef struct
28f540f4 RM	46	{
	47	char *lo;
	48	char *hi;
	49	} stack_node;
	50
	51	/* The next 4 #defines implement a very fast in-line stack abstraction. */
	52	#define STACK_SIZE (8 * sizeof(unsigned long int))
	53	#define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
	54	#define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi)))
6d52618b	55	#define STACK_NOT_EMPTY (stack < top)
28f540f4 RM	56
	57
	58	/* Order size using quicksort. This implementation incorporates
	59	four optimizations discussed in Sedgewick:
	60
6d52618b UD	61	1. Non-recursive, using an explicit stack of pointer that store the
	62	next array partition to sort. To save time, this maximum amount
	63	of space required to store an array of MAX_INT is allocated on the
	64	stack. Assuming a 32-bit integer, this needs only 32 *
28f540f4 RM	65	sizeof(stack_node) == 136 bits. Pretty cheap, actually.
	66
	67	2. Chose the pivot element using a median-of-three decision tree.
6d52618b	68	This reduces the probability of selecting a bad pivot value and
28f540f4 RM	69	eliminates certain extraneous comparisons.
	70
	71	3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
6d52618b	72	insertion sort to order the MAX_THRESH items within each partition.
28f540f4	73	This is a big win, since insertion sort is faster for small, mostly
6d52618b	74	sorted array segments.
28f540f4 RM	75
	76	4. The larger of the two sub-partitions is always pushed onto the
	77	stack first, with the algorithm then concentrating on the
	78	smaller partition. This guarantees no more than log (n)
	79	stack size is needed (actually O(1) in this case)! */
	80
	81	void
7cc27f44 UD	82	_quicksort (pbase, total_elems, size, cmp)
	83	void *const pbase;
	84	size_t total_elems;
	85	size_t size;
1fb05e3d	86	__compar_fn_t cmp;
28f540f4 RM	87	{
	88	register char base_ptr = (char ) pbase;
	89
	90	/* Allocating SIZE bytes for a pivot buffer facilitates a better
	91	algorithm below since we can do comparisons directly on the pivot. */
	92	char pivot_buffer = (char ) __alloca (size);
7cc27f44	93	const size_t max_thresh = MAX_THRESH * size;
28f540f4 RM	94
	95	if (total_elems == 0)
	96	/* Avoid lossage with unsigned arithmetic below. */
	97	return;
	98
	99	if (total_elems > MAX_THRESH)
	100	{
	101	char *lo = base_ptr;
	102	char hi = &lo[size (total_elems - 1)];
	103	/* Largest size needed for 32-bit int!!! */
	104	stack_node stack[STACK_SIZE];
	105	stack_node *top = stack + 1;
	106
	107	while (STACK_NOT_EMPTY)
	108	{
	109	char *left_ptr;
	110	char *right_ptr;
	111
	112	char *pivot = pivot_buffer;
	113
	114	/* Select median value from among LO, MID, and HI. Rearrange
6d52618b UD	115	LO and HI so the three values are sorted. This lowers the
6d52618b UD	116	probability of picking a pathological pivot value and
28f540f4 RM	117	skips a comparison for both the LEFT_PTR and RIGHT_PTR. */
	118
	119	char mid = lo + size ((hi - lo) / size >> 1);
	120
7cc27f44 UD	121	if ((cmp) ((void ) mid, (void *) lo) < 0)
	122	SWAP (mid, lo, size);
	123	if ((cmp) ((void ) hi, (void *) mid) < 0)
	124	SWAP (mid, hi, size);
6d52618b	125	else
28f540f4	126	goto jump_over;
7cc27f44 UD	127	if ((cmp) ((void ) mid, (void *) lo) < 0)
7cc27f44 UD	128	SWAP (mid, lo, size);
28f540f4	129	jump_over:;
7cc27f44	130	memcpy (pivot, mid, size);
28f540f4 RM	131	pivot = pivot_buffer;
	132
	133	left_ptr = lo + size;
6d52618b	134	right_ptr = hi - size;
28f540f4	135
6d52618b UD	136	/* Here's the famous ``collapse the walls'' section of quicksort.
6d52618b UD	137	Gotta like those tight inner loops! They are the main reason
28f540f4	138	that this algorithm runs much faster than others. */
6d52618b	139	do
28f540f4	140	{
7cc27f44	141	while ((cmp) ((void ) left_ptr, (void *) pivot) < 0)
28f540f4 RM	142	left_ptr += size;
28f540f4 RM	143
7cc27f44	144	while ((cmp) ((void ) pivot, (void *) right_ptr) < 0)
28f540f4 RM	145	right_ptr -= size;
28f540f4 RM	146
6d52618b	147	if (left_ptr < right_ptr)
28f540f4	148	{
7cc27f44	149	SWAP (left_ptr, right_ptr, size);
28f540f4 RM	150	left_ptr += size;
	151	right_ptr -= size;
	152	}
6d52618b	153	else if (left_ptr == right_ptr)
28f540f4 RM	154	{
	155	left_ptr += size;
	156	right_ptr -= size;
	157	break;
	158	}
6d52618b	159	}
28f540f4 RM	160	while (left_ptr <= right_ptr);
	161
	162	/* Set up pointers for next iteration. First determine whether
6d52618b	163	left and right partitions are below the threshold size. If so,
28f540f4 RM	164	ignore one or both. Otherwise, push the larger partition's
	165	bounds on the stack and continue sorting the smaller one. */
	166
	167	if ((size_t) (right_ptr - lo) <= max_thresh)
	168	{
	169	if ((size_t) (hi - left_ptr) <= max_thresh)
	170	/* Ignore both small partitions. */
7cc27f44	171	POP (lo, hi);
28f540f4	172	else
6d52618b	173	/* Ignore small left partition. */
28f540f4 RM	174	lo = left_ptr;
	175	}
	176	else if ((size_t) (hi - left_ptr) <= max_thresh)
	177	/* Ignore small right partition. */
	178	hi = right_ptr;
	179	else if ((right_ptr - lo) > (hi - left_ptr))
6d52618b	180	{
28f540f4	181	/* Push larger left partition indices. */
7cc27f44	182	PUSH (lo, right_ptr);
28f540f4 RM	183	lo = left_ptr;
	184	}
	185	else
6d52618b	186	{
28f540f4	187	/* Push larger right partition indices. */
7cc27f44	188	PUSH (left_ptr, hi);
28f540f4 RM	189	hi = right_ptr;
	190	}
	191	}
	192	}
	193
	194	/* Once the BASE_PTR array is partially sorted by quicksort the rest
6d52618b UD	195	is completely sorted using insertion sort, since this is efficient
6d52618b UD	196	for partitions below MAX_THRESH size. BASE_PTR points to the beginning
28f540f4 RM	197	of the array to sort, and END_PTR points at the very last element in
	198	the array (not one beyond it!). */
	199
	200	#define min(x, y) ((x) < (y) ? (x) : (y))
	201
	202	{
7cc27f44	203	char const end_ptr = &base_ptr[size (total_elems - 1)];
28f540f4 RM	204	char *tmp_ptr = base_ptr;
	205	char *thresh = min(end_ptr, base_ptr + max_thresh);
	206	register char *run_ptr;
	207
	208	/* Find smallest element in first threshold and place it at the
	209	array's beginning. This is the smallest array element,
	210	and the operation speeds up insertion sort's inner loop. */
	211
	212	for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
7cc27f44	213	if ((cmp) ((void ) run_ptr, (void *) tmp_ptr) < 0)
28f540f4 RM	214	tmp_ptr = run_ptr;
	215
	216	if (tmp_ptr != base_ptr)
7cc27f44	217	SWAP (tmp_ptr, base_ptr, size);
28f540f4 RM	218
	219	/* Insertion sort, running from left-hand-side up to right-hand-side. */
	220
	221	run_ptr = base_ptr + size;
	222	while ((run_ptr += size) <= end_ptr)
	223	{
	224	tmp_ptr = run_ptr - size;
7cc27f44	225	while ((cmp) ((void ) run_ptr, (void *) tmp_ptr) < 0)
28f540f4 RM	226	tmp_ptr -= size;
	227
	228	tmp_ptr += size;
	229	if (tmp_ptr != run_ptr)
	230	{
	231	char *trav;
	232
	233	trav = run_ptr + size;
	234	while (--trav >= run_ptr)
	235	{
	236	char c = *trav;
	237	char hi, lo;
	238
	239	for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
	240	hi = lo;
	241	*hi = c;
	242	}
	243	}
	244	}
	245	}
	246	}