unordered-containers 0.2.19.0 → 0.2.19.1
raw patch · 4 files changed
+88/−14 lines, 4 filesdep ~basedep ~template-haskell
Dependency ranges changed: base, template-haskell
Files
- CHANGES.md +8/−0
- Data/HashMap/Internal.hs +64/−13
- tests/Regressions.hs +15/−0
- unordered-containers.cabal +1/−1
CHANGES.md view
@@ -1,3 +1,11 @@+## [0.2.19.1] – April 2022++* [Fix bug in `intersection[With[Key]]`](https://github.com/haskell-unordered-containers/unordered-containers/pull/427)++* [Improve docs of bit twiddling functions](https://github.com/haskell-unordered-containers/unordered-containers/pull/396)++[0.2.19.1]: https://github.com/haskell-unordered-containers/unordered-containers/compare/v0.2.19.0...v0.2.19.1+ ## [0.2.19.0] – April 2022 * [Make intersections much faster](https://github.com/haskell-unordered-containers/unordered-containers/pull/406)
Data/HashMap/Internal.hs view
@@ -311,8 +311,20 @@ hashMapDataType :: DataType hashMapDataType = Data.mkDataType "Data.HashMap.Internal.HashMap" [fromListConstr] +-- | This type is used to store the hash of a key, as produced with 'hash'. type Hash = Word++-- | A bitmap as contained by a 'BitmapIndexed' node, or a 'fullNodeMask'+-- corresponding to a 'Full' node.+--+-- Only the lower 'maxChildren' bits are used. The remaining bits must be zeros. type Bitmap = Word++-- | 'Shift' values correspond to the level of the tree that we're currently+-- operating at. At the root level the 'Shift' is @0@. For the subsequent+-- levels the 'Shift' values are 'bitsPerSubkey', @2*'bitsPerSubkey'@ etc.+--+-- Valid values are non-negative and less than @bitSize (0 :: Word)@. type Shift = Int instance Show2 HashMap where@@ -1861,7 +1873,11 @@ (len, bFinal) <- go 0 0 0 bCombined bIntersect case len of 0 -> pure Empty- 1 -> A.read mary 0+ 1 -> do+ l <- A.read mary 0+ if isLeafOrCollision l+ then pure l+ else BitmapIndexed bFinal <$> (A.unsafeFreeze =<< A.shrink mary 1) _ -> bitmapIndexedOrFull bFinal <$> (A.unsafeFreeze =<< A.shrink mary len) where bCombined = b1 .|. b2@@ -1915,7 +1931,6 @@ else go i0 k (i + 1) mary {-# INLINE searchSwap #-} - ------------------------------------------------------------------------ -- * Folds @@ -2358,35 +2373,71 @@ ------------------------------------------------------------------------ -- Bit twiddling +-- TODO: Name this 'bitsPerLevel'?! What is a "subkey"?+-- https://github.com/haskell-unordered-containers/unordered-containers/issues/425++-- | Number of bits that are inspected at each level of the hash tree.+--+-- This constant is named /t/ in the original /Ideal Hash Trees/ paper. bitsPerSubkey :: Int bitsPerSubkey = 5 +-- | The size of a 'Full' node, i.e. @2 ^ 'bitsPerSubkey'@. maxChildren :: Int maxChildren = 1 `unsafeShiftL` bitsPerSubkey -subkeyMask :: Bitmap+-- | Bit mask with the lowest 'bitsPerSubkey' bits set, i.e. @0b11111@.+subkeyMask :: Word subkeyMask = 1 `unsafeShiftL` bitsPerSubkey - 1 -sparseIndex :: Bitmap -> Bitmap -> Int-sparseIndex b m = popCount (b .&. (m - 1))-{-# INLINE sparseIndex #-}+-- | Given a 'Hash' and a 'Shift' that indicates the level in the tree, compute+-- the index into a 'Full' node or into the bitmap of a `BitmapIndexed` node.+--+-- >>> index 0b0010_0010 0+-- 0b0000_0010+index :: Hash -> Shift -> Int+index w s = fromIntegral $ unsafeShiftR w s .&. subkeyMask+{-# INLINE index #-} -mask :: Word -> Shift -> Bitmap+-- | Given a 'Hash' and a 'Shift' that indicates the level in the tree, compute+-- the bitmap that contains only the 'index' of the hash at this level.+--+-- The result can be used for constructing one-element 'BitmapIndexed' nodes or+-- to check whether a 'BitmapIndexed' node may possibly contain the given 'Hash'.+--+-- >>> mask 0b0010_0010 0+-- 0b0100+mask :: Hash -> Shift -> Bitmap mask w s = 1 `unsafeShiftL` index w s {-# INLINE mask #-} --- | Mask out the 'bitsPerSubkey' bits used for indexing at this level--- of the tree.-index :: Hash -> Shift -> Int-index w s = fromIntegral $ unsafeShiftR w s .&. subkeyMask-{-# INLINE index #-}+-- | This array index is computed by counting the number of bits below the+-- 'index' represented by the mask.+--+-- >>> sparseIndex 0b0110_0110 0b0010_0000+-- 2+sparseIndex+ :: Bitmap+ -- ^ Bitmap of a 'BitmapIndexed' node+ -> Bitmap+ -- ^ One-bit 'mask' corresponding to the 'index' of a hash+ -> Int+ -- ^ Index into the array of the 'BitmapIndexed' node+sparseIndex b m = popCount (b .&. (m - 1))+{-# INLINE sparseIndex #-} --- | A bitmask with the 'bitsPerSubkey' least significant bits set.+-- TODO: Should be named _(bit)map_ instead of _mask_++-- | A bitmap with the 'maxChildren' least significant bits set, i.e.+-- @0xFF_FF_FF_FF@. fullNodeMask :: Bitmap -- This needs to use 'shiftL' instead of 'unsafeShiftL', to avoid UB. -- See issue #412. fullNodeMask = complement (complement 0 `shiftL` maxChildren) {-# INLINE fullNodeMask #-}++------------------------------------------------------------------------+-- Pointer equality -- | Check if two the two arguments are the same value. N.B. This -- function might give false negatives (due to GC moving objects.)
tests/Regressions.hs view
@@ -7,6 +7,7 @@ import Control.Exception (evaluate) import Control.Monad (replicateM)+import Data.Bits (shiftL) import Data.Hashable (Hashable (..)) import Data.List (delete) import Data.Maybe (isJust, isNothing)@@ -24,6 +25,7 @@ import qualified Data.HashMap.Lazy as HML import qualified Data.HashMap.Strict as HMS+import qualified Data.HashSet as HS #if MIN_VERSION_base(4,12,0) -- nothunks requires base >= 4.12@@ -249,6 +251,18 @@ #endif ------------------------------------------------------------------------+-- Issue #420++issue420 :: Assertion+issue420 = do+ let k1 :: Int = 1 `shiftL` 10+ let k2 :: Int = 2 `shiftL` 10+ let s0 = HS.fromList [k1, k2]+ let s1 = s0 `HS.intersection` s0+ assert $ k1 `HS.member` s1+ assert $ k2 `HS.member` s1++------------------------------------------------------------------------ -- * Test list tests :: TestTree@@ -277,4 +291,5 @@ #ifdef HAVE_NOTHUNKS , testCase "issue383" issue383 #endif+ , testCase "issue420" issue420 ]
unordered-containers.cabal view
@@ -1,5 +1,5 @@ name: unordered-containers-version: 0.2.19.0+version: 0.2.19.1 synopsis: Efficient hashing-based container types description: Efficient hashing-based container types. The containers have been