xpcom/threads/Queue.h
author Henri Sivonen <hsivonen@hsivonen.fi>
Fri, 06 Jul 2018 10:44:43 +0300
changeset 489140 4ef0f163fdeb9afeddd87b37bfd987298c038542
parent 485670 171531e99eeb589b37c50950127b4b664c5d61f5
child 507921 04f0bbf40bf36957dc1f72a8aae9916df0e3222f
permissions -rw-r--r--
Bug 1402247 - Use encoding_rs for XPCOM string encoding conversions. r=Nika,erahm,froydnj. Correctness improvements: * UTF errors are handled safely per spec instead of dangerously truncating strings. * There are fewer converter implementations. Performance improvements: * The old code did exact buffer length math, which meant doing UTF math twice on each input string (once for length calculation and another time for conversion). Exact length math is more complicated when handling errors properly, which the old code didn't do. The new code does UTF math on the string content only once (when converting) but risks allocating more than once. There are heuristics in place to lower the probability of reallocation in cases where the double math avoidance isn't enough of a saving to absorb an allocation and memcpy. * Previously, in UTF-16 <-> UTF-8 conversions, an ASCII prefix was optimized but a single non-ASCII code point pessimized the rest of the string. The new code tries to get back on the fast ASCII path. * UTF-16 to Latin1 conversion guarantees less about handling of out-of-range input to eliminate an operation from the inner loop on x86/x86_64. * When assigning to a pre-existing string, the new code tries to reuse the old buffer instead of first releasing the old buffer and then allocating a new one. * When reallocating from the new code, the memcpy covers only the data that is part of the logical length of the old string instead of memcpying the whole capacity. (For old callers old excess memcpy behavior is preserved due to bogus callers. See bug 1472113.) * UTF-8 strings in XPConnect that are in the Latin1 range are passed to SpiderMonkey as Latin1. New features: * Conversion between UTF-8 and Latin1 is added in order to enable faster future interop between Rust code (or otherwise UTF-8-using code) and text node and SpiderMonkey code that uses Latin1. MozReview-Commit-ID: JaJuExfILM9

/* -*- 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 mozilla_Queue_h
#define mozilla_Queue_h

#include "mozilla/MemoryReporting.h"

namespace mozilla {

// A queue implements a singly linked list of pages, each of which contains some
// number of elements. Since the queue needs to store a "next" pointer, the
// actual number of elements per page won't be quite as many as were requested.
//
// This class should only be used if it's valid to construct T elements from all
// zeroes. The class also fails to call the destructor on items. However, it
// will only destroy items after it has moved out their contents. The queue is
// required to be empty when it is destroyed.
template<class T, size_t RequestedItemsPerPage = 256>
class Queue
{
public:
  Queue() {}

  ~Queue()
  {
    MOZ_ASSERT(IsEmpty());

    if (mHead) {
      free(mHead);
    }
  }

  T& Push(T&& aElement)
  {
    if (!mHead) {
      mHead = NewPage();
      MOZ_ASSERT(mHead);

      mTail = mHead;
      mOffsetHead = 0;
      mOffsetTail = 0;
    } else if (mOffsetTail == ItemsPerPage) {
      Page* page = NewPage();
      MOZ_ASSERT(page);

      mTail->mNext = page;
      mTail = page;
      mOffsetTail = 0;
    }

    T& eltLocation = mTail->mEvents[mOffsetTail];
    eltLocation = std::move(aElement);
    ++mOffsetTail;

    return eltLocation;
  }

  bool IsEmpty() const
  {
    return !mHead || (mHead == mTail && mOffsetHead == mOffsetTail);
  }

  T Pop()
  {
    MOZ_ASSERT(!IsEmpty());

    MOZ_ASSERT(mOffsetHead < ItemsPerPage);
    MOZ_ASSERT_IF(mHead == mTail, mOffsetHead <= mOffsetTail);
    T result = std::move(mHead->mEvents[mOffsetHead++]);

    MOZ_ASSERT(mOffsetHead <= ItemsPerPage);

    // Check if mHead points to empty Page
    if (mOffsetHead == ItemsPerPage) {
      Page* dead = mHead;
      mHead = mHead->mNext;
      free(dead);
      mOffsetHead = 0;
    }

    return result;
  }

  void FirstElementAssertions() const
  {
    MOZ_ASSERT(!IsEmpty());
    MOZ_ASSERT(mOffsetHead < ItemsPerPage);
    MOZ_ASSERT_IF(mHead == mTail, mOffsetHead <= mOffsetTail);
  }

  T& FirstElement()
  {
    FirstElementAssertions();
    return mHead->mEvents[mOffsetHead];
  }

  const T& FirstElement() const
  {
    FirstElementAssertions();
    return mHead->mEvents[mOffsetHead];
  }

  void LastElementAssertions() const
  {
    MOZ_ASSERT(!IsEmpty());
    MOZ_ASSERT(mOffsetTail > 0);
    MOZ_ASSERT(mOffsetTail <= ItemsPerPage);
    MOZ_ASSERT_IF(mHead == mTail, mOffsetHead <= mOffsetTail);
  }

  T& LastElement()
  {
    LastElementAssertions();
    return mTail->mEvents[mOffsetTail - 1];
  }

  const T& LastElement() const
  {
    LastElementAssertions();
    return mTail->mEvents[mOffsetTail - 1];
  }

  size_t Count() const
  {
    // It is obvious count is 0 when the queue is empty.
    if (!mHead) {
      return 0;
    }

    /* How we count the number of events in the queue:
     * 1. Let pageCount(x, y) denote the number of pages excluding the tail page
     *    where x is the index of head page and y is the index of the tail page.
     * 2. Then we have pageCount(x, y) = y - x.
     *
     * Ex: pageCount(0, 0) = 0 where both head and tail pages point to page 0.
     *     pageCount(0, 1) = 1 where head points to page 0 and tail points page 1.
     *
     * 3. number of events = (ItemsPerPage * pageCount(x, y))
     *      - (empty slots in head page) + (non-empty slots in tail page)
     *      = (ItemsPerPage * pageCount(x, y)) - mOffsetHead + mOffsetTail
     */

    int count = -mOffsetHead;

    // Compute (ItemsPerPage * pageCount(x, y))
    for (Page* page = mHead; page != mTail; page = page->mNext) {
      count += ItemsPerPage;
    }

    count += mOffsetTail;
    MOZ_ASSERT(count >= 0);

    return count;
  }

  size_t ShallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const
  {
    size_t n = 0;
    if (mHead) {
      for (Page* page = mHead; page != mTail; page = page->mNext) {
        n += aMallocSizeOf(page);
      }
    }
    return n;
  }

  size_t ShallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const
  {
    return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
  }

private:
  static_assert((RequestedItemsPerPage & (RequestedItemsPerPage - 1)) == 0,
                "RequestedItemsPerPage should be a power of two to avoid heap slop.");

  // Since a Page must also contain a "next" pointer, we use one of the items to
  // store this pointer. If sizeof(T) > sizeof(Page*), then some space will be
  // wasted. So be it.
  static const size_t ItemsPerPage = RequestedItemsPerPage - 1;

  // Page objects are linked together to form a simple deque.
  struct Page
  {
    struct Page* mNext;
    T mEvents[ItemsPerPage];
  };

  static Page* NewPage()
  {
    return static_cast<Page*>(moz_xcalloc(1, sizeof(Page)));
  }

  Page* mHead = nullptr;
  Page* mTail = nullptr;

  uint16_t mOffsetHead = 0;  // offset into mHead where next item is removed
  uint16_t mOffsetTail = 0;  // offset into mTail where next item is added
};

} // namespace mozilla

#endif // mozilla_Queue_h