The Tor Browser: js/src/ds/Sort.h@b8a032363ba2

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

     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/. */

     7 #ifndef ds_Sort_h

     8 #define ds_Sort_h

    10 #include "jstypes.h"

    12 namespace js {

    14 namespace detail {

    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 }

    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);

    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;

    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 }

    65 } /* namespace detail */

    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;

    86     if (nelems <= 1)

    87         return true;

    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     }

   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 }

   135 } /* namespace js */

   137 #endif /* ds_Sort_h */

The Tor Browser / file revision