mfbt/EnumSet.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 /* A set abstraction for enumeration values. */
   8
   9 #ifndef mozilla_EnumSet_h
  10 #define mozilla_EnumSet_h
  11
  12 #include "mozilla/Assertions.h"
  13 #include "mozilla/Attributes.h"
  14 #include "mozilla/MathAlgorithms.h"
  15
  16 #include <initializer_list>
  17 #include <type_traits>
  18
  19 #include <stdint.h>
  20
  21 namespace mozilla {
  22
  23 /**
  24  * EnumSet<T, U> is a set of values defined by an enumeration. It is implemented
  25  * using a bit mask with the size of U for each value. It works both for enum
  26  * and enum class types. EnumSet also works with U being a BitSet.
  27  */
  28 template <typename T, typename Serialized = typename std::make_unsigned<
  29                           typename std::underlying_type<T>::type>::type>
  30 class EnumSet {
  31  public:
  32   using valueType = T;
  33   using serializedType = Serialized;
  34
  35   constexpr EnumSet() : mBitField() {}
  36
  37   constexpr MOZ_IMPLICIT EnumSet(T aEnum) : mBitField(bitFor(aEnum)) {}
  38
  39   constexpr EnumSet(T aEnum1, T aEnum2)
  40       : mBitField(bitFor(aEnum1) | bitFor(aEnum2)) {}
  41
  42   constexpr EnumSet(T aEnum1, T aEnum2, T aEnum3)
  43       : mBitField(bitFor(aEnum1) | bitFor(aEnum2) | bitFor(aEnum3)) {}
  44
  45   constexpr EnumSet(T aEnum1, T aEnum2, T aEnum3, T aEnum4)
  46       : mBitField(bitFor(aEnum1) | bitFor(aEnum2) | bitFor(aEnum3) |
  47                   bitFor(aEnum4)) {}
  48
  49   constexpr MOZ_IMPLICIT EnumSet(std::initializer_list<T> list) : mBitField() {
  50     for (auto value : list) {
  51       (*this) += value;
  52     }
  53   }
  54
  55 #ifdef DEBUG
  56   constexpr EnumSet(const EnumSet& aEnumSet) : mBitField(aEnumSet.mBitField) {}
  57
  58   constexpr EnumSet& operator=(const EnumSet& aEnumSet) {
  59     mBitField = aEnumSet.mBitField;
  60     incVersion();
  61     return *this;
  62   }
  63 #endif
  64
  65   /**
  66    * Add an element
  67    */
  68   constexpr void operator+=(T aEnum) {
  69     incVersion();
  70     mBitField |= bitFor(aEnum);
  71   }
  72
  73   /**
  74    * Add an element
  75    */
  76   constexpr EnumSet operator+(T aEnum) const {
  77     EnumSet result(*this);
  78     result += aEnum;
  79     return result;
  80   }
  81
  82   /**
  83    * Union
  84    */
  85   void operator+=(const EnumSet& aEnumSet) {
  86     incVersion();
  87     mBitField |= aEnumSet.mBitField;
  88   }
  89
  90   /**
  91    * Union
  92    */
  93   EnumSet operator+(const EnumSet& aEnumSet) const {
  94     EnumSet result(*this);
  95     result += aEnumSet;
  96     return result;
  97   }
  98
  99   /**
 100    * Remove an element
 101    */
 102   void operator-=(T aEnum) {
 103     incVersion();
 104     mBitField &= ~(bitFor(aEnum));
 105   }
 106
 107   /**
 108    * Remove an element
 109    */
 110   EnumSet operator-(T aEnum) const {
 111     EnumSet result(*this);
 112     result -= aEnum;
 113     return result;
 114   }
 115
 116   /**
 117    * Remove a set of elements
 118    */
 119   void operator-=(const EnumSet& aEnumSet) {
 120     incVersion();
 121     mBitField &= ~(aEnumSet.mBitField);
 122   }
 123
 124   /**
 125    * Remove a set of elements
 126    */
 127   EnumSet operator-(const EnumSet& aEnumSet) const {
 128     EnumSet result(*this);
 129     result -= aEnumSet;
 130     return result;
 131   }
 132
 133   /**
 134    * Clear
 135    */
 136   void clear() {
 137     incVersion();
 138     mBitField = Serialized();
 139   }
 140
 141   /**
 142    * Intersection
 143    */
 144   void operator&=(const EnumSet& aEnumSet) {
 145     incVersion();
 146     mBitField &= aEnumSet.mBitField;
 147   }
 148
 149   /**
 150    * Intersection
 151    */
 152   EnumSet operator&(const EnumSet& aEnumSet) const {
 153     EnumSet result(*this);
 154     result &= aEnumSet;
 155     return result;
 156   }
 157
 158   /**
 159    * Equality
 160    */
 161   bool operator==(const EnumSet& aEnumSet) const {
 162     return mBitField == aEnumSet.mBitField;
 163   }
 164
 165   /**
 166    * Equality
 167    */
 168   bool operator==(T aEnum) const { return mBitField == bitFor(aEnum); }
 169
 170   /**
 171    * Not equal
 172    */
 173   bool operator!=(const EnumSet& aEnumSet) const {
 174     return !operator==(aEnumSet);
 175   }
 176
 177   /**
 178    * Not equal
 179    */
 180   bool operator!=(T aEnum) const { return !operator==(aEnum); }
 181
 182   /**
 183    * Test is an element is contained in the set.
 184    */
 185   bool contains(T aEnum) const {
 186     return static_cast<bool>(mBitField & bitFor(aEnum));
 187   }
 188
 189   /**
 190    * Test if a set is contained in the set.
 191    */
 192   bool contains(const EnumSet& aEnumSet) const {
 193     return (mBitField & aEnumSet.mBitField) == aEnumSet.mBitField;
 194   }
 195
 196   /**
 197    * Return the number of elements in the set.
 198    */
 199   size_t size() const {
 200     if constexpr (std::is_unsigned_v<Serialized>) {
 201       if constexpr (kMaxBits > 32) {
 202         return CountPopulation64(mBitField);
 203       } else {
 204         return CountPopulation32(mBitField);
 205       }
 206     } else {
 207       return mBitField.Count();
 208     }
 209   }
 210
 211   bool isEmpty() const {
 212     if constexpr (std::is_unsigned_v<Serialized>) {
 213       return mBitField == 0;
 214     } else {
 215       return mBitField.IsEmpty();
 216     }
 217   }
 218
 219   Serialized serialize() const { return mBitField; }
 220
 221   void deserialize(Serialized aValue) {
 222     incVersion();
 223     mBitField = aValue;
 224   }
 225
 226   class ConstIterator {
 227     const EnumSet* mSet;
 228     uint32_t mPos;
 229 #ifdef DEBUG
 230     uint64_t mVersion;
 231 #endif
 232
 233     void checkVersion() const {
 234       // Check that the set has not been modified while being iterated.
 235       MOZ_ASSERT_IF(mSet, mSet->mVersion == mVersion);
 236     }
 237
 238    public:
 239     ConstIterator(const EnumSet& aSet, uint32_t aPos)
 240         : mSet(&aSet), mPos(aPos) {
 241 #ifdef DEBUG
 242       mVersion = mSet->mVersion;
 243 #endif
 244       MOZ_ASSERT(aPos <= kMaxBits);
 245       if (aPos != kMaxBits && !mSet->contains(T(mPos))) {
 246         ++*this;
 247       }
 248     }
 249
 250     ConstIterator(const ConstIterator& aOther)
 251         : mSet(aOther.mSet), mPos(aOther.mPos) {
 252 #ifdef DEBUG
 253       mVersion = aOther.mVersion;
 254       checkVersion();
 255 #endif
 256     }
 257
 258     ConstIterator(ConstIterator&& aOther)
 259         : mSet(aOther.mSet), mPos(aOther.mPos) {
 260 #ifdef DEBUG
 261       mVersion = aOther.mVersion;
 262       checkVersion();
 263 #endif
 264       aOther.mSet = nullptr;
 265     }
 266
 267     ~ConstIterator() { checkVersion(); }
 268
 269     bool operator==(const ConstIterator& other) const {
 270       MOZ_ASSERT(mSet == other.mSet);
 271       checkVersion();
 272       return mPos == other.mPos;
 273     }
 274
 275     bool operator!=(const ConstIterator& other) const {
 276       return !(*this == other);
 277     }
 278
 279     T operator*() const {
 280       MOZ_ASSERT(mSet);
 281       MOZ_ASSERT(mPos < kMaxBits);
 282       MOZ_ASSERT(mSet->contains(T(mPos)));
 283       checkVersion();
 284       return T(mPos);
 285     }
 286
 287     ConstIterator& operator++() {
 288       MOZ_ASSERT(mSet);
 289       MOZ_ASSERT(mPos < kMaxBits);
 290       checkVersion();
 291       do {
 292         mPos++;
 293       } while (mPos < kMaxBits && !mSet->contains(T(mPos)));
 294       return *this;
 295     }
 296   };
 297
 298   ConstIterator begin() const { return ConstIterator(*this, 0); }
 299
 300   ConstIterator end() const { return ConstIterator(*this, kMaxBits); }
 301
 302  private:
 303   constexpr static Serialized bitFor(T aEnum) {
 304     auto bitNumber = static_cast<size_t>(aEnum);
 305     MOZ_DIAGNOSTIC_ASSERT(bitNumber < kMaxBits);
 306     if constexpr (std::is_unsigned_v<Serialized>) {
 307       return static_cast<Serialized>(Serialized{1} << bitNumber);
 308     } else {
 309       Serialized bitField;
 310       bitField[bitNumber] = true;
 311       return bitField;
 312     }
 313   }
 314
 315   constexpr void incVersion() {
 316 #ifdef DEBUG
 317     mVersion++;
 318 #endif
 319   }
 320
 321   static constexpr size_t MaxBits() {
 322     if constexpr (std::is_unsigned_v<Serialized>) {
 323       return sizeof(Serialized) * 8;
 324     } else {
 325       return Serialized::Size();
 326     }
 327   }
 328
 329   static constexpr size_t kMaxBits = MaxBits();
 330
 331   Serialized mBitField;
 332
 333 #ifdef DEBUG
 334   uint64_t mVersion = 0;
 335 #endif
 336 };
 337
 338 }  // namespace mozilla
 339
 340 #endif /* mozilla_EnumSet_h_*/