xpcom/ds/ArrayIterator.h

   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 // Common iterator implementation for array classes e.g. nsTArray.
   8
   9 #ifndef mozilla_ArrayIterator_h
  10 #define mozilla_ArrayIterator_h
  11
  12 #include <iterator>
  13 #include <type_traits>
  14
  15 namespace mozilla {
  16
  17 namespace detail {
  18 template <typename T>
  19 struct AddInnerConst;
  20
  21 template <typename T>
  22 struct AddInnerConst<T&> {
  23   using Type = const T&;
  24 };
  25
  26 template <typename T>
  27 struct AddInnerConst<T*> {
  28   using Type = const T*;
  29 };
  30
  31 template <typename T>
  32 using AddInnerConstT = typename AddInnerConst<T>::Type;
  33 }  // namespace detail
  34
  35 // We have implemented a custom iterator class for array rather than using
  36 // raw pointers into the backing storage to improve the safety of C++11-style
  37 // range based iteration in the presence of array mutation, or script execution
  38 // (bug 1299489).
  39 //
  40 // Mutating an array which is being iterated is still wrong, and will either
  41 // cause elements to be missed or firefox to crash, but will not trigger memory
  42 // safety problems due to the release-mode bounds checking found in ElementAt.
  43 //
  44 // Dereferencing this iterator returns type Element. When Element is a reference
  45 // type, this iterator implements the full standard random access iterator spec,
  46 // and can be treated in many ways as though it is a pointer. Otherwise, it is
  47 // just enough to be used in range-based for loop.
  48 template <class Element, class ArrayType>
  49 class ArrayIterator {
  50  public:
  51   typedef ArrayType array_type;
  52   typedef ArrayIterator<Element, ArrayType> iterator_type;
  53   typedef typename array_type::index_type index_type;
  54   typedef std::remove_reference_t<Element> value_type;
  55   typedef ptrdiff_t difference_type;
  56   typedef value_type* pointer;
  57   typedef value_type& reference;
  58   typedef std::random_access_iterator_tag iterator_category;
  59   typedef ArrayIterator<detail::AddInnerConstT<Element>, ArrayType>
  60       const_iterator_type;
  61
  62  private:
  63   const array_type* mArray;
  64   index_type mIndex;
  65
  66  public:
  67   ArrayIterator() : mArray(nullptr), mIndex(0) {}
  68   ArrayIterator(const iterator_type& aOther)
  69       : mArray(aOther.mArray), mIndex(aOther.mIndex) {}
  70   ArrayIterator(const array_type& aArray, index_type aIndex)
  71       : mArray(&aArray), mIndex(aIndex) {}
  72
  73   iterator_type& operator=(const iterator_type& aOther) {
  74     mArray = aOther.mArray;
  75     mIndex = aOther.mIndex;
  76     return *this;
  77   }
  78
  79   constexpr operator const_iterator_type() const {
  80     return mArray ? const_iterator_type{*mArray, mIndex}
  81                   : const_iterator_type{};
  82   }
  83
  84   bool operator==(const iterator_type& aRhs) const {
  85     return mIndex == aRhs.mIndex;
  86   }
  87   bool operator!=(const iterator_type& aRhs) const { return !(*this == aRhs); }
  88   bool operator<(const iterator_type& aRhs) const {
  89     return mIndex < aRhs.mIndex;
  90   }
  91   bool operator>(const iterator_type& aRhs) const {
  92     return mIndex > aRhs.mIndex;
  93   }
  94   bool operator<=(const iterator_type& aRhs) const {
  95     return mIndex <= aRhs.mIndex;
  96   }
  97   bool operator>=(const iterator_type& aRhs) const {
  98     return mIndex >= aRhs.mIndex;
  99   }
 100
 101   // These operators depend on the release mode bounds checks in
 102   // ArrayIterator::ElementAt for safety.
 103   value_type* operator->() const {
 104     return const_cast<value_type*>(&mArray->ElementAt(mIndex));
 105   }
 106   Element operator*() const {
 107     return const_cast<Element>(mArray->ElementAt(mIndex));
 108   }
 109
 110   iterator_type& operator++() {
 111     ++mIndex;
 112     return *this;
 113   }
 114   iterator_type operator++(int) {
 115     iterator_type it = *this;
 116     ++*this;
 117     return it;
 118   }
 119   iterator_type& operator--() {
 120     --mIndex;
 121     return *this;
 122   }
 123   iterator_type operator--(int) {
 124     iterator_type it = *this;
 125     --*this;
 126     return it;
 127   }
 128
 129   iterator_type& operator+=(difference_type aDiff) {
 130     mIndex += aDiff;
 131     return *this;
 132   }
 133   iterator_type& operator-=(difference_type aDiff) {
 134     mIndex -= aDiff;
 135     return *this;
 136   }
 137
 138   iterator_type operator+(difference_type aDiff) const {
 139     iterator_type it = *this;
 140     it += aDiff;
 141     return it;
 142   }
 143   iterator_type operator-(difference_type aDiff) const {
 144     iterator_type it = *this;
 145     it -= aDiff;
 146     return it;
 147   }
 148
 149   difference_type operator-(const iterator_type& aOther) const {
 150     return static_cast<difference_type>(mIndex) -
 151            static_cast<difference_type>(aOther.mIndex);
 152   }
 153
 154   Element operator[](difference_type aIndex) const {
 155     return *this->operator+(aIndex);
 156   }
 157
 158   constexpr const array_type* GetArray() const { return mArray; }
 159
 160   constexpr index_type GetIndex() const { return mIndex; }
 161 };
 162
 163 }  // namespace mozilla
 164
 165 #endif  // mozilla_ArrayIterator_h