Remove Sort_quicksort
Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/03903102 Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/03903102 Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/03903102 Branch: refs/heads/master Commit: 039031025c8f6b353674f701c815857e1ca96e7b Parents: 9423582 Author: Nick Wellnhofer <[email protected]> Authored: Wed Apr 29 11:36:07 2015 +0200 Committer: Nick Wellnhofer <[email protected]> Committed: Wed Apr 29 11:36:07 2015 +0200 ---------------------------------------------------------------------- runtime/core/Clownfish/Util/SortUtils.c | 284 ------------------------- runtime/core/Clownfish/Util/SortUtils.cfh | 8 - 2 files changed, 292 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/03903102/runtime/core/Clownfish/Util/SortUtils.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Util/SortUtils.c b/runtime/core/Clownfish/Util/SortUtils.c index d7bb655..d620098 100644 --- a/runtime/core/Clownfish/Util/SortUtils.c +++ b/runtime/core/Clownfish/Util/SortUtils.c @@ -21,14 +21,6 @@ #include "Clownfish/Util/SortUtils.h" #include "Clownfish/Err.h" -// Define four-byte and eight-byte types so that we can dereference void -// pointers like integer pointers. The only significance of using int32_t and -// int64_t is that they are 4 and 8 bytes. -#define FOUR_BYTE_TYPE int32_t -#define EIGHT_BYTE_TYPE int64_t - -/***************************** mergesort ************************************/ - // Recursive merge sorting functions. static void S_msort4(void *velems, void *vscratch, size_t left, size_t right, @@ -176,280 +168,4 @@ SI_merge(void *left_vptr, size_t left_size, memcpy(dest, right_ptr, right_remaining); } -/***************************** quicksort ************************************/ - -// Quicksort implementations optimized for four-byte and eight-byte elements. -static void -S_qsort4(FOUR_BYTE_TYPE *elems, size_t left, size_t right, - CFISH_Sort_Compare_t compare, void *context); -static void -S_qsort8(EIGHT_BYTE_TYPE *elems, size_t left, size_t right, - CFISH_Sort_Compare_t compare, void *context); - -// Swap two elements. -static CFISH_INLINE void -SI_exchange4(FOUR_BYTE_TYPE *elems, size_t left, size_t right); -static CFISH_INLINE void -SI_exchange8(EIGHT_BYTE_TYPE *elems, size_t left, size_t right); - -/* Select a pivot by choosing the median of three values, guarding against - * the worst-case behavior of quicksort. Place the pivot in the rightmost - * slot. - * - * Possible states: - * - * abc => abc => abc => acb - * acb => acb => acb => acb - * bac => abc => abc => acb - * bca => bca => acb => acb - * cba => bca => acb => acb - * cab => acb => acb => acb - * aab => aab => aab => aba - * aba => aba => aba => aba - * baa => aba => aba => aba - * bba => bba => abb => abb - * bab => abb => abb => abb - * abb => abb => abb => abb - * aaa => aaa => aaa => aaa - */ -static CFISH_INLINE FOUR_BYTE_TYPE* -SI_choose_pivot4(FOUR_BYTE_TYPE *elems, size_t left, size_t right, - CFISH_Sort_Compare_t compare, void *context); -static CFISH_INLINE EIGHT_BYTE_TYPE* -SI_choose_pivot8(EIGHT_BYTE_TYPE *elems, size_t left, size_t right, - CFISH_Sort_Compare_t compare, void *context); - -void -Sort_quicksort(void *elems, size_t num_elems, size_t width, - CFISH_Sort_Compare_t compare, void *context) { - // Arrays of 0 or 1 items are already sorted. - if (num_elems < 2) { return; } - - if (width == 4) { - S_qsort4((FOUR_BYTE_TYPE*)elems, 0, num_elems - 1, compare, context); - } - else if (width == 8) { - S_qsort8((EIGHT_BYTE_TYPE*)elems, 0, num_elems - 1, compare, context); - } - else { - THROW(ERR, "Unsupported width: %i64", (int64_t)width); - } -} - -/************************* quicksort 4 byte *********************************/ - -static CFISH_INLINE void -SI_exchange4(FOUR_BYTE_TYPE *elems, size_t left, size_t right) { - FOUR_BYTE_TYPE saved = elems[left]; - elems[left] = elems[right]; - elems[right] = saved; -} - -static CFISH_INLINE FOUR_BYTE_TYPE* -SI_choose_pivot4(FOUR_BYTE_TYPE *elems, size_t left, size_t right, - CFISH_Sort_Compare_t compare, void *context) { - if (right - left > 1) { - size_t mid = left + (right - left) / 2; - if (compare(context, elems + left, elems + mid) > 0) { - SI_exchange4(elems, left, mid); - } - if (compare(context, elems + left, elems + right) > 0) { - SI_exchange4(elems, left, right); - } - if (compare(context, elems + right, elems + mid) > 0) { - SI_exchange4(elems, right, mid); - } - } - return elems + right; -} - -static void -S_qsort4(FOUR_BYTE_TYPE *elems, size_t left, size_t right, - CFISH_Sort_Compare_t compare, void *context) { - if (right == (size_t)-1 || right <= left) { return; } - - /* TODO: A standard optimization for quicksort is to fall back to an - * insertion sort when the the number of elements to be sorted becomes - * small enough. */ - - FOUR_BYTE_TYPE *const pivot - = SI_choose_pivot4(elems, left, right, compare, context); - size_t i = left; - size_t j = right - 1; - size_t p = left; - size_t q = right - 1; - - while (1) { - int comparison1; - int comparison2; - - // Find an element from the left that is greater than or equal to the - // pivot (i.e. that should move to the right). - while (1) { - comparison1 = compare(context, elems + i, pivot); - if (comparison1 >= 0) { break; } - if (i == right) { break; } - i++; - } - - // Find an element from the right that is less than or equal to the - // pivot (i.e. that should move to the left). - while (1) { - comparison2 = compare(context, elems + j, pivot); - if (comparison2 <= 0) { break; } - if (j == left) { break; } - j--; - } - - // Bail out of loop when we meet in the middle. - if (i >= j) { break; } - - // Swap the elements we found, so the lesser element moves left and - // the greater element moves right. - SI_exchange4(elems, i, j); - - // Move any elements which test as "equal" to the pivot to the outside - // edges of the array. - if (comparison2 == 0) { - SI_exchange4(elems, p, i); - p++; - } - if (comparison1 == 0) { - SI_exchange4(elems, j, q); - q--; - } - - i++; - j--; - } - - /* Move "equal" elements from the outside edges to the center. - * - * Before: - * - * equal | less_than | greater_than | equal - * - * After: - * - * less_than | equal | greater_than - */ - SI_exchange4(elems, i, right); - j = i - 1; - i++; - for (size_t k = left; k < p; k++, j--) { SI_exchange4(elems, k, j); } - for (size_t k = right - 1; k > q; k--, i++) { SI_exchange4(elems, i, k); } - - // Recurse. - S_qsort4(elems, left, j, compare, context); // Sort less_than. - S_qsort4(elems, i, right, compare, context); // Sort greater_than. -} - -/************************* quicksort 8 byte *********************************/ - -static CFISH_INLINE void -SI_exchange8(EIGHT_BYTE_TYPE *elems, size_t left, size_t right) { - EIGHT_BYTE_TYPE saved = elems[left]; - elems[left] = elems[right]; - elems[right] = saved; -} - -static CFISH_INLINE EIGHT_BYTE_TYPE* -SI_choose_pivot8(EIGHT_BYTE_TYPE *elems, size_t left, size_t right, - CFISH_Sort_Compare_t compare, void *context) { - if (right - left > 1) { - size_t mid = left + (right - left) / 2; - if (compare(context, elems + left, elems + mid) > 0) { - SI_exchange8(elems, left, mid); - } - if (compare(context, elems + left, elems + right) > 0) { - SI_exchange8(elems, left, right); - } - if (compare(context, elems + right, elems + mid) > 0) { - SI_exchange8(elems, right, mid); - } - } - return elems + right; -} - -static void -S_qsort8(EIGHT_BYTE_TYPE *elems, size_t left, size_t right, - CFISH_Sort_Compare_t compare, void *context) { - if (right == (size_t)-1 || right <= left) { return; } - - /* TODO: A standard optimization for quicksort is to fall back to an - * insertion sort when the the number of elements to be sorted becomes - * small enough. */ - - EIGHT_BYTE_TYPE *const pivot - = SI_choose_pivot8(elems, left, right, compare, context); - size_t i = left; - size_t j = right - 1; - size_t p = left; - size_t q = right - 1; - - while (1) { - int comparison1; - int comparison2; - - // Find an element from the left that is greater than or equal to the - // pivot (i.e. that should move to the right). - while (1) { - comparison1 = compare(context, elems + i, pivot); - if (comparison1 >= 0) { break; } - if (i == right) { break; } - i++; - } - - // Find an element from the right that is less than or equal to the - // pivot (i.e. that should move to the left). - while (1) { - comparison2 = compare(context, elems + j, pivot); - if (comparison2 <= 0) { break; } - if (j == left) { break; } - j--; - } - - // Bail out of loop when we meet in the middle. - if (i >= j) { break; } - - // Swap the elements we found, so the lesser element moves left and - // the greater element moves right. - SI_exchange8(elems, i, j); - - // Move any elements which test as "equal" to the pivot to the outside - // edges of the array. - if (comparison2 == 0) { - SI_exchange8(elems, p, i); - p++; - } - if (comparison1 == 0) { - SI_exchange8(elems, j, q); - q--; - } - - i++; - j--; - } - - /* Move "equal" elements from the outside edges to the center. - * - * Before: - * - * equal | less_than | greater_than | equal - * - * After: - * - * less_than | equal | greater_than - */ - SI_exchange8(elems, i, right); - j = i - 1; - i++; - for (size_t k = left; k < p; k++, j--) { SI_exchange8(elems, k, j); } - for (size_t k = right - 1; k > q; k--, i++) { SI_exchange8(elems, i, k); } - - // Recurse. - S_qsort8(elems, left, j, compare, context); // Sort less_than. - S_qsort8(elems, i, right, compare, context); // Sort greater_than. -} - http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/03903102/runtime/core/Clownfish/Util/SortUtils.cfh ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Util/SortUtils.cfh b/runtime/core/Clownfish/Util/SortUtils.cfh index 224396a..de9b03b 100644 --- a/runtime/core/Clownfish/Util/SortUtils.cfh +++ b/runtime/core/Clownfish/Util/SortUtils.cfh @@ -26,8 +26,6 @@ __END_C__ * SortUtils provides a merge sort algorithm which allows access to its * internals, enabling specialized functions to jump in and only execute part * of the sort. - * - * SortUtils also provides a quicksort with an additional context argument. */ inert class Clownfish::Util::SortUtils nickname Sort { @@ -57,12 +55,6 @@ inert class Clownfish::Util::SortUtils nickname Sort { merge(void *left_ptr, size_t left_num_elems, void *right_ptr, size_t right_num_elems, void *dest, size_t width, CFISH_Sort_Compare_t compare, void *context); - - /** Quicksort. - */ - inert void - quicksort(void *elems, size_t num_elems, size_t width, - CFISH_Sort_Compare_t compare, void *context); }
