Line data    Source code

       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           2 : CopyNonEmptyArray(T* dst, const T* src, size_t nelems)
      19             : {
      20           2 :     MOZ_ASSERT(nelems != 0);
      21           2 :     const T* end = src + nelems;
      22           5 :     do {
      23           7 :         *dst++ = *src++;
      24           7 :     } while (src != end);
      25           2 : }
      26             : 
      27             : /* Helper function for MergeSort. */
      28             : template<typename T, typename Comparator>
      29             : MOZ_ALWAYS_INLINE bool
      30           1 : MergeArrayRuns(T* dst, const T* src, size_t run1, size_t run2, Comparator c)
      31             : {
      32           1 :     MOZ_ASSERT(run1 >= 1);
      33           1 :     MOZ_ASSERT(run2 >= 1);
      34             : 
      35             :     /* Copy runs already in sorted order. */
      36           1 :     const T* b = src + run1;
      37             :     bool lessOrEqual;
      38           1 :     if (!c(b[-1],  b[0], &lessOrEqual))
      39           0 :         return false;
      40             : 
      41           1 :     if (!lessOrEqual) {
      42             :         /* Runs are not already sorted, merge them. */
      43           1 :         for (const T* a = src;;) {
      44           9 :             if (!c(*a, *b, &lessOrEqual))
      45           0 :                 return false;
      46           5 :             if (lessOrEqual) {
      47           3 :                 *dst++ = *a++;
      48           3 :                 if (!--run1) {
      49           1 :                     src = b;
      50           1 :                     break;
      51             :                 }
      52             :             } else {
      53           2 :                 *dst++ = *b++;
      54           2 :                 if (!--run2) {
      55           0 :                     src = a;
      56           0 :                     break;
      57             :                 }
      58             :             }
      59             :         }
      60             :     }
      61           1 :     CopyNonEmptyArray(dst, src, run1 + run2);
      62           1 :     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             : MOZ_MUST_USE bool
      82           1 : MergeSort(T* array, size_t nelems, T* scratch, Comparator c)
      83             : {
      84           1 :     const size_t INS_SORT_LIMIT = 3;
      85             : 
      86           1 :     if (nelems <= 1)
      87           0 :         return true;
      88             : 
      89             :     /*
      90             :      * Apply insertion sort to small chunks to reduce the number of merge
      91             :      * passes needed.
      92             :      */
      93           3 :     for (size_t lo = 0; lo < nelems; lo += INS_SORT_LIMIT) {
      94           2 :         size_t hi = lo + INS_SORT_LIMIT;
      95           2 :         if (hi >= nelems)
      96           1 :             hi = nelems;
      97           6 :         for (size_t i = lo + 1; i != hi; i++) {
      98           6 :             for (size_t j = i; ;) {
      99             :                 bool lessOrEqual;
     100           6 :                 if (!c(array[j - 1], array[j], &lessOrEqual))
     101           0 :                     return false;
     102           6 :                 if (lessOrEqual)
     103           8 :                     break;
     104           2 :                 T tmp = array[j - 1];
     105           2 :                 array[j - 1] = array[j];
     106           2 :                 array[j] = tmp;
     107           2 :                 if (--j == lo)
     108           0 :                     break;
     109             :             }
     110             :         }
     111             :     }
     112             : 
     113           1 :     T* vec1 = array;
     114           1 :     T* vec2 = scratch;
     115           2 :     for (size_t run = INS_SORT_LIMIT; run < nelems; run *= 2) {
     116           2 :         for (size_t lo = 0; lo < nelems; lo += 2 * run) {
     117           1 :             size_t hi = lo + run;
     118           1 :             if (hi >= nelems) {
     119           0 :                 detail::CopyNonEmptyArray(vec2 + lo, vec1 + lo, nelems - lo);
     120           0 :                 break;
     121             :             }
     122           1 :             size_t run2 = (run <= nelems - hi) ? run : nelems - hi;
     123           1 :             if (!detail::MergeArrayRuns(vec2 + lo, vec1 + lo, run, run2, c))
     124           0 :                 return false;
     125             :         }
     126           1 :         T* swap = vec1;
     127           1 :         vec1 = vec2;
     128           1 :         vec2 = swap;
     129             :     }
     130           1 :     if (vec1 == scratch)
     131           1 :         detail::CopyNonEmptyArray(array, scratch, nelems);
     132           1 :     return true;
     133             : }
     134             : 
     135             : } /* namespace js */
     136             : 
     137             : #endif /* ds_Sort_h */