Hello community, here is the log from the commit of package ghc-unordered-containers for openSUSE:Factory checked in at 2014-11-26 20:55:10 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/ghc-unordered-containers (Old) and /work/SRC/openSUSE:Factory/.ghc-unordered-containers.new (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Package is "ghc-unordered-containers" Changes: -------- --- /work/SRC/openSUSE:Factory/ghc-unordered-containers/ghc-unordered-containers.changes 2014-08-25 11:06:10.000000000 +0200 +++ /work/SRC/openSUSE:Factory/.ghc-unordered-containers.new/ghc-unordered-containers.changes 2014-11-26 20:55:19.000000000 +0100 @@ -1,0 +2,12 @@ +Fri Sep 12 06:48:21 UTC 2014 - peter.trommler@ohm-hochschule.de + +- update to 0.2.4.0 +* no changelog +* Haskell Platform 2014.2.0.0 + +------------------------------------------------------------------- +Tue Sep 2 10:25:16 UTC 2014 - peter.trommler@ohm-hochschule.de + +- regenerate spec file + +------------------------------------------------------------------- Old: ---- unordered-containers-0.2.3.0.tar.gz New: ---- unordered-containers-0.2.4.0.tar.gz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ ghc-unordered-containers.spec ++++++ --- /var/tmp/diff_new_pack.hcQsNU/_old 2014-11-26 20:55:20.000000000 +0100 +++ /var/tmp/diff_new_pack.hcQsNU/_new 2014-11-26 20:55:20.000000000 +0100 @@ -1,8 +1,7 @@ # # spec file for package ghc-unordered-containers # -# Copyright (c) 2013 SUSE LINUX Products GmbH, Nuernberg, Germany. -# Copyright (c) 2012 Peter Trommler peter.trommler@ohm-hochschule.de +# Copyright (c) 2014 SUSE LINUX Products GmbH, Nuernberg, Germany. # # All modifications and additions to the file contributed by third parties # remain the property of their copyright owners, unless otherwise agreed @@ -19,43 +18,46 @@ %global pkg_name unordered-containers -%global common_summary Haskell %{pkg_name} library - -%global common_description A %{pkg_name} library for Haskell. - Name: ghc-unordered-containers -Version: 0.2.3.0 +Version: 0.2.4.0 Release: 0 -Summary: %{common_summary} +Summary: Efficient hashing-based container types License: BSD-3-Clause Group: System/Libraries -BuildRoot: %{_tmppath}/%{name}-%{version}-build -# BEGIN cabal2spec Url: http://hackage.haskell.org/package/%{pkg_name} Source0: http://hackage.haskell.org/packages/archive/%{pkg_name}/%{version}/%{pkg_name}-%{version}.tar.gz BuildRoot: %{_tmppath}/%{name}-%{version}-build -BuildRequires: %{!?without_hscolour:hscolour} + BuildRequires: ghc-Cabal-devel +BuildRequires: ghc-rpm-macros +# Begin cabal-rpm deps: BuildRequires: ghc-deepseq-devel BuildRequires: ghc-hashable-devel -BuildRequires: ghc-rpm-macros -# END cabal2spec +# End cabal-rpm deps %description -%{common_description} +Efficient hashing-based container types. The containers have been optimized for +performance critical use, both in terms of large data quantities and high +speed. + +The declared cost of each operation is either worst-case or amortized, but +remains valid even if structures are shared. + %package devel Summary: Haskell %{pkg_name} library development files -Group: Development/Languages/Other -Requires: ghc-compiler -Requires(post): ghc-compiler -Requires(postun): ghc-compiler +Group: Development/Libraries/Other +Provides: %{name}-static = %{version}-%{release} +Requires: ghc-compiler = %{ghc_version} +Requires(post): ghc-compiler = %{ghc_version} +Requires(postun): ghc-compiler = %{ghc_version} Requires: %{name} = %{version}-%{release} %description devel -%{common_description} -This package contains the development files. +This package provides the Haskell %{pkg_name} library development +files. + %prep %setup -q -n %{pkg_name}-%{version} ++++++ unordered-containers-0.2.3.0.tar.gz -> unordered-containers-0.2.4.0.tar.gz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/unordered-containers-0.2.3.0/Data/HashMap/Array.hs new/unordered-containers-0.2.4.0/Data/HashMap/Array.hs --- old/unordered-containers-0.2.3.0/Data/HashMap/Array.hs 2012-12-14 01:19:47.000000000 +0100 +++ new/unordered-containers-0.2.4.0/Data/HashMap/Array.hs 2014-04-12 12:40:40.000000000 +0200 @@ -52,10 +52,23 @@ import Control.Applicative (Applicative) import Control.DeepSeq import Control.Monad.ST hiding (runST) -import GHC.Exts +-- GHC 7.7 exports toList/fromList from GHC.Exts +-- In order to avoid warnings on previous GHC versions, we provide +-- an explicit import list instead of only hiding the offending symbols +import GHC.Exts (Array#, Int(..), newArray#, readArray#, writeArray#, + indexArray#, unsafeFreezeArray#, unsafeThawArray#, + MutableArray#) import GHC.ST (ST(..)) import Prelude hiding (filter, foldr, length, map, read) + +#if __GLASGOW_HASKELL__ >= 702 +import GHC.Exts (sizeofArray#, copyArray#, thawArray#, sizeofMutableArray#, + copyMutableArray#) +#endif + +#if defined(ASSERTS) import qualified Prelude +#endif import Data.HashMap.Unsafe (runST) diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/unordered-containers-0.2.3.0/Data/HashMap/Base.hs new/unordered-containers-0.2.4.0/Data/HashMap/Base.hs --- old/unordered-containers-0.2.3.0/Data/HashMap/Base.hs 2012-12-14 01:19:47.000000000 +0100 +++ new/unordered-containers-0.2.4.0/Data/HashMap/Base.hs 2014-04-12 12:40:40.000000000 +0200 @@ -31,6 +31,7 @@ -- * Transformations , map + , mapWithKey , traverseWithKey -- * Difference and intersection @@ -58,6 +59,7 @@ , fromListWith -- Internals used by the strict version + , Hash , Bitmap , bitmapIndexedOrFull , collision @@ -79,11 +81,13 @@ import Control.DeepSeq (NFData(rnf)) import Control.Monad.ST (ST) import Data.Bits ((.&.), (.|.), complement) +import Data.Data hiding (Typeable) import qualified Data.Foldable as Foldable import qualified Data.List as L import Data.Monoid (Monoid(mempty, mappend)) import Data.Traversable (Traversable(..)) import Data.Word (Word) +import GHC.Exts ((==#), build, reallyUnsafePtrEquality#) import Prelude hiding (filter, foldr, lookup, map, null, pred) import qualified Data.HashMap.Array as A @@ -94,11 +98,11 @@ import Data.HashMap.UnsafeShift (unsafeShiftL, unsafeShiftR) import Data.Typeable (Typeable) -#if defined(__GLASGOW_HASKELL__) -import Data.Data hiding (Typeable) -import GHC.Exts ((==#), build, reallyUnsafePtrEquality#) +#if __GLASGOW_HASKELL__ >= 707 +import GHC.Exts (isTrue#) #endif + ------------------------------------------------------------------------ -- | Convenience function. Compute a hash value for the given value. @@ -143,7 +147,6 @@ mappend = union {-# INLINE mappend #-} -#if __GLASGOW_HASKELL__ instance (Data k, Data v, Eq k, Hashable k) => Data (HashMap k v) where gfoldl f z m = z fromList `f` toList m toConstr _ = fromListConstr @@ -158,7 +161,6 @@ hashMapDataType :: DataType hashMapDataType = mkDataType "Data.HashMap.Base.HashMap" [fromListConstr] -#endif type Hash = Word type Bitmap = Word @@ -237,14 +239,12 @@ member k m = case lookup k m of Nothing -> False Just _ -> True -#if __GLASGOW_HASKELL__ >= 700 -{-# INLINEABLE member #-} -#endif +{-# INLINABLE member #-} -- | /O(log n)/ Return the value to which the specified key is mapped, -- or 'Nothing' if this map contains no mapping for the key. lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v -lookup k0 = go h0 k0 0 +lookup k0 m0 = go h0 k0 0 m0 where h0 = hash k0 go !_ !_ !_ Empty = Nothing @@ -259,9 +259,7 @@ go h k _ (Collision hx v) | h == hx = lookupInArray k v | otherwise = Nothing -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE lookup #-} -#endif -- | /O(log n)/ Return the value to which the specified key is mapped, -- or the default value if this map contains no mapping for the key. @@ -316,7 +314,7 @@ | otherwise = runST (two s h k x hy ky y) go h k x s t@(BitmapIndexed b ary) | b .&. m == 0 = - let ary' = A.insert ary i $! Leaf h (L k x) + let !ary' = A.insert ary i $! Leaf h (L k x) in bitmapIndexedOrFull (b .|. m) ary' | otherwise = let !st = A.index ary i @@ -336,9 +334,7 @@ go h k x s t@(Collision hy v) | h == hy = Collision h (updateOrSnocWith const k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t) -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insert #-} -#endif -- | In-place update version of insert unsafeInsert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v @@ -373,9 +369,7 @@ go h k x s t@(Collision hy v) | h == hy = return $! Collision h (updateOrSnocWith const k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t) -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE unsafeInsert #-} -#endif -- | Create a map from two key-value pairs which hashes don't collide. two :: Shift -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v) @@ -436,9 +430,7 @@ go h k x s t@(Collision hy v) | h == hy = Collision h (updateOrSnocWith f k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t) -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insertWith #-} -#endif -- | In-place update version of insertWith unsafeInsertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v @@ -472,9 +464,7 @@ go h k x s t@(Collision hy v) | h == hy = return $! Collision h (updateOrSnocWith f k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t) -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE unsafeInsertWith #-} -#endif -- | /O(log n)/ Remove the mapping for the specified key from this map -- if present. @@ -529,14 +519,12 @@ | otherwise -> Collision h (A.delete v i) Nothing -> t | otherwise = t -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE delete #-} -#endif -- | /O(log n)/ Adjust the value tied to a given key in this map only -- if it is present. Otherwise, leave the map alone. adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v -adjust f k0 = go h0 k0 0 +adjust f k0 m0 = go h0 k0 0 m0 where h0 = hash k0 go !_ !_ !_ Empty = Empty @@ -560,9 +548,7 @@ go h k _ t@(Collision hy v) | h == hy = Collision h (updateWith f k v) | otherwise = t -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE adjust #-} -#endif ------------------------------------------------------------------------ -- * Combine @@ -571,9 +557,7 @@ -- mapping from the first will be the mapping in the result. union :: (Eq k, Hashable k) => HashMap k v -> HashMap k v -> HashMap k v union = unionWith const -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE union #-} -#endif -- | /O(n+m)/ The union of two maps. If a key occurs in both maps, -- the provided function (first argument) will be used to compute the @@ -712,6 +696,7 @@ A.map' (\ (L k v) -> L k (f k v)) ary {-# INLINE mapWithKey #-} +-- | /O(n)/ Transform this map by applying a function to every value. map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2 map f = mapWithKey (const f) {-# INLINE map #-} @@ -744,9 +729,7 @@ go m k v = case lookup k b of Nothing -> insert k v m _ -> m -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE difference #-} -#endif -- | /O(n*log m)/ Intersection of two maps. Return elements of the first -- map for keys existing in the second. @@ -756,9 +739,7 @@ go m k v = case lookup k b of Just _ -> insert k v m _ -> m -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE intersection #-} -#endif -- | /O(n+m)/ Intersection of two maps. If a key occurs in both maps -- the provided function is used to combine the values from the two @@ -770,9 +751,7 @@ go m k v = case lookup k b of Just w -> insert k (f v w) m _ -> m -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE intersectionWith #-} -#endif ------------------------------------------------------------------------ -- * Folds @@ -921,28 +900,20 @@ -- | /O(n)/ Return a list of this map's elements. The list is -- produced lazily. toList :: HashMap k v -> [(k, v)] -#if defined(__GLASGOW_HASKELL__) toList t = build (\ c z -> foldrWithKey (curry c) z t) -#else -toList = foldrWithKey (\ k v xs -> (k, v) : xs) [] -#endif {-# INLINE toList #-} -- | /O(n)/ Construct a map with the supplied mappings. If the list -- contains duplicate mappings, the later mappings take precedence. fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v fromList = L.foldl' (\ m (k, v) -> unsafeInsert k v m) empty -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE fromList #-} -#endif -- | /O(n*log n)/ Construct a map from a list of elements. Uses -- the provided function to merge duplicate entries. fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v fromListWith f = L.foldl' (\ m (k, v) -> unsafeInsertWith f k v m) empty -#if __GLASGOW_HASKELL__ >= 700 {-# INLINE fromListWith #-} -#endif ------------------------------------------------------------------------ -- Array operations @@ -958,9 +929,7 @@ (L kx v) | k == kx -> Just v | otherwise -> go k ary (i+1) n -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE lookupInArray #-} -#endif -- | /O(n)/ Lookup the value associated with the given key in this -- array. Returns 'Nothing' if the key wasn't found. @@ -973,9 +942,7 @@ (L kx _) | k == kx -> Just i | otherwise -> go k ary (i+1) n -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE indexOf #-} -#endif updateWith :: Eq k => (v -> v) -> k -> A.Array (Leaf k v) -> A.Array (Leaf k v) updateWith f k0 ary0 = go k0 ary0 0 (A.length ary0) @@ -985,9 +952,7 @@ | otherwise = case A.index ary i of (L kx y) | k == kx -> A.update ary i (L k (f y)) | otherwise -> go k ary (i+1) n -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE updateWith #-} -#endif updateOrSnocWith :: Eq k => (v -> v -> v) -> k -> v -> A.Array (Leaf k v) -> A.Array (Leaf k v) @@ -1003,9 +968,7 @@ | otherwise = case A.index ary i of (L kx y) | k == kx -> A.update ary i (L k (f v y)) | otherwise -> go k v ary (i+1) n -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE updateOrSnocWith #-} -#endif updateOrConcatWith :: Eq k => (v -> v -> v) -> A.Array (Leaf k v) -> A.Array (Leaf k v) -> A.Array (Leaf k v) updateOrConcatWith f ary1 ary2 = A.run $ do @@ -1033,9 +996,7 @@ go (iEnd+1) (i2+1) go n1 0 return mary -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE updateOrConcatWith #-} -#endif ------------------------------------------------------------------------ -- Manually unrolled loops @@ -1118,9 +1079,9 @@ -- | Check if two the two arguments are the same value. N.B. This -- function might give false negatives (due to GC moving objects.) ptrEq :: a -> a -> Bool -#if defined(__GLASGOW_HASKELL__) +#if __GLASGOW_HASKELL__ < 707 ptrEq x y = reallyUnsafePtrEquality# x y ==# 1# #else -ptrEq _ _ = False +ptrEq x y = isTrue# (reallyUnsafePtrEquality# x y ==# 1#) #endif {-# INLINE ptrEq #-} diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/unordered-containers-0.2.3.0/Data/HashMap/Lazy.hs new/unordered-containers-0.2.4.0/Data/HashMap/Lazy.hs --- old/unordered-containers-0.2.3.0/Data/HashMap/Lazy.hs 2012-12-14 01:19:47.000000000 +0100 +++ new/unordered-containers-0.2.4.0/Data/HashMap/Lazy.hs 2014-04-12 12:40:40.000000000 +0200 @@ -17,10 +17,6 @@ -- duplicate keys; each key can map to at most one value. A 'HashMap' -- makes no guarantees as to the order of its elements. -- --- This map is strict in the keys and lazy in the values; keys are --- evaluated to /weak head normal form/ before they are added to the --- map. --- -- The implementation is based on /hash array mapped tries/. A -- 'HashMap' is often faster than other tree-based set types, -- especially when key comparison is expensive, as in the case of @@ -31,6 +27,9 @@ -- operations are constant time. module Data.HashMap.Lazy ( + -- * Strictness properties + -- $strictness + HashMap -- * Construction @@ -57,6 +56,7 @@ -- * Transformations , HM.map + , mapWithKey , traverseWithKey -- * Difference and intersection @@ -85,3 +85,9 @@ ) where import Data.HashMap.Base as HM + +-- $strictness +-- +-- This module satisfies the following strictness property: +-- +-- * Key arguments are evaluated to WHNF diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/unordered-containers-0.2.3.0/Data/HashMap/Strict.hs new/unordered-containers-0.2.4.0/Data/HashMap/Strict.hs --- old/unordered-containers-0.2.3.0/Data/HashMap/Strict.hs 2012-12-14 01:19:47.000000000 +0100 +++ new/unordered-containers-0.2.4.0/Data/HashMap/Strict.hs 2014-04-12 12:40:40.000000000 +0200 @@ -17,11 +17,6 @@ -- duplicate keys; each key can map to at most one value. A 'HashMap' -- makes no guarantees as to the order of its elements. -- --- This map is strict in both the keys and the values; keys and values --- are evaluated to /weak head normal form/ before they are added to --- the map. Exception: the provided instances are the same as for the --- lazy version of this module. --- -- The implementation is based on /hash array mapped tries/. A -- 'HashMap' is often faster than other tree-based set types, -- especially when key comparison is expensive, as in the case of @@ -32,6 +27,9 @@ -- operations are constant time. module Data.HashMap.Strict ( + -- * Strictness properties + -- $strictness + HashMap -- * Construction @@ -58,6 +56,7 @@ -- * Transformations , map + , mapWithKey , traverseWithKey -- * Difference and intersection @@ -94,9 +93,18 @@ import qualified Data.HashMap.Base as HM import Data.HashMap.Base hiding ( adjust, fromList, fromListWith, insert, insertWith, intersectionWith, - lookupDefault, map, singleton, unionWith) + map, mapWithKey, singleton, unionWith) import Data.HashMap.Unsafe (runST) +-- $strictness +-- +-- This module satisfies the following strictness properties: +-- +-- 1. Key arguments are evaluated to WHNF; +-- +-- 2. Keys and values are evaluated to WHNF before they are stored in +-- the map. + ------------------------------------------------------------------------ -- * Construction @@ -107,22 +115,12 @@ ------------------------------------------------------------------------ -- * Basic interface --- | /O(log n)/ Return the value to which the specified key is mapped, --- or the default value if this map contains no mapping for the key. -lookupDefault :: (Eq k, Hashable k) - => v -- ^ Default value to return. - -> k -> HashMap k v -> v -lookupDefault !def k t = HM.lookupDefault def k t -{-# INLINABLE lookupDefault #-} - -- | /O(log n)/ Associate the specified value with the specified -- key in this map. If this map previously contained a mapping for -- the key, the old value is replaced. insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v insert k !v = HM.insert k v -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insert #-} -#endif -- | /O(log n)/ Associate the value with the key in this map. If -- this map previously contained a mapping for the key, the old value @@ -133,18 +131,18 @@ -- > where f new old = new + old insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v -insertWith f k0 !v0 m0 = go h0 k0 v0 0 m0 +insertWith f k0 v0 m0 = go h0 k0 v0 0 m0 where h0 = hash k0 - go !h !k x !_ Empty = Leaf h (L k x) + go !h !k x !_ Empty = leaf h k x go h k x s (Leaf hy l@(L ky y)) | hy == h = if ky == k - then let !v' = f x y in Leaf h (L k v') - else collision h l (L k x) - | otherwise = runST (two s h k x hy ky y) + then leaf h k (f x y) + else x `seq` (collision h l (L k x)) + | otherwise = x `seq` runST (two s h k x hy ky y) go h k x s (BitmapIndexed b ary) | b .&. m == 0 = - let ary' = A.insert ary i $! Leaf h (L k x) + let ary' = A.insert ary i $! leaf h k x in bitmapIndexedOrFull (b .|. m) ary' | otherwise = let st = A.index ary i @@ -162,9 +160,7 @@ go h k x s t@(Collision hy v) | h == hy = Collision h (updateOrSnocWith f k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t) -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insertWith #-} -#endif -- | In-place update version of insertWith unsafeInsertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v @@ -172,15 +168,17 @@ unsafeInsertWith f k0 v0 m0 = runST (go h0 k0 v0 0 m0) where h0 = hash k0 - go !h !k x !_ Empty = return $! Leaf h (L k x) + go !h !k x !_ Empty = return $! leaf h k x go h k x s (Leaf hy l@(L ky y)) | hy == h = if ky == k - then let !v' = f x y in return $! Leaf h (L k v') - else return $! collision h l (L k x) + then return $! leaf h k (f x y) + else do + let l' = x `seq` (L k x) + return $! collision h l l' | otherwise = two s h k x hy ky y go h k x s t@(BitmapIndexed b ary) | b .&. m == 0 = do - ary' <- A.insertM ary i $! Leaf h (L k x) + ary' <- A.insertM ary i $! leaf h k x return $! bitmapIndexedOrFull (b .|. m) ary' | otherwise = do st <- A.indexM ary i @@ -198,19 +196,17 @@ go h k x s t@(Collision hy v) | h == hy = return $! Collision h (updateOrSnocWith f k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t) -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE unsafeInsertWith #-} -#endif -- | /O(log n)/ Adjust the value tied to a given key in this map only -- if it is present. Otherwise, leave the map alone. adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v -adjust f k0 = go h0 k0 0 +adjust f k0 m0 = go h0 k0 0 m0 where h0 = hash k0 go !_ !_ !_ Empty = Empty go h k _ t@(Leaf hy (L ky y)) - | hy == h && ky == k = let !v' = f y in Leaf h (L k v') + | hy == h && ky == k = leaf h k (f y) | otherwise = t go h k s t@(BitmapIndexed b ary) | b .&. m == 0 = t @@ -229,9 +225,7 @@ go h k _ t@(Collision hy v) | h == hy = Collision h (updateWith f k v) | otherwise = t -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE adjust #-} -#endif ------------------------------------------------------------------------ -- * Combine @@ -248,7 +242,7 @@ -- leaf vs. leaf go s t1@(Leaf h1 l1@(L k1 v1)) t2@(Leaf h2 l2@(L k2 v2)) | h1 == h2 = if k1 == k2 - then Leaf h1 . L k1 $! f v1 v2 + then leaf h1 k1 (f v1 v2) else collision h1 l1 l2 | otherwise = goDifferentHash s h1 h2 t1 t2 go s t1@(Leaf h1 (L k1 v1)) t2@(Collision h2 ls2) @@ -330,13 +324,14 @@ mapWithKey f = go where go Empty = Empty - go (Leaf h (L k v)) = let !v' = f k v in Leaf h $ L k v' + go (Leaf h (L k v)) = leaf h k (f k v) go (BitmapIndexed b ary) = BitmapIndexed b $ A.map' go ary go (Full ary) = Full $ A.map' go ary go (Collision h ary) = Collision h $ A.map' (\ (L k v) -> let !v' = f k v in L k v') ary {-# INLINE mapWithKey #-} +-- | /O(n)/ Transform this map by applying a function to every value. map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2 map f = mapWithKey (const f) {-# INLINE map #-} @@ -356,9 +351,7 @@ go m k v = case HM.lookup k b of Just w -> insert k (f v w) m _ -> m -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE intersectionWith #-} -#endif ------------------------------------------------------------------------ -- ** Lists @@ -367,10 +360,8 @@ -- list contains duplicate mappings, the later mappings take -- precedence. fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v -fromList = L.foldl' (\ m (k, v) -> HM.unsafeInsert k v m) empty -#if __GLASGOW_HASKELL__ >= 700 +fromList = L.foldl' (\ m (k, !v) -> HM.unsafeInsert k v m) empty {-# INLINABLE fromList #-} -#endif -- | /O(n*log n)/ Construct a map from a list of elements. Uses -- the provided function to merge duplicate entries. @@ -389,10 +380,13 @@ | otherwise = case A.index ary i of (L kx y) | k == kx -> let !v' = f y in A.update ary i (L k v') | otherwise -> go k ary (i+1) n -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE updateWith #-} -#endif +-- | Append the given key and value to the array. If the key is +-- already present, instead update the value of the key by applying +-- the given function to the new and old value (in that order). The +-- value is always evaluated to WHNF before being inserted into the +-- array. updateOrSnocWith :: Eq k => (v -> v -> v) -> k -> v -> A.Array (Leaf k v) -> A.Array (Leaf k v) updateOrSnocWith f k0 v0 ary0 = go k0 v0 ary0 0 (A.length ary0) @@ -402,11 +396,20 @@ -- Not found, append to the end. mary <- A.new_ (n + 1) A.copy ary 0 mary 0 n - A.write mary n (L k v) + let !l = v `seq` (L k v) + A.write mary n l return mary | otherwise = case A.index ary i of (L kx y) | k == kx -> let !v' = f v y in A.update ary i (L k v') | otherwise -> go k v ary (i+1) n -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE updateOrSnocWith #-} -#endif + +------------------------------------------------------------------------ +-- Smart constructors +-- +-- These constructors make sure the value is in WHNF before it's +-- inserted into the constructor. + +leaf :: Hash -> k -> v -> HashMap k v +leaf h k !v = Leaf h (L k v) +{-# INLINE leaf #-} diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/unordered-containers-0.2.3.0/Data/HashSet.hs new/unordered-containers-0.2.4.0/Data/HashSet.hs --- old/unordered-containers-0.2.3.0/Data/HashSet.hs 2012-12-14 01:19:47.000000000 +0100 +++ new/unordered-containers-0.2.4.0/Data/HashSet.hs 2014-04-12 12:40:40.000000000 +0200 @@ -60,20 +60,17 @@ ) where import Control.DeepSeq (NFData(..)) +import Data.Data hiding (Typeable) import Data.HashMap.Base (HashMap, foldrWithKey) import Data.Hashable (Hashable) import Data.Monoid (Monoid(..)) +import GHC.Exts (build) import Prelude hiding (filter, foldr, map, null) import qualified Data.Foldable as Foldable import qualified Data.HashMap.Lazy as H import qualified Data.List as List import Data.Typeable (Typeable) -#if defined(__GLASGOW_HASKELL__) -import Data.Data hiding (Typeable) -import GHC.Exts (build) -#endif - -- | A set of values. A set cannot contain duplicate values. newtype HashSet a = HashSet { asMap :: HashMap a () @@ -103,7 +100,6 @@ showsPrec d m = showParen (d > 10) $ showString "fromList " . shows (toList m) -#if __GLASGOW_HASKELL__ instance (Data a, Eq a, Hashable a) => Data (HashSet a) where gfoldl f z m = z fromList `f` toList m toConstr _ = fromListConstr @@ -118,7 +114,6 @@ hashSetDataType :: DataType hashSetDataType = mkDataType "Data.HashSet" [fromListConstr] -#endif -- | /O(1)/ Construct an empty set. empty :: HashSet a @@ -127,9 +122,7 @@ -- | /O(1)/ Construct a set with a single element. singleton :: Hashable a => a -> HashSet a singleton a = HashSet (H.singleton a ()) -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE singleton #-} -#endif -- | /O(n+m)/ Construct a set containing all elements from both sets. -- @@ -162,24 +155,18 @@ member a s = case H.lookup a (asMap s) of Just _ -> True _ -> False -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE member #-} -#endif -- | /O(min(n,W))/ Add the specified value to this set. insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a insert a = HashSet . H.insert a () . asMap -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insert #-} -#endif -- | /O(min(n,W))/ Remove the specified value from this set if -- present. delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a delete a = HashSet . H.delete a . asMap -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE delete #-} -#endif -- | /O(n)/ Transform this set by applying a function to every value. -- The resulting set may be smaller than the source. @@ -191,17 +178,13 @@ -- not existing in the second. difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a difference (HashSet a) (HashSet b) = HashSet (H.difference a b) -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE difference #-} -#endif -- | /O(n)/ Intersection of two sets. Return elements present in both -- the first set and the second. intersection :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a intersection (HashSet a) (HashSet b) = HashSet (H.intersection a b) -#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE intersection #-} -#endif -- | /O(n)/ Reduce this set by applying a binary operator to all -- elements, using the given starting value (typically the @@ -231,11 +214,7 @@ -- | /O(n)/ Return a list of this set's elements. The list is -- produced lazily. toList :: HashSet a -> [a] -#if defined(__GLASGOW_HASKELL__) toList t = build (\ c z -> foldrWithKey ((const .) c) z (asMap t)) -#else -toList = foldrWithKey (\ k _ xs -> k : xs) [] . asMap -#endif {-# INLINE toList #-} -- | /O(n*min(W, n))/ Construct a set from a list of elements. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/unordered-containers-0.2.3.0/benchmarks/Benchmarks.hs new/unordered-containers-0.2.4.0/benchmarks/Benchmarks.hs --- old/unordered-containers-0.2.3.0/benchmarks/Benchmarks.hs 2012-12-14 01:19:47.000000000 +0100 +++ new/unordered-containers-0.2.4.0/benchmarks/Benchmarks.hs 2014-04-12 12:40:40.000000000 +0200 @@ -1,4 +1,4 @@ -{-# LANGUAGE CPP, GADTs #-} +{-# LANGUAGE CPP, GADTs, PackageImports #-} module Main where @@ -10,6 +10,7 @@ import Data.Bits ((.&.)) import Data.Hashable (Hashable) import qualified Data.ByteString as BS +import qualified "hashmap" Data.HashMap as IHM import qualified Data.HashMap.Strict as HM import qualified Data.IntMap as IM import qualified Data.Map as M @@ -40,6 +41,8 @@ m = M.fromList elems :: M.Map String Int mbs = M.fromList elemsBS :: M.Map BS.ByteString Int im = IM.fromList elemsI :: IM.IntMap Int + ihm = IHM.fromList elems :: IHM.Map String Int + ihmbs = IHM.fromList elemsBS :: IHM.Map BS.ByteString Int defaultMainWith defaultConfig (liftIO . evaluate $ rnf [B m, B mbs, B hm, B hmbs, B hmi, B im]) [ @@ -80,6 +83,42 @@ ] ] + -- ** Map from the hashmap package + , bgroup "hashmap/Map" + [ bgroup "lookup" + [ bench "String" $ whnf (lookupIHM keys) ihm + , bench "ByteString" $ whnf (lookupIHM keysBS) ihmbs + ] + , bgroup "lookup-miss" + [ bench "String" $ whnf (lookupIHM keys') ihm + , bench "ByteString" $ whnf (lookupIHM keysBS') ihmbs + ] + , bgroup "insert" + [ bench "String" $ whnf (insertIHM elems) IHM.empty + , bench "ByteStringString" $ whnf (insertIHM elemsBS) IHM.empty + ] + , bgroup "insert-dup" + [ bench "String" $ whnf (insertIHM elems) ihm + , bench "ByteStringString" $ whnf (insertIHM elemsBS) ihmbs + ] + , bgroup "delete" + [ bench "String" $ whnf (deleteIHM keys) ihm + , bench "ByteString" $ whnf (deleteIHM keysBS) ihmbs + ] + , bgroup "delete-miss" + [ bench "String" $ whnf (deleteIHM keys') ihm + , bench "ByteString" $ whnf (deleteIHM keysBS') ihmbs + ] + , bgroup "size" + [ bench "String" $ whnf IHM.size ihm + , bench "ByteString" $ whnf IHM.size ihmbs + ] + , bgroup "fromList" + [ bench "String" $ whnf IHM.fromList elems + , bench "ByteString" $ whnf IHM.fromList elemsBS + ] + ] + -- ** IntMap , bgroup "IntMap" [ bench "lookup" $ whnf (lookupIM keysI) im @@ -152,39 +191,29 @@ -- fromList , bgroup "fromList" - [ bgroup name - [ bgroup "long" - [ bench "String" $ whnf fl1 elems - , bench "ByteString" $ whnf fl2 elemsBS - , bench "Int" $ whnf fl3 elemsI - ] - , bgroup "short" - [ bench "String" $ whnf fl1 elemsDup - , bench "ByteString" $ whnf fl2 elemsDupBS - , bench "Int" $ whnf fl3 elemsDupI - ] + [ bgroup "long" + [ bench "String" $ whnf HM.fromList elems + , bench "ByteString" $ whnf HM.fromList elemsBS + , bench "Int" $ whnf HM.fromList elemsI + ] + , bgroup "short" + [ bench "String" $ whnf HM.fromList elemsDup + , bench "ByteString" $ whnf HM.fromList elemsDupBS + , bench "Int" $ whnf HM.fromList elemsDupI ] - | (name,fl1,fl2,fl3) - <- [("Base",HM.fromList,HM.fromList,HM.fromList) - ,("insert",fromList_insert,fromList_insert,fromList_insert)] ] - -- fromList + -- fromListWith , bgroup "fromListWith" - [ bgroup name - [ bgroup "long" - [ bench "String" $ whnf (fl1 (+)) elems - , bench "ByteString" $ whnf (fl2 (+)) elemsBS - , bench "Int" $ whnf (fl3 (+)) elemsI - ] - , bgroup "short" - [ bench "String" $ whnf (fl1 (+)) elemsDup - , bench "ByteString" $ whnf (fl2 (+)) elemsDupBS - , bench "Int" $ whnf (fl3 (+)) elemsDupI - ] + [ bgroup "long" + [ bench "String" $ whnf (HM.fromListWith (+)) elems + , bench "ByteString" $ whnf (HM.fromListWith (+)) elemsBS + , bench "Int" $ whnf (HM.fromListWith (+)) elemsI + ] + , bgroup "short" + [ bench "String" $ whnf (HM.fromListWith (+)) elemsDup + , bench "ByteString" $ whnf (HM.fromListWith (+)) elemsDupBS + , bench "Int" $ whnf (HM.fromListWith (+)) elemsDupI ] - | (name,fl1,fl2,fl3) - <- [("Base",HM.fromListWith,HM.fromListWith,HM.fromListWith) - ,("insert",fromListWith_insert,fromListWith_insert,fromListWith_insert)] ] ] ] @@ -261,6 +290,30 @@ -> M.Map BS.ByteString Int #-} ------------------------------------------------------------------------ +-- * Map from the hashmap package + +lookupIHM :: (Eq k, Hashable k, Ord k) => [k] -> IHM.Map k Int -> Int +lookupIHM xs m = foldl' (\z k -> fromMaybe z (IHM.lookup k m)) 0 xs +{-# SPECIALIZE lookupIHM :: [String] -> IHM.Map String Int -> Int #-} +{-# SPECIALIZE lookupIHM :: [BS.ByteString] -> IHM.Map BS.ByteString Int + -> Int #-} + +insertIHM :: (Eq k, Hashable k, Ord k) => [(k, Int)] -> IHM.Map k Int + -> IHM.Map k Int +insertIHM xs m0 = foldl' (\m (k, v) -> IHM.insert k v m) m0 xs +{-# SPECIALIZE insertIHM :: [(String, Int)] -> IHM.Map String Int + -> IHM.Map String Int #-} +{-# SPECIALIZE insertIHM :: [(BS.ByteString, Int)] -> IHM.Map BS.ByteString Int + -> IHM.Map BS.ByteString Int #-} + +deleteIHM :: (Eq k, Hashable k, Ord k) => [k] -> IHM.Map k Int -> IHM.Map k Int +deleteIHM xs m0 = foldl' (\m k -> IHM.delete k m) m0 xs +{-# SPECIALIZE deleteIHM :: [String] -> IHM.Map String Int + -> IHM.Map String Int #-} +{-# SPECIALIZE deleteIHM :: [BS.ByteString] -> IHM.Map BS.ByteString Int + -> IHM.Map BS.ByteString Int #-} + +------------------------------------------------------------------------ -- * IntMap lookupIM :: [Int] -> IM.IntMap Int -> Int @@ -271,18 +324,3 @@ deleteIM :: [Int] -> IM.IntMap Int -> IM.IntMap Int deleteIM xs m0 = foldl' (\m k -> IM.delete k m) m0 xs - ------------------------------------------------------------------------- --- * Reference implementations - -fromList_insert :: (Eq k, Hashable k) => [(k, v)] -> HM.HashMap k v -fromList_insert = foldl' (\ m (k, v) -> HM.insert k v m) HM.empty -#if __GLASGOW_HASKELL__ >= 700 -{-# INLINABLE fromList_insert #-} -#endif - -fromListWith_insert :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HM.HashMap k v -fromListWith_insert f = foldl' (\ m (k, v) -> HM.insertWith f k v m) HM.empty -#if __GLASGOW_HASKELL__ >= 700 -{-# INLINABLE fromListWith_insert #-} -#endif diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/unordered-containers-0.2.3.0/tests/Strictness.hs new/unordered-containers-0.2.4.0/tests/Strictness.hs --- old/unordered-containers-0.2.3.0/tests/Strictness.hs 2012-12-14 01:19:47.000000000 +0100 +++ new/unordered-containers-0.2.4.0/tests/Strictness.hs 2014-04-12 12:40:40.000000000 +0200 @@ -44,9 +44,6 @@ pLookupDefaultKeyStrict :: Int -> HashMap Key Int -> Bool pLookupDefaultKeyStrict def m = isBottom $ HM.lookupDefault def bottom m -pLookupDefaultValueStrict :: Key -> HashMap Key Int -> Bool -pLookupDefaultValueStrict k m = isBottom $ HM.lookupDefault bottom k m - pAdjustKeyStrict :: (Int -> Int) -> HashMap Key Int -> Bool pAdjustKeyStrict f m = isBottom $ HM.adjust f bottom m @@ -72,6 +69,21 @@ | HM.member k m = isBottom $ HM.insertWith (const2 bottom) k v m | otherwise = isBottom $ HM.insertWith f k bottom m +pFromListKeyStrict :: Bool +pFromListKeyStrict = isBottom $ HM.fromList [(undefined :: Key, 1 :: Int)] + +pFromListValueStrict :: Bool +pFromListValueStrict = isBottom $ HM.fromList [(K 1, undefined)] + +pFromListWithKeyStrict :: (Int -> Int -> Int) -> Bool +pFromListWithKeyStrict f = + isBottom $ HM.fromListWith f [(undefined :: Key, 1 :: Int)] + +pFromListWithValueStrict :: [(Key, Int)] -> Bool +pFromListWithValueStrict xs = case xs of + [] -> True + (x:_) -> isBottom $ HM.fromListWith (\ _ _ -> undefined) (x:xs) + ------------------------------------------------------------------------ -- * Test list @@ -85,7 +97,6 @@ , testProperty "member is key-strict" $ keyStrict HM.member , testProperty "lookup is key-strict" $ keyStrict HM.lookup , testProperty "lookupDefault is key-strict" pLookupDefaultKeyStrict - , testProperty "lookupDefault is value-strict" pLookupDefaultValueStrict , testProperty "! is key-strict" $ keyStrict (flip (HM.!)) , testProperty "delete is key-strict" $ keyStrict HM.delete , testProperty "adjust is key-strict" pAdjustKeyStrict @@ -94,6 +105,10 @@ , testProperty "insert is value-strict" pInsertValueStrict , testProperty "insertWith is key-strict" pInsertWithKeyStrict , testProperty "insertWith is value-strict" pInsertWithValueStrict + , testProperty "fromList is key-strict" pFromListKeyStrict + , testProperty "fromList is value-strict" pFromListValueStrict + , testProperty "fromListWith is key-strict" pFromListWithKeyStrict + , testProperty "fromListWith is value-strict" pFromListWithValueStrict ] ] diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/unordered-containers-0.2.3.0/unordered-containers.cabal new/unordered-containers-0.2.4.0/unordered-containers.cabal --- old/unordered-containers-0.2.3.0/unordered-containers.cabal 2012-12-14 01:19:47.000000000 +0100 +++ new/unordered-containers-0.2.4.0/unordered-containers.cabal 2014-04-12 12:40:41.000000000 +0200 @@ -1,5 +1,5 @@ name: unordered-containers -version: 0.2.3.0 +version: 0.2.4.0 synopsis: Efficient hashing-based container types description: Efficient hashing-based container types. The containers have been @@ -14,7 +14,7 @@ maintainer: johan.tibell@gmail.com Homepage: https://github.com/tibbe/unordered-containers bug-reports: https://github.com/tibbe/unordered-containers/issues -copyright: 2010-2012 Johan Tibell +copyright: 2010-2014 Johan Tibell 2010 Edward Z. Yang category: Data build-type: Simple @@ -154,6 +154,7 @@ criterion, deepseq >= 1.1, hashable >= 1.0.1.1, + hashmap, mtl, random -- To unsubscribe, e-mail: opensuse-commit+unsubscribe@opensuse.org For additional commands, e-mail: opensuse-commit+help@opensuse.org