js/src/ds/Sort.h@b8a032363ba2 (annotated)
js/src/ds/Sort.h
Thu, 22 Jan 2015 13:21:57 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 22 Jan 2015 13:21:57 +0100
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
- permissions
- -rw-r--r--
Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6
| michael@0 | 1 | /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- |
| michael@0 | 2 | * vim: set ts=8 sts=4 et sw=4 tw=99: |
| michael@0 | 3 | * This Source Code Form is subject to the terms of the Mozilla Public |
| michael@0 | 4 | * License, v. 2.0. If a copy of the MPL was not distributed with this |
| michael@0 | 5 | * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ |
| michael@0 | 6 | |
| michael@0 | 7 | #ifndef ds_Sort_h |
| michael@0 | 8 | #define ds_Sort_h |
| michael@0 | 9 | |
| michael@0 | 10 | #include "jstypes.h" |
| michael@0 | 11 | |
| michael@0 | 12 | namespace js { |
| michael@0 | 13 | |
| michael@0 | 14 | namespace detail { |
| michael@0 | 15 | |
| michael@0 | 16 | template<typename T> |
| michael@0 | 17 | MOZ_ALWAYS_INLINE void |
| michael@0 | 18 | CopyNonEmptyArray(T *dst, const T *src, size_t nelems) |
| michael@0 | 19 | { |
| michael@0 | 20 | JS_ASSERT(nelems != 0); |
| michael@0 | 21 | const T *end = src + nelems; |
| michael@0 | 22 | do { |
| michael@0 | 23 | *dst++ = *src++; |
| michael@0 | 24 | } while (src != end); |
| michael@0 | 25 | } |
| michael@0 | 26 | |
| michael@0 | 27 | /* Helper function for MergeSort. */ |
| michael@0 | 28 | template<typename T, typename Comparator> |
| michael@0 | 29 | MOZ_ALWAYS_INLINE bool |
| michael@0 | 30 | MergeArrayRuns(T *dst, const T *src, size_t run1, size_t run2, Comparator c) |
| michael@0 | 31 | { |
| michael@0 | 32 | JS_ASSERT(run1 >= 1); |
| michael@0 | 33 | JS_ASSERT(run2 >= 1); |
| michael@0 | 34 | |
| michael@0 | 35 | /* Copy runs already in sorted order. */ |
| michael@0 | 36 | const T *b = src + run1; |
| michael@0 | 37 | bool lessOrEqual; |
| michael@0 | 38 | if (!c(b[-1], b[0], &lessOrEqual)) |
| michael@0 | 39 | return false; |
| michael@0 | 40 | |
| michael@0 | 41 | if (!lessOrEqual) { |
| michael@0 | 42 | /* Runs are not already sorted, merge them. */ |
| michael@0 | 43 | for (const T *a = src;;) { |
| michael@0 | 44 | if (!c(*a, *b, &lessOrEqual)) |
| michael@0 | 45 | return false; |
| michael@0 | 46 | if (lessOrEqual) { |
| michael@0 | 47 | *dst++ = *a++; |
| michael@0 | 48 | if (!--run1) { |
| michael@0 | 49 | src = b; |
| michael@0 | 50 | break; |
| michael@0 | 51 | } |
| michael@0 | 52 | } else { |
| michael@0 | 53 | *dst++ = *b++; |
| michael@0 | 54 | if (!--run2) { |
| michael@0 | 55 | src = a; |
| michael@0 | 56 | break; |
| michael@0 | 57 | } |
| michael@0 | 58 | } |
| michael@0 | 59 | } |
| michael@0 | 60 | } |
| michael@0 | 61 | CopyNonEmptyArray(dst, src, run1 + run2); |
| michael@0 | 62 | return true; |
| michael@0 | 63 | } |
| michael@0 | 64 | |
| michael@0 | 65 | } /* namespace detail */ |
| michael@0 | 66 | |
| michael@0 | 67 | /* |
| michael@0 | 68 | * Sort the array using the merge sort algorithm. The scratch should point to |
| michael@0 | 69 | * a temporary storage that can hold nelems elements. |
| michael@0 | 70 | * |
| michael@0 | 71 | * The comparator must provide the () operator with the following signature: |
| michael@0 | 72 | * |
| michael@0 | 73 | * bool operator()(const T& a, const T& a, bool *lessOrEqualp); |
| michael@0 | 74 | * |
| michael@0 | 75 | * It should return true on success and set *lessOrEqualp to the result of |
| michael@0 | 76 | * a <= b operation. If it returns false, the sort terminates immediately with |
| michael@0 | 77 | * the false result. In this case the content of the array and scratch is |
| michael@0 | 78 | * arbitrary. |
| michael@0 | 79 | */ |
| michael@0 | 80 | template<typename T, typename Comparator> |
| michael@0 | 81 | bool |
| michael@0 | 82 | MergeSort(T *array, size_t nelems, T *scratch, Comparator c) |
| michael@0 | 83 | { |
| michael@0 | 84 | const size_t INS_SORT_LIMIT = 3; |
| michael@0 | 85 | |
| michael@0 | 86 | if (nelems <= 1) |
| michael@0 | 87 | return true; |
| michael@0 | 88 | |
| michael@0 | 89 | /* |
| michael@0 | 90 | * Apply insertion sort to small chunks to reduce the number of merge |
| michael@0 | 91 | * passes needed. |
| michael@0 | 92 | */ |
| michael@0 | 93 | for (size_t lo = 0; lo < nelems; lo += INS_SORT_LIMIT) { |
| michael@0 | 94 | size_t hi = lo + INS_SORT_LIMIT; |
| michael@0 | 95 | if (hi >= nelems) |
| michael@0 | 96 | hi = nelems; |
| michael@0 | 97 | for (size_t i = lo + 1; i != hi; i++) { |
| michael@0 | 98 | for (size_t j = i; ;) { |
| michael@0 | 99 | bool lessOrEqual; |
| michael@0 | 100 | if (!c(array[j - 1], array[j], &lessOrEqual)) |
| michael@0 | 101 | return false; |
| michael@0 | 102 | if (lessOrEqual) |
| michael@0 | 103 | break; |
| michael@0 | 104 | T tmp = array[j - 1]; |
| michael@0 | 105 | array[j - 1] = array[j]; |
| michael@0 | 106 | array[j] = tmp; |
| michael@0 | 107 | if (--j == lo) |
| michael@0 | 108 | break; |
| michael@0 | 109 | } |
| michael@0 | 110 | } |
| michael@0 | 111 | } |
| michael@0 | 112 | |
| michael@0 | 113 | T *vec1 = array; |
| michael@0 | 114 | T *vec2 = scratch; |
| michael@0 | 115 | for (size_t run = INS_SORT_LIMIT; run < nelems; run *= 2) { |
| michael@0 | 116 | for (size_t lo = 0; lo < nelems; lo += 2 * run) { |
| michael@0 | 117 | size_t hi = lo + run; |
| michael@0 | 118 | if (hi >= nelems) { |
| michael@0 | 119 | detail::CopyNonEmptyArray(vec2 + lo, vec1 + lo, nelems - lo); |
| michael@0 | 120 | break; |
| michael@0 | 121 | } |
| michael@0 | 122 | size_t run2 = (run <= nelems - hi) ? run : nelems - hi; |
| michael@0 | 123 | if (!detail::MergeArrayRuns(vec2 + lo, vec1 + lo, run, run2, c)) |
| michael@0 | 124 | return false; |
| michael@0 | 125 | } |
| michael@0 | 126 | T *swap = vec1; |
| michael@0 | 127 | vec1 = vec2; |
| michael@0 | 128 | vec2 = swap; |
| michael@0 | 129 | } |
| michael@0 | 130 | if (vec1 == scratch) |
| michael@0 | 131 | detail::CopyNonEmptyArray(array, scratch, nelems); |
| michael@0 | 132 | return true; |
| michael@0 | 133 | } |
| michael@0 | 134 | |
| michael@0 | 135 | } /* namespace js */ |
| michael@0 | 136 | |
| michael@0 | 137 | #endif /* ds_Sort_h */ |
