From 11fe6505b848a968f4c89cb3c3fd37a6a03bcaea Mon Sep 17 00:00:00 2001 From: Vadim Zeitlin Date: Fri, 27 Jul 2007 13:48:20 +0000 Subject: [PATCH] deTABbed wxQsort() git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@47745 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775 --- src/common/utilscmn.cpp | 156 ++++++++++++++++++++-------------------- 1 file changed, 78 insertions(+), 78 deletions(-) diff --git a/src/common/utilscmn.cpp b/src/common/utilscmn.cpp index c48cd24201..471aa86569 100644 --- a/src/common/utilscmn.cpp +++ b/src/common/utilscmn.cpp @@ -681,13 +681,13 @@ wxRegisterId (long id) /* 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" To: Robert Roebling -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> @@ -705,17 +705,17 @@ Thanks, /* 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. @@ -730,10 +730,10 @@ typedef struct } 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 @@ -760,7 +760,7 @@ typedef struct 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; @@ -783,54 +783,54 @@ void wxQsort(void *const pbase, size_t total_elems, 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, @@ -840,24 +840,24 @@ void wxQsort(void *const pbase, size_t total_elems, 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; } @@ -894,17 +894,17 @@ void wxQsort(void *const pbase, size_t total_elems, 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; -- 2.45.2