DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Mercurial (c68fe15a81fc)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef ds_Sort_h
#define ds_Sort_h

#include "jstypes.h"

namespace js {

namespace detail {

template <typename T>
MOZ_ALWAYS_INLINE void CopyNonEmptyArray(T* dst, const T* src, size_t nelems) {
  MOZ_ASSERT(nelems != 0);
  const T* end = src + nelems;
  do {
    *dst++ = *src++;
  } while (src != end);
}

/* Helper function for MergeSort. */
template <typename T, typename Comparator>
MOZ_ALWAYS_INLINE bool MergeArrayRuns(T* dst, const T* src, size_t run1,
                                      size_t run2, Comparator c) {
  MOZ_ASSERT(run1 >= 1);
  MOZ_ASSERT(run2 >= 1);

  /* Copy runs already in sorted order. */
  const T* b = src + run1;
  bool lessOrEqual;
  if (!c(b[-1], b[0], &lessOrEqual)) {
    return false;
  }

  if (!lessOrEqual) {
    /* Runs are not already sorted, merge them. */
    for (const T* a = src;;) {
      if (!c(*a, *b, &lessOrEqual)) {
        return false;
      }
      if (lessOrEqual) {
        *dst++ = *a++;
        if (!--run1) {
          src = b;
          break;
        }
      } else {
        *dst++ = *b++;
        if (!--run2) {
          src = a;
          break;
        }
      }
    }
  }
  CopyNonEmptyArray(dst, src, run1 + run2);
  return true;
}

} /* namespace detail */

/*
 * Sort the array using the merge sort algorithm. The scratch should point to
 * a temporary storage that can hold nelems elements.
 *
 * The comparator must provide the () operator with the following signature:
 *
 *     bool operator()(const T& a, const T& a, bool* lessOrEqualp);
 *
 * It should return true on success and set *lessOrEqualp to the result of
 * a <= b operation. If it returns false, the sort terminates immediately with
 * the false result. In this case the content of the array and scratch is
 * arbitrary.
 *
 * Note: The merge sort algorithm is a stable sort, preserving relative ordering
 * of entries that compare equal. This makes it a useful substitute for
 * |std::stable_sort|, which can't be used in SpiderMonkey because it internally
 * allocates memory without using SpiderMonkey's allocator.
 */
template <typename T, typename Comparator>
MOZ_MUST_USE bool MergeSort(T* array, size_t nelems, T* scratch, Comparator c) {
  const size_t INS_SORT_LIMIT = 3;

  if (nelems <= 1) {
    return true;
  }

  /*
   * Apply insertion sort to small chunks to reduce the number of merge
   * passes needed.
   */
  for (size_t lo = 0; lo < nelems; lo += INS_SORT_LIMIT) {
    size_t hi = lo + INS_SORT_LIMIT;
    if (hi >= nelems) {
      hi = nelems;
    }
    for (size_t i = lo + 1; i != hi; i++) {
      for (size_t j = i;;) {
        bool lessOrEqual;
        if (!c(array[j - 1], array[j], &lessOrEqual)) {
          return false;
        }
        if (lessOrEqual) {
          break;
        }
        T tmp = array[j - 1];
        array[j - 1] = array[j];
        array[j] = tmp;
        if (--j == lo) {
          break;
        }
      }
    }
  }

  T* vec1 = array;
  T* vec2 = scratch;
  for (size_t run = INS_SORT_LIMIT; run < nelems; run *= 2) {
    for (size_t lo = 0; lo < nelems; lo += 2 * run) {
      size_t hi = lo + run;
      if (hi >= nelems) {
        detail::CopyNonEmptyArray(vec2 + lo, vec1 + lo, nelems - lo);
        break;
      }
      size_t run2 = (run <= nelems - hi) ? run : nelems - hi;
      if (!detail::MergeArrayRuns(vec2 + lo, vec1 + lo, run, run2, c)) {
        return false;
      }
    }
    T* swap = vec1;
    vec1 = vec2;
    vec2 = swap;
  }
  if (vec1 == scratch) {
    detail::CopyNonEmptyArray(array, scratch, nelems);
  }
  return true;
}

} /* namespace js */

#endif /* ds_Sort_h */