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