lucy-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nwelln...@apache.org
Subject [20/22] lucy-clownfish git commit: Remove Sort_quicksort
Date Wed, 29 Apr 2015 19:55:21 GMT
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 <wellnhofer@aevum.de>
Authored: Wed Apr 29 11:36:07 2015 +0200
Committer: Nick Wellnhofer <wellnhofer@aevum.de>
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);
 }
 
 


Mime
View raw message