Move bitcount to Utils.Internal.BitUtil. (#498)
authorMatt Renaud <matt@m-renaud.com>
Fri, 19 Jan 2018 16:27:24 +0000 (08:27 -0800)
committerGitHub <noreply@github.com>
Fri, 19 Jan 2018 16:27:24 +0000 (08:27 -0800)
Previously this lived in IntSet.Internal and was not exported. This utility
function will be needed by IntSet.Internal, IntSetValidity, and
IntMapValidity. The latter two need it to verify that the mask is a power
of two (the bitcount of the mask == 1).

Data/IntSet/Internal.hs
Utils/Containers/Internal/BitUtil.hs

index 48f27b9..ea1124e 100644 (file)
@@ -1457,28 +1457,6 @@ foldr'Bits prefix f z bm = let lb = lowestBitSet bm
 
 #endif
 
-{----------------------------------------------------------------------
-  [bitcount] as posted by David F. Place to haskell-cafe on April 11, 2006,
-  based on the code on
-  http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan,
-  where the following source is given:
-    Published in 1988, the C Programming Language 2nd Ed. (by Brian W.
-    Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April
-    19, 2006 Don Knuth pointed out to me that this method "was first published
-    by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by
-    Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)"
-----------------------------------------------------------------------}
-
-bitcount :: Int -> Word -> Int
-#if MIN_VERSION_base(4,5,0)
-bitcount a x = a + popCount x
-#else
-bitcount a0 x0 = go a0 x0
-  where go a 0 = a
-        go a x = go (a + 1) (x .&. (x-1))
-#endif
-{-# INLINE bitcount #-}
-
 
 {--------------------------------------------------------------------
   Utilities
index b629946..a8725e2 100644 (file)
@@ -31,7 +31,8 @@
 -- closely.
 
 module Utils.Containers.Internal.BitUtil
-    ( highestBitMask
+    ( bitcount
+    , highestBitMask
     , shiftLL
     , shiftRL
     , wordSize
@@ -39,9 +40,9 @@ module Utils.Containers.Internal.BitUtil
 
 import Data.Bits ((.|.), xor)
 #if MIN_VERSION_base(4,5,0)
-import Data.Bits (unsafeShiftL, unsafeShiftR)
+import Data.Bits (popCount, unsafeShiftL, unsafeShiftR)
 #else
-import Data.Bits (shiftL, shiftR)
+import Data.Bits ((.&.), shiftL, shiftR)
 #endif
 #if MIN_VERSION_base(4,7,0)
 import Data.Bits (finiteBitSize)
@@ -53,6 +54,28 @@ import Data.Bits (bitSize)
 import Data.Word (Word)
 #endif
 
+{----------------------------------------------------------------------
+  [bitcount] as posted by David F. Place to haskell-cafe on April 11, 2006,
+  based on the code on
+  http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan,
+  where the following source is given:
+    Published in 1988, the C Programming Language 2nd Ed. (by Brian W.
+    Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April
+    19, 2006 Don Knuth pointed out to me that this method "was first published
+    by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by
+    Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)"
+----------------------------------------------------------------------}
+
+bitcount :: Int -> Word -> Int
+#if MIN_VERSION_base(4,5,0)
+bitcount a x = a + popCount x
+#else
+bitcount a0 x0 = go a0 x0
+  where go a 0 = a
+        go a x = go (a + 1) (x .&. (x-1))
+#endif
+{-# INLINE bitcount #-}
+
 -- The highestBitMask implementation is based on
 -- http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
 -- which has been put in the public domain.