hashmap 1.0.0.3 → 1.1.0
raw patch · 4 files changed
+12/−131 lines, 4 filesdep +hashabledep −bytestringPVP ok
version bump matches the API change (PVP)
Dependencies added: hashable
Dependencies removed: bytestring
API changes (from Hackage documentation)
- Data.HashMap: instance (Ord k) => Monoid (HashMap k a)
- Data.HashSet: instance (Eq a) => Eq (HashSet a)
- Data.HashSet: instance (Eq a) => Eq (Some a)
- Data.HashSet: instance (Ord a) => Monoid (HashSet a)
- Data.HashSet: instance (Ord a) => Ord (HashSet a)
- Data.HashSet: instance (Ord a) => Ord (Some a)
- Data.HashSet: instance (Show a) => Show (HashSet a)
- Data.Hashable: class Hashable a
- Data.Hashable: combine :: Int -> Int -> Int
- Data.Hashable: hash :: (Hashable a) => a -> Int
- Data.Hashable: instance (Hashable a) => Hashable (Maybe a)
- Data.Hashable: instance (Hashable a) => Hashable [a]
- Data.Hashable: instance (Hashable a1, Hashable a2) => Hashable (a1, a2)
- Data.Hashable: instance (Hashable a1, Hashable a2, Hashable a3) => Hashable (a1, a2, a3)
- Data.Hashable: instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4) => Hashable (a1, a2, a3, a4)
- Data.Hashable: instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5) => Hashable (a1, a2, a3, a4, a5)
- Data.Hashable: instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5, Hashable a6) => Hashable (a1, a2, a3, a4, a5, a6)
- Data.Hashable: instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5, Hashable a6, Hashable a7) => Hashable (a1, a2, a3, a4, a5, a6, a7)
- Data.Hashable: instance Hashable ()
- Data.Hashable: instance Hashable Bool
- Data.Hashable: instance Hashable ByteString
- Data.Hashable: instance Hashable Char
- Data.Hashable: instance Hashable Int
- Data.Hashable: instance Hashable Int16
- Data.Hashable: instance Hashable Int32
- Data.Hashable: instance Hashable Int64
- Data.Hashable: instance Hashable Int8
- Data.Hashable: instance Hashable Word
- Data.Hashable: instance Hashable Word16
- Data.Hashable: instance Hashable Word32
- Data.Hashable: instance Hashable Word64
- Data.Hashable: instance Hashable Word8
+ Data.HashMap: instance Ord k => Monoid (HashMap k a)
+ Data.HashSet: instance Eq a => Eq (HashSet a)
+ Data.HashSet: instance Eq a => Eq (Some a)
+ Data.HashSet: instance Ord a => Monoid (HashSet a)
+ Data.HashSet: instance Ord a => Ord (HashSet a)
+ Data.HashSet: instance Ord a => Ord (Some a)
+ Data.HashSet: instance Show a => Show (HashSet a)
- Data.HashMap: (\\) :: (Ord k) => HashMap k a -> HashMap k b -> HashMap k a
+ Data.HashMap: (\\) :: Ord k => HashMap k a -> HashMap k b -> HashMap k a
- Data.HashMap: difference :: (Ord k) => HashMap k a -> HashMap k b -> HashMap k a
+ Data.HashMap: difference :: Ord k => HashMap k a -> HashMap k b -> HashMap k a
- Data.HashMap: differenceWith :: (Ord k) => (a -> b -> Maybe a) -> HashMap k a -> HashMap k b -> HashMap k a
+ Data.HashMap: differenceWith :: Ord k => (a -> b -> Maybe a) -> HashMap k a -> HashMap k b -> HashMap k a
- Data.HashMap: differenceWithKey :: (Ord k) => (k -> a -> b -> Maybe a) -> HashMap k a -> HashMap k b -> HashMap k a
+ Data.HashMap: differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> HashMap k a -> HashMap k b -> HashMap k a
- Data.HashMap: filter :: (Ord k) => (a -> Bool) -> HashMap k a -> HashMap k a
+ Data.HashMap: filter :: Ord k => (a -> Bool) -> HashMap k a -> HashMap k a
- Data.HashMap: filterWithKey :: (Ord k) => (k -> a -> Bool) -> HashMap k a -> HashMap k a
+ Data.HashMap: filterWithKey :: Ord k => (k -> a -> Bool) -> HashMap k a -> HashMap k a
- Data.HashMap: intersection :: (Ord k) => HashMap k a -> HashMap k b -> HashMap k a
+ Data.HashMap: intersection :: Ord k => HashMap k a -> HashMap k b -> HashMap k a
- Data.HashMap: intersectionWith :: (Ord k) => (a -> b -> c) -> HashMap k a -> HashMap k b -> HashMap k c
+ Data.HashMap: intersectionWith :: Ord k => (a -> b -> c) -> HashMap k a -> HashMap k b -> HashMap k c
- Data.HashMap: intersectionWithKey :: (Ord k) => (k -> a -> b -> c) -> HashMap k a -> HashMap k b -> HashMap k c
+ Data.HashMap: intersectionWithKey :: Ord k => (k -> a -> b -> c) -> HashMap k a -> HashMap k b -> HashMap k c
- Data.HashMap: isProperSubmapOfBy :: (Ord k) => (a -> b -> Bool) -> HashMap k a -> HashMap k b -> Bool
+ Data.HashMap: isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> HashMap k a -> HashMap k b -> Bool
- Data.HashMap: isSubmapOfBy :: (Ord k) => (a -> b -> Bool) -> HashMap k a -> HashMap k b -> Bool
+ Data.HashMap: isSubmapOfBy :: Ord k => (a -> b -> Bool) -> HashMap k a -> HashMap k b -> Bool
- Data.HashMap: keysSet :: (Ord k) => HashMap k a -> Set k
+ Data.HashMap: keysSet :: Ord k => HashMap k a -> Set k
- Data.HashMap: mapEither :: (Ord k) => (a -> Either b c) -> HashMap k a -> (HashMap k b, HashMap k c)
+ Data.HashMap: mapEither :: Ord k => (a -> Either b c) -> HashMap k a -> (HashMap k b, HashMap k c)
- Data.HashMap: mapEitherWithKey :: (Ord k) => (k -> a -> Either b c) -> HashMap k a -> (HashMap k b, HashMap k c)
+ Data.HashMap: mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> HashMap k a -> (HashMap k b, HashMap k c)
- Data.HashMap: mapMaybe :: (Ord k) => (a -> Maybe b) -> HashMap k a -> HashMap k b
+ Data.HashMap: mapMaybe :: Ord k => (a -> Maybe b) -> HashMap k a -> HashMap k b
- Data.HashMap: mapMaybeWithKey :: (Ord k) => (k -> a -> Maybe b) -> HashMap k a -> HashMap k b
+ Data.HashMap: mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> HashMap k a -> HashMap k b
- Data.HashMap: partition :: (Ord k) => (a -> Bool) -> HashMap k a -> (HashMap k a, HashMap k a)
+ Data.HashMap: partition :: Ord k => (a -> Bool) -> HashMap k a -> (HashMap k a, HashMap k a)
- Data.HashMap: partitionWithKey :: (Ord k) => (k -> a -> Bool) -> HashMap k a -> (HashMap k a, HashMap k a)
+ Data.HashMap: partitionWithKey :: Ord k => (k -> a -> Bool) -> HashMap k a -> (HashMap k a, HashMap k a)
- Data.HashMap: singleton :: (Hashable k) => k -> a -> HashMap k a
+ Data.HashMap: singleton :: Hashable k => k -> a -> HashMap k a
- Data.HashMap: union :: (Ord k) => HashMap k a -> HashMap k a -> HashMap k a
+ Data.HashMap: union :: Ord k => HashMap k a -> HashMap k a -> HashMap k a
- Data.HashMap: unionWith :: (Ord k) => (a -> a -> a) -> HashMap k a -> HashMap k a -> HashMap k a
+ Data.HashMap: unionWith :: Ord k => (a -> a -> a) -> HashMap k a -> HashMap k a -> HashMap k a
- Data.HashMap: unionWithKey :: (Ord k) => (k -> a -> a -> a) -> HashMap k a -> HashMap k a -> HashMap k a
+ Data.HashMap: unionWithKey :: Ord k => (k -> a -> a -> a) -> HashMap k a -> HashMap k a -> HashMap k a
- Data.HashMap: unions :: (Ord k) => [HashMap k a] -> HashMap k a
+ Data.HashMap: unions :: Ord k => [HashMap k a] -> HashMap k a
- Data.HashMap: unionsWith :: (Ord k) => (a -> a -> a) -> [HashMap k a] -> HashMap k a
+ Data.HashMap: unionsWith :: Ord k => (a -> a -> a) -> [HashMap k a] -> HashMap k a
- Data.HashSet: (\\) :: (Ord a) => HashSet a -> HashSet a -> HashSet a
+ Data.HashSet: (\\) :: Ord a => HashSet a -> HashSet a -> HashSet a
- Data.HashSet: difference :: (Ord a) => HashSet a -> HashSet a -> HashSet a
+ Data.HashSet: difference :: Ord a => HashSet a -> HashSet a -> HashSet a
- Data.HashSet: filter :: (Ord a) => (a -> Bool) -> HashSet a -> HashSet a
+ Data.HashSet: filter :: Ord a => (a -> Bool) -> HashSet a -> HashSet a
- Data.HashSet: intersection :: (Ord a) => HashSet a -> HashSet a -> HashSet a
+ Data.HashSet: intersection :: Ord a => HashSet a -> HashSet a -> HashSet a
- Data.HashSet: isProperSubsetOf :: (Ord a) => HashSet a -> HashSet a -> Bool
+ Data.HashSet: isProperSubsetOf :: Ord a => HashSet a -> HashSet a -> Bool
- Data.HashSet: isSubsetOf :: (Ord a) => HashSet a -> HashSet a -> Bool
+ Data.HashSet: isSubsetOf :: Ord a => HashSet a -> HashSet a -> Bool
- Data.HashSet: partition :: (Ord a) => (a -> Bool) -> HashSet a -> (HashSet a, HashSet a)
+ Data.HashSet: partition :: Ord a => (a -> Bool) -> HashSet a -> (HashSet a, HashSet a)
- Data.HashSet: singleton :: (Hashable a) => a -> HashSet a
+ Data.HashSet: singleton :: Hashable a => a -> HashSet a
- Data.HashSet: union :: (Ord a) => HashSet a -> HashSet a -> HashSet a
+ Data.HashSet: union :: Ord a => HashSet a -> HashSet a -> HashSet a
- Data.HashSet: unions :: (Ord a) => [HashSet a] -> HashSet a
+ Data.HashSet: unions :: Ord a => [HashSet a] -> HashSet a
Files
- CHANGES +6/−0
- Data/Hashable.hs +0/−113
- hashmap.cabal +6/−9
- src/hashByteString.c +0/−9
CHANGES view
@@ -1,3 +1,9 @@+= Version 1.1.0, 2010-08-07 =+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^+* Separating Hashable class to its own package+and depending on it.++ = Version 1.0.0.3, 2010-08-07 = ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ * Improving the performance of HashSet and HashMap
− Data/Hashable.hs
@@ -1,113 +0,0 @@-{-# LANGUAGE ForeignFunctionInterface #-}---------------------------------------------------------------------------------- |--- Module : Data.Hash--- Copyright : (c) Milan Straka 2010--- License : BSD-style--- Maintainer : fox@ucw.cz--- Stability : provisional--- Portability : portable------ 'Hashable' class for hashable types, with instances for basic types. The only--- function of this class is------ @--- 'hash' :: Hashable h => h -> Int--- @------ The 'hash' function should be as collision-free as possible, the probability--- of @'hash' a == 'hash' b@ should ideally be 1 over the number of representable--- values in an 'Int'.------ Returning an 'Int' is a result of the 'Data.IntMap.IntMap' using 'Int' as--- a key, as inserting the hash values to the 'Data.IntMap.IntMap' was the--- purpose of creating this class.--------------------------------------------------------------------------------module Data.Hashable ( Hashable(..)- , combine- ) where--import Data.Bits-import Data.Int-import Data.Word-import Data.List (foldl')-import qualified Data.ByteString as B-import qualified Data.ByteString.Internal as BInt-import qualified Data.ByteString.Unsafe as BInt-import qualified Data.ByteString.Lazy as BL-import qualified Data.ByteString.Lazy.Internal as BLInt-import Foreign.C---- | The class containing a function 'hash' which computes the hash values of--- given value.-class Hashable a where- -- | The computed 'hash' value should be as collision-free as possible, the- -- probability of @'hash' a == 'hash' b@ should ideally be 1 over the- -- number of representable values in an 'Int'.- hash :: a -> Int---- | Combines two given hash values.-combine :: Int -> Int -> Int-combine h1 h2 = (h1 + h1 `shiftL` 5) `xor` h2--hashAndCombine :: Hashable h => Int -> h -> Int-hashAndCombine acc h = acc `combine` hash h--instance Hashable () where hash _ = 0--instance Hashable Bool where hash x = case x of { True -> 1; False -> 0 }--instance Hashable Int where hash = id-instance Hashable Int8 where hash = fromIntegral-instance Hashable Int16 where hash = fromIntegral-instance Hashable Int32 where hash = fromIntegral-instance Hashable Int64 where hash = fromIntegral--instance Hashable Word where hash = fromIntegral-instance Hashable Word8 where hash = fromIntegral-instance Hashable Word16 where hash = fromIntegral-instance Hashable Word32 where hash = fromIntegral-instance Hashable Word64 where hash = fromIntegral--instance Hashable Char where hash = fromEnum--instance Hashable a => Hashable (Maybe a) where- hash Nothing = 0- hash (Just a) = 42 `combine` hash a--instance (Hashable a1, Hashable a2) => Hashable (a1, a2) where- hash (a1, a2) = hash a1 `combine` hash a2--instance (Hashable a1, Hashable a2, Hashable a3) => Hashable (a1, a2, a3) where- hash (a1, a2, a3) = hash a1 `combine` hash a2 `combine` hash a3--instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4) => Hashable (a1, a2, a3, a4) where- hash (a1, a2, a3, a4) = hash a1 `combine` hash a2 `combine` hash a3 `combine` hash a4--instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5)- => Hashable (a1, a2, a3, a4, a5) where- hash (a1, a2, a3, a4, a5) =- hash a1 `combine` hash a2 `combine` hash a3 `combine` hash a4 `combine` hash a5--instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5, Hashable a6)- => Hashable (a1, a2, a3, a4, a5, a6) where- hash (a1, a2, a3, a4, a5, a6) =- hash a1 `combine` hash a2 `combine` hash a3 `combine` hash a4 `combine` hash a5 `combine` hash a6--instance (Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5, Hashable a6, Hashable a7)- => Hashable (a1, a2, a3, a4, a5, a6, a7) where- hash (a1, a2, a3, a4, a5, a6, a7) =- hash a1 `combine` hash a2 `combine` hash a3 `combine` hash a4 `combine` hash a5 `combine` hash a6 `combine` hash a7--instance Hashable a => Hashable [a] where- {-# SPECIALIZE instance Hashable [Char] #-}- hash = foldl' hashAndCombine 0--foreign import ccall unsafe hashByteString :: CString -> CInt -> IO CInt-instance Hashable B.ByteString where- hash bstr = fromIntegral $ BInt.inlinePerformIO $ BInt.unsafeUseAsCStringLen bstr $- \(str, len) -> hashByteString str (fromIntegral len)--instance Hashable BL.ByteString where hash = BLInt.foldlChunks hashAndCombine 0
hashmap.cabal view
@@ -1,12 +1,10 @@ Name: hashmap-Version: 1.0.0.3+Version: 1.1.0 Synopsis: Persistent containers HashMap and HashSet. Description: An implementation of persistent 'HashMap' and 'HashSet' on top of 'Data.IntMap.IntMap' and 'Data.IntSet.IntSet',- with very similar API.- .- The class 'Hashable' is providing the 'Hashable.hash'- method.+ with very similar API. It uses 'Hashable' class from the+ @hashable@ package for hashing. . The @'HashMap' key value@ is an 'Data.IntMap.IntMap' indexed by the hash value, containing @'Data.Map.Map' key value@@@ -15,6 +13,7 @@ The @'HashSet' elem@ is an 'Data.IntMap.IntMap' indexed by the hash value, containing @'Data.Set.Set' elem@ for all elements with the same hash value.+Homepage: http://fox.auryn.cz/darcs/hashmap/ License: BSD3 License-file: LICENSE Author: Milan Straka@@ -26,10 +25,8 @@ Extra-source-files: CHANGES Library- Exposed-modules: Data.Hashable, Data.HashMap, Data.HashSet+ Exposed-modules: Data.HashMap, Data.HashSet Build-depends: base >= 4.0 && < 5, containers >= 0.3,- bytestring >= 0.9-- C-sources: src/hashByteString.c+ hashable >= 1.0
− src/hashByteString.c
@@ -1,9 +0,0 @@-int hashByteString(const char* str, int len) {- int hash = 0;-- while (len--) {- hash = (hash * 33) ^ *str++;- }-- return hash;-}