mf_qsort.c:

  qsort implementation backported from 4.0 tree, the old one was buggy


mysys/mf_qsort.c:
  qsort implementation backported from 4.0 tree, the old one was buggy

1 files changed, 164 insertions, 196 deletions

diff --git a/mysys/mf_qsort.c b/mysys/mf_qsort.c
index 64e70990696..9cc937f6e8b 100644
--- a/mysys/mf_qsort.c
+++ b/mysys/mf_qsort.c
@@ -1,249 +1,217 @@
-/* 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).
+/* Copyright (C) 2000 MySQL AB
 
-   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.
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU 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,
+   This program 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.
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU 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.	*/
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
 /*
-    Modifications by monty:
-  - Uses mysys include files
-  - Small fixes to make the it a bit faster
-  - Can be compiled with a cmp function that takes one extra argument.
+  qsort implementation optimized for comparison of pointers
+  Inspired by the qsort implementations by Douglas C. Schmidt,
+  and Bentley & McIlroy's "Engineering a Sort Function".
 */
 
+
 #include "mysys_priv.h"
+#ifndef SCO
 #include <m_string.h>
+#endif
 
-/* Envoke the comparison function, returns either 0, < 0, or > 0. */
+/* We need to use qsort with 2 different compare functions */
 #ifdef QSORT_EXTRA_CMP_ARGUMENT
 #define CMP(A,B) ((*cmp)(cmp_argument,(A),(B)))
 #else
 #define CMP(A,B) ((*cmp)((A),(B)))
 #endif
 
-/* 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 8
-
-/* Stack node declarations used to store unfulfilled partition obligations. */
-typedef struct _qsort_stack_node
-  {
-    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) do {top->lo = LOW;top++->hi = HIGH;} while (0)
-#define POP(LOW,HIGH)  do {LOW = (--top)->lo;HIGH = top->hi;} while (0)
-#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.
+#define SWAP(A, B, size,swap_ptrs)			\
+do {							\
+   if (swap_ptrs)					\
+   {							\
+     reg1 char **a = (char**) (A), **b = (char**) (B);  \
+     char *tmp = *a; *a++ = *b; *b++ = tmp;		\
+   }							\
+   else							\
+   {							\
+     reg1 char *a = (A), *b = (B);			\
+     reg3 char *end= a+size;				\
+     do							\
+     {							\
+       char tmp = *a; *a++ = *b; *b++ = tmp;		\
+     } while (a < end);					\
+   }							\
+} while (0)
+
+/* Put the median in the middle argument */
+#define MEDIAN(low, mid, high)				\
+{							\
+    if (CMP(high,low) < 0)				\
+      SWAP(high, low, size, ptr_cmp);			\
+    if (CMP(mid, low) < 0)				\
+      SWAP(mid, low, size, ptr_cmp);			\
+    else if (CMP(high, mid) < 0)			\
+      SWAP(mid, high, size, ptr_cmp);			\
+}
 
-   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.
+/* The following node is used to store ranges to avoid recursive calls */
 
-   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.
+typedef struct st_stack
+{
+  char *low,*high;
+} stack_node;
 
-   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)! */
+#define PUSH(LOW,HIGH)  {stack_ptr->low = LOW; stack_ptr++->high = HIGH;}
+#define POP(LOW,HIGH)   {LOW = (--stack_ptr)->low; HIGH = stack_ptr->high;}
 
+/* The following stack size is enough for ulong ~0 elements */
+#define STACK_SIZE	(8 * sizeof(unsigned long int))
+#define THRESHOLD_FOR_INSERT_SORT 10
 #if defined(QSORT_TYPE_IS_VOID)
 #define SORT_RETURN return
 #else
 #define SORT_RETURN return 0
 #endif
 
+/****************************************************************************
+** 'standard' quicksort with the following extensions:
+**
+** Can be compiled with the qsort2_cmp compare function
+** Store ranges on stack to avoid recursion
+** Use insert sort on small ranges
+** Optimize for sorting of pointers (used often by MySQL)
+** Use median comparison to find partition element
+*****************************************************************************/
+
 #ifdef QSORT_EXTRA_CMP_ARGUMENT
-qsort_t qsort2(void *base_ptr, size_t total_elems, size_t size, qsort2_cmp cmp,
+qsort_t qsort2(void *base_ptr, size_t count, size_t size, qsort2_cmp cmp,
 	       void *cmp_argument)
 #else
-qsort_t qsort(void *base_ptr, size_t total_elems, size_t size, qsort_cmp cmp)
+qsort_t qsort(void *base_ptr, size_t count, size_t size, qsort_cmp cmp)
 #endif
 {
-  /* Allocating SIZE bytes for a pivot buffer facilitates a better
-     algorithm below since we can do comparisons directly on the pivot.
-     */
-  size_t max_thresh   = (size_t) (MAX_THRESH * size);
-  if (total_elems <= 1)
-    SORT_RETURN;		/* Crashes on MSDOS if continues */
-
-  if (total_elems > MAX_THRESH)
-  {
-    char       *lo = (char*) base_ptr;
-    char       *hi = &lo[size * (total_elems - 1)];
-    stack_node stack[STACK_SIZE]; /* Largest size needed for 32-bit int!!! */
-    stack_node *top = stack + 1;
-    char *pivot = (char *) my_alloca ((int) size);
+  char *low, *high, *pivot;
+  stack_node stack[STACK_SIZE], *stack_ptr;
+  my_bool ptr_cmp;
+  /* Handle the simple case first */
+  /* This will also make the rest of the code simpler */
+  if (count <= 1)
+    SORT_RETURN;
+
+  low  = (char*) base_ptr;
+  high = low+ size * (count - 1);
+  stack_ptr = stack + 1;
 #ifdef HAVE_purify
-    stack[0].lo=stack[0].hi=0;
+  /* The first element in the stack will be accessed for the last POP */
+  stack[0].low=stack[0].high=0;
 #endif
+  pivot = (char *) my_alloca((int) size);
+  ptr_cmp= size == sizeof(char*) && !((low - (char*) 0)& (sizeof(char*)-1));
 
-    do
+  /* The following loop sorts elements between high and low */
+  do
+  {
+    char *low_ptr, *high_ptr, *mid;
+
+    count=((size_t) (high - low) / size)+1;
+    /* If count is small, then an insert sort is faster than qsort */
+    if (count < THRESHOLD_FOR_INSERT_SORT)
     {
-      char *left_ptr,*right_ptr;
-
-      /* 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 * (((ulong) (hi - lo) / (ulong) size) >> 1);
-
-      if (CMP(hi,lo) < 0)
-	SWAP (hi, lo, size);
-      if (CMP (mid, lo) < 0)
-	SWAP (mid, lo, size);
-      else if (CMP (hi, mid) < 0)
-	SWAP (mid, hi, size);
-      memcpy (pivot, mid, size);
-
-      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
+      for (low_ptr = low + size; low_ptr <= high; low_ptr += size)
       {
-	while (CMP (left_ptr, pivot) < 0)
-	  left_ptr += size;
-
-	while (CMP (pivot, 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;
-	}
-	else
-	  break;				/* left_ptr > right_ptr */
+	char *ptr;
+	for (ptr = low_ptr; ptr > low && CMP(ptr - size, ptr) > 0;
+	     ptr -= size)
+	  SWAP(ptr, ptr - size, size, ptr_cmp);
       }
-      while (left_ptr <= right_ptr);
+      POP(low, high);
+      continue;
+    }
 
+    /* Try to find a good middle element */
+    mid= low + size * (count >> 1);
+    if (count > 40)				/* Must be bigger than 24 */
+    {
+      size_t step = size* (count / 8);
+      MEDIAN(low, low + step, low+step*2);
+      MEDIAN(mid - step, mid, mid+step);
+      MEDIAN(high - 2 * step, high-step, high);
+      /* Put best median in 'mid' */
+      MEDIAN(low+step, mid, high-step);
+      low_ptr  = low;
+      high_ptr = high;
+    }
+    else
+    {
+      MEDIAN(low, mid, high);
+      /* The low and high argument are already in sorted against 'pivot' */
+      low_ptr  = low + size;
+      high_ptr = high - size;
+    }
+    memcpy(pivot, mid, size);
 
-      /* 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. */
+    do
+    {
+      while (CMP(low_ptr, pivot) < 0)
+	low_ptr += size;
+      while (CMP(pivot, high_ptr) < 0)
+	high_ptr -= size;
 
-      if ((size_t) (right_ptr - lo) <= max_thresh)
+      if (low_ptr < high_ptr)
       {
-	if ((size_t) (hi - left_ptr) <= max_thresh)
-	  POP (lo, hi);			/* Ignore both small partitions. */
-	else
-	  lo = left_ptr;		/* Ignore small left part. */
+	SWAP(low_ptr, high_ptr, size, ptr_cmp);
+	low_ptr += size;
+	high_ptr -= size;
       }
-      else if ((size_t) (hi - left_ptr) <= max_thresh)
-	hi = right_ptr;			/* Ignore small right partition. */
-      else if ((right_ptr - lo) > (hi - left_ptr))
-      {
-	PUSH (lo, right_ptr);		/* Push larger left part */
-	lo = left_ptr;
-      }
-      else
+      else 
       {
-	PUSH (left_ptr, hi);		/* Push larger right part */
-	hi = right_ptr;
+	if (low_ptr == high_ptr)
+	{
+	  low_ptr += size;
+	  high_ptr -= size;
+	}
+	break;
       }
-    } while (STACK_NOT_EMPTY);
-    my_afree(pivot);
-  }
-
-  /* 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!). */
-
-  {
-    char *end_ptr = (char*) base_ptr + size * (total_elems - 1);
-    char *tmp_ptr = (char*) base_ptr;
-    char *thresh  = min (end_ptr, (char*) 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 (run_ptr, tmp_ptr) < 0)
-	tmp_ptr = run_ptr;
-
-    if (tmp_ptr != (char*) base_ptr)
-      SWAP (tmp_ptr, (char*) base_ptr, size);
+    }
+    while (low_ptr <= high_ptr);
 
-    /* Insertion sort, running from left-hand-side up to right-hand-side.  */
+    /*
+      Prepare for next iteration.
+       Skip partitions of size 1 as these doesn't have to be sorted
+       Push the larger partition and sort the smaller one first.
+       This ensures that the stack is keept small.
+    */
 
-    for (run_ptr = (char*) base_ptr + size;
-	 (run_ptr += size) <= end_ptr; )
+    if ((int) (high_ptr - low) <= 0)
     {
-      if (CMP (run_ptr, (tmp_ptr = run_ptr-size)) < 0)
+      if ((int) (high - low_ptr) <= 0)
       {
-	char *trav;
-	while (CMP (run_ptr, tmp_ptr -= size) < 0) ;
-	tmp_ptr += size;
-
-	/* Shift down all smaller elements, put found element in 'run_ptr' */
-	for (trav = run_ptr + size; --trav >= run_ptr;)
-	{
-	  char c = *trav;
-	  char *hi, *lo;
-
-	  for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
-	    *hi = *lo;
-	  *hi = c;
-	}
+	POP(low, high);			/* Nothing more to sort */
       }
+      else
+	low = low_ptr;			/* Ignore small left part. */
+    }
+    else if ((int) (high - low_ptr) <= 0)
+      high = high_ptr;			/* Ignore small right part. */
+    else if ((high_ptr - low) > (high - low_ptr))
+    {
+      PUSH(low, high_ptr);		/* Push larger left part */
+      low = low_ptr;
+    }
+    else
+    {
+      PUSH(low_ptr, high);		/* Push larger right part */
+      high = high_ptr;
     }
-  }
+  } while (stack_ptr > stack);
+  my_afree(pivot);
   SORT_RETURN;
 }