bitset 1.4.7 → 1.4.8
raw patch · 7 files changed
+113/−31 lines, 7 filesdep +tastydep +tasty-quickcheckdep −test-frameworkdep −test-framework-quickcheck2dep ~QuickCheckdep ~base
Dependencies added: tasty, tasty-quickcheck
Dependencies removed: test-framework, test-framework-quickcheck2
Dependency ranges changed: QuickCheck, base
Files
- CHANGES +5/−0
- bitset.cabal +7/−7
- cbits/gmp-extras.cmm +59/−1
- src/Data/BitSet/Dynamic.hs +8/−2
- src/Data/BitSet/Generic.hs +13/−0
- src/GHC/Integer/GMP/TypeExt.hs +13/−7
- tests/Tests.hs +8/−14
CHANGES view
@@ -3,6 +3,11 @@ Here you can see the full list of changes between each bitset release. +Version 1.4.8++- Add support for GHC 7.8+- IsList instance for BitSet, so it's possible to use OverloadedLists extension.+ Version 1.4.7 -------------
bitset.cabal view
@@ -1,5 +1,5 @@ Name: bitset-Version: 1.4.7+Version: 1.4.8 Synopsis: A space-efficient set data structure. Description: A /bit set/ is a compact data structure, which maintains a set of members@@ -36,7 +36,7 @@ else Extra-libraries: gmp - Build-depends: base >= 4.4.0 && < 4.7+ Build-depends: base >= 4.4.0 && < 4.8 , deepseq == 1.3.* , integer-gmp , ghc-prim@@ -56,10 +56,10 @@ Type: exitcode-stdio-1.0 Main-is: Tests.hs - Build-depends: base >= 4.4.0 && < 4.7- , QuickCheck == 2.5.*- , test-framework == 0.6.*- , test-framework-quickcheck2 == 0.2.*+ Build-depends: base >= 4.4.0 && < 4.8+ , QuickCheck == 2.6.*+ , tasty == 0.8.*+ , tasty-quickcheck == 0.8.* , bitset Benchmark bitset-benchmarks@@ -74,7 +74,7 @@ Type: exitcode-stdio-1.0 Main-is: Benchmarks.hs - Build-depends: base >= 4.4.0 || < 4.7+ Build-depends: base >= 4.4.0 || < 4.8 , deepseq == 1.3.* , integer-gmp , ghc-prim
cbits/gmp-extras.cmm view
@@ -6,11 +6,68 @@ import "integer-gmp" __gmpz_init_set; import "integer-gmp" __gmpz_popcount;-import "integer-gmp" __gmpz_tstbit; import "integer-gmp" __gmpz_setbit; import "integer-gmp" __gmpz_clrbit; +#if __GLASGOW_HASKELL__ >= 707+ #define GMP_TAKE1_UL1_RET1(name,mp_fun) \+name (W_ ws1, P_ d1, W_ wul) \+{ \+ CInt s1; \+ CLong ul; \+ W_ mp_tmp; \+ W_ mp_result; \+ \+ /* call doYouWantToGC() */ \+again: \+ STK_CHK_GEN_N (2 * SIZEOF_MP_INT); \+ MAYBE_GC(again); \+ \+ s1 = W_TO_INT(ws1); \+ ul = W_TO_LONG(wul); \+ \+ mp_tmp = Sp - 1 * SIZEOF_MP_INT; \+ mp_result = Sp - 2 * SIZEOF_MP_INT; \+ MP_INT__mp_alloc(mp_tmp) = W_TO_INT(BYTE_ARR_WDS(d1)); \+ MP_INT__mp_size(mp_tmp) = (s1); \+ MP_INT__mp_d(mp_tmp) = BYTE_ARR_CTS(d1); \+ \+ ccall __gmpz_init_set(mp_result "ptr", mp_tmp "ptr"); \+ \+ /* Perform the operation */ \+ ccall mp_fun(mp_result "ptr", ul); \+ \+ return(TO_W_(MP_INT__mp_size(mp_result)), \+ MP_INT__mp_d(mp_result) - SIZEOF_StgArrWords); \+}++GMP_TAKE1_UL1_RET1(integer_cmm_setBitIntegerzh, __gmpz_setbit)+GMP_TAKE1_UL1_RET1(integer_cmm_clearBitIntegerzh, __gmpz_clrbit)++integer_cmm_popCountIntegerzh (W_ ws, W_ d)+{+ CInt s, res;+ W_ mp_tmp;++again:+ STK_CHK_P_LL(SIZEOF_MP_INT, integer_cmm_popCountIntegerzh, R2);+ MAYBE_GC(again);++ s = W_TO_INT(ws);++ mp_tmp = Sp - 1 * SIZEOF_MP_INT;+ MP_INT__mp_alloc(mp_tmp) = W_TO_INT(BYTE_ARR_WDS(d));+ MP_INT__mp_size(mp_tmp) = (s);+ MP_INT__mp_d(mp_tmp) = BYTE_ARR_CTS(d);++ (res) = foreign "C" __gmpz_popcount(mp_tmp "ptr");++ return (TO_W_(res));+}+#else++#define GMP_TAKE1_UL1_RET1(name,mp_fun) \ name \ { \ CInt s; \@@ -89,3 +146,4 @@ RET_N(TO_W_(res)); }+#endif
src/Data/BitSet/Dynamic.hs view
@@ -1,3 +1,4 @@+{-# LANGUAGE CPP #-} {-# LANGUAGE MagicHash #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} @@ -118,11 +119,16 @@ popCount (FasterInteger x) = I# (popCountInteger x) {-# SPECIALIZE INLINE popCount :: FasterInteger -> Int #-} + isSigned = isSigned . unFI+ {-# INLINE isSigned #-}+ bitSize = bitSize . unFI {-# INLINE bitSize #-} - isSigned = isSigned . unFI- {-# INLINE isSigned #-}+#if defined(__GLASGOW_HASKELL__) && (__GLASGOW_HASKELL__ >= 707)+ bitSizeMaybe = bitSizeMaybe . unFI+ {-# INLINE bitSizeMaybe #-}+#endif type BitSet = GS.BitSet FasterInteger
src/Data/BitSet/Generic.hs view
@@ -25,6 +25,8 @@ -- independent of container choice, the maximum number of elements in a -- bit set is bounded by @maxBound :: Int@. +{-# LANGUAGE CPP #-}+{-# LANGUAGE TypeFamilies #-} {-# LANGUAGE BangPatterns #-} {-# LANGUAGE DeriveDataTypeable #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-}@@ -81,6 +83,10 @@ import Data.Monoid (Monoid(..)) import Foreign (Storable) import GHC.Exts (build)+#if defined(__GLASGOW_HASKELL__) && (__GLASGOW_HASKELL__ >= 707)+import GHC.Exts (IsList)+import qualified GHC.Exts as Exts+#endif import Text.Read (Read(..), Lexeme(..), lexP, prec, parens) import qualified Data.List as List @@ -100,6 +106,13 @@ instance (Enum a, Bits c, Num c) => Monoid (BitSet c a) where mempty = empty mappend = union++#if defined(__GLASGOW_HASKELL__) && (__GLASGOW_HASKELL__ >= 707)+instance (Enum a, Bits c, Num c) => IsList (BitSet c a) where+ type Item (BitSet c a) = a+ fromList = fromList+ toList = toList+#endif -- | /O(1)/. Is the bit set empty? null :: (Eq c, Num c) => BitSet c a -> Bool
src/GHC/Integer/GMP/TypeExt.hs view
@@ -21,6 +21,12 @@ import GHC.Integer.GMP.PrimExt (popCountInteger#, testBitInteger#, setBitInteger#, clearBitInteger#) +#if __GLASGOW_HASKELL__ >= 707+import GHC.Exts (isTrue#)+#else+isTrue# = id+#endif+ popCountInteger :: Integer -> Int# popCountInteger (S# i) = word2Int# (popCnt# (int2Word# i)) popCountInteger (J# s d) = popCountInteger# s d@@ -28,19 +34,19 @@ testBitInteger :: Integer -> Int# -> Bool testBitInteger (S# j) i- | i <# 0# = False- | i <# (WORD_SIZE_IN_BITS# -# 1#) =+ | isTrue# (i <# 0#) = False+ | isTrue# (i <# (WORD_SIZE_IN_BITS# -# 1#)) = let !mask = 1# `uncheckedIShiftL#` i in- word2Int# (int2Word# j `and#` int2Word# mask) /=# 0#+ isTrue# (word2Int# (int2Word# j `and#` int2Word# mask) /=# 0#) | otherwise = let !(# s, d #) = int2Integer# j in testBitInteger (J# s d) i-testBitInteger (J# s d) i = testBitInteger# s d i /=# 0#+testBitInteger (J# s d) i = isTrue# (testBitInteger# s d i /=# 0#) {-# NOINLINE testBitInteger #-} setBitInteger :: Integer -> Int# -> Integer setBitInteger (S# j) i- | i <# 0# = S# j- | i <# (WORD_SIZE_IN_BITS# -# 1#) =+ | isTrue# (i <# 0#) = S# j+ | isTrue# (i <# (WORD_SIZE_IN_BITS# -# 1#)) = let !mask = 1# `uncheckedIShiftL#` i in S# (word2Int# (int2Word# j `or#` int2Word# mask)) | otherwise =@@ -51,7 +57,7 @@ clearBitInteger :: Integer -> Int# -> Integer clearBitInteger (S# j) i- | i <# 0# || i >=# (WORD_SIZE_IN_BITS# -# 1#) = S# j+ | isTrue# (i <# 0#) || isTrue# (i >=# (WORD_SIZE_IN_BITS# -# 1#)) = S# j | otherwise = let !mask = int2Word# (1# `uncheckedIShiftL#` i) `xor#`
tests/Tests.hs view
@@ -1,5 +1,4 @@ {-# LANGUAGE CPP #-}-{-# LANGUAGE TypeSynonymInstances #-} {-# LANGUAGE FlexibleInstances #-} module Main (main) where@@ -12,8 +11,8 @@ import Data.Word (Word16) import Foreign (Storable(..), allocaBytes) -import Test.Framework (Test, testGroup, defaultMain)-import Test.Framework.Providers.QuickCheck2 (testProperty)+import Test.Tasty (TestTree, testGroup, defaultMain)+import Test.Tasty.QuickCheck (testProperty) import Test.QuickCheck (Property, Arbitrary(..), (==>), classify) import Test.QuickCheck.Monadic (monadicIO, assert, run) @@ -28,9 +27,6 @@ instance (Arbitrary a, Enum a) => Arbitrary (GS.BitSet Word16 a) where arbitrary = GS.fromList <$> arbitrary -instance Show (Word16 -> a) where- show = const "FUNCTION"- instance Arbitrary FasterInteger where arbitrary = FasterInteger <$> arbitrary @@ -225,13 +221,11 @@ main :: IO () main = defaultMain tests where- tests :: [Test]- tests = [ testGroup "Data.BitSet" testsBitSet- , testGroup "GHC.Integer.GMP" testsFasterInteger- ]+ tests :: TestTree+ tests = testGroup "Tests" $ [ testsBitSet, testsFasterInteger] - testsBitSet :: [Test]- testsBitSet =+ testsBitSet :: TestTree+ testsBitSet = testGroup "Data.BitSet" $ [ testProperty "size" propSize , testProperty "size after insert" propSizeAfterInsert , testProperty "size after delete" propSizeAfterDelete@@ -258,8 +252,8 @@ , testProperty "storable instance" propStorable ] - testsFasterInteger :: [Test]- testsFasterInteger =+ testsFasterInteger :: TestTree+ testsFasterInteger = testGroup "GHC.Integer.GMP" $ [ #if defined(__GLASGOW_HASKELL__) && (__GLASGOW_HASKELL__ >= 706) testProperty "pop count" propPopCount