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 - [email protected]
+
+- update to 0.2.4.0
+* no changelog
+* Haskell Platform 2014.2.0.0
+
+-------------------------------------------------------------------
+Tue Sep 2 10:25:16 UTC 2014 - [email protected]
+
+- 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 [email protected]
+# 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: [email protected]
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: [email protected]
For additional commands, e-mail: [email protected]
