Fix a limitation of SmallPtrSet. Before it would assert if the smallsize

was not a power of two.  Now it rounds up to the next power of two internally.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33580 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 30 insertions, 2 deletions

diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h
index d617d6b..d2a68ff 100644
--- a/include/llvm/ADT/SmallPtrSet.h
+++ b/include/llvm/ADT/SmallPtrSet.h
@@ -161,13 +161,41 @@ public:
   }
 };
 
+/// NextPowerOfTwo - This is a helper template that rounds N up to the next
+/// power of two.
+template<unsigned N>
+struct NextPowerOfTwo;
+
+/// NextPowerOfTwoH - If N is not a power of two, increase it.  This is a helper
+/// template used to implement NextPowerOfTwo.
+template<unsigned N, bool isPowerTwo>
+struct NextPowerOfTwoH {
+  enum { Val = N };
+};
+template<unsigned N>
+struct NextPowerOfTwoH<N, false> {
+  enum {
+    // We could just use NextVal = N+1, but this converges faster.  N|(N-1) sets
+    // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.
+    NextVal = (N|(N-1)) + 1,
+    Val = NextPowerOfTwo<NextVal>::Val
+  };
+};
+
+template<unsigned N>
+struct NextPowerOfTwo {
+  enum { Val = NextPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
+};
+
 
 /// SmallPtrSet - This class implements 
 template<class PtrType, unsigned SmallSize>
 class SmallPtrSet : public SmallPtrSetImpl {
-  void *SmallArray[SmallSize];
+  // Make sure that SmallSize is a power of two, round up if not.
+  enum { SmallSizePowTwo = NextPowerOfTwo<SmallSize>::Val };
+  void *SmallArray[SmallSizePowTwo];
 public:
-  SmallPtrSet() : SmallPtrSetImpl(SmallSize) {}
+  SmallPtrSet() : SmallPtrSetImpl(NextPowerOfTwo<SmallSizePowTwo>::Val) {}
   
   typedef SmallPtrSetIterator<PtrType> iterator;
   typedef SmallPtrSetIterator<PtrType> const_iterator;