hashtables 1.2.4.2 → 1.4.2
raw patch · 13 files changed
Files
- cabal.project +7/−0
- cbits/common.c +2/−6
- cbits/defs.h +1/−1
- cbits/sse-42-check.c +1/−1
- changelog.md +34/−1
- hashtables.cabal +24/−21
- src/Data/HashTable/IO.hs +30/−30
- src/Data/HashTable/Internal/CacheLine.hs +7/−4
- src/Data/HashTable/Internal/IntArray.hs +2/−2
- src/Data/HashTable/ST/Basic.hs +10/−5
- test/hashtables-test.cabal +2/−2
- test/suite/Data/HashTable/Test/Common.hs +9/−13
- test/suite/TestSuite.hs +2/−2
cabal.project view
@@ -1,1 +1,8 @@ packages: .++tests: True++test-show-details: direct++allow-newer:+ , *:base
cbits/common.c view
@@ -3,7 +3,7 @@ #ifdef WIN32 #include <windows.h> #else-#include <signal.h>+#include <stdlib.h> #include <unistd.h> #endif @@ -19,11 +19,7 @@ #endif if (*check) { printf("timeout expired, dying!!\n");-#ifdef WIN32- abort();-#else- raise(SIGKILL);-#endif+ exit(1); } }
cbits/defs.h view
@@ -30,6 +30,6 @@ void suicide(volatile int* check, int i); void CHECK(int actual, int expected, char* what);-void check_impl_specific();+void check_impl_specific(int* num_tests, int* num_errors); #endif /* HASHTABLES_DEFS_H */
cbits/sse-42-check.c view
@@ -29,7 +29,7 @@ #undef F } -void check_impl_specific() {+void check_impl_specific(int* num_tests, int* num_errors) { check_fill(0); check_fill((small_hash_t) (-1)); check_fill((small_hash_t) (-5));
changelog.md view
@@ -1,8 +1,41 @@ # Hashtables changelog +## 1.4.2++ - Fix C compile errors in cbits.+ - Bump lower bound for QuickCheck.++## 1.4.1++ - Fix broken compile when compiling with `-fportable` flag.+ - Make it build with GHC WASM (Bodigrim).++## 1.4.0++ - Replace deprecated Mutable Array function, which modifies the signature of the `length`+ function and hence the API.+ - Support more recent compilers.++## 1.3.1++ - Fix Noncanonical mappend definition warning.+ - Support more recent compilers.+++## 1.3++ - Support Hashable 1.4. This new version of Hashable drops the Eq constraint, so the Eq constraint+ needs to be dropped in the SPECIALIZE statements in Hashtables.++## 1.2.4.2++ - Cabal file: add missing other-modules+ - Silence import warnings. Know that we require ghc >= 7.8.+ - Fix build with GHC 9.2+ ## 1.2.4.1 -Update some test suite dep upper bounds.+ - Update some test suite dep upper bounds. ## 1.2.4.0
hashtables.cabal view
@@ -1,6 +1,6 @@ Cabal-Version: 2.2 Name: hashtables-Version: 1.2.4.2+Version: 1.4.2 Synopsis: Mutable hash tables in the ST monad Homepage: http://github.com/gregorycollins/hashtables License: BSD-3-Clause@@ -13,16 +13,19 @@ tested-with:- GHC == 7.8.4- GHC == 7.10.3- GHC == 8.0.2- GHC == 8.2.2- GHC == 8.4.4- GHC == 8.6.5- GHC == 8.8.4+ GHC == 9.12.1+ GHC == 9.10.1+ GHC == 9.8.2+ GHC == 9.6.6+ GHC == 9.4.8+ GHC == 9.2.8+ GHC == 9.0.2 GHC == 8.10.7- GHC == 9.0.1- GHC == 9.2.1+ GHC == 8.8.4+ GHC == 8.6.5+ GHC == 8.4.4+ GHC == 8.2.2+ GHC == 8.0.2 Description: This package provides a couple of different implementations of mutable hash@@ -192,9 +195,9 @@ Data.HashTable.Internal.Linear.Bucket Build-depends: base >= 4.7 && <5,- hashable >= 1.1 && <1.2 || >= 1.2.1 && <1.4,+ hashable >= 1.4 && < 1.6, primitive,- vector >= 0.7 && <0.13+ vector >= 0.7 && <0.14 if flag(portable) cpp-options: -DNO_C_SEARCH -DPORTABLE@@ -270,14 +273,13 @@ cpp-options: -DBOUNDS_CHECKING Build-depends: base >= 4 && <5,- hashable >= 1.1 && <1.2 || >= 1.2.1 && <1.4,+ hashable >= 1.4 && < 1.6, mwc-random >= 0.8 && <0.16, primitive,- QuickCheck >= 2.3.0.2,- HUnit >= 1.2 && <2,- test-framework >= 0.3.1 && <0.9,- test-framework-quickcheck2 >= 0.2.6 && <0.4,- test-framework-hunit >= 0.2.6 && <3,+ QuickCheck >= 2.9,+ tasty >= 1.4 && <= 1.6,+ tasty-quickcheck >= 0.10 && <0.12,+ tasty-hunit >= 0.10 && <0.11, vector >= 0.7 cpp-options: -DTESTSUITE@@ -287,11 +289,12 @@ if impl(ghc >= 6.12.0) ghc-options: -Wall -fwarn-tabs -funbox-strict-fields- -fno-warn-unused-do-bind -threaded+ -fno-warn-unused-do-bind else- ghc-options: -Wall -fwarn-tabs -funbox-strict-fields -threaded-+ ghc-options: -Wall -fwarn-tabs -funbox-strict-fields + if !arch(wasm32)+ ghc-options: -threaded source-repository head type: git
src/Data/HashTable/IO.hs view
@@ -123,11 +123,11 @@ IOHashTable h k v -> k -> v -> IO () insert h k v = stToIO $ C.insert h k v {-# INLINE insert #-}-{-# SPECIALIZE INLINE insert :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE insert :: Hashable k => BasicHashTable k v -> k -> v -> IO () #-}-{-# SPECIALIZE INLINE insert :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE insert :: Hashable k => LinearHashTable k v -> k -> v -> IO () #-}-{-# SPECIALIZE INLINE insert :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE insert :: Hashable k => CuckooHashTable k v -> k -> v -> IO () #-} @@ -137,11 +137,11 @@ IOHashTable h k v -> k -> IO () delete h k = stToIO $ C.delete h k {-# INLINE delete #-}-{-# SPECIALIZE INLINE delete :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE delete :: Hashable k => BasicHashTable k v -> k -> IO () #-}-{-# SPECIALIZE INLINE delete :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE delete :: Hashable k => LinearHashTable k v -> k -> IO () #-}-{-# SPECIALIZE INLINE delete :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE delete :: Hashable k => CuckooHashTable k v -> k -> IO () #-} @@ -151,11 +151,11 @@ IOHashTable h k v -> k -> IO (Maybe v) lookup h k = stToIO $ C.lookup h k {-# INLINE lookup #-}-{-# SPECIALIZE INLINE lookup :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE lookup :: Hashable k => BasicHashTable k v -> k -> IO (Maybe v) #-}-{-# SPECIALIZE INLINE lookup :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE lookup :: Hashable k => LinearHashTable k v -> k -> IO (Maybe v) #-}-{-# SPECIALIZE INLINE lookup :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE lookup :: Hashable k => CuckooHashTable k v -> k -> IO (Maybe v) #-} ------------------------------------------------------------------------------@@ -164,11 +164,11 @@ IOHashTable h k v -> k -> IO (Maybe Word) lookupIndex h k = stToIO $ C.lookupIndex h k {-# INLINE lookupIndex #-}-{-# SPECIALIZE INLINE lookupIndex :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE lookupIndex :: Hashable k => BasicHashTable k v -> k -> IO (Maybe Word) #-}-{-# SPECIALIZE INLINE lookupIndex :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE lookupIndex :: Hashable k => LinearHashTable k v -> k -> IO (Maybe Word) #-}-{-# SPECIALIZE INLINE lookupIndex :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE lookupIndex :: Hashable k => CuckooHashTable k v -> k -> IO (Maybe Word) #-} ------------------------------------------------------------------------------@@ -177,11 +177,11 @@ IOHashTable h k v -> Word -> IO (Maybe (Word,k,v)) nextByIndex h k = stToIO $ C.nextByIndex h k {-# INLINE nextByIndex #-}-{-# SPECIALIZE INLINE nextByIndex :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE nextByIndex :: Hashable k => BasicHashTable k v -> Word -> IO (Maybe (Word,k,v)) #-}-{-# SPECIALIZE INLINE nextByIndex :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE nextByIndex :: Hashable k => LinearHashTable k v -> Word -> IO (Maybe (Word,k,v)) #-}-{-# SPECIALIZE INLINE nextByIndex :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE nextByIndex :: Hashable k => CuckooHashTable k v -> Word -> IO (Maybe (Word,k,v)) #-} ------------------------------------------------------------------------------@@ -190,11 +190,11 @@ IOHashTable h k v -> k -> (Maybe v -> IO (Maybe v, a)) -> IO a mutateIO h k f = stToIO $ C.mutateST h k (ioToST . f) {-# INLINE mutateIO #-}-{-# SPECIALIZE INLINE mutateIO :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE mutateIO :: Hashable k => BasicHashTable k v -> k -> (Maybe v -> IO (Maybe v, a)) -> IO a #-}-{-# SPECIALIZE INLINE mutateIO :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE mutateIO :: Hashable k => LinearHashTable k v -> k -> (Maybe v -> IO (Maybe v, a)) -> IO a #-}-{-# SPECIALIZE INLINE mutateIO :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE mutateIO :: Hashable k => CuckooHashTable k v -> k -> (Maybe v -> IO (Maybe v, a)) -> IO a #-} ------------------------------------------------------------------------------@@ -203,11 +203,11 @@ IOHashTable h k v -> k -> (Maybe v -> (Maybe v, a)) -> IO a mutate h k f = stToIO $ C.mutate h k f {-# INLINE mutate #-}-{-# SPECIALIZE INLINE mutate :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE mutate :: Hashable k => BasicHashTable k v -> k -> (Maybe v -> (Maybe v, a)) -> IO a #-}-{-# SPECIALIZE INLINE mutate :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE mutate :: Hashable k => LinearHashTable k v -> k -> (Maybe v -> (Maybe v, a)) -> IO a #-}-{-# SPECIALIZE INLINE mutate :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE mutate :: Hashable k => CuckooHashTable k v -> k -> (Maybe v -> (Maybe v, a)) -> IO a #-} @@ -218,11 +218,11 @@ [(k,v)] -> IO (IOHashTable h k v) fromList = stToIO . C.fromList {-# INLINE fromList #-}-{-# SPECIALIZE INLINE fromList :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE fromList :: Hashable k => [(k,v)] -> IO (BasicHashTable k v) #-}-{-# SPECIALIZE INLINE fromList :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE fromList :: Hashable k => [(k,v)] -> IO (LinearHashTable k v) #-}-{-# SPECIALIZE INLINE fromList :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE fromList :: Hashable k => [(k,v)] -> IO (CuckooHashTable k v) #-} @@ -233,11 +233,11 @@ Int -> [(k,v)] -> IO (IOHashTable h k v) fromListWithSizeHint n = stToIO . C.fromListWithSizeHint n {-# INLINE fromListWithSizeHint #-}-{-# SPECIALIZE INLINE fromListWithSizeHint :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE fromListWithSizeHint :: Hashable k => Int -> [(k,v)] -> IO (BasicHashTable k v) #-}-{-# SPECIALIZE INLINE fromListWithSizeHint :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE fromListWithSizeHint :: Hashable k => Int -> [(k,v)] -> IO (LinearHashTable k v) #-}-{-# SPECIALIZE INLINE fromListWithSizeHint :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE fromListWithSizeHint :: Hashable k => Int -> [(k,v)] -> IO (CuckooHashTable k v) #-} @@ -247,11 +247,11 @@ IOHashTable h k v -> IO [(k,v)] toList = stToIO . C.toList {-# INLINE toList #-}-{-# SPECIALIZE INLINE toList :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE toList :: Hashable k => BasicHashTable k v -> IO [(k,v)] #-}-{-# SPECIALIZE INLINE toList :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE toList :: Hashable k => LinearHashTable k v -> IO [(k,v)] #-}-{-# SPECIALIZE INLINE toList :: (Eq k, Hashable k) =>+{-# SPECIALIZE INLINE toList :: Hashable k => CuckooHashTable k v -> IO [(k,v)] #-}
src/Data/HashTable/Internal/CacheLine.hs view
@@ -251,9 +251,12 @@ 27# !idx = I# (word2Int# idxW#) !(I8# pos8#) = U.unsafeIndex deBruijnBitPositions idx+#if __GLASGOW_HASKELL__ >= 900+ !posw# = int2Word# (int8ToInt# pos8#)+#else !posw# = int2Word# pos8#- #endif+#endif #ifdef NO_C_SEARCH@@ -745,7 +748,7 @@ -- \"-1\" if not found cacheLineSearch !vec !start !value = do #ifdef NO_C_SEARCH- let !vlen = M.length vec+ vlen <- M.length vec let !st1 = vlen - start let !nvlen = numElemsInCacheLine - st1 let adv = (start + cacheLineIntMask) .&. complement cacheLineIntMask@@ -776,7 +779,7 @@ -- \"-1\" if not found cacheLineSearch2 !vec !start !value !value2 = do #ifdef NO_C_SEARCH- let !vlen = M.length vec+ !vlen <- M.length vec let !st1 = vlen - start let !nvlen = numElemsInCacheLine - st1 let adv = (start + cacheLineIntMask) .&. complement cacheLineIntMask@@ -807,7 +810,7 @@ -- \"-1\" if not found cacheLineSearch3 !vec !start !value !value2 !value3 = do #ifdef NO_C_SEARCH- let !vlen = M.length vec+ !vlen <- M.length vec let !st1 = vlen - start let !nvlen = numElemsInCacheLine - st1 let adv = (start + cacheLineIntMask) .&. complement cacheLineIntMask
src/Data/HashTable/Internal/IntArray.hs view
@@ -106,8 +106,8 @@ -------------------------------------------------------------------------------length :: IntArray s -> Int-length (IA a) = A.sizeofMutableByteArray a `div` wordSizeInBytes+length :: IntArray s -> ST s Int+length (IA a) = (`div` wordSizeInBytes) <$> A.getSizeofMutableByteArray a ------------------------------------------------------------------------------
src/Data/HashTable/ST/Basic.hs view
@@ -519,15 +519,19 @@ #if MIN_VERSION_base(4,9,0) instance Semigroup Slot where- (<>) = mappend+ (<>) = slotMappend #endif instance Monoid Slot where- mempty = Slot maxBound- (Slot x1) `mappend` (Slot x2) =- let !m = mask x1 maxBound- in Slot $! (complement m .&. x1) .|. (m .&. x2)+ mempty = Slot maxBound+#if ! MIN_VERSION_base(4,11,0)+ mappend = slotMappend+#endif +slotMappend :: Slot -> Slot -> Slot+slotMappend (Slot x1) (Slot x2) =+ let !m = mask x1 maxBound+ in Slot $! (complement m .&. x1) .|. (m .&. x2) ------------------------------------------------------------------------------ -- findSafeSlots return type@@ -841,3 +845,4 @@ let !i' = fromIntegral i return (Just (i', k, v)) {-# INLINE nextByIndex #-}+
test/hashtables-test.cabal view
@@ -5,7 +5,7 @@ Copyright: (c) 2011-2013, Google, Inc. Category: Data Build-type: Simple-Cabal-version: >= 1.8+Cabal-version: >= 1.10 ------------------------------------------------------------------------------ Flag debug@@ -65,7 +65,7 @@ Build-depends: base >= 4 && <5, hashable >= 1.1 && <1.2 || >= 1.2.1 && <1.3, mwc-random >= 0.8 && <0.14,- QuickCheck >= 2.3.0.2 && <3,+ QuickCheck >= 2.9 && <3, HUnit >= 1.2 && <2, test-framework >= 0.3.1 && <0.9, test-framework-quickcheck2 >= 0.2.6 && <0.4,
test/suite/Data/HashTable/Test/Common.hs view
@@ -15,7 +15,7 @@ import Control.Applicative (pure, (<$>)) #endif import Control.Applicative ((<|>))-import Control.Monad (foldM_, liftM, when)+import Control.Monad (foldM_, when) import qualified Control.Monad as Monad import Data.IORef import Data.List hiding (delete, insert,@@ -26,13 +26,9 @@ import Prelude hiding (lookup, mapM_) import System.Random.MWC import System.Timeout-import Test.Framework-import Test.Framework.Providers.HUnit-import Test.Framework.Providers.QuickCheck2-import Test.HUnit (assertEqual,- assertFailure)-import Test.QuickCheck (arbitrary, choose,- sample')+import Test.Tasty+import Test.Tasty.HUnit hiding (assert)+import Test.Tasty.QuickCheck import Test.QuickCheck.Monadic (PropertyM, assert, forAllM, monadicIO, pre, run)@@ -49,7 +45,7 @@ ------------------------------------------------------------------------------ type FixedTableType h = forall k v . IOHashTable h k v-type HashTest = forall h . C.HashTable h => String -> FixedTableType h -> Test+type HashTest = forall h . C.HashTable h => String -> FixedTableType h -> TestTree data SomeTest = SomeTest HashTest @@ -95,7 +91,7 @@ -------------------------------------------------------------------------------tests :: C.HashTable h => String -> FixedTableType h -> Test+tests :: C.HashTable h => String -> FixedTableType h -> TestTree tests prefix dummyArg = testGroup prefix $ map f ts where f (SomeTest ht) = ht prefix dummyArg@@ -242,7 +238,7 @@ prop n = do announceQ "growTable" n ht <- run $ go n- i <- liftM head $ run $ sample' $ choose (0,n-1)+ i <- run $ generate $ choose (0,n-1) v <- run $ lookup ht i assertEq ("lookup " ++ show i) (Just i) v@@ -290,7 +286,7 @@ ht <- run $ go n - i <- liftM head $ run $ sample' $ choose (4,n-1)+ i <- run $ generate $ choose (4,n-1) v <- run $ lookup ht i assertEq ("lookup " ++ show i) (Just i) v @@ -351,7 +347,7 @@ timeout_ :: Int -> IO a -> IO ()-#ifdef PORTABLE+#if defined(PORTABLE) || defined(wasm32_HOST_ARCH) timeout_ t m = timeout t m >>= maybe (assertFailure "timeout") (const $ return ()) #else
test/suite/TestSuite.hs view
@@ -2,7 +2,7 @@ module Main where -import Test.Framework (defaultMain)+import Test.Tasty (defaultMain, testGroup) ------------------------------------------------------------------------------ import qualified Data.HashTable.Test.Common as Common import qualified Data.HashTable.ST.Basic as B@@ -13,7 +13,7 @@ ------------------------------------------------------------------------------ main :: IO ()-main = defaultMain tests+main = defaultMain $ testGroup "All" tests where dummyBasicTable = Common.dummyTable :: forall k v . IO.IOHashTable (B.HashTable) k v