tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

FastFrontRemovableArray.h (4200B)

      1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
      2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
      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 mozilla_dom_FastFrontRemovableArray_h
      8 #define mozilla_dom_FastFrontRemovableArray_h
      9 
     10 // An nsTArray of pointers where removing from the front is amortized constant
     11 // time.
     12 
     13 #include "mozilla/Span.h"
     14 #include "nsTArray.h"
     15 
     16 namespace mozilla::dom {
     17 
     18 template <typename T, size_t InlineCapacity = 0>
     19 class FastFrontRemovableArray {
     20  using InternalList = AutoTArray<T, InlineCapacity>;
     21 
     22 public:
     23  static const size_t NoIndex = InternalList::NoIndex;
     24 
     25  operator Span<const T>() const { return AsSpan(); }
     26  operator Span<T>() { return AsSpan(); }
     27 
     28  Span<const T> AsSpan() const {
     29    return Span<const T>(mList).From(mIndexOfFirstElement);
     30  }
     31  Span<T> AsSpan() { return Span<T>(mList).From(mIndexOfFirstElement); }
     32 
     33  size_t Length() const { return mList.Length() - mIndexOfFirstElement; }
     34 
     35  bool IsEmpty() const { return Length() == 0; }
     36 
     37  void RemoveElementAt(size_t aIndex) {
     38    if (aIndex == 0) {
     39      mList[mIndexOfFirstElement++] = nullptr;
     40      if (mIndexOfFirstElement > std::max(size_t(4), mList.Length() / 4)) {
     41        // Compact the list if it gets too big. This shifts all the elements,
     42        // which is expensive, so only do it if we have more than 4 elements
     43        // wasted at the front, and more than a quarter of the list is wasted
     44        // space in the front.
     45        mList.RemoveElementsAt(0, mIndexOfFirstElement);
     46        mIndexOfFirstElement = 0;
     47      }
     48      return;
     49    }
     50    mList.RemoveElementAt(aIndex + mIndexOfFirstElement);
     51    if (IsEmpty()) {
     52      Clear();
     53    }
     54  }
     55 
     56  template <typename U>
     57  void InsertElementAt(size_t aIndex, U* aElem) {
     58    if (mIndexOfFirstElement && aIndex == 0) {
     59      mList[--mIndexOfFirstElement] = aElem;
     60      return;
     61    }
     62    mList.InsertElementAt(aIndex + mIndexOfFirstElement, aElem);
     63  }
     64 
     65  T& operator[](size_t aIndex) { return mList[aIndex + mIndexOfFirstElement]; }
     66 
     67  const T& operator[](size_t aIndex) const {
     68    return mList[aIndex + mIndexOfFirstElement];
     69  }
     70  T& ElementAt(size_t aIndex) { return mList[aIndex + mIndexOfFirstElement]; }
     71  const T& ElementAt(size_t aIndex) const {
     72    return mList[aIndex + mIndexOfFirstElement];
     73  }
     74 
     75  T& SafeElementAt(size_t aIndex, T& aDef) {
     76    return mList.SafeElementAt(aIndex + mIndexOfFirstElement, aDef);
     77  }
     78 
     79  const T& SafeElementAt(size_t aIndex, const T& aDef) const {
     80    return mList.SafeElementAt(aIndex + mIndexOfFirstElement, aDef);
     81  }
     82 
     83  const T& FirstElement() const { return ElementAt(0); }
     84  const T& LastElement() const { return mList.LastElement(); }
     85  T& FirstElement() { return ElementAt(0); }
     86  T& LastElement() { return mList.LastElement(); }
     87 
     88  template <typename U>
     89  void AppendElement(U* aElem) {
     90    mList.AppendElement(aElem);
     91  }
     92 
     93  template <typename Item>
     94  bool RemoveElement(const Item& aItem) {
     95    auto i = IndexOf(aItem);
     96    if (i == NoIndex) {
     97      return false;
     98    }
     99    RemoveElementAt(i);
    100    return true;
    101  }
    102 
    103  template <typename Item>
    104  bool Contains(const Item& aItem) const {
    105    return IndexOf(aItem) != NoIndex;
    106  }
    107 
    108  void Clear() {
    109    mList.Clear();
    110    mIndexOfFirstElement = 0;
    111  }
    112 
    113  template <typename Item>
    114  size_t IndexOf(const Item& aItem) const {
    115    auto index = mList.IndexOf(aItem, mIndexOfFirstElement);
    116    if (index == NoIndex || mIndexOfFirstElement == 0) {
    117      return index;
    118    }
    119    return index - mIndexOfFirstElement;
    120  }
    121 
    122 private:
    123  AutoTArray<T, InlineCapacity> mList;
    124  size_t mIndexOfFirstElement = 0;
    125 };
    126 
    127 template <typename T, size_t InlineCap>
    128 inline void ImplCycleCollectionUnlink(
    129    FastFrontRemovableArray<T, InlineCap>& aField) {
    130  aField.Clear();
    131 }
    132 
    133 template <typename T, size_t InlineCap, typename Callback>
    134 inline void ImplCycleCollectionIndexedContainer(
    135    FastFrontRemovableArray<T, InlineCap>& aField, Callback&& aCallback) {
    136  for (auto& value : aField.AsSpan()) {
    137    aCallback(value);
    138  }
    139 }
    140 
    141 }  // namespace mozilla::dom
    142 
    143 #endif