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 { return HasBitFor(aEnum); }
 186
 187   /**
 188    * Test if a set is contained in the set.
 189    */
 190   bool contains(const EnumSet& aEnumSet) const {
 191     return (mBitField & aEnumSet.mBitField) == aEnumSet.mBitField;
 192   }
 193
 194   /**
 195    * Return the number of elements in the set.
 196    */
 197   size_t size() const {
 198     if constexpr (std::is_unsigned_v<Serialized>) {
 199       if constexpr (kMaxBits > 32) {
 200         return CountPopulation64(mBitField);
 201       } else {
 202         return CountPopulation32(mBitField);
 203       }
 204     } else {
 205       return mBitField.Count();
 206     }
 207   }
 208
 209   bool isEmpty() const {
 210     if constexpr (std::is_unsigned_v<Serialized>) {
 211       return mBitField == 0;
 212     } else {
 213       return mBitField.IsEmpty();
 214     }
 215   }
 216
 217   Serialized serialize() const { return mBitField; }
 218
 219   void deserialize(Serialized aValue) {
 220     IncVersion();
 221     mBitField = aValue;
 222   }
 223
 224   class ConstIterator {
 225     const EnumSet* mSet;
 226     size_t mPos;
 227 #ifdef DEBUG
 228     uint64_t mVersion;
 229 #endif
 230
 231     void checkVersion() const {
 232       // Check that the set has not been modified while being iterated.
 233       MOZ_ASSERT_IF(mSet, mSet->mVersion == mVersion);
 234     }
 235
 236    public:
 237     ConstIterator(const EnumSet& aSet, size_t aPos) : mSet(&aSet), mPos(aPos) {
 238 #ifdef DEBUG
 239       mVersion = mSet->mVersion;
 240 #endif
 241       MOZ_ASSERT(aPos <= kMaxBits);
 242       if (aPos != kMaxBits && !mSet->HasBitAt(mPos)) {
 243         ++*this;
 244       }
 245     }
 246
 247     ConstIterator(const ConstIterator& aOther)
 248         : mSet(aOther.mSet), mPos(aOther.mPos) {
 249 #ifdef DEBUG
 250       mVersion = aOther.mVersion;
 251       checkVersion();
 252 #endif
 253     }
 254
 255     ConstIterator(ConstIterator&& aOther)
 256         : mSet(aOther.mSet), mPos(aOther.mPos) {
 257 #ifdef DEBUG
 258       mVersion = aOther.mVersion;
 259       checkVersion();
 260 #endif
 261       aOther.mSet = nullptr;
 262     }
 263
 264     ~ConstIterator() { checkVersion(); }
 265
 266     bool operator==(const ConstIterator& other) const {
 267       MOZ_ASSERT(mSet == other.mSet);
 268       checkVersion();
 269       return mPos == other.mPos;
 270     }
 271
 272     bool operator!=(const ConstIterator& other) const {
 273       return !(*this == other);
 274     }
 275
 276     T operator*() const {
 277       MOZ_ASSERT(mSet);
 278       MOZ_ASSERT(mPos < kMaxBits);
 279       MOZ_ASSERT(mSet->HasBitAt(mPos));
 280       checkVersion();
 281       return T(mPos);
 282     }
 283
 284     ConstIterator& operator++() {
 285       MOZ_ASSERT(mSet);
 286       MOZ_ASSERT(mPos < kMaxBits);
 287       checkVersion();
 288       do {
 289         mPos++;
 290       } while (mPos < kMaxBits && !mSet->HasBitAt(mPos));
 291       return *this;
 292     }
 293   };
 294
 295   ConstIterator begin() const { return ConstIterator(*this, 0); }
 296
 297   ConstIterator end() const { return ConstIterator(*this, kMaxBits); }
 298
 299  private:
 300   constexpr static Serialized BitFor(T aEnum) {
 301     const auto pos = static_cast<size_t>(aEnum);
 302     return BitAt(pos);
 303   }
 304
 305   constexpr static Serialized BitAt(size_t aPos) {
 306     MOZ_DIAGNOSTIC_ASSERT(aPos < kMaxBits);
 307     if constexpr (std::is_unsigned_v<Serialized>) {
 308       return static_cast<Serialized>(Serialized{1} << aPos);
 309     } else {
 310       Serialized bitField;
 311       bitField[aPos] = true;
 312       return bitField;
 313     }
 314   }
 315
 316   constexpr bool HasBitFor(T aEnum) const {
 317     const auto pos = static_cast<size_t>(aEnum);
 318     return HasBitAt(pos);
 319   }
 320
 321   constexpr bool HasBitAt(size_t aPos) const {
 322     return static_cast<bool>(mBitField & BitAt(aPos));
 323   }
 324
 325   constexpr void IncVersion() {
 326 #ifdef DEBUG
 327     mVersion++;
 328 #endif
 329   }
 330
 331   static constexpr size_t MaxBits() {
 332     if constexpr (std::is_unsigned_v<Serialized>) {
 333       return sizeof(Serialized) * 8;
 334     } else {
 335       return Serialized::Size();
 336     }
 337   }
 338
 339   static constexpr size_t kMaxBits = MaxBits();
 340
 341   Serialized mBitField;
 342
 343 #ifdef DEBUG
 344   uint64_t mVersion = 0;
 345 #endif
 346 };
 347
 348 }  // namespace mozilla
 349
 350 #endif /* mozilla_EnumSet_h_*/