25 #include <drizzled/internal/my_sys.h>
26 #include <drizzled/internal/m_string.h>
32 #ifdef QSORT_EXTRA_CMP_ARGUMENT
33 #define CMP(A,B) ((*cmp)(cmp_argument,(A),(B)))
35 #define CMP(A,B) ((*cmp)((A),(B)))
38 #define SWAP(A, B, size,swap_ptrs) \
42 char **a = (char**) (A), **b = (char**) (B); \
43 char *tmp = *a; *a++ = *b; *b++ = tmp; \
47 char *a = (A), *b = (B); \
51 char tmp = *a; *a++ = *b; *b++ = tmp; \
57 #define MEDIAN(low, mid, high) \
59 if (CMP(high,low) < 0) \
60 SWAP(high, low, size, ptr_cmp); \
61 if (CMP(mid, low) < 0) \
62 SWAP(mid, low, size, ptr_cmp); \
63 else if (CMP(high, mid) < 0) \
64 SWAP(mid, high, size, ptr_cmp); \
74 #define PUSH(LOW,HIGH) {stack_ptr->low = LOW; stack_ptr++->high = HIGH;}
75 #define POP(LOW,HIGH) {LOW = (--stack_ptr)->low; HIGH = stack_ptr->high;}
78 #define STACK_SIZE (8 * sizeof(unsigned long int))
79 #define THRESHOLD_FOR_INSERT_SORT 10
91 #ifdef QSORT_EXTRA_CMP_ARGUMENT
92 void my_qsort2(
void *base_ptr,
size_t count,
size_t size,
93 qsort2_cmp cmp,
void *cmp_argument)
95 void my_qsort(
void *base_ptr,
size_t count,
size_t size,
99 char *low, *high, *pivot;
107 low = (
char*) base_ptr;
108 high = low+ size * (count - 1);
109 stack_ptr = stack + 1;
112 stack[0].low=stack[0].high=0;
114 pivot = (
char *) malloc(size);
115 ptr_cmp= size ==
sizeof(
char*) && !((low - (
char*) 0)& (
sizeof(
char*)-1));
120 char *low_ptr, *high_ptr, *mid;
122 count=((size_t) (high - low) / size)+1;
124 if (count < THRESHOLD_FOR_INSERT_SORT)
126 for (low_ptr = low + size; low_ptr <= high; low_ptr += size)
129 for (ptr = low_ptr; ptr > low && CMP(ptr - size, ptr) > 0;
131 SWAP(ptr, ptr - size, size, ptr_cmp);
138 mid= low + size * (count >> 1);
141 size_t step = size* (count / 8);
142 MEDIAN(low, low + step, low+step*2);
143 MEDIAN(mid - step, mid, mid+step);
144 MEDIAN(high - 2 * step, high-step, high);
146 MEDIAN(low+step, mid, high-step);
152 MEDIAN(low, mid, high);
154 low_ptr = low + size;
155 high_ptr = high - size;
157 memcpy(pivot, mid, size);
161 while (CMP(low_ptr, pivot) < 0)
163 while (CMP(pivot, high_ptr) < 0)
166 if (low_ptr < high_ptr)
168 SWAP(low_ptr, high_ptr, size, ptr_cmp);
174 if (low_ptr == high_ptr)
182 while (low_ptr <= high_ptr);
191 if ((
int) (high_ptr - low) <= 0)
193 if ((
int) (high - low_ptr) <= 0)
200 else if ((
int) (high - low_ptr) <= 0)
202 else if ((high_ptr - low) > (high - low_ptr))
212 }
while (stack_ptr > stack);