mf_qsort.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:6k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /* Copyright (C) 2000 MySQL AB
  2.    This program is free software; you can redistribute it and/or modify
  3.    it under the terms of the GNU General Public License as published by
  4.    the Free Software Foundation; either version 2 of the License, or
  5.    (at your option) any later version.
  6.    This program is distributed in the hope that it will be useful,
  7.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  8.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  9.    GNU General Public License for more details.
  10.    You should have received a copy of the GNU General Public License
  11.    along with this program; if not, write to the Free Software
  12.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  13. /*
  14.   qsort implementation optimized for comparison of pointers
  15.   Inspired by the qsort implementations by Douglas C. Schmidt,
  16.   and Bentley & McIlroy's "Engineering a Sort Function".
  17. */
  18. #include "mysys_priv.h"
  19. #ifndef SCO
  20. #include <m_string.h>
  21. #endif
  22. /* We need to use qsort with 2 different compare functions */
  23. #ifdef QSORT_EXTRA_CMP_ARGUMENT
  24. #define CMP(A,B) ((*cmp)(cmp_argument,(A),(B)))
  25. #else
  26. #define CMP(A,B) ((*cmp)((A),(B)))
  27. #endif
  28. #define SWAP(A, B, size,swap_ptrs)
  29. do {
  30.    if (swap_ptrs)
  31.    {
  32.      reg1 char **a = (char**) (A), **b = (char**) (B);  
  33.      char *tmp = *a; *a++ = *b; *b++ = tmp;
  34.    }
  35.    else
  36.    {
  37.      reg1 char *a = (A), *b = (B);
  38.      reg3 char *end= a+size;
  39.      do
  40.      {
  41.        char tmp = *a; *a++ = *b; *b++ = tmp;
  42.      } while (a < end);
  43.    }
  44. } while (0)
  45. /* Put the median in the middle argument */
  46. #define MEDIAN(low, mid, high)
  47. {
  48.     if (CMP(high,low) < 0)
  49.       SWAP(high, low, size, ptr_cmp);
  50.     if (CMP(mid, low) < 0)
  51.       SWAP(mid, low, size, ptr_cmp);
  52.     else if (CMP(high, mid) < 0)
  53.       SWAP(mid, high, size, ptr_cmp);
  54. }
  55. /* The following node is used to store ranges to avoid recursive calls */
  56. typedef struct st_stack
  57. {
  58.   char *low,*high;
  59. } stack_node;
  60. #define PUSH(LOW,HIGH)  {stack_ptr->low = LOW; stack_ptr++->high = HIGH;}
  61. #define POP(LOW,HIGH)   {LOW = (--stack_ptr)->low; HIGH = stack_ptr->high;}
  62. /* The following stack size is enough for ulong ~0 elements */
  63. #define STACK_SIZE (8 * sizeof(unsigned long int))
  64. #define THRESHOLD_FOR_INSERT_SORT 10
  65. #if defined(QSORT_TYPE_IS_VOID)
  66. #define SORT_RETURN return
  67. #else
  68. #define SORT_RETURN return 0
  69. #endif
  70. /****************************************************************************
  71. ** 'standard' quicksort with the following extensions:
  72. **
  73. ** Can be compiled with the qsort2_cmp compare function
  74. ** Store ranges on stack to avoid recursion
  75. ** Use insert sort on small ranges
  76. ** Optimize for sorting of pointers (used often by MySQL)
  77. ** Use median comparison to find partition element
  78. *****************************************************************************/
  79. #ifdef QSORT_EXTRA_CMP_ARGUMENT
  80. qsort_t qsort2(void *base_ptr, size_t count, size_t size, qsort2_cmp cmp,
  81.        void *cmp_argument)
  82. #else
  83. qsort_t qsort(void *base_ptr, size_t count, size_t size, qsort_cmp cmp)
  84. #endif
  85. {
  86.   char *low, *high, *pivot;
  87.   stack_node stack[STACK_SIZE], *stack_ptr;
  88.   my_bool ptr_cmp;
  89.   /* Handle the simple case first */
  90.   /* This will also make the rest of the code simpler */
  91.   if (count <= 1)
  92.     SORT_RETURN;
  93.   low  = (char*) base_ptr;
  94.   high = low+ size * (count - 1);
  95.   stack_ptr = stack + 1;
  96. #ifdef HAVE_purify
  97.   /* The first element in the stack will be accessed for the last POP */
  98.   stack[0].low=stack[0].high=0;
  99. #endif
  100.   pivot = (char *) my_alloca((int) size);
  101.   ptr_cmp= size == sizeof(char*) && !((low - (char*) 0)& (sizeof(char*)-1));
  102.   /* The following loop sorts elements between high and low */
  103.   do
  104.   {
  105.     char *low_ptr, *high_ptr, *mid;
  106.     count=((size_t) (high - low) / size)+1;
  107.     /* If count is small, then an insert sort is faster than qsort */
  108.     if (count < THRESHOLD_FOR_INSERT_SORT)
  109.     {
  110.       for (low_ptr = low + size; low_ptr <= high; low_ptr += size)
  111.       {
  112. char *ptr;
  113. for (ptr = low_ptr; ptr > low && CMP(ptr - size, ptr) > 0;
  114.      ptr -= size)
  115.   SWAP(ptr, ptr - size, size, ptr_cmp);
  116.       }
  117.       POP(low, high);
  118.       continue;
  119.     }
  120.     /* Try to find a good middle element */
  121.     mid= low + size * (count >> 1);
  122.     if (count > 40) /* Must be bigger than 24 */
  123.     {
  124.       size_t step = size* (count / 8);
  125.       MEDIAN(low, low + step, low+step*2);
  126.       MEDIAN(mid - step, mid, mid+step);
  127.       MEDIAN(high - 2 * step, high-step, high);
  128.       /* Put best median in 'mid' */
  129.       MEDIAN(low+step, mid, high-step);
  130.       low_ptr  = low;
  131.       high_ptr = high;
  132.     }
  133.     else
  134.     {
  135.       MEDIAN(low, mid, high);
  136.       /* The low and high argument are already in sorted against 'pivot' */
  137.       low_ptr  = low + size;
  138.       high_ptr = high - size;
  139.     }
  140.     memcpy(pivot, mid, size);
  141.     do
  142.     {
  143.       while (CMP(low_ptr, pivot) < 0)
  144. low_ptr += size;
  145.       while (CMP(pivot, high_ptr) < 0)
  146. high_ptr -= size;
  147.       if (low_ptr < high_ptr)
  148.       {
  149. SWAP(low_ptr, high_ptr, size, ptr_cmp);
  150. low_ptr += size;
  151. high_ptr -= size;
  152.       }
  153.       else 
  154.       {
  155. if (low_ptr == high_ptr)
  156. {
  157.   low_ptr += size;
  158.   high_ptr -= size;
  159. }
  160. break;
  161.       }
  162.     }
  163.     while (low_ptr <= high_ptr);
  164.     /*
  165.       Prepare for next iteration.
  166.        Skip partitions of size 1 as these doesn't have to be sorted
  167.        Push the larger partition and sort the smaller one first.
  168.        This ensures that the stack is keept small.
  169.     */
  170.     if ((int) (high_ptr - low) <= 0)
  171.     {
  172.       if ((int) (high - low_ptr) <= 0)
  173.       {
  174. POP(low, high); /* Nothing more to sort */
  175.       }
  176.       else
  177. low = low_ptr; /* Ignore small left part. */
  178.     }
  179.     else if ((int) (high - low_ptr) <= 0)
  180.       high = high_ptr; /* Ignore small right part. */
  181.     else if ((high_ptr - low) > (high - low_ptr))
  182.     {
  183.       PUSH(low, high_ptr); /* Push larger left part */
  184.       low = low_ptr;
  185.     }
  186.     else
  187.     {
  188.       PUSH(low_ptr, high); /* Push larger right part */
  189.       high = high_ptr;
  190.     }
  191.   } while (stack_ptr > stack);
  192.   my_afree(pivot);
  193.   SORT_RETURN;
  194. }