00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include <config.h>
00024
00025 #include <drizzled/internal/my_sys.h>
00026 #include <drizzled/internal/m_string.h>
00027
00028 namespace drizzled
00029 {
00030 namespace internal
00031 {
00032
00033
00034 #ifdef QSORT_EXTRA_CMP_ARGUMENT
00035 #define CMP(A,B) ((*cmp)(cmp_argument,(A),(B)))
00036 #else
00037 #define CMP(A,B) ((*cmp)((A),(B)))
00038 #endif
00039
00040 #define SWAP(A, B, size,swap_ptrs) \
00041 do { \
00042 if (swap_ptrs) \
00043 { \
00044 char **a = (char**) (A), **b = (char**) (B); \
00045 char *tmp = *a; *a++ = *b; *b++ = tmp; \
00046 } \
00047 else \
00048 { \
00049 char *a = (A), *b = (B); \
00050 char *end= a+size; \
00051 do \
00052 { \
00053 char tmp = *a; *a++ = *b; *b++ = tmp; \
00054 } while (a < end); \
00055 } \
00056 } while (0)
00057
00058
00059 #define MEDIAN(low, mid, high) \
00060 { \
00061 if (CMP(high,low) < 0) \
00062 SWAP(high, low, size, ptr_cmp); \
00063 if (CMP(mid, low) < 0) \
00064 SWAP(mid, low, size, ptr_cmp); \
00065 else if (CMP(high, mid) < 0) \
00066 SWAP(mid, high, size, ptr_cmp); \
00067 }
00068
00069
00070
00071 typedef struct st_stack
00072 {
00073 char *low,*high;
00074 } stack_node;
00075
00076 #define PUSH(LOW,HIGH) {stack_ptr->low = LOW; stack_ptr++->high = HIGH;}
00077 #define POP(LOW,HIGH) {LOW = (--stack_ptr)->low; HIGH = stack_ptr->high;}
00078
00079
00080 #define STACK_SIZE (8 * sizeof(unsigned long int))
00081 #define THRESHOLD_FOR_INSERT_SORT 10
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093 #ifdef QSORT_EXTRA_CMP_ARGUMENT
00094 void my_qsort2(void *base_ptr, size_t count, size_t size,
00095 qsort2_cmp cmp, void *cmp_argument)
00096 #else
00097 void my_qsort(void *base_ptr, size_t count, size_t size,
00098 qsort_cmp cmp)
00099 #endif
00100 {
00101 char *low, *high, *pivot;
00102 stack_node stack[STACK_SIZE], *stack_ptr;
00103 bool ptr_cmp;
00104
00105
00106 if (count <= 1)
00107 return;
00108
00109 low = (char*) base_ptr;
00110 high = low+ size * (count - 1);
00111 stack_ptr = stack + 1;
00112 #ifdef HAVE_VALGRIND
00113
00114 stack[0].low=stack[0].high=0;
00115 #endif
00116 pivot = (char *) malloc(size);
00117 ptr_cmp= size == sizeof(char*) && !((low - (char*) 0)& (sizeof(char*)-1));
00118
00119
00120 do
00121 {
00122 char *low_ptr, *high_ptr, *mid;
00123
00124 count=((size_t) (high - low) / size)+1;
00125
00126 if (count < THRESHOLD_FOR_INSERT_SORT)
00127 {
00128 for (low_ptr = low + size; low_ptr <= high; low_ptr += size)
00129 {
00130 char *ptr;
00131 for (ptr = low_ptr; ptr > low && CMP(ptr - size, ptr) > 0;
00132 ptr -= size)
00133 SWAP(ptr, ptr - size, size, ptr_cmp);
00134 }
00135 POP(low, high);
00136 continue;
00137 }
00138
00139
00140 mid= low + size * (count >> 1);
00141 if (count > 40)
00142 {
00143 size_t step = size* (count / 8);
00144 MEDIAN(low, low + step, low+step*2);
00145 MEDIAN(mid - step, mid, mid+step);
00146 MEDIAN(high - 2 * step, high-step, high);
00147
00148 MEDIAN(low+step, mid, high-step);
00149 low_ptr = low;
00150 high_ptr = high;
00151 }
00152 else
00153 {
00154 MEDIAN(low, mid, high);
00155
00156 low_ptr = low + size;
00157 high_ptr = high - size;
00158 }
00159 memcpy(pivot, mid, size);
00160
00161 do
00162 {
00163 while (CMP(low_ptr, pivot) < 0)
00164 low_ptr += size;
00165 while (CMP(pivot, high_ptr) < 0)
00166 high_ptr -= size;
00167
00168 if (low_ptr < high_ptr)
00169 {
00170 SWAP(low_ptr, high_ptr, size, ptr_cmp);
00171 low_ptr += size;
00172 high_ptr -= size;
00173 }
00174 else
00175 {
00176 if (low_ptr == high_ptr)
00177 {
00178 low_ptr += size;
00179 high_ptr -= size;
00180 }
00181 break;
00182 }
00183 }
00184 while (low_ptr <= high_ptr);
00185
00186
00187
00188
00189
00190
00191
00192
00193 if ((int) (high_ptr - low) <= 0)
00194 {
00195 if ((int) (high - low_ptr) <= 0)
00196 {
00197 POP(low, high);
00198 }
00199 else
00200 low = low_ptr;
00201 }
00202 else if ((int) (high - low_ptr) <= 0)
00203 high = high_ptr;
00204 else if ((high_ptr - low) > (high - low_ptr))
00205 {
00206 PUSH(low, high_ptr);
00207 low = low_ptr;
00208 }
00209 else
00210 {
00211 PUSH(low_ptr, high);
00212 high = high_ptr;
00213 }
00214 } while (stack_ptr > stack);
00215 free(pivot);
00216 return;
00217 }
00218
00219 }
00220 }