xpcom/ds/nsTHashSet.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 #ifndef XPCOM_DS_NSTHASHSET_H_
   8 #define XPCOM_DS_NSTHASHSET_H_
   9
  10 #include "nsHashtablesFwd.h"
  11 #include "nsTHashMap.h"  // for nsKeyClass
  12
  13 /**
  14  * Templated hash set. Don't use this directly, but use nsTHashSet instead
  15  * (defined as a type alias in nsHashtablesFwd.h).
  16  *
  17  * @param KeyClass a wrapper-class for the hashtable key, see nsHashKeys.h
  18  *   for a complete specification.
  19  */
  20 template <class KeyClass>
  21 class nsTBaseHashSet : protected nsTHashtable<KeyClass> {
  22   using Base = nsTHashtable<KeyClass>;
  23   typedef mozilla::fallible_t fallible_t;
  24
  25  public:
  26   // XXX We have a similar situation here like with DataType/UserDataType in
  27   // nsBaseHashtable. It's less problematic here due to the more constrained
  28   // interface, but it may still be confusing. KeyType is not the stored key
  29   // type, but the one exposed to the user, i.e. as a parameter type, and as the
  30   // value type when iterating. It is currently impossible to move-insert a
  31   // RefPtr<T>, e.g., since the KeyType is T* in that case.
  32   using ValueType = typename KeyClass::KeyType;
  33
  34   // KeyType is defined just for compatibility with nsTHashMap. For a set, the
  35   // key type is conceptually equivalent to the value type.
  36   using KeyType = typename KeyClass::KeyType;
  37
  38   using Base::Base;
  39
  40   // Query operations.
  41
  42   using Base::Contains;
  43   using Base::GetGeneration;
  44   using Base::ShallowSizeOfExcludingThis;
  45   using Base::ShallowSizeOfIncludingThis;
  46   using Base::SizeOfExcludingThis;
  47   using Base::SizeOfIncludingThis;
  48
  49   /**
  50    * Return the number of entries in the table.
  51    * @return    number of entries
  52    */
  53   [[nodiscard]] uint32_t Count() const { return Base::Count(); }
  54
  55   /**
  56    * Return whether the table is empty.
  57    * @return    whether empty
  58    */
  59   [[nodiscard]] bool IsEmpty() const { return Base::IsEmpty(); }
  60
  61   using iterator = ::detail::nsTHashtableKeyIterator<KeyClass>;
  62   using const_iterator = iterator;
  63
  64   [[nodiscard]] auto begin() const { return Base::Keys().begin(); }
  65
  66   [[nodiscard]] auto end() const { return Base::Keys().end(); }
  67
  68   [[nodiscard]] auto cbegin() const { return Base::Keys().cbegin(); }
  69
  70   [[nodiscard]] auto cend() const { return Base::Keys().cend(); }
  71
  72   // Mutating operations.
  73
  74   using Base::Clear;
  75   using Base::MarkImmutable;
  76
  77   /**
  78    * Inserts a value into the set. Has no effect if the value is already in the
  79    * set. This overload is infallible and crashes if memory is exhausted.
  80    *
  81    * \note For strict consistency with nsTHashtable::EntryHandle method naming,
  82    * this should rather be called OrInsert, as it is legal to call it when the
  83    * value is already in the set. For simplicity, as we don't have two methods,
  84    * we still use "Insert" instead.
  85    */
  86   void Insert(ValueType aValue) { Base::PutEntry(aValue); }
  87
  88   /**
  89    * Inserts a value into the set. Has no effect if the value is already in the
  90    * set. This overload is fallible and returns false if memory is exhausted.
  91    *
  92    * \note See note on infallible overload.
  93    */
  94   [[nodiscard]] bool Insert(ValueType aValue, const mozilla::fallible_t&) {
  95     return Base::PutEntry(aValue, mozilla::fallible);
  96   }
  97
  98   /**
  99    * Inserts a value into the set. Has no effect if the value is already in the
 100    * set. This member function is infallible and crashes if memory is exhausted.
 101    *
 102    * \return true if the value was actually inserted, false if it was already in
 103    * the set.
 104    */
 105   bool EnsureInserted(ValueType aValue) { return Base::EnsureInserted(aValue); }
 106
 107   using Base::Remove;
 108
 109   /**
 110    * Removes a value from the set. Has no effect if the value is not in the set.
 111    *
 112    * \note For strict consistency with nsTHashtable::EntryHandle method naming,
 113    * this should rather be called OrRemove, as it is legal to call it when the
 114    * value is not in the set. For simplicity, as we don't have two methods,
 115    * we still use "Remove" instead.
 116    */
 117   void Remove(ValueType aValue) { Base::RemoveEntry(aValue); }
 118
 119   using Base::EnsureRemoved;
 120
 121   /**
 122    * Removes all elements matching a predicate.
 123    *
 124    * The predicate must be compatible with signature bool (ValueType).
 125    */
 126   template <typename Pred>
 127   void RemoveIf(Pred&& aPred) {
 128     for (auto it = cbegin(), end = cend(); it != end; ++it) {
 129       if (aPred(static_cast<ValueType>(*it))) {
 130         Remove(it);
 131       }
 132     }
 133   }
 134 };
 135
 136 template <typename KeyClass>
 137 auto RangeSize(const nsTBaseHashSet<KeyClass>& aRange) {
 138   return aRange.Count();
 139 }
 140
 141 class nsCycleCollectionTraversalCallback;
 142
 143 template <class KeyClass>
 144 inline void ImplCycleCollectionUnlink(nsTBaseHashSet<KeyClass>& aField) {
 145   aField.Clear();
 146 }
 147
 148 template <class KeyClass>
 149 inline void ImplCycleCollectionTraverse(
 150     nsCycleCollectionTraversalCallback& aCallback,
 151     const nsTBaseHashSet<KeyClass>& aField, const char* aName,
 152     uint32_t aFlags = 0) {
 153   for (const auto& entry : aField) {
 154     CycleCollectionNoteChild(aCallback, mozilla::detail::PtrGetWeak(entry),
 155                              aName, aFlags);
 156   }
 157 }
 158
 159 namespace mozilla {
 160 template <typename SetT>
 161 class nsTSetInserter {
 162   SetT* mSet;
 163
 164   class Proxy {
 165     SetT& mSet;
 166
 167    public:
 168     explicit Proxy(SetT& aSet) : mSet{aSet} {}
 169
 170     template <typename E2>
 171     void operator=(E2&& aValue) {
 172       mSet.Insert(std::forward<E2>(aValue));
 173     }
 174   };
 175
 176  public:
 177   using iterator_category = std::output_iterator_tag;
 178
 179   explicit nsTSetInserter(SetT& aSet) : mSet{&aSet} {}
 180
 181   Proxy operator*() { return Proxy(*mSet); }
 182
 183   nsTSetInserter& operator++() { return *this; }
 184   nsTSetInserter& operator++(int) { return *this; }
 185 };
 186 }  // namespace mozilla
 187
 188 template <typename E>
 189 auto MakeInserter(nsTBaseHashSet<E>& aSet) {
 190   return mozilla::nsTSetInserter<nsTBaseHashSet<E>>{aSet};
 191 }
 192
 193 #endif  // XPCOM_DS_NSTHASHSET_H_