js/src/ds/Sort.h
author Nika Layzell <nika@thelayzells.com>
Wed, 16 Sep 2020 20:47:55 +0000
changeset 549331 ab7d302fd3186b10ada9264528c80f6840e44571
parent 514670 d25ea1954d9937ffd1ed0b29b5d785dbb889c232
permissions -rw-r--r--
Bug 1659696 - Check PendingInitialization before targeting in window.open, r=kmag This requires adding the flag as a synced field on the BrowsingContext, and checking it in a few more places. Attempts to open a new window in this racy manner will now raise an exception. This should avoid the issue from bug 1658854 by blocking the buggy attempts to load before the nested event loop has been exited. Differential Revision: https://phabricator.services.mozilla.com/D87927

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