unordered-containers 0.2.0.0 → 0.2.0.1
raw patch · 4 files changed
+147/−15 lines, 4 files
Files
- Data/HashMap/Array.hs +19/−0
- Data/HashMap/Base.hs +89/−12
- Data/HashMap/Strict.hs +38/−2
- unordered-containers.cabal +1/−1
Data/HashMap/Array.hs view
@@ -26,12 +26,14 @@ , update , update' , updateWith+ , unsafeUpdate' , insert , insert' , delete , delete' , unsafeFreeze+ , unsafeThaw , run , run2 , copy@@ -201,6 +203,12 @@ (# s', ary #) -> (# s', array ary (lengthM mary) #) {-# INLINE unsafeFreeze #-} +unsafeThaw :: Array a -> ST s (MArray s a)+unsafeThaw ary+ = ST $ \s -> case unsafeThawArray# (unArray ary) s of+ (# s', mary #) -> (# s', marray mary (length ary) #)+{-# INLINE unsafeThaw #-}+ run :: (forall s . ST s (MArray s e)) -> Array e run act = runST $ act >>= unsafeFreeze {-# INLINE run #-}@@ -295,6 +303,17 @@ updateWith :: Array e -> Int -> (e -> e) -> Array e updateWith ary idx f = update ary idx $! f (index ary idx) {-# INLINE updateWith #-}++-- | /O(1)/ Update the element at the given position in this array,+-- without copying.+unsafeUpdate' :: Array e -> Int -> e -> ST s ()+unsafeUpdate' ary idx b =+ CHECK_BOUNDS("unsafeUpdate'", length ary, idx)+ do mary <- unsafeThaw ary+ write mary idx b+ _ <- unsafeFreeze mary+ return ()+{-# INLINE unsafeUpdate' #-} foldl' :: (b -> a -> b) -> b -> Array a -> b foldl' f = \ z0 ary0 -> go ary0 (length ary0) 0 z0
Data/HashMap/Base.hs view
@@ -17,6 +17,7 @@ , lookupDefault , insert , insertWith+ , unsafeInsert , delete , adjust @@ -226,9 +227,6 @@ | otherwise = BitmapIndexed b ary {-# INLINE bitmapIndexedOrFull #-} --- TODO: Use ptrEq to check if the value being inserted is the same--- and if so don't modify the tree at all.- -- | /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.@@ -244,28 +242,71 @@ else return $! Leaf h (L k x) else return $! collision h l (L k x) | otherwise = two s h k x hy ky y- go h k x s (BitmapIndexed b ary)+ go h k x s t@(BitmapIndexed b ary) | b .&. m == 0 = do ary' <- A.insert' ary i $! Leaf h (L k x) return $! bitmapIndexedOrFull (b .|. m) ary' | otherwise = do st <- A.index_ ary i+ !st' <- go h k x (s+bitsPerSubkey) st+ if st' `ptrEq` st+ then return t+ else do+ ary' <- A.update' ary i st'+ return $! BitmapIndexed b ary'+ where m = mask h s+ i = sparseIndex b m+ go h k x s t@(Full ary) = do+ st <- A.index_ ary i+ !st' <- go h k x (s+bitsPerSubkey) st+ if st' `ptrEq` st+ then return t+ else do+ ary' <- update16' ary i st'+ return $! Full ary'+ where i = index h s+ 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 insert #-}+#endif++-- | In-place update version of insert+unsafeInsert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v+unsafeInsert 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 s t@(Leaf hy l@(L ky y))+ | hy == h = if ky == k+ then if x `ptrEq` y+ then return t+ else return $! Leaf h (L k x)+ else return $! collision h l (L k x)+ | otherwise = two s h k x hy ky y+ go h k x s t@(BitmapIndexed b ary)+ | b .&. m == 0 = do+ ary' <- A.insert' ary i $! Leaf h (L k x)+ return $! bitmapIndexedOrFull (b .|. m) ary'+ | otherwise = do+ st <- A.index_ ary i st' <- go h k x (s+bitsPerSubkey) st- ary' <- A.update' ary i st'- return $! BitmapIndexed b ary'+ A.unsafeUpdate' ary i st'+ return t where m = mask h s i = sparseIndex b m- go h k x s (Full ary) = do+ go h k x s t@(Full ary) = do st <- A.index_ ary i st' <- go h k x (s+bitsPerSubkey) st- ary' <- update16' ary i st'- return $! Full ary'+ A.unsafeUpdate' ary i st'+ return t where i = index h s 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 insert #-}+{-# INLINABLE unsafeInsert #-} #endif -- | Create a map from two key-value pairs which hashes don't collide.@@ -331,6 +372,42 @@ {-# INLINABLE insertWith #-} #endif +-- | In-place update version of insertWith+unsafeInsertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v+ -> HashMap k v+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 s (Leaf hy l@(L ky y))+ | hy == h = if ky == k+ then return $! Leaf h (L k (f x y))+ else return $! collision h l (L k x)+ | otherwise = two s h k x hy ky y+ go h k x s t@(BitmapIndexed b ary)+ | b .&. m == 0 = do+ ary' <- A.insert' ary i $! Leaf h (L k x)+ return $! bitmapIndexedOrFull (b .|. m) ary'+ | otherwise = do+ st <- A.index_ ary i+ st' <- go h k x (s+bitsPerSubkey) st+ A.unsafeUpdate' ary i st'+ return t+ where m = mask h s+ i = sparseIndex b m+ go h k x s t@(Full ary) = do+ st <- A.index_ ary i+ st' <- go h k x (s+bitsPerSubkey) st+ A.unsafeUpdate' ary i st'+ return t+ where i = index h s+ 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. delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v@@ -751,7 +828,7 @@ -- | /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) -> insert k v m) empty+fromList = L.foldl' (\ m (k, v) -> unsafeInsert k v m) empty #if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE fromList #-} #endif@@ -759,7 +836,7 @@ -- | /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) -> insertWith f k v m) empty+fromListWith f = L.foldl' (\ m (k, v) -> unsafeInsertWith f k v m) empty #if __GLASGOW_HASKELL__ >= 700 {-# INLINE fromListWith #-} #endif
Data/HashMap/Strict.hs view
@@ -154,6 +154,42 @@ {-# INLINABLE insertWith #-} #endif +-- | In-place update version of insertWith+unsafeInsertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v+ -> HashMap k v+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 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)+ | otherwise = two s h k x hy ky y+ go h k x s t@(BitmapIndexed b ary)+ | b .&. m == 0 = do+ ary' <- A.insert' ary i $! Leaf h (L k x)+ return $! bitmapIndexedOrFull (b .|. m) ary'+ | otherwise = do+ st <- A.index_ ary i+ st' <- go h k x (s+bitsPerSubkey) st+ A.unsafeUpdate' ary i st'+ return t+ where m = mask h s+ i = sparseIndex b m+ go h k x s t@(Full ary) = do+ st <- A.index_ ary i+ st' <- go h k x (s+bitsPerSubkey) st+ A.unsafeUpdate' ary i st'+ return t+ where i = index h s+ 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@@ -298,7 +334,7 @@ -- 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) -> insert k v m) empty+fromList = L.foldl' (\ m (k, v) -> HM.unsafeInsert k v m) empty #if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE fromList #-} #endif@@ -306,7 +342,7 @@ -- | /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) -> insertWith f k v m) empty+fromListWith f = L.foldl' (\ m (k, v) -> unsafeInsertWith f k v m) empty {-# INLINE fromListWith #-} ------------------------------------------------------------------------
unordered-containers.cabal view
@@ -1,5 +1,5 @@ name: unordered-containers-version: 0.2.0.0+version: 0.2.0.1 synopsis: Efficient hashing-based container types description: Efficient hashing-based container types. The containers have been