hashtables 1.0.1.8 → 1.1.0.0
raw patch · 8 files changed
+71/−88 lines, 8 filesdep ~basedep ~primitivePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base, primitive
API changes (from Hackage documentation)
+ Data.HashTable.Class: fromListWithSizeHint :: (HashTable h, Eq k, Hashable k) => Int -> [(k, v)] -> ST s (h s k v)
+ Data.HashTable.IO: fromListWithSizeHint :: (HashTable h, Eq k, Hashable k) => Int -> [(k, v)] -> IO (IOHashTable h k v)
Files
- benchmark/hashtable-benchmark.cabal +3/−3
- benchmark/src/Main.hs +12/−13
- hashtables.cabal +4/−4
- src/Data/HashTable/Class.hs +23/−2
- src/Data/HashTable/IO.hs +18/−55
- src/Data/HashTable/Internal/CacheLine.hs +2/−1
- test/hashtables-test.cabal +2/−2
- test/suite/Data/HashTable/Test/Common.hs +7/−8
benchmark/hashtable-benchmark.cabal view
@@ -17,9 +17,9 @@ main-is: Main.hs hs-source-dirs: src ../src - build-depends: base == 4.*,+ build-depends: base >= 4.4 && <5, base16-bytestring == 0.1.*,- bytestring >= 0.9 && <0.11,+ bytestring >= 0.10 && <0.11, containers >= 0.4 && <0.6, criterion >= 0.5 && <0.7, csv == 0.1.*,@@ -33,7 +33,7 @@ statistics >= 0.8 && <0.11, threads >= 0.4 && <0.6, unordered-containers >= 0.2 && <0.3,- vector >= 0.7 && <0.10,+ vector >= 0.7 && <0.11, vector-algorithms >= 0.5 && <0.6 if flag(chart)
benchmark/src/Main.hs view
@@ -4,22 +4,22 @@ module Main (main) where -import Data.Bits-import qualified Data.ByteString as B-import Data.ByteString (ByteString)-import qualified Data.ByteString.Base16 as B16-import Data.Hashable-import Data.IORef import Control.DeepSeq import Control.Monad import Control.Monad.ST import Control.Monad.Trans-import qualified Data.HashMap.Strict as UC-import qualified Data.HashTable as H-import qualified Data.Map as Map-import qualified Data.HashTable.IO as IOH import Data.Benchmarks.UnorderedCollections.Distributions import Data.Benchmarks.UnorderedCollections.Types+import Data.Bits+import Data.ByteString (ByteString)+import qualified Data.ByteString as B+import qualified Data.ByteString.Base16 as B16+import Data.Hashable+import qualified Data.HashMap.Strict as UC+import qualified Data.HashTable as H+import qualified Data.HashTable.IO as IOH+import Data.IORef+import qualified Data.Map as Map import System.Environment import System.FilePath import System.Random.MWC@@ -118,9 +118,6 @@ return $! B16.encode s -instance NFData ByteString where- rnf s = rnf $! B.unpack s- ------------------------------------------------------------------------------ mkConsecutiveIntegers :: IORef Int -> GenIO -> IO Int mkConsecutiveIntegers ref _ = do@@ -179,6 +176,8 @@ ] +------------------------------------------------------------------------------+testSizes :: [Int] testSizes = [ 250 , 500 , 1000
hashtables.cabal view
@@ -1,5 +1,5 @@ Name: hashtables-Version: 1.0.1.8+Version: 1.1.0.0 Synopsis: Mutable hash tables in the ST monad Homepage: http://github.com/gregorycollins/hashtables License: BSD3@@ -169,10 +169,10 @@ Data.HashTable.Internal.Utils, Data.HashTable.Internal.Linear.Bucket - Build-depends: base >= 4 && <5,+ Build-depends: base >= 4.4 && <5, hashable >= 1.1 && <2,- primitive >= 0.4 && <0.6,- vector >= 0.7 && <0.11+ primitive,+ vector >= 0.7 && < 0.11 if flag(portable) cpp-options: -DNO_C_SEARCH -DPORTABLE
src/Data/HashTable/Class.hs view
@@ -41,13 +41,14 @@ module Data.HashTable.Class ( HashTable(..) , fromList+ , fromListWithSizeHint , toList ) where import Control.Monad.ST import Data.Hashable-import Prelude hiding (mapM_)+import Prelude hiding (mapM_) -- | A typeclass for hash tables in the 'ST' monad. The operations on these -- hash tables are typically both key- and value-strict.@@ -90,7 +91,7 @@ -- | Create a hash table from a list of key-value pairs. /O(n)/. fromList :: (HashTable h, Eq k, Hashable k) => [(k,v)] -> ST s (h s k v) fromList l = do- ht <- newSized (length l)+ ht <- new go ht l where@@ -101,6 +102,26 @@ insert ht k v go' xs {-# INLINE fromList #-}+++------------------------------------------------------------------------------+-- | Create a hash table from a list of key-value pairs, with a size hint. /O(n)/.+fromListWithSizeHint :: (HashTable h, Eq k, Hashable k) =>+ Int+ -> [(k,v)]+ -> ST s (h s k v)+fromListWithSizeHint n l = do+ ht <- newSized n+ go ht l++ where+ go ht = go'+ where+ go' [] = return ht+ go' ((!k,!v):xs) = do+ insert ht k v+ go' xs+{-# INLINE fromListWithSizeHint #-} ------------------------------------------------------------------------------
src/Data/HashTable/IO.hs view
@@ -35,7 +35,7 @@ -- below, you can plug in any of @'BasicHashTable' k v@, @'CuckooHashTable' k -- v@, or @'LinearHashTable' k v@. ---module Data.HashTable.IO +module Data.HashTable.IO ( BasicHashTable , CuckooHashTable , LinearHashTable@@ -46,6 +46,7 @@ , delete , lookup , fromList+ , fromListWithSizeHint , toList , mapM_ , foldM@@ -54,15 +55,16 @@ -------------------------------------------------------------------------------import Control.Monad.Primitive (PrimState)-import Control.Monad.ST-import Data.Hashable (Hashable)-import qualified Data.HashTable.Class as C-import Prelude hiding (lookup, mapM_)+import Control.Monad.Primitive (PrimState)+import Control.Monad.ST (stToIO)+import Control.Monad.ST.Unsafe (unsafeIOToST)+import Data.Hashable (Hashable)+import qualified Data.HashTable.Class as C+import Prelude hiding (lookup, mapM_) ------------------------------------------------------------------------------ import qualified Data.HashTable.ST.Basic as B-import qualified Data.HashTable.ST.Cuckoo as Cu+import qualified Data.HashTable.ST.Cuckoo as Cu import qualified Data.HashTable.ST.Linear as L @@ -90,9 +92,6 @@ new :: C.HashTable h => IO (IOHashTable h k v) new = stToIO C.new {-# INLINE new #-}-{-# SPECIALIZE INLINE new :: IO (BasicHashTable k v) #-}-{-# SPECIALIZE INLINE new :: IO (LinearHashTable k v) #-}-{-# SPECIALIZE INLINE new :: IO (CuckooHashTable k v) #-} ------------------------------------------------------------------------------ -- | See the documentation for this function in@@ -100,9 +99,6 @@ newSized :: C.HashTable h => Int -> IO (IOHashTable h k v) newSized = stToIO . C.newSized {-# INLINE newSized #-}-{-# SPECIALIZE INLINE newSized :: Int -> IO (BasicHashTable k v) #-}-{-# SPECIALIZE INLINE newSized :: Int -> IO (LinearHashTable k v) #-}-{-# SPECIALIZE INLINE newSized :: Int -> IO (CuckooHashTable k v) #-} ------------------------------------------------------------------------------@@ -111,12 +107,6 @@ 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) =>- BasicHashTable k v -> k -> v -> IO () #-}-{-# SPECIALIZE INLINE insert :: (Eq k, Hashable k) =>- LinearHashTable k v -> k -> v -> IO () #-}-{-# SPECIALIZE INLINE insert :: (Eq k, Hashable k) =>- CuckooHashTable k v -> k -> v -> IO () #-} ------------------------------------------------------------------------------@@ -125,12 +115,6 @@ IOHashTable h k v -> k -> IO () delete h k = stToIO $ C.delete h k {-# INLINE delete #-}-{-# SPECIALIZE INLINE delete :: (Eq k, Hashable k) =>- BasicHashTable k v -> k -> IO () #-}-{-# SPECIALIZE INLINE delete :: (Eq k, Hashable k) =>- LinearHashTable k v -> k -> IO () #-}-{-# SPECIALIZE INLINE delete :: (Eq k, Hashable k) =>- CuckooHashTable k v -> k -> IO () #-} ------------------------------------------------------------------------------@@ -139,12 +123,6 @@ 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) =>- BasicHashTable k v -> k -> IO (Maybe v) #-}-{-# SPECIALIZE INLINE lookup :: (Eq k, Hashable k) =>- LinearHashTable k v -> k -> IO (Maybe v) #-}-{-# SPECIALIZE INLINE lookup :: (Eq k, Hashable k) =>- CuckooHashTable k v -> k -> IO (Maybe v) #-} ------------------------------------------------------------------------------@@ -154,26 +132,23 @@ [(k,v)] -> IO (IOHashTable h k v) fromList = stToIO . C.fromList {-# INLINE fromList #-}-{-# SPECIALIZE INLINE fromList :: (Eq k, Hashable k) =>- [(k,v)] -> IO (BasicHashTable k v) #-}-{-# SPECIALIZE INLINE fromList :: (Eq k, Hashable k) =>- [(k,v)] -> IO (LinearHashTable k v) #-}-{-# SPECIALIZE INLINE fromList :: (Eq k, Hashable k) =>- [(k,v)] -> IO (CuckooHashTable k v) #-} ------------------------------------------------------------------------------+-- | See the documentation for this function in+-- "Data.HashTable.Class#v:fromListWithSizeHint".+fromListWithSizeHint :: (C.HashTable h, Eq k, Hashable k) =>+ Int -> [(k,v)] -> IO (IOHashTable h k v)+fromListWithSizeHint n = stToIO . C.fromListWithSizeHint n+{-# INLINE fromListWithSizeHint #-}+++------------------------------------------------------------------------------ -- | See the documentation for this function in "Data.HashTable.Class#v:toList". toList :: (C.HashTable h, Eq k, Hashable k) => IOHashTable h k v -> IO [(k,v)] toList = stToIO . C.toList {-# INLINE toList #-}-{-# SPECIALIZE INLINE toList :: (Eq k, Hashable k) =>- BasicHashTable k v -> IO [(k,v)] #-}-{-# SPECIALIZE INLINE toList :: (Eq k, Hashable k) =>- LinearHashTable k v -> IO [(k,v)] #-}-{-# SPECIALIZE INLINE toList :: (Eq k, Hashable k) =>- CuckooHashTable k v -> IO [(k,v)] #-} ------------------------------------------------------------------------------@@ -186,12 +161,6 @@ where f' !i !t = unsafeIOToST $ f i t {-# INLINE foldM #-}-{-# SPECIALIZE INLINE foldM :: (a -> (k,v) -> IO a) -> a- -> BasicHashTable k v -> IO a #-}-{-# SPECIALIZE INLINE foldM :: (a -> (k,v) -> IO a) -> a- -> LinearHashTable k v -> IO a #-}-{-# SPECIALIZE INLINE foldM :: (a -> (k,v) -> IO a) -> a- -> CuckooHashTable k v -> IO a #-} ------------------------------------------------------------------------------@@ -201,12 +170,6 @@ where f' = unsafeIOToST . f {-# INLINE mapM_ #-}-{-# SPECIALIZE INLINE mapM_ :: ((k,v) -> IO a) -> BasicHashTable k v- -> IO () #-}-{-# SPECIALIZE INLINE mapM_ :: ((k,v) -> IO a) -> LinearHashTable k v- -> IO () #-}-{-# SPECIALIZE INLINE mapM_ :: ((k,v) -> IO a) -> CuckooHashTable k v- -> IO () #-} ------------------------------------------------------------------------------
src/Data/HashTable/Internal/CacheLine.hs view
@@ -19,7 +19,8 @@ , maskw# ) where -import Control.Monad.ST+import Control.Monad.ST (ST)+import Control.Monad.ST.Unsafe import Data.HashTable.Internal.IntArray (IntArray) import qualified Data.HashTable.Internal.IntArray as M
test/hashtables-test.cabal view
@@ -69,8 +69,8 @@ primitive, QuickCheck >= 2.3.0.2, HUnit >= 1.2 && <2,- test-framework >= 0.3.1 && <0.7,- test-framework-quickcheck2 >= 0.2.6 && <0.3,+ test-framework >= 0.3.1 && <0.9,+ test-framework-quickcheck2 >= 0.2.6 && <0.4, test-framework-hunit >= 0.2.6 && <3, vector >= 0.7
test/suite/Data/HashTable/Test/Common.hs view
@@ -12,11 +12,10 @@ ------------------------------------------------------------------------------ import Control.Monad (foldM_, liftM, when)-import Control.Monad.ST (unsafeIOToST)+import Control.Monad.ST.Unsafe (unsafeIOToST) import Data.IORef-import Data.List hiding ( insert- , delete- , lookup )+import Data.List hiding (delete, insert,+ lookup) import Data.Vector (Vector) import qualified Data.Vector as V import qualified Data.Vector.Mutable as MV@@ -26,7 +25,7 @@ import Test.Framework import Test.Framework.Providers.HUnit import Test.Framework.Providers.QuickCheck2-import Test.HUnit (assertFailure)+import Test.HUnit (assertFailure) import Test.QuickCheck import Test.QuickCheck.Monadic ------------------------------------------------------------------------------@@ -35,8 +34,8 @@ #ifndef PORTABLE import Control.Concurrent-import Foreign (malloc, free, poke, Ptr)-import Foreign.C.Types (CInt)+import Foreign (Ptr, free, malloc, poke)+import Foreign.C.Types (CInt (..)) #endif ------------------------------------------------------------------------------@@ -236,7 +235,7 @@ delete ht 2 delete ht 3 insert ht 2 2- + _ -> if i `mod` 2 == 0 then do delete ht i