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