Bug 793013 - Add EnumSet to replace 1 << n bit type bitfields. r=Waldo
authorAnthony Jones <ajones@mozilla.com>
Tue, 06 Nov 2012 18:23:13 -0500
changeset 120423 40a702087f7d20d967aeff97c9e3de533b9063ba
parent 120422 098958fa76f3be74c293989a67ccc16b631e308b
child 120424 c394c477d2a898ad0c4abf35769b640a4c3b63c7
push id1997
push userakeybl@mozilla.com
push dateMon, 07 Jan 2013 21:25:26 +0000
treeherdermozilla-beta@4baf45cdcf21 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersWaldo
bugs793013
milestone19.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 793013 - Add EnumSet to replace 1 << n bit type bitfields. r=Waldo
mfbt/EnumSet.h
mfbt/exported_headers.mk
mfbt/tests/Makefile.in
mfbt/tests/TestEnumSet.cpp
new file mode 100644
--- /dev/null
+++ b/mfbt/EnumSet.h
@@ -0,0 +1,175 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/* A set abstraction for enumeration values. */
+
+#ifndef mozilla_EnumSet_h
+#define mozilla_EnumSet_h
+
+#include "mozilla/Assertions.h"
+#include "mozilla/StandardInteger.h"
+
+namespace mozilla {
+
+/**
+ * EnumSet<T> is a set of values defined by an enumeration. It is implemented
+ * using a 32 bit mask for each value so it will only work for enums with an int
+ * representation less than 32. It works both for enum and enum class types.
+ */
+template<typename T>
+class EnumSet
+{
+  public:
+    EnumSet()
+      : mBitField(0)
+    { }
+
+    EnumSet(T aEnum)
+      : mBitField(aEnum)
+    { }
+
+    EnumSet(T aEnum1, T aEnum2)
+      : mBitField(bitFor(aEnum1) |
+                  bitFor(aEnum2))
+    { }
+
+    EnumSet(T aEnum1, T aEnum2, T aEnum3)
+      : mBitField(bitFor(aEnum1) |
+                  bitFor(aEnum2) |
+                  bitFor(aEnum3))
+    { }
+
+    EnumSet(T aEnum1, T aEnum2, T aEnum3, T aEnum4)
+     : mBitField(bitFor(aEnum1) |
+                 bitFor(aEnum2) |
+                 bitFor(aEnum3) |
+                 bitFor(aEnum4))
+    { }
+
+    EnumSet(const EnumSet& aEnumSet)
+     : mBitField(aEnumSet.mBitField)
+    { }
+
+    /**
+     * Add an element
+     */
+    void operator+=(T aEnum) {
+      mBitField |= bitFor(aEnum);
+    }
+
+    /**
+     * Add an element
+     */
+    EnumSet<T> operator+(T aEnum) const {
+      EnumSet<T> result(*this);
+      result += aEnum;
+      return result;
+    }
+
+    /**
+     * Union
+     */
+    void operator+=(const EnumSet<T> aEnumSet) {
+      mBitField |= aEnumSet.mBitField;
+    }
+
+    /**
+     * Union
+     */
+    EnumSet<T> operator+(const EnumSet<T> aEnumSet) const {
+      EnumSet<T> result(*this);
+      result += aEnumSet;
+      return result;
+    }
+
+    /**
+     * Remove an element
+     */
+    void operator-=(T aEnum) {
+      mBitField &= ~(bitFor(aEnum));
+    }
+
+    /**
+     * Remove an element
+     */
+    EnumSet<T> operator-(T aEnum) const {
+      EnumSet<T> result(*this);
+      result -= aEnum;
+      return result;
+    }
+
+    /**
+     * Remove a set of elements
+     */
+    void operator-=(const EnumSet<T> aEnumSet) {
+      mBitField &= ~(aEnumSet.mBitField);
+    }
+
+    /**
+     * Remove a set of elements
+     */
+    EnumSet<T> operator-(const EnumSet<T> aEnumSet) const {
+      EnumSet<T> result(*this);
+      result -= aEnumSet;
+      return result;
+    }
+
+    /**
+     * Intersection
+     */
+    void operator&=(const EnumSet<T> aEnumSet) {
+      mBitField &= aEnumSet.mBitField;
+    }
+
+    /**
+     * Intersection
+     */
+    EnumSet<T> operator&(const EnumSet<T> aEnumSet) const {
+      EnumSet<T> result(*this);
+      result &= aEnumSet;
+      return result;
+    }
+
+    /**
+     * Equality
+     */
+
+    bool operator==(const EnumSet<T> aEnumSet) const {
+      return mBitField == aEnumSet.mBitField;
+    }
+
+    /**
+     * Test is an element is contained in the set
+     */
+    bool contains(T aEnum) const {
+      return mBitField & bitFor(aEnum);
+    }
+
+    /**
+     * Return the number of elements in the set
+     */
+
+    uint8_t size() {
+      uint8_t count = 0;
+      for (uint32_t bitField = mBitField; bitField; bitField >>= 1) {
+        if (bitField & 1)
+          count++;
+      }
+      return count;
+    }
+
+  private:
+    static uint32_t bitFor(T aEnum) {
+      uint32_t bitNumber(aEnum);
+      MOZ_ASSERT(bitNumber < 32);
+      return 1U << bitNumber;
+    }
+
+    uint32_t mBitField;
+};
+
+} // namespace mozilla
+
+#endif // mozilla_EnumSet_h_
--- a/mfbt/exported_headers.mk
+++ b/mfbt/exported_headers.mk
@@ -9,16 +9,17 @@
 EXPORTS_NAMESPACES += mozilla
 
 EXPORTS_mozilla += \
   Assertions.h \
   Attributes.h \
   BloomFilter.h \
   CheckedInt.h \
   Constants.h \
+  EnumSet.h \
   FloatingPoint.h \
   GuardObjects.h \
   HashFunctions.h \
   Likely.h \
   LinkedList.h \
   MathAlgorithms.h \
   MSStdInt.h \
   NullPtr.h \
--- a/mfbt/tests/Makefile.in
+++ b/mfbt/tests/Makefile.in
@@ -9,16 +9,17 @@ VPATH = @srcdir@
 
 include $(DEPTH)/config/autoconf.mk
 
 STL_FLAGS =
 
 CPP_UNIT_TESTS = \
   TestBloomFilter.cpp \
   TestCheckedInt.cpp \
+  TestEnumSet.cpp \
   TestSHA1.cpp \
   TestTypeTraits.cpp \
   TestWeakPtr.cpp \
   $(NULL)
 
 # in order to prevent rules.mk from trying to link to libraries that are
 # not available to MFBT, we have to reset these MOZ_GLUE*_LDFLAGS before including it
 # and LIBS_ after including it. For WRAP_LDFLAGS, it shouldn't matter.
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestEnumSet.cpp
@@ -0,0 +1,232 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/EnumSet.h"
+
+using namespace mozilla;
+
+enum SeaBird {
+  PENGUIN,
+  ALBATROSS,
+  FULMAR,
+  PRION,
+  SHEARWATER,
+  GADFLY_PETREL,
+  TRUE_PETREL,
+  DIVING_PETREL,
+  STORM_PETREL,
+  PELICAN,
+  GANNET,
+  BOOBY,
+  CORMORANT,
+  FRIGATEBIRD,
+  TROPICBIRD,
+  SKUA,
+  GULL,
+  TERN,
+  SKIMMER,
+  AUK
+};
+
+class EnumSetSuite {
+  public:
+    EnumSetSuite()
+      : mAlcidae(),
+        mDiomedeidae(ALBATROSS),
+        mPetrelProcellariidae(GADFLY_PETREL, TRUE_PETREL),
+        mNonPetrelProcellariidae(FULMAR, PRION, SHEARWATER),
+        mPetrels(GADFLY_PETREL, TRUE_PETREL, DIVING_PETREL, STORM_PETREL)
+    { }
+
+    void runTests() {
+      testSize();
+      testContains();
+      testAddTo();
+      testAdd();
+      testAddAll();
+      testUnion();
+      testRemoveFrom();
+      testRemove();
+      testRemoveAllFrom();
+      testRemoveAll();
+      testIntersect();
+      testInsersection();
+      testEquality();
+      testDuplicates();
+    }
+
+  private:
+    void testSize() {
+      MOZ_ASSERT(mAlcidae.size() == 0);
+      MOZ_ASSERT(mDiomedeidae.size() == 1);
+      MOZ_ASSERT(mPetrelProcellariidae.size() == 2);
+      MOZ_ASSERT(mNonPetrelProcellariidae.size() == 3);
+      MOZ_ASSERT(mPetrels.size() == 4);
+    }
+
+    void testContains() {
+      MOZ_ASSERT(!mPetrels.contains(PENGUIN));
+      MOZ_ASSERT(!mPetrels.contains(ALBATROSS));
+      MOZ_ASSERT(!mPetrels.contains(FULMAR));
+      MOZ_ASSERT(!mPetrels.contains(PRION));
+      MOZ_ASSERT(!mPetrels.contains(SHEARWATER));
+      MOZ_ASSERT(mPetrels.contains(GADFLY_PETREL));
+      MOZ_ASSERT(mPetrels.contains(TRUE_PETREL));
+      MOZ_ASSERT(mPetrels.contains(DIVING_PETREL));
+      MOZ_ASSERT(mPetrels.contains(STORM_PETREL));
+      MOZ_ASSERT(!mPetrels.contains(PELICAN));
+      MOZ_ASSERT(!mPetrels.contains(GANNET));
+      MOZ_ASSERT(!mPetrels.contains(BOOBY));
+      MOZ_ASSERT(!mPetrels.contains(CORMORANT));
+      MOZ_ASSERT(!mPetrels.contains(FRIGATEBIRD));
+      MOZ_ASSERT(!mPetrels.contains(TROPICBIRD));
+      MOZ_ASSERT(!mPetrels.contains(SKUA));
+      MOZ_ASSERT(!mPetrels.contains(GULL));
+      MOZ_ASSERT(!mPetrels.contains(TERN));
+      MOZ_ASSERT(!mPetrels.contains(SKIMMER));
+      MOZ_ASSERT(!mPetrels.contains(AUK));
+    }
+
+    void testCopy() {
+      EnumSet<SeaBird> likes = mPetrels;
+      likes -= TRUE_PETREL;
+      MOZ_ASSERT(mPetrels.size() == 4);
+      MOZ_ASSERT(mPetrels.contains(TRUE_PETREL));
+
+      MOZ_ASSERT(likes.size() == 3);
+      MOZ_ASSERT(likes.contains(GADFLY_PETREL));
+      MOZ_ASSERT(likes.contains(DIVING_PETREL));
+      MOZ_ASSERT(likes.contains(STORM_PETREL));
+    }
+
+    void testAddTo() {
+      EnumSet<SeaBird> seen = mPetrels;
+      seen += CORMORANT;
+      seen += TRUE_PETREL;
+      MOZ_ASSERT(mPetrels.size() == 4);
+      MOZ_ASSERT(!mPetrels.contains(CORMORANT));
+      MOZ_ASSERT(seen.size() == 5);
+      MOZ_ASSERT(seen.contains(GADFLY_PETREL));
+      MOZ_ASSERT(seen.contains(TRUE_PETREL));
+      MOZ_ASSERT(seen.contains(DIVING_PETREL));
+      MOZ_ASSERT(seen.contains(STORM_PETREL));
+      MOZ_ASSERT(seen.contains(CORMORANT));
+    }
+
+    void testAdd() {
+      EnumSet<SeaBird> seen = mPetrels + CORMORANT +
+                                         STORM_PETREL;
+      MOZ_ASSERT(mPetrels.size() == 4);
+      MOZ_ASSERT(!mPetrels.contains(CORMORANT));
+      MOZ_ASSERT(seen.size() == 5);
+      MOZ_ASSERT(seen.contains(GADFLY_PETREL));
+      MOZ_ASSERT(seen.contains(TRUE_PETREL));
+      MOZ_ASSERT(seen.contains(DIVING_PETREL));
+      MOZ_ASSERT(seen.contains(STORM_PETREL));
+      MOZ_ASSERT(seen.contains(CORMORANT));
+    }
+
+    void testAddAll() {
+      EnumSet<SeaBird> procellariidae;
+      procellariidae += mPetrelProcellariidae;
+      procellariidae += mNonPetrelProcellariidae;
+      MOZ_ASSERT(procellariidae.size() == 5);
+
+      // Both procellariidae and mPetrels include GADFLY_PERTEL and TRUE_PETREL
+      EnumSet<SeaBird> procellariiformes;
+      procellariiformes += mDiomedeidae;
+      procellariiformes += procellariidae;
+      procellariiformes += mPetrels;
+      MOZ_ASSERT(procellariiformes.size() == 8);
+    }
+
+    void testUnion() {
+      EnumSet<SeaBird> procellariidae = mPetrelProcellariidae +
+                                        mNonPetrelProcellariidae;
+      MOZ_ASSERT(procellariidae.size() == 5);
+
+      // Both procellariidae and mPetrels include GADFLY_PETREL and TRUE_PETREL
+      EnumSet<SeaBird> procellariiformes = mDiomedeidae + procellariidae +
+                                           mPetrels;
+      MOZ_ASSERT(procellariiformes.size() == 8);
+    }
+
+    void testRemoveFrom() {
+      EnumSet<SeaBird> likes = mPetrels;
+      likes -= TRUE_PETREL;
+      likes -= DIVING_PETREL;
+      MOZ_ASSERT(likes.size() == 2);
+      MOZ_ASSERT(likes.contains(GADFLY_PETREL));
+      MOZ_ASSERT(likes.contains(STORM_PETREL));
+    }
+
+    void testRemove() {
+      EnumSet<SeaBird> likes = mPetrels - TRUE_PETREL -
+                               DIVING_PETREL;
+      MOZ_ASSERT(likes.size() == 2);
+      MOZ_ASSERT(likes.contains(GADFLY_PETREL));
+      MOZ_ASSERT(likes.contains(STORM_PETREL));
+    }
+
+    void testRemoveAllFrom() {
+      EnumSet<SeaBird> likes = mPetrels;
+      likes -= mPetrelProcellariidae;
+      MOZ_ASSERT(likes.size() == 2);
+      MOZ_ASSERT(likes.contains(DIVING_PETREL));
+      MOZ_ASSERT(likes.contains(STORM_PETREL));
+    }
+
+    void testRemoveAll() {
+      EnumSet<SeaBird> likes = mPetrels - mPetrelProcellariidae;
+      MOZ_ASSERT(likes.size() == 2);
+      MOZ_ASSERT(likes.contains(DIVING_PETREL));
+      MOZ_ASSERT(likes.contains(STORM_PETREL));
+    }
+
+    void testIntersect() {
+      EnumSet<SeaBird> likes = mPetrels;
+      likes &= mPetrelProcellariidae;
+      MOZ_ASSERT(likes.size() == 2);
+      MOZ_ASSERT(likes.contains(GADFLY_PETREL));
+      MOZ_ASSERT(likes.contains(TRUE_PETREL));
+    }
+
+    void testInsersection() {
+      EnumSet<SeaBird> likes = mPetrels & mPetrelProcellariidae;
+      MOZ_ASSERT(likes.size() == 2);
+      MOZ_ASSERT(likes.contains(GADFLY_PETREL));
+      MOZ_ASSERT(likes.contains(TRUE_PETREL));
+    }
+
+    void testEquality() {
+      EnumSet<SeaBird> likes = mPetrels & mPetrelProcellariidae;
+      MOZ_ASSERT(likes == EnumSet<SeaBird>(GADFLY_PETREL,
+                                           TRUE_PETREL));
+    }
+
+    void testDuplicates() {
+      EnumSet<SeaBird> likes = mPetrels;
+      likes += GADFLY_PETREL;
+      likes += TRUE_PETREL;
+      likes += DIVING_PETREL;
+      likes += STORM_PETREL;
+      MOZ_ASSERT(likes.size() == 4);
+      MOZ_ASSERT(likes == mPetrels);
+    }
+
+
+    EnumSet<SeaBird> mAlcidae;
+    EnumSet<SeaBird> mDiomedeidae;
+    EnumSet<SeaBird> mPetrelProcellariidae;
+    EnumSet<SeaBird> mNonPetrelProcellariidae;
+    EnumSet<SeaBird> mPetrels;
+};
+
+int main()
+{
+  EnumSetSuite suite;
+  suite.runTests();
+  return 0;
+}