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 112490 40a702087f7d20d967aeff97c9e3de533b9063ba
parent 112489 098958fa76f3be74c293989a67ccc16b631e308b
child 112491 c394c477d2a898ad0c4abf35769b640a4c3b63c7
push id1191
push userpastithas@mozilla.com
push dateFri, 09 Nov 2012 07:00:47 +0000
treeherderfx-team@90cea19e27e2 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersWaldo
bugs793013
milestone19.0a1
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;
+}