/* This file is part of the GNU C Library.
Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
-
+
Douglas Schmidt kindly gave permission to relicence the
code under the wxWindows licence:
-
+
From: "Douglas C. Schmidt" <schmidt@dre.vanderbilt.edu>
To: Robert Roebling <robert.roebling@uni-ulm.de>
-Subject: Re: qsort licence
+Subject: Re: qsort licence
Date: Mon, 23 Jul 2007 03:44:25 -0500
Sender: schmidt@dre.vanderbilt.edu
Message-Id: <20070723084426.64F511000A8@tango.dre.vanderbilt.edu>
/* 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); \
+#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.
} 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)
+#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
stack size is needed (actually O(1) in this case)! */
void wxQsort(void *const pbase, size_t total_elems,
- size_t size, CMPFUNCDATA cmp, const void* user_data)
+ size_t size, CMPFUNCDATA cmp, const void* user_data)
{
register char *base_ptr = (char *) pbase;
const size_t max_thresh = MAX_THRESH * size;
char *left_ptr;
char *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 * ((hi - lo) / size >> 1);
-
- if ((*cmp) ((void *) mid, (void *) lo, user_data) < 0)
- SWAP (mid, lo, size);
- if ((*cmp) ((void *) hi, (void *) mid, user_data) < 0)
- SWAP (mid, hi, size);
- else
- goto jump_over;
- if ((*cmp) ((void *) mid, (void *) lo, user_data) < 0)
- SWAP (mid, lo, size);
- jump_over:;
- 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 *) mid, user_data) < 0)
- left_ptr += size;
-
- while ((*cmp) ((void *) mid, (void *) right_ptr, user_data) < 0)
- right_ptr -= size;
-
- if (left_ptr < right_ptr)
- {
- SWAP (left_ptr, right_ptr, size);
- if (mid == left_ptr)
- mid = right_ptr;
- else if (mid == right_ptr)
- mid = left_ptr;
- left_ptr += size;
- right_ptr -= size;
- }
- else if (left_ptr == right_ptr)
- {
- left_ptr += size;
- right_ptr -= size;
- break;
- }
- }
- while (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 * ((hi - lo) / size >> 1);
+
+ if ((*cmp) ((void *) mid, (void *) lo, user_data) < 0)
+ SWAP (mid, lo, size);
+ if ((*cmp) ((void *) hi, (void *) mid, user_data) < 0)
+ SWAP (mid, hi, size);
+ else
+ goto jump_over;
+ if ((*cmp) ((void *) mid, (void *) lo, user_data) < 0)
+ SWAP (mid, lo, size);
+ jump_over:;
+ 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 *) mid, user_data) < 0)
+ left_ptr += size;
+
+ while ((*cmp) ((void *) mid, (void *) right_ptr, user_data) < 0)
+ right_ptr -= size;
+
+ if (left_ptr < right_ptr)
+ {
+ SWAP (left_ptr, right_ptr, size);
+ if (mid == left_ptr)
+ mid = right_ptr;
+ else if (mid == right_ptr)
+ mid = left_ptr;
+ 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,
if ((size_t) (right_ptr - lo) <= max_thresh)
{
if ((size_t) (hi - left_ptr) <= max_thresh)
- /* Ignore both small partitions. */
+ /* Ignore both small partitions. */
POP (lo, hi);
else
- /* Ignore small left partition. */
+ /* Ignore small left partition. */
lo = left_ptr;
}
else if ((size_t) (hi - left_ptr) <= max_thresh)
- /* Ignore small right partition. */
+ /* Ignore small right partition. */
hi = right_ptr;
else if ((right_ptr - lo) > (hi - left_ptr))
{
- /* Push larger left partition indices. */
+ /* Push larger left partition indices. */
PUSH (lo, right_ptr);
lo = left_ptr;
}
else
{
- /* Push larger right partition indices. */
+ /* Push larger right partition indices. */
PUSH (left_ptr, hi);
hi = right_ptr;
}
run_ptr = base_ptr + size;
while ((run_ptr += size) <= end_ptr)
{
- tmp_ptr = run_ptr - size;
- while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, user_data) < 0)
- tmp_ptr -= size;
+ tmp_ptr = run_ptr - size;
+ while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, user_data) < 0)
+ tmp_ptr -= size;
- tmp_ptr += size;
+ tmp_ptr += size;
if (tmp_ptr != run_ptr)
{
char *trav;
- trav = run_ptr + size;
- while (--trav >= run_ptr)
+ trav = run_ptr + size;
+ while (--trav >= run_ptr)
{
char c = *trav;
char *hi, *lo;
projects / wxWidgets.git / commitdiff
