{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE DeriveLift #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE PatternGuards #-}
{-# LANGUAGE RoleAnnotations #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TemplateHaskellQuotes #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeInType #-}
{-# LANGUAGE UnboxedSums #-}
{-# LANGUAGE UnboxedTuples #-}
{-# OPTIONS_GHC -fno-full-laziness -funbox-strict-fields #-}
{-# OPTIONS_HADDOCK not-home #-}
module Data.HashMap.Internal
(
HashMap(..)
, Leaf(..)
, empty
, singleton
, null
, size
, member
, lookup
, (!?)
, findWithDefault
, lookupDefault
, (!)
, insert
, insertWith
, unsafeInsert
, delete
, adjust
, update
, alter
, alterF
, isSubmapOf
, isSubmapOfBy
, union
, unionWith
, unionWithKey
, unions
, compose
, map
, mapWithKey
, traverseWithKey
, mapKeys
, difference
, differenceWith
, intersection
, intersectionWith
, intersectionWithKey
, foldr'
, foldl'
, foldrWithKey'
, foldlWithKey'
, foldr
, foldl
, foldrWithKey
, foldlWithKey
, foldMapWithKey
, mapMaybe
, mapMaybeWithKey
, filter
, filterWithKey
, keys
, elems
, toList
, fromList
, fromListWith
, fromListWithKey
, Hash
, Bitmap
, bitmapIndexedOrFull
, collision
, hash
, mask
, index
, bitsPerSubkey
, fullNodeMask
, sparseIndex
, two
, unionArrayBy
, update32
, update32M
, update32With'
, updateOrConcatWith
, updateOrConcatWithKey
, filterMapAux
, equalKeys
, equalKeys1
, lookupRecordCollision
, LookupRes(..)
, insert'
, delete'
, lookup'
, insertNewKey
, insertKeyExists
, deleteKeyExists
, insertModifying
, ptrEq
, adjust#
) where
import Control.Applicative (Const (..))
import Control.DeepSeq (NFData (..), NFData1 (..), NFData2 (..))
import Control.Monad.ST (ST, runST)
import Data.Bifoldable (Bifoldable (..))
import Data.Bits (complement, popCount, unsafeShiftL,
unsafeShiftR, (.&.), (.|.))
import Data.Coerce (coerce)
import Data.Data (Constr, Data (..), DataType)
import Data.Functor.Classes (Eq1 (..), Eq2 (..), Ord1 (..), Ord2 (..),
Read1 (..), Show1 (..), Show2 (..))
import Data.Functor.Identity (Identity (..))
import Data.HashMap.Internal.List (isPermutationBy, unorderedCompare)
import Data.Hashable (Hashable)
import Data.Hashable.Lifted (Hashable1, Hashable2)
import Data.Semigroup (Semigroup (..), stimesIdempotentMonoid)
import GHC.Exts (Int (..), Int#, TYPE, (==#))
import GHC.Stack (HasCallStack)
import Prelude hiding (filter, foldl, foldr, lookup, map,
null, pred)
import Text.Read hiding (step)
import qualified Data.Data as Data
import qualified Data.Foldable as Foldable
import qualified Data.Functor.Classes as FC
import qualified Data.HashMap.Internal.Array as A
import qualified Data.Hashable as H
import qualified Data.Hashable.Lifted as H
import qualified Data.List as List
import qualified GHC.Exts as Exts
import qualified Language.Haskell.TH.Syntax as TH
hash :: H.Hashable a => a -> Hash
hash :: a -> Hash
hash = Int -> Hash
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Hash) -> (a -> Int) -> a -> Hash
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Int
forall a. Hashable a => a -> Int
H.hash
data Leaf k v = L !k v
deriving (Leaf k v -> Leaf k v -> Bool
(Leaf k v -> Leaf k v -> Bool)
-> (Leaf k v -> Leaf k v -> Bool) -> Eq (Leaf k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v. (Eq k, Eq v) => Leaf k v -> Leaf k v -> Bool
/= :: Leaf k v -> Leaf k v -> Bool
$c/= :: forall k v. (Eq k, Eq v) => Leaf k v -> Leaf k v -> Bool
== :: Leaf k v -> Leaf k v -> Bool
$c== :: forall k v. (Eq k, Eq v) => Leaf k v -> Leaf k v -> Bool
Eq)
instance (NFData k, NFData v) => NFData (Leaf k v) where
rnf :: Leaf k v -> ()
rnf (L k :: k
k v :: v
v) = k -> ()
forall a. NFData a => a -> ()
rnf k
k () -> () -> ()
forall a b. a -> b -> b
`seq` v -> ()
forall a. NFData a => a -> ()
rnf v
v
instance (TH.Lift k, TH.Lift v) => TH.Lift (Leaf k v) where
#if MIN_VERSION_template_haskell(2,16,0)
liftTyped (L k v) = [|| L k $! v ||]
#else
lift :: Leaf k v -> Q Exp
lift (L k :: k
k v :: v
v) = [| L k $! v |]
#endif
instance NFData k => NFData1 (Leaf k) where
liftRnf :: (a -> ()) -> Leaf k a -> ()
liftRnf rnf2 :: a -> ()
rnf2 = (k -> ()) -> (a -> ()) -> Leaf k a -> ()
forall (p :: * -> * -> *) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
liftRnf2 k -> ()
forall a. NFData a => a -> ()
rnf a -> ()
rnf2
instance NFData2 Leaf where
liftRnf2 :: (a -> ()) -> (b -> ()) -> Leaf a b -> ()
liftRnf2 rnf1 :: a -> ()
rnf1 rnf2 :: b -> ()
rnf2 (L k :: a
k v :: b
v) = a -> ()
rnf1 a
k () -> () -> ()
forall a b. a -> b -> b
`seq` b -> ()
rnf2 b
v
data HashMap k v
= Empty
| BitmapIndexed !Bitmap !(A.Array (HashMap k v))
| Leaf !Hash !(Leaf k v)
| Full !(A.Array (HashMap k v))
| Collision !Hash !(A.Array (Leaf k v))
type role HashMap nominal representational
deriving instance (TH.Lift k, TH.Lift v) => TH.Lift (HashMap k v)
instance (NFData k, NFData v) => NFData (HashMap k v) where
rnf :: HashMap k v -> ()
rnf Empty = ()
rnf (BitmapIndexed _ ary :: Array (HashMap k v)
ary) = Array (HashMap k v) -> ()
forall a. NFData a => a -> ()
rnf Array (HashMap k v)
ary
rnf (Leaf _ l :: Leaf k v
l) = Leaf k v -> ()
forall a. NFData a => a -> ()
rnf Leaf k v
l
rnf (Full ary :: Array (HashMap k v)
ary) = Array (HashMap k v) -> ()
forall a. NFData a => a -> ()
rnf Array (HashMap k v)
ary
rnf (Collision _ ary :: Array (Leaf k v)
ary) = Array (Leaf k v) -> ()
forall a. NFData a => a -> ()
rnf Array (Leaf k v)
ary
instance NFData k => NFData1 (HashMap k) where
liftRnf :: (a -> ()) -> HashMap k a -> ()
liftRnf rnf2 :: a -> ()
rnf2 = (k -> ()) -> (a -> ()) -> HashMap k a -> ()
forall (p :: * -> * -> *) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
liftRnf2 k -> ()
forall a. NFData a => a -> ()
rnf a -> ()
rnf2
instance NFData2 HashMap where
liftRnf2 :: (a -> ()) -> (b -> ()) -> HashMap a b -> ()
liftRnf2 _ _ Empty = ()
liftRnf2 rnf1 :: a -> ()
rnf1 rnf2 :: b -> ()
rnf2 (BitmapIndexed _ ary :: Array (HashMap a b)
ary) = (HashMap a b -> ()) -> Array (HashMap a b) -> ()
forall (f :: * -> *) a. NFData1 f => (a -> ()) -> f a -> ()
liftRnf ((a -> ()) -> (b -> ()) -> HashMap a b -> ()
forall (p :: * -> * -> *) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
liftRnf2 a -> ()
rnf1 b -> ()
rnf2) Array (HashMap a b)
ary
liftRnf2 rnf1 :: a -> ()
rnf1 rnf2 :: b -> ()
rnf2 (Leaf _ l :: Leaf a b
l) = (a -> ()) -> (b -> ()) -> Leaf a b -> ()
forall (p :: * -> * -> *) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
liftRnf2 a -> ()
rnf1 b -> ()
rnf2 Leaf a b
l
liftRnf2 rnf1 :: a -> ()
rnf1 rnf2 :: b -> ()
rnf2 (Full ary :: Array (HashMap a b)
ary) = (HashMap a b -> ()) -> Array (HashMap a b) -> ()
forall (f :: * -> *) a. NFData1 f => (a -> ()) -> f a -> ()
liftRnf ((a -> ()) -> (b -> ()) -> HashMap a b -> ()
forall (p :: * -> * -> *) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
liftRnf2 a -> ()
rnf1 b -> ()
rnf2) Array (HashMap a b)
ary
liftRnf2 rnf1 :: a -> ()
rnf1 rnf2 :: b -> ()
rnf2 (Collision _ ary :: Array (Leaf a b)
ary) = (Leaf a b -> ()) -> Array (Leaf a b) -> ()
forall (f :: * -> *) a. NFData1 f => (a -> ()) -> f a -> ()
liftRnf ((a -> ()) -> (b -> ()) -> Leaf a b -> ()
forall (p :: * -> * -> *) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
liftRnf2 a -> ()
rnf1 b -> ()
rnf2) Array (Leaf a b)
ary
instance Functor (HashMap k) where
fmap :: (a -> b) -> HashMap k a -> HashMap k b
fmap = (a -> b) -> HashMap k a -> HashMap k b
forall v1 v2 k. (v1 -> v2) -> HashMap k v1 -> HashMap k v2
map
instance Foldable.Foldable (HashMap k) where
foldMap :: (a -> m) -> HashMap k a -> m
foldMap f :: a -> m
f = (k -> a -> m) -> HashMap k a -> m
forall m k v. Monoid m => (k -> v -> m) -> HashMap k v -> m
foldMapWithKey (\ _k :: k
_k v :: a
v -> a -> m
f a
v)
{-# INLINE foldMap #-}
foldr :: (a -> b -> b) -> b -> HashMap k a -> b
foldr = (a -> b -> b) -> b -> HashMap k a -> b
forall v a k. (v -> a -> a) -> a -> HashMap k v -> a
foldr
{-# INLINE foldr #-}
foldl :: (b -> a -> b) -> b -> HashMap k a -> b
foldl = (b -> a -> b) -> b -> HashMap k a -> b
forall a v k. (a -> v -> a) -> a -> HashMap k v -> a
foldl
{-# INLINE foldl #-}
foldr' :: (a -> b -> b) -> b -> HashMap k a -> b
foldr' = (a -> b -> b) -> b -> HashMap k a -> b
forall v a k. (v -> a -> a) -> a -> HashMap k v -> a
foldr'
{-# INLINE foldr' #-}
foldl' :: (b -> a -> b) -> b -> HashMap k a -> b
foldl' = (b -> a -> b) -> b -> HashMap k a -> b
forall a v k. (a -> v -> a) -> a -> HashMap k v -> a
foldl'
{-# INLINE foldl' #-}
null :: HashMap k a -> Bool
null = HashMap k a -> Bool
forall k a. HashMap k a -> Bool
null
{-# INLINE null #-}
length :: HashMap k a -> Int
length = HashMap k a -> Int
forall k a. HashMap k a -> Int
size
{-# INLINE length #-}
instance Bifoldable HashMap where
bifoldMap :: (a -> m) -> (b -> m) -> HashMap a b -> m
bifoldMap f :: a -> m
f g :: b -> m
g = (a -> b -> m) -> HashMap a b -> m
forall m k v. Monoid m => (k -> v -> m) -> HashMap k v -> m
foldMapWithKey (\ k :: a
k v :: b
v -> a -> m
f a
k m -> m -> m
forall a. Monoid a => a -> a -> a
`mappend` b -> m
g b
v)
{-# INLINE bifoldMap #-}
bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> HashMap a b -> c
bifoldr f :: a -> c -> c
f g :: b -> c -> c
g = (a -> b -> c -> c) -> c -> HashMap a b -> c
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey (\ k :: a
k v :: b
v acc :: c
acc -> a
k a -> c -> c
`f` (b
v b -> c -> c
`g` c
acc))
{-# INLINE bifoldr #-}
bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> HashMap a b -> c
bifoldl f :: c -> a -> c
f g :: c -> b -> c
g = (c -> a -> b -> c) -> c -> HashMap a b -> c
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey (\ acc :: c
acc k :: a
k v :: b
v -> (c
acc c -> a -> c
`f` a
k) c -> b -> c
`g` b
v)
{-# INLINE bifoldl #-}
instance (Eq k, Hashable k) => Semigroup (HashMap k v) where
<> :: HashMap k v -> HashMap k v -> HashMap k v
(<>) = HashMap k v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
HashMap k v -> HashMap k v -> HashMap k v
union
{-# INLINE (<>) #-}
stimes :: b -> HashMap k v -> HashMap k v
stimes = b -> HashMap k v -> HashMap k v
forall b a. (Integral b, Monoid a) => b -> a -> a
stimesIdempotentMonoid
{-# INLINE stimes #-}
instance (Eq k, Hashable k) => Monoid (HashMap k v) where
mempty :: HashMap k v
mempty = HashMap k v
forall k v. HashMap k v
empty
{-# INLINE mempty #-}
mappend :: HashMap k v -> HashMap k v -> HashMap k v
mappend = HashMap k v -> HashMap k v -> HashMap k v
forall a. Semigroup a => a -> a -> a
(<>)
{-# INLINE mappend #-}
instance (Data k, Data v, Eq k, Hashable k) => Data (HashMap k v) where
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> HashMap k v -> c (HashMap k v)
gfoldl f :: forall d b. Data d => c (d -> b) -> d -> c b
f z :: forall g. g -> c g
z m :: HashMap k v
m = ([(k, v)] -> HashMap k v) -> c ([(k, v)] -> HashMap k v)
forall g. g -> c g
z [(k, v)] -> HashMap k v
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList c ([(k, v)] -> HashMap k v) -> [(k, v)] -> c (HashMap k v)
forall d b. Data d => c (d -> b) -> d -> c b
`f` HashMap k v -> [(k, v)]
forall k v. HashMap k v -> [(k, v)]
toList HashMap k v
m
toConstr :: HashMap k v -> Constr
toConstr _ = Constr
fromListConstr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (HashMap k v)
gunfold k :: forall b r. Data b => c (b -> r) -> c r
k z :: forall r. r -> c r
z c :: Constr
c = case Constr -> Int
Data.constrIndex Constr
c of
1 -> c ([(k, v)] -> HashMap k v) -> c (HashMap k v)
forall b r. Data b => c (b -> r) -> c r
k (([(k, v)] -> HashMap k v) -> c ([(k, v)] -> HashMap k v)
forall r. r -> c r
z [(k, v)] -> HashMap k v
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList)
_ -> [Char] -> c (HashMap k v)
forall a. HasCallStack => [Char] -> a
error "gunfold"
dataTypeOf :: HashMap k v -> DataType
dataTypeOf _ = DataType
hashMapDataType
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (HashMap k v))
dataCast1 f :: forall d. Data d => c (t d)
f = c (t v) -> Maybe (c (HashMap k v))
forall k1 k2 (c :: k1 -> *) (t :: k2 -> k1) (t' :: k2 -> k1)
(a :: k2).
(Typeable t, Typeable t') =>
c (t a) -> Maybe (c (t' a))
Data.gcast1 c (t v)
forall d. Data d => c (t d)
f
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (HashMap k v))
dataCast2 f :: forall d e. (Data d, Data e) => c (t d e)
f = c (t k v) -> Maybe (c (HashMap k v))
forall k1 k2 k3 (c :: k1 -> *) (t :: k2 -> k3 -> k1)
(t' :: k2 -> k3 -> k1) (a :: k2) (b :: k3).
(Typeable t, Typeable t') =>
c (t a b) -> Maybe (c (t' a b))
Data.gcast2 c (t k v)
forall d e. (Data d, Data e) => c (t d e)
f
fromListConstr :: Constr
fromListConstr :: Constr
fromListConstr = DataType -> [Char] -> [[Char]] -> Fixity -> Constr
Data.mkConstr DataType
hashMapDataType "fromList" [] Fixity
Data.Prefix
hashMapDataType :: DataType
hashMapDataType :: DataType
hashMapDataType = [Char] -> [Constr] -> DataType
Data.mkDataType "Data.HashMap.Internal.HashMap" [Constr
fromListConstr]
type Hash = Word
type Bitmap = Word
type Shift = Int
instance Show2 HashMap where
liftShowsPrec2 :: (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> HashMap a b
-> ShowS
liftShowsPrec2 spk :: Int -> a -> ShowS
spk slk :: [a] -> ShowS
slk spv :: Int -> b -> ShowS
spv slv :: [b] -> ShowS
slv d :: Int
d m :: HashMap a b
m =
(Int -> [(a, b)] -> ShowS) -> [Char] -> Int -> [(a, b)] -> ShowS
forall a. (Int -> a -> ShowS) -> [Char] -> Int -> a -> ShowS
FC.showsUnaryWith ((Int -> (a, b) -> ShowS)
-> ([(a, b)] -> ShowS) -> Int -> [(a, b)] -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> (a, b) -> ShowS
sp [(a, b)] -> ShowS
sl) "fromList" Int
d (HashMap a b -> [(a, b)]
forall k v. HashMap k v -> [(k, v)]
toList HashMap a b
m)
where
sp :: Int -> (a, b) -> ShowS
sp = (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> (a, b)
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> f a b
-> ShowS
liftShowsPrec2 Int -> a -> ShowS
spk [a] -> ShowS
slk Int -> b -> ShowS
spv [b] -> ShowS
slv
sl :: [(a, b)] -> ShowS
sl = (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [(a, b)]
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [f a b]
-> ShowS
liftShowList2 Int -> a -> ShowS
spk [a] -> ShowS
slk Int -> b -> ShowS
spv [b] -> ShowS
slv
instance Show k => Show1 (HashMap k) where
liftShowsPrec :: (Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> HashMap k a -> ShowS
liftShowsPrec = (Int -> k -> ShowS)
-> ([k] -> ShowS)
-> (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> Int
-> HashMap k a
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> f a b
-> ShowS
liftShowsPrec2 Int -> k -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec [k] -> ShowS
forall a. Show a => [a] -> ShowS
showList
instance (Eq k, Hashable k, Read k) => Read1 (HashMap k) where
liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (HashMap k a)
liftReadsPrec rp :: Int -> ReadS a
rp rl :: ReadS [a]
rl = ([Char] -> ReadS (HashMap k a)) -> Int -> ReadS (HashMap k a)
forall a. ([Char] -> ReadS a) -> Int -> ReadS a
FC.readsData (([Char] -> ReadS (HashMap k a)) -> Int -> ReadS (HashMap k a))
-> ([Char] -> ReadS (HashMap k a)) -> Int -> ReadS (HashMap k a)
forall a b. (a -> b) -> a -> b
$
(Int -> ReadS [(k, a)])
-> [Char]
-> ([(k, a)] -> HashMap k a)
-> [Char]
-> ReadS (HashMap k a)
forall a t.
(Int -> ReadS a) -> [Char] -> (a -> t) -> [Char] -> ReadS t
FC.readsUnaryWith ((Int -> ReadS (k, a)) -> ReadS [(k, a)] -> Int -> ReadS [(k, a)]
forall (f :: * -> *) a.
Read1 f =>
(Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (f a)
liftReadsPrec Int -> ReadS (k, a)
rp' ReadS [(k, a)]
rl') "fromList" [(k, a)] -> HashMap k a
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList
where
rp' :: Int -> ReadS (k, a)
rp' = (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (k, a)
forall (f :: * -> *) a.
Read1 f =>
(Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (f a)
liftReadsPrec Int -> ReadS a
rp ReadS [a]
rl
rl' :: ReadS [(k, a)]
rl' = (Int -> ReadS a) -> ReadS [a] -> ReadS [(k, a)]
forall (f :: * -> *) a.
Read1 f =>
(Int -> ReadS a) -> ReadS [a] -> ReadS [f a]
liftReadList Int -> ReadS a
rp ReadS [a]
rl
instance (Eq k, Hashable k, Read k, Read e) => Read (HashMap k e) where
readPrec :: ReadPrec (HashMap k e)
readPrec = ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (HashMap k e) -> ReadPrec (HashMap k e))
-> ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a. Int -> ReadPrec a -> ReadPrec a
prec 10 (ReadPrec (HashMap k e) -> ReadPrec (HashMap k e))
-> ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a b. (a -> b) -> a -> b
$ do
Ident "fromList" <- ReadPrec Lexeme
lexP
[(k, e)]
xs <- ReadPrec [(k, e)]
forall a. Read a => ReadPrec a
readPrec
HashMap k e -> ReadPrec (HashMap k e)
forall (m :: * -> *) a. Monad m => a -> m a
return ([(k, e)] -> HashMap k e
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList [(k, e)]
xs)
readListPrec :: ReadPrec [HashMap k e]
readListPrec = ReadPrec [HashMap k e]
forall a. Read a => ReadPrec [a]
readListPrecDefault
instance (Show k, Show v) => Show (HashMap k v) where
showsPrec :: Int -> HashMap k v -> ShowS
showsPrec d :: Int
d m :: HashMap k v
m = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> 10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
[Char] -> ShowS
showString "fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, v)] -> ShowS
forall a. Show a => a -> ShowS
shows (HashMap k v -> [(k, v)]
forall k v. HashMap k v -> [(k, v)]
toList HashMap k v
m)
instance Traversable (HashMap k) where
traverse :: (a -> f b) -> HashMap k a -> f (HashMap k b)
traverse f :: a -> f b
f = (k -> a -> f b) -> HashMap k a -> f (HashMap k b)
forall (f :: * -> *) k v1 v2.
Applicative f =>
(k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)
traverseWithKey ((a -> f b) -> k -> a -> f b
forall a b. a -> b -> a
const a -> f b
f)
{-# INLINABLE traverse #-}
instance Eq2 HashMap where
liftEq2 :: (a -> b -> Bool)
-> (c -> d -> Bool) -> HashMap a c -> HashMap b d -> Bool
liftEq2 = (a -> b -> Bool)
-> (c -> d -> Bool) -> HashMap a c -> HashMap b d -> Bool
forall a b c d.
(a -> b -> Bool)
-> (c -> d -> Bool) -> HashMap a c -> HashMap b d -> Bool
equal2
instance Eq k => Eq1 (HashMap k) where
liftEq :: (a -> b -> Bool) -> HashMap k a -> HashMap k b -> Bool
liftEq = (a -> b -> Bool) -> HashMap k a -> HashMap k b -> Bool
forall k v v'.
Eq k =>
(v -> v' -> Bool) -> HashMap k v -> HashMap k v' -> Bool
equal1
instance (Eq k, Eq v) => Eq (HashMap k v) where
== :: HashMap k v -> HashMap k v -> Bool
(==) = (v -> v -> Bool) -> HashMap k v -> HashMap k v -> Bool
forall k v v'.
Eq k =>
(v -> v' -> Bool) -> HashMap k v -> HashMap k v' -> Bool
equal1 v -> v -> Bool
forall a. Eq a => a -> a -> Bool
(==)
equal1 :: Eq k
=> (v -> v' -> Bool)
-> HashMap k v -> HashMap k v' -> Bool
equal1 :: (v -> v' -> Bool) -> HashMap k v -> HashMap k v' -> Bool
equal1 eq :: v -> v' -> Bool
eq = HashMap k v -> HashMap k v' -> Bool
go
where
go :: HashMap k v -> HashMap k v' -> Bool
go Empty Empty = Bool
True
go (BitmapIndexed bm1 :: Hash
bm1 ary1 :: Array (HashMap k v)
ary1) (BitmapIndexed bm2 :: Hash
bm2 ary2 :: Array (HashMap k v')
ary2)
= Hash
bm1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
bm2 Bool -> Bool -> Bool
&& (HashMap k v -> HashMap k v' -> Bool)
-> Array (HashMap k v) -> Array (HashMap k v') -> Bool
forall a b. (a -> b -> Bool) -> Array a -> Array b -> Bool
A.sameArray1 HashMap k v -> HashMap k v' -> Bool
go Array (HashMap k v)
ary1 Array (HashMap k v')
ary2
go (Leaf h1 :: Hash
h1 l1 :: Leaf k v
l1) (Leaf h2 :: Hash
h2 l2 :: Leaf k v'
l2) = Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 Bool -> Bool -> Bool
&& Leaf k v -> Leaf k v' -> Bool
leafEq Leaf k v
l1 Leaf k v'
l2
go (Full ary1 :: Array (HashMap k v)
ary1) (Full ary2 :: Array (HashMap k v')
ary2) = (HashMap k v -> HashMap k v' -> Bool)
-> Array (HashMap k v) -> Array (HashMap k v') -> Bool
forall a b. (a -> b -> Bool) -> Array a -> Array b -> Bool
A.sameArray1 HashMap k v -> HashMap k v' -> Bool
go Array (HashMap k v)
ary1 Array (HashMap k v')
ary2
go (Collision h1 :: Hash
h1 ary1 :: Array (Leaf k v)
ary1) (Collision h2 :: Hash
h2 ary2 :: Array (Leaf k v')
ary2)
= Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 Bool -> Bool -> Bool
&& (Leaf k v -> Leaf k v' -> Bool)
-> [Leaf k v] -> [Leaf k v'] -> Bool
forall a b. (a -> b -> Bool) -> [a] -> [b] -> Bool
isPermutationBy Leaf k v -> Leaf k v' -> Bool
leafEq (Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList Array (Leaf k v)
ary1) (Array (Leaf k v') -> [Leaf k v']
forall a. Array a -> [a]
A.toList Array (Leaf k v')
ary2)
go _ _ = Bool
False
leafEq :: Leaf k v -> Leaf k v' -> Bool
leafEq (L k1 :: k
k1 v1 :: v
v1) (L k2 :: k
k2 v2 :: v'
v2) = k
k1 k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k2 Bool -> Bool -> Bool
&& v -> v' -> Bool
eq v
v1 v'
v2
equal2 :: (k -> k' -> Bool) -> (v -> v' -> Bool)
-> HashMap k v -> HashMap k' v' -> Bool
equal2 :: (k -> k' -> Bool)
-> (v -> v' -> Bool) -> HashMap k v -> HashMap k' v' -> Bool
equal2 eqk :: k -> k' -> Bool
eqk eqv :: v -> v' -> Bool
eqv t1 :: HashMap k v
t1 t2 :: HashMap k' v'
t2 = [HashMap k v] -> [HashMap k' v'] -> Bool
go (HashMap k v -> [HashMap k v] -> [HashMap k v]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k v
t1 []) (HashMap k' v' -> [HashMap k' v'] -> [HashMap k' v']
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k' v'
t2 [])
where
go :: [HashMap k v] -> [HashMap k' v'] -> Bool
go (Leaf k1 :: Hash
k1 l1 :: Leaf k v
l1 : tl1 :: [HashMap k v]
tl1) (Leaf k2 :: Hash
k2 l2 :: Leaf k' v'
l2 : tl2 :: [HashMap k' v']
tl2)
| Hash
k1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
k2 Bool -> Bool -> Bool
&&
Leaf k v -> Leaf k' v' -> Bool
leafEq Leaf k v
l1 Leaf k' v'
l2
= [HashMap k v] -> [HashMap k' v'] -> Bool
go [HashMap k v]
tl1 [HashMap k' v']
tl2
go (Collision k1 :: Hash
k1 ary1 :: Array (Leaf k v)
ary1 : tl1 :: [HashMap k v]
tl1) (Collision k2 :: Hash
k2 ary2 :: Array (Leaf k' v')
ary2 : tl2 :: [HashMap k' v']
tl2)
| Hash
k1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
k2 Bool -> Bool -> Bool
&&
Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Array (Leaf k' v') -> Int
forall a. Array a -> Int
A.length Array (Leaf k' v')
ary2 Bool -> Bool -> Bool
&&
(Leaf k v -> Leaf k' v' -> Bool)
-> [Leaf k v] -> [Leaf k' v'] -> Bool
forall a b. (a -> b -> Bool) -> [a] -> [b] -> Bool
isPermutationBy Leaf k v -> Leaf k' v' -> Bool
leafEq (Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList Array (Leaf k v)
ary1) (Array (Leaf k' v') -> [Leaf k' v']
forall a. Array a -> [a]
A.toList Array (Leaf k' v')
ary2)
= [HashMap k v] -> [HashMap k' v'] -> Bool
go [HashMap k v]
tl1 [HashMap k' v']
tl2
go [] [] = Bool
True
go _ _ = Bool
False
leafEq :: Leaf k v -> Leaf k' v' -> Bool
leafEq (L k :: k
k v :: v
v) (L k' :: k'
k' v' :: v'
v') = k -> k' -> Bool
eqk k
k k'
k' Bool -> Bool -> Bool
&& v -> v' -> Bool
eqv v
v v'
v'
instance Ord2 HashMap where
liftCompare2 :: (a -> b -> Ordering)
-> (c -> d -> Ordering) -> HashMap a c -> HashMap b d -> Ordering
liftCompare2 = (a -> b -> Ordering)
-> (c -> d -> Ordering) -> HashMap a c -> HashMap b d -> Ordering
forall a b c d.
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> HashMap a c -> HashMap b d -> Ordering
cmp
instance Ord k => Ord1 (HashMap k) where
liftCompare :: (a -> b -> Ordering) -> HashMap k a -> HashMap k b -> Ordering
liftCompare = (k -> k -> Ordering)
-> (a -> b -> Ordering) -> HashMap k a -> HashMap k b -> Ordering
forall a b c d.
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> HashMap a c -> HashMap b d -> Ordering
cmp k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
instance (Ord k, Ord v) => Ord (HashMap k v) where
compare :: HashMap k v -> HashMap k v -> Ordering
compare = (k -> k -> Ordering)
-> (v -> v -> Ordering) -> HashMap k v -> HashMap k v -> Ordering
forall a b c d.
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> HashMap a c -> HashMap b d -> Ordering
cmp k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare v -> v -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
cmp :: (k -> k' -> Ordering) -> (v -> v' -> Ordering)
-> HashMap k v -> HashMap k' v' -> Ordering
cmp :: (k -> k' -> Ordering)
-> (v -> v' -> Ordering)
-> HashMap k v
-> HashMap k' v'
-> Ordering
cmp cmpk :: k -> k' -> Ordering
cmpk cmpv :: v -> v' -> Ordering
cmpv t1 :: HashMap k v
t1 t2 :: HashMap k' v'
t2 = [HashMap k v] -> [HashMap k' v'] -> Ordering
go (HashMap k v -> [HashMap k v] -> [HashMap k v]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k v
t1 []) (HashMap k' v' -> [HashMap k' v'] -> [HashMap k' v']
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k' v'
t2 [])
where
go :: [HashMap k v] -> [HashMap k' v'] -> Ordering
go (Leaf k1 :: Hash
k1 l1 :: Leaf k v
l1 : tl1 :: [HashMap k v]
tl1) (Leaf k2 :: Hash
k2 l2 :: Leaf k' v'
l2 : tl2 :: [HashMap k' v']
tl2)
= Hash -> Hash -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Hash
k1 Hash
k2 Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend`
Leaf k v -> Leaf k' v' -> Ordering
leafCompare Leaf k v
l1 Leaf k' v'
l2 Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend`
[HashMap k v] -> [HashMap k' v'] -> Ordering
go [HashMap k v]
tl1 [HashMap k' v']
tl2
go (Collision k1 :: Hash
k1 ary1 :: Array (Leaf k v)
ary1 : tl1 :: [HashMap k v]
tl1) (Collision k2 :: Hash
k2 ary2 :: Array (Leaf k' v')
ary2 : tl2 :: [HashMap k' v']
tl2)
= Hash -> Hash -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Hash
k1 Hash
k2 Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend`
Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary1) (Array (Leaf k' v') -> Int
forall a. Array a -> Int
A.length Array (Leaf k' v')
ary2) Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend`
(Leaf k v -> Leaf k' v' -> Ordering)
-> [Leaf k v] -> [Leaf k' v'] -> Ordering
forall a b. (a -> b -> Ordering) -> [a] -> [b] -> Ordering
unorderedCompare Leaf k v -> Leaf k' v' -> Ordering
leafCompare (Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList Array (Leaf k v)
ary1) (Array (Leaf k' v') -> [Leaf k' v']
forall a. Array a -> [a]
A.toList Array (Leaf k' v')
ary2) Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend`
[HashMap k v] -> [HashMap k' v'] -> Ordering
go [HashMap k v]
tl1 [HashMap k' v']
tl2
go (Leaf _ _ : _) (Collision _ _ : _) = Ordering
LT
go (Collision _ _ : _) (Leaf _ _ : _) = Ordering
GT
go [] [] = Ordering
EQ
go [] _ = Ordering
LT
go _ [] = Ordering
GT
go _ _ = [Char] -> Ordering
forall a. HasCallStack => [Char] -> a
error "cmp: Should never happen, toList' includes non Leaf / Collision"
leafCompare :: Leaf k v -> Leaf k' v' -> Ordering
leafCompare (L k :: k
k v :: v
v) (L k' :: k'
k' v' :: v'
v') = k -> k' -> Ordering
cmpk k
k k'
k' Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend` v -> v' -> Ordering
cmpv v
v v'
v'
equalKeys1 :: (k -> k' -> Bool) -> HashMap k v -> HashMap k' v' -> Bool
equalKeys1 :: (k -> k' -> Bool) -> HashMap k v -> HashMap k' v' -> Bool
equalKeys1 eq :: k -> k' -> Bool
eq t1 :: HashMap k v
t1 t2 :: HashMap k' v'
t2 = [HashMap k v] -> [HashMap k' v'] -> Bool
go (HashMap k v -> [HashMap k v] -> [HashMap k v]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k v
t1 []) (HashMap k' v' -> [HashMap k' v'] -> [HashMap k' v']
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k' v'
t2 [])
where
go :: [HashMap k v] -> [HashMap k' v'] -> Bool
go (Leaf k1 :: Hash
k1 l1 :: Leaf k v
l1 : tl1 :: [HashMap k v]
tl1) (Leaf k2 :: Hash
k2 l2 :: Leaf k' v'
l2 : tl2 :: [HashMap k' v']
tl2)
| Hash
k1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
k2 Bool -> Bool -> Bool
&& Leaf k v -> Leaf k' v' -> Bool
leafEq Leaf k v
l1 Leaf k' v'
l2
= [HashMap k v] -> [HashMap k' v'] -> Bool
go [HashMap k v]
tl1 [HashMap k' v']
tl2
go (Collision k1 :: Hash
k1 ary1 :: Array (Leaf k v)
ary1 : tl1 :: [HashMap k v]
tl1) (Collision k2 :: Hash
k2 ary2 :: Array (Leaf k' v')
ary2 : tl2 :: [HashMap k' v']
tl2)
| Hash
k1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
k2 Bool -> Bool -> Bool
&& Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Array (Leaf k' v') -> Int
forall a. Array a -> Int
A.length Array (Leaf k' v')
ary2 Bool -> Bool -> Bool
&&
(Leaf k v -> Leaf k' v' -> Bool)
-> [Leaf k v] -> [Leaf k' v'] -> Bool
forall a b. (a -> b -> Bool) -> [a] -> [b] -> Bool
isPermutationBy Leaf k v -> Leaf k' v' -> Bool
leafEq (Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList Array (Leaf k v)
ary1) (Array (Leaf k' v') -> [Leaf k' v']
forall a. Array a -> [a]
A.toList Array (Leaf k' v')
ary2)
= [HashMap k v] -> [HashMap k' v'] -> Bool
go [HashMap k v]
tl1 [HashMap k' v']
tl2
go [] [] = Bool
True
go _ _ = Bool
False
leafEq :: Leaf k v -> Leaf k' v' -> Bool
leafEq (L k :: k
k _) (L k' :: k'
k' _) = k -> k' -> Bool
eq k
k k'
k'
equalKeys :: Eq k => HashMap k v -> HashMap k v' -> Bool
equalKeys :: HashMap k v -> HashMap k v' -> Bool
equalKeys = HashMap k v -> HashMap k v' -> Bool
forall k v v'. Eq k => HashMap k v -> HashMap k v' -> Bool
go
where
go :: Eq k => HashMap k v -> HashMap k v' -> Bool
go :: HashMap k v -> HashMap k v' -> Bool
go Empty Empty = Bool
True
go (BitmapIndexed bm1 :: Hash
bm1 ary1 :: Array (HashMap k v)
ary1) (BitmapIndexed bm2 :: Hash
bm2 ary2 :: Array (HashMap k v')
ary2)
= Hash
bm1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
bm2 Bool -> Bool -> Bool
&& (HashMap k v -> HashMap k v' -> Bool)
-> Array (HashMap k v) -> Array (HashMap k v') -> Bool
forall a b. (a -> b -> Bool) -> Array a -> Array b -> Bool
A.sameArray1 HashMap k v -> HashMap k v' -> Bool
forall k v v'. Eq k => HashMap k v -> HashMap k v' -> Bool
go Array (HashMap k v)
ary1 Array (HashMap k v')
ary2
go (Leaf h1 :: Hash
h1 l1 :: Leaf k v
l1) (Leaf h2 :: Hash
h2 l2 :: Leaf k v'
l2) = Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 Bool -> Bool -> Bool
&& Leaf k v -> Leaf k v' -> Bool
forall a v v. Eq a => Leaf a v -> Leaf a v -> Bool
leafEq Leaf k v
l1 Leaf k v'
l2
go (Full ary1 :: Array (HashMap k v)
ary1) (Full ary2 :: Array (HashMap k v')
ary2) = (HashMap k v -> HashMap k v' -> Bool)
-> Array (HashMap k v) -> Array (HashMap k v') -> Bool
forall a b. (a -> b -> Bool) -> Array a -> Array b -> Bool
A.sameArray1 HashMap k v -> HashMap k v' -> Bool
forall k v v'. Eq k => HashMap k v -> HashMap k v' -> Bool
go Array (HashMap k v)
ary1 Array (HashMap k v')
ary2
go (Collision h1 :: Hash
h1 ary1 :: Array (Leaf k v)
ary1) (Collision h2 :: Hash
h2 ary2 :: Array (Leaf k v')
ary2)
= Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 Bool -> Bool -> Bool
&& (Leaf k v -> Leaf k v' -> Bool)
-> [Leaf k v] -> [Leaf k v'] -> Bool
forall a b. (a -> b -> Bool) -> [a] -> [b] -> Bool
isPermutationBy Leaf k v -> Leaf k v' -> Bool
forall a v v. Eq a => Leaf a v -> Leaf a v -> Bool
leafEq (Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList Array (Leaf k v)
ary1) (Array (Leaf k v') -> [Leaf k v']
forall a. Array a -> [a]
A.toList Array (Leaf k v')
ary2)
go _ _ = Bool
False
leafEq :: Leaf a v -> Leaf a v -> Bool
leafEq (L k1 :: a
k1 _) (L k2 :: a
k2 _) = a
k1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
k2
instance Hashable2 HashMap where
liftHashWithSalt2 :: (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> HashMap a b -> Int
liftHashWithSalt2 hk :: Int -> a -> Int
hk hv :: Int -> b -> Int
hv salt :: Int
salt hm :: HashMap a b
hm = Int -> [HashMap a b] -> Int
go Int
salt (HashMap a b -> [HashMap a b] -> [HashMap a b]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap a b
hm [])
where
go :: Int -> [HashMap a b] -> Int
go s :: Int
s [] = Int
s
go s :: Int
s (Leaf _ l :: Leaf a b
l : tl :: [HashMap a b]
tl)
= Int
s Int -> Leaf a b -> Int
`hashLeafWithSalt` Leaf a b
l Int -> [HashMap a b] -> Int
`go` [HashMap a b]
tl
go s :: Int
s (Collision h :: Hash
h a :: Array (Leaf a b)
a : tl :: [HashMap a b]
tl)
= (Int
s Int -> Hash -> Int
forall a. Hashable a => Int -> a -> Int
`H.hashWithSalt` Hash
h) Int -> Array (Leaf a b) -> Int
`hashCollisionWithSalt` Array (Leaf a b)
a Int -> [HashMap a b] -> Int
`go` [HashMap a b]
tl
go s :: Int
s (_ : tl :: [HashMap a b]
tl) = Int
s Int -> [HashMap a b] -> Int
`go` [HashMap a b]
tl
hashLeafWithSalt :: Int -> Leaf a b -> Int
hashLeafWithSalt s :: Int
s (L k :: a
k v :: b
v) = (Int
s Int -> a -> Int
`hk` a
k) Int -> b -> Int
`hv` b
v
hashCollisionWithSalt :: Int -> Array (Leaf a b) -> Int
hashCollisionWithSalt s :: Int
s
= (Int -> Int -> Int) -> Int -> [Int] -> Int
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
H.hashWithSalt Int
s ([Int] -> Int)
-> (Array (Leaf a b) -> [Int]) -> Array (Leaf a b) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Array (Leaf a b) -> [Int]
arrayHashesSorted Int
s
arrayHashesSorted :: Int -> Array (Leaf a b) -> [Int]
arrayHashesSorted s :: Int
s = [Int] -> [Int]
forall a. Ord a => [a] -> [a]
List.sort ([Int] -> [Int])
-> (Array (Leaf a b) -> [Int]) -> Array (Leaf a b) -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Leaf a b -> Int) -> [Leaf a b] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
List.map (Int -> Leaf a b -> Int
hashLeafWithSalt Int
s) ([Leaf a b] -> [Int])
-> (Array (Leaf a b) -> [Leaf a b]) -> Array (Leaf a b) -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Array (Leaf a b) -> [Leaf a b]
forall a. Array a -> [a]
A.toList
instance (Hashable k) => Hashable1 (HashMap k) where
liftHashWithSalt :: (Int -> a -> Int) -> Int -> HashMap k a -> Int
liftHashWithSalt = (Int -> k -> Int) -> (Int -> a -> Int) -> Int -> HashMap k a -> Int
forall (t :: * -> * -> *) a b.
Hashable2 t =>
(Int -> a -> Int) -> (Int -> b -> Int) -> Int -> t a b -> Int
H.liftHashWithSalt2 Int -> k -> Int
forall a. Hashable a => Int -> a -> Int
H.hashWithSalt
instance (Hashable k, Hashable v) => Hashable (HashMap k v) where
hashWithSalt :: Int -> HashMap k v -> Int
hashWithSalt salt :: Int
salt hm :: HashMap k v
hm = Int -> HashMap k v -> Int
go Int
salt HashMap k v
hm
where
go :: Int -> HashMap k v -> Int
go :: Int -> HashMap k v -> Int
go s :: Int
s Empty = Int
s
go s :: Int
s (BitmapIndexed _ a :: Array (HashMap k v)
a) = (Int -> HashMap k v -> Int) -> Int -> Array (HashMap k v) -> Int
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' Int -> HashMap k v -> Int
go Int
s Array (HashMap k v)
a
go s :: Int
s (Leaf h :: Hash
h (L _ v :: v
v))
= Int
s Int -> Hash -> Int
forall a. Hashable a => Int -> a -> Int
`H.hashWithSalt` Hash
h Int -> v -> Int
forall a. Hashable a => Int -> a -> Int
`H.hashWithSalt` v
v
go s :: Int
s (Full a :: Array (HashMap k v)
a) = (Int -> HashMap k v -> Int) -> Int -> Array (HashMap k v) -> Int
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' Int -> HashMap k v -> Int
go Int
s Array (HashMap k v)
a
go s :: Int
s (Collision h :: Hash
h a :: Array (Leaf k v)
a)
= (Int
s Int -> Hash -> Int
forall a. Hashable a => Int -> a -> Int
`H.hashWithSalt` Hash
h) Int -> Array (Leaf k v) -> Int
`hashCollisionWithSalt` Array (Leaf k v)
a
hashLeafWithSalt :: Int -> Leaf k v -> Int
hashLeafWithSalt :: Int -> Leaf k v -> Int
hashLeafWithSalt s :: Int
s (L k :: k
k v :: v
v) = Int
s Int -> k -> Int
forall a. Hashable a => Int -> a -> Int
`H.hashWithSalt` k
k Int -> v -> Int
forall a. Hashable a => Int -> a -> Int
`H.hashWithSalt` v
v
hashCollisionWithSalt :: Int -> A.Array (Leaf k v) -> Int
hashCollisionWithSalt :: Int -> Array (Leaf k v) -> Int
hashCollisionWithSalt s :: Int
s
= (Int -> Int -> Int) -> Int -> [Int] -> Int
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
H.hashWithSalt Int
s ([Int] -> Int)
-> (Array (Leaf k v) -> [Int]) -> Array (Leaf k v) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Array (Leaf k v) -> [Int]
arrayHashesSorted Int
s
arrayHashesSorted :: Int -> A.Array (Leaf k v) -> [Int]
arrayHashesSorted :: Int -> Array (Leaf k v) -> [Int]
arrayHashesSorted s :: Int
s = [Int] -> [Int]
forall a. Ord a => [a] -> [a]
List.sort ([Int] -> [Int])
-> (Array (Leaf k v) -> [Int]) -> Array (Leaf k v) -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Leaf k v -> Int) -> [Leaf k v] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
List.map (Int -> Leaf k v -> Int
hashLeafWithSalt Int
s) ([Leaf k v] -> [Int])
-> (Array (Leaf k v) -> [Leaf k v]) -> Array (Leaf k v) -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList
toList' :: HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' :: HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' (BitmapIndexed _ ary :: Array (HashMap k v)
ary) a :: [HashMap k v]
a = (HashMap k v -> [HashMap k v] -> [HashMap k v])
-> [HashMap k v] -> Array (HashMap k v) -> [HashMap k v]
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr HashMap k v -> [HashMap k v] -> [HashMap k v]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' [HashMap k v]
a Array (HashMap k v)
ary
toList' (Full ary :: Array (HashMap k v)
ary) a :: [HashMap k v]
a = (HashMap k v -> [HashMap k v] -> [HashMap k v])
-> [HashMap k v] -> Array (HashMap k v) -> [HashMap k v]
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr HashMap k v -> [HashMap k v] -> [HashMap k v]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' [HashMap k v]
a Array (HashMap k v)
ary
toList' l :: HashMap k v
l@(Leaf _ _) a :: [HashMap k v]
a = HashMap k v
l HashMap k v -> [HashMap k v] -> [HashMap k v]
forall a. a -> [a] -> [a]
: [HashMap k v]
a
toList' c :: HashMap k v
c@(Collision _ _) a :: [HashMap k v]
a = HashMap k v
c HashMap k v -> [HashMap k v] -> [HashMap k v]
forall a. a -> [a] -> [a]
: [HashMap k v]
a
toList' Empty a :: [HashMap k v]
a = [HashMap k v]
a
isLeafOrCollision :: HashMap k v -> Bool
isLeafOrCollision :: HashMap k v -> Bool
isLeafOrCollision (Leaf _ _) = Bool
True
isLeafOrCollision (Collision _ _) = Bool
True
isLeafOrCollision _ = Bool
False
empty :: HashMap k v
empty :: HashMap k v
empty = HashMap k v
forall k v. HashMap k v
Empty
singleton :: (Hashable k) => k -> v -> HashMap k v
singleton :: k -> v -> HashMap k v
singleton k :: k
k v :: v
v = Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf (k -> Hash
forall a. Hashable a => a -> Hash
hash k
k) (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
v)
null :: HashMap k v -> Bool
null :: HashMap k v -> Bool
null Empty = Bool
True
null _ = Bool
False
size :: HashMap k v -> Int
size :: HashMap k v -> Int
size t :: HashMap k v
t = HashMap k v -> Int -> Int
forall k v. HashMap k v -> Int -> Int
go HashMap k v
t 0
where
go :: HashMap k v -> Int -> Int
go Empty !Int
n = Int
n
go (Leaf _ _) n :: Int
n = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1
go (BitmapIndexed _ ary :: Array (HashMap k v)
ary) n :: Int
n = (Int -> HashMap k v -> Int) -> Int -> Array (HashMap k v) -> Int
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' ((HashMap k v -> Int -> Int) -> Int -> HashMap k v -> Int
forall a b c. (a -> b -> c) -> b -> a -> c
flip HashMap k v -> Int -> Int
go) Int
n Array (HashMap k v)
ary
go (Full ary :: Array (HashMap k v)
ary) n :: Int
n = (Int -> HashMap k v -> Int) -> Int -> Array (HashMap k v) -> Int
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' ((HashMap k v -> Int -> Int) -> Int -> HashMap k v -> Int
forall a b c. (a -> b -> c) -> b -> a -> c
flip HashMap k v -> Int -> Int
go) Int
n Array (HashMap k v)
ary
go (Collision _ ary :: Array (Leaf k v)
ary) n :: Int
n = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary
member :: (Eq k, Hashable k) => k -> HashMap k a -> Bool
member :: k -> HashMap k a -> Bool
member k :: k
k m :: HashMap k a
m = case k -> HashMap k a -> Maybe a
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k a
m of
Nothing -> Bool
False
Just _ -> Bool
True
{-# INLINABLE member #-}
lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup :: k -> HashMap k v -> Maybe v
lookup k :: k
k m :: HashMap k v
m = case k -> HashMap k v -> (# (# #) | v #)
forall k v.
(Eq k, Hashable k) =>
k -> HashMap k v -> (# (# #) | v #)
lookup# k
k HashMap k v
m of
(# (# #) | #) -> Maybe v
forall a. Maybe a
Nothing
(# | v
a #) -> v -> Maybe v
forall a. a -> Maybe a
Just v
a
{-# INLINE lookup #-}
lookup# :: (Eq k, Hashable k) => k -> HashMap k v -> (# (# #) | v #)
lookup# :: k -> HashMap k v -> (# (# #) | v #)
lookup# k :: k
k m :: HashMap k v
m = ((# #) -> (# (# #) | v #))
-> (v -> Int -> (# (# #) | v #))
-> Hash
-> k
-> Int
-> HashMap k v
-> (# (# #) | v #)
forall r k v.
Eq k =>
((# #) -> r)
-> (v -> Int -> r) -> Hash -> k -> Int -> HashMap k v -> r
lookupCont (\_ -> (# (# #) | #)) (\v :: v
v _i :: Int
_i -> (# | v
v #)) (k -> Hash
forall a. Hashable a => a -> Hash
hash k
k) k
k 0 HashMap k v
m
{-# INLINABLE lookup# #-}
lookup' :: Eq k => Hash -> k -> HashMap k v -> Maybe v
lookup' :: Hash -> k -> HashMap k v -> Maybe v
lookup' h :: Hash
h k :: k
k m :: HashMap k v
m = case Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
forall k v.
Eq k =>
Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
lookupRecordCollision# Hash
h k
k HashMap k v
m of
(# (# #) | #) -> Maybe v
forall a. Maybe a
Nothing
(# | (# a :: v
a, _i :: Int#
_i #) #) -> v -> Maybe v
forall a. a -> Maybe a
Just v
a
{-# INLINE lookup' #-}
data LookupRes a = Absent | Present a !Int
lookupRecordCollision :: Eq k => Hash -> k -> HashMap k v -> LookupRes v
lookupRecordCollision :: Hash -> k -> HashMap k v -> LookupRes v
lookupRecordCollision h :: Hash
h k :: k
k m :: HashMap k v
m = case Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
forall k v.
Eq k =>
Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
lookupRecordCollision# Hash
h k
k HashMap k v
m of
(# (# #) | #) -> LookupRes v
forall a. LookupRes a
Absent
(# | (# a :: v
a, i :: Int#
i #) #) -> v -> Int -> LookupRes v
forall a. a -> Int -> LookupRes a
Present v
a (Int# -> Int
I# Int#
i)
{-# INLINE lookupRecordCollision #-}
lookupRecordCollision# :: Eq k => Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
lookupRecordCollision# :: Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
lookupRecordCollision# h :: Hash
h k :: k
k m :: HashMap k v
m =
((# #) -> (# (# #) | (# v, Int# #) #))
-> (v -> Int -> (# (# #) | (# v, Int# #) #))
-> Hash
-> k
-> Int
-> HashMap k v
-> (# (# #) | (# v, Int# #) #)
forall r k v.
Eq k =>
((# #) -> r)
-> (v -> Int -> r) -> Hash -> k -> Int -> HashMap k v -> r
lookupCont (\_ -> (# (# #) | #)) (\v :: v
v (I# i :: Int#
i) -> (# | (# v
v, Int#
i #) #)) Hash
h k
k 0 HashMap k v
m
{-# INLINABLE lookupRecordCollision# #-}
lookupCont ::
forall rep (r :: TYPE rep) k v.
Eq k
=> ((# #) -> r)
-> (v -> Int -> r)
-> Hash
-> k
-> Int
-> HashMap k v -> r
lookupCont :: ((# #) -> r)
-> (v -> Int -> r) -> Hash -> k -> Int -> HashMap k v -> r
lookupCont absent :: (# #) -> r
absent present :: v -> Int -> r
present !Hash
h0 !k
k0 !Int
s0 !HashMap k v
m0 = Eq k => Hash -> k -> Int -> HashMap k v -> r
Hash -> k -> Int -> HashMap k v -> r
go Hash
h0 k
k0 Int
s0 HashMap k v
m0
where
go :: Eq k => Hash -> k -> Int -> HashMap k v -> r
go :: Hash -> k -> Int -> HashMap k v -> r
go !Hash
_ !k
_ !Int
_ Empty = (# #) -> r
absent (# #)
go h :: Hash
h k :: k
k _ (Leaf hx :: Hash
hx (L kx :: k
kx x :: v
x))
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hx Bool -> Bool -> Bool
&& k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx = v -> Int -> r
present v
x (-1)
| Bool
otherwise = (# #) -> r
absent (# #)
go h :: Hash
h k :: k
k s :: Int
s (BitmapIndexed b :: Hash
b v :: Array (HashMap k v)
v)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = (# #) -> r
absent (# #)
| Bool
otherwise =
Eq k => Hash -> k -> Int -> HashMap k v -> r
Hash -> k -> Int -> HashMap k v -> r
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) (Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
v (Hash -> Hash -> Int
sparseIndex Hash
b Hash
m))
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
go h :: Hash
h k :: k
k s :: Int
s (Full v :: Array (HashMap k v)
v) =
Eq k => Hash -> k -> Int -> HashMap k v -> r
Hash -> k -> Int -> HashMap k v -> r
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) (Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
v (Hash -> Int -> Int
index Hash
h Int
s))
go h :: Hash
h k :: k
k _ (Collision hx :: Hash
hx v :: Array (Leaf k v)
v)
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hx = ((# #) -> r) -> (v -> Int -> r) -> k -> Array (Leaf k v) -> r
forall r k v.
Eq k =>
((# #) -> r) -> (v -> Int -> r) -> k -> Array (Leaf k v) -> r
lookupInArrayCont (# #) -> r
absent v -> Int -> r
present k
k Array (Leaf k v)
v
| Bool
otherwise = (# #) -> r
absent (# #)
{-# INLINE lookupCont #-}
(!?) :: (Eq k, Hashable k) => HashMap k v -> k -> Maybe v
!? :: HashMap k v -> k -> Maybe v
(!?) m :: HashMap k v
m k :: k
k = k -> HashMap k v -> Maybe v
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k v
m
{-# INLINE (!?) #-}
findWithDefault :: (Eq k, Hashable k)
=> v
-> k -> HashMap k v -> v
findWithDefault :: v -> k -> HashMap k v -> v
findWithDefault def :: v
def k :: k
k t :: HashMap k v
t = case k -> HashMap k v -> Maybe v
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k v
t of
Just v :: v
v -> v
v
_ -> v
def
{-# INLINABLE findWithDefault #-}
lookupDefault :: (Eq k, Hashable k)
=> v
-> k -> HashMap k v -> v
lookupDefault :: v -> k -> HashMap k v -> v
lookupDefault def :: v
def k :: k
k t :: HashMap k v
t = v -> k -> HashMap k v -> v
forall k v. (Eq k, Hashable k) => v -> k -> HashMap k v -> v
findWithDefault v
def k
k HashMap k v
t
{-# INLINE lookupDefault #-}
(!) :: (Eq k, Hashable k, HasCallStack) => HashMap k v -> k -> v
(!) m :: HashMap k v
m k :: k
k = case k -> HashMap k v -> Maybe v
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k v
m of
Just v :: v
v -> v
v
Nothing -> [Char] -> v
forall a. HasCallStack => [Char] -> a
error "Data.HashMap.Internal.(!): key not found"
{-# INLINABLE (!) #-}
infixl 9 !
collision :: Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision :: Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision h :: Hash
h !Leaf k v
e1 !Leaf k v
e2 =
let v :: Array (Leaf k v)
v = (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall e. (forall s. ST s (MArray s e)) -> Array e
A.run ((forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v))
-> (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall a b. (a -> b) -> a -> b
$ do MArray s (Leaf k v)
mary <- Int -> Leaf k v -> ST s (MArray s (Leaf k v))
forall a s. Int -> a -> ST s (MArray s a)
A.new 2 Leaf k v
e1
MArray s (Leaf k v) -> Int -> Leaf k v -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (Leaf k v)
mary 1 Leaf k v
e2
MArray s (Leaf k v) -> ST s (MArray s (Leaf k v))
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s (Leaf k v)
mary
in Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h Array (Leaf k v)
v
{-# INLINE collision #-}
bitmapIndexedOrFull :: Bitmap -> A.Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull :: Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull b :: Hash
b ary :: Array (HashMap k v)
ary
| Hash
b Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
fullNodeMask = Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary
| Bool
otherwise = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b Array (HashMap k v)
ary
{-# INLINE bitmapIndexedOrFull #-}
insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v
insert :: k -> v -> HashMap k v -> HashMap k v
insert k :: k
k v :: v
v m :: HashMap k v
m = Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> v -> HashMap k v -> HashMap k v
insert' (k -> Hash
forall a. Hashable a => a -> Hash
hash k
k) k
k v
v HashMap k v
m
{-# INLINABLE insert #-}
insert' :: Eq k => Hash -> k -> v -> HashMap k v -> HashMap k v
insert' :: Hash -> k -> v -> HashMap k v -> HashMap k v
insert' h0 :: Hash
h0 k0 :: k
k0 v0 :: v
v0 m0 :: HashMap k v
m0 = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
forall k v.
Eq k =>
Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 v
v0 0 HashMap k v
m0
where
go :: Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go !Hash
h !k
k x :: v
x !Int
_ Empty = Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Leaf hy :: Hash
hy l :: Leaf k v
l@(L ky :: k
ky y :: v
y))
| Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h = if k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k
then if v
x v -> v -> Bool
forall a. a -> a -> Bool
`ptrEq` v
y
then HashMap k v
t
else Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
else Hash -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision Hash
h Leaf k v
l (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
| Bool
otherwise = (forall s. ST s (HashMap k v)) -> HashMap k v
forall a. (forall s. ST s a) -> a
runST (Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy HashMap k v
t)
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: Array (HashMap k v)
ary)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 =
let !ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.insert Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m) Array (HashMap k v)
ary'
| Bool
otherwise =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
in if HashMap k v
st' HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
`ptrEq` HashMap k v
st
then HashMap k v
t
else Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap k v)
ary Int
i HashMap k v
st')
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Full ary :: Array (HashMap k v)
ary) =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
in if HashMap k v
st' HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
`ptrEq` HashMap k v
st
then HashMap k v
t
else Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full (Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
update32 Array (HashMap k v)
ary Int
i HashMap k v
st')
where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Collision hy :: Hash
hy v :: Array (Leaf k v)
v)
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h ((v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWith (\a :: v
a _ -> (# v
a #)) k
k v
x Array (Leaf k v)
v)
| Bool
otherwise = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k v
x Int
s (HashMap k v -> HashMap k v) -> HashMap k v -> HashMap k v
forall a b. (a -> b) -> a -> b
$ Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash -> Int -> Hash
mask Hash
hy Int
s) (HashMap k v -> Array (HashMap k v)
forall a. a -> Array a
A.singleton HashMap k v
t)
{-# INLINABLE insert' #-}
insertNewKey :: Hash -> k -> v -> HashMap k v -> HashMap k v
insertNewKey :: Hash -> k -> v -> HashMap k v -> HashMap k v
insertNewKey !Hash
h0 !k
k0 x0 :: v
x0 !HashMap k v
m0 = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
forall k v. Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 v
x0 0 HashMap k v
m0
where
go :: Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go !Hash
h !k
k x :: v
x !Int
_ Empty = Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Leaf hy :: Hash
hy l :: Leaf k v
l)
| Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h = Hash -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision Hash
h Leaf k v
l (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
| Bool
otherwise = (forall s. ST s (HashMap k v)) -> HashMap k v
forall a. (forall s. ST s a) -> a
runST (Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy HashMap k v
t)
go h :: Hash
h k :: k
k x :: v
x s :: Int
s (BitmapIndexed b :: Hash
b ary :: Array (HashMap k v)
ary)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 =
let !ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.insert Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m) Array (HashMap k v)
ary'
| Bool
otherwise =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap k v)
ary Int
i HashMap k v
st')
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go h :: Hash
h k :: k
k x :: v
x s :: Int
s (Full ary :: Array (HashMap k v)
ary) =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full (Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
update32 Array (HashMap k v)
ary Int
i HashMap k v
st')
where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Collision hy :: Hash
hy v :: Array (Leaf k v)
v)
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Leaf k v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v. Leaf k v -> Array (Leaf k v) -> Array (Leaf k v)
snocNewLeaf (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x) Array (Leaf k v)
v)
| Bool
otherwise =
Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k v
x Int
s (HashMap k v -> HashMap k v) -> HashMap k v -> HashMap k v
forall a b. (a -> b) -> a -> b
$ Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash -> Int -> Hash
mask Hash
hy Int
s) (HashMap k v -> Array (HashMap k v)
forall a. a -> Array a
A.singleton HashMap k v
t)
where
snocNewLeaf :: Leaf k v -> A.Array (Leaf k v) -> A.Array (Leaf k v)
snocNewLeaf :: Leaf k v -> Array (Leaf k v) -> Array (Leaf k v)
snocNewLeaf leaf :: Leaf k v
leaf ary :: Array (Leaf k v)
ary = (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall e. (forall s. ST s (MArray s e)) -> Array e
A.run ((forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v))
-> (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall a b. (a -> b) -> a -> b
$ do
let n :: Int
n = Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary
MArray s (Leaf k v)
mary <- Int -> ST s (MArray s (Leaf k v))
forall s a. Int -> ST s (MArray s a)
A.new_ (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1)
Array (Leaf k v)
-> Int -> MArray s (Leaf k v) -> Int -> Int -> ST s ()
forall e s. Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
A.copy Array (Leaf k v)
ary 0 MArray s (Leaf k v)
mary 0 Int
n
MArray s (Leaf k v) -> Int -> Leaf k v -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (Leaf k v)
mary Int
n Leaf k v
leaf
MArray s (Leaf k v) -> ST s (MArray s (Leaf k v))
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s (Leaf k v)
mary
{-# NOINLINE insertNewKey #-}
insertKeyExists :: Int -> Hash -> k -> v -> HashMap k v -> HashMap k v
insertKeyExists :: Int -> Hash -> k -> v -> HashMap k v -> HashMap k v
insertKeyExists !Int
collPos0 !Hash
h0 !k
k0 x0 :: v
x0 !HashMap k v
m0 = Int -> Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
forall k v.
Int -> Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Int
collPos0 Hash
h0 k
k0 v
x0 0 HashMap k v
m0
where
go :: Int -> Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go !Int
_collPos !Hash
h !k
k x :: v
x !Int
_s (Leaf _hy :: Hash
_hy _kx :: Leaf k v
_kx)
= Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
go collPos :: Int
collPos h :: Hash
h k :: k
k x :: v
x s :: Int
s (BitmapIndexed b :: Hash
b ary :: Array (HashMap k v)
ary)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 =
let !ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.insert Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m) Array (HashMap k v)
ary'
| Bool
otherwise =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Int -> Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Int
collPos Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap k v)
ary Int
i HashMap k v
st')
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go collPos :: Int
collPos h :: Hash
h k :: k
k x :: v
x s :: Int
s (Full ary :: Array (HashMap k v)
ary) =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Int -> Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Int
collPos Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full (Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
update32 Array (HashMap k v)
ary Int
i HashMap k v
st')
where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
go collPos :: Int
collPos h :: Hash
h k :: k
k x :: v
x _s :: Int
_s (Collision _hy :: Hash
_hy v :: Array (Leaf k v)
v)
| Int
collPos Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= 0 = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Int -> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v. Int -> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
setAtPosition Int
collPos k
k v
x Array (Leaf k v)
v)
| Bool
otherwise = HashMap k v
forall k v. HashMap k v
Empty
go _ _ _ _ _ Empty = HashMap k v
forall k v. HashMap k v
Empty
{-# NOINLINE insertKeyExists #-}
setAtPosition :: Int -> k -> v -> A.Array (Leaf k v) -> A.Array (Leaf k v)
setAtPosition :: Int -> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
setAtPosition i :: Int
i k :: k
k x :: v
x ary :: Array (Leaf k v)
ary = Array (Leaf k v) -> Int -> Leaf k v -> Array (Leaf k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (Leaf k v)
ary Int
i (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
{-# INLINE setAtPosition #-}
unsafeInsert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v
unsafeInsert :: k -> v -> HashMap k v -> HashMap k v
unsafeInsert k0 :: k
k0 v0 :: v
v0 m0 :: HashMap k v
m0 = (forall s. ST s (HashMap k v)) -> HashMap k v
forall a. (forall s. ST s a) -> a
runST (Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
forall k v s.
Eq k =>
Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h0 k
k0 v
v0 0 HashMap k v
m0)
where
h0 :: Hash
h0 = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k0
go :: Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go !Hash
h !k
k x :: v
x !Int
_ Empty = HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Leaf hy :: Hash
hy l :: Leaf k v
l@(L ky :: k
ky y :: v
y))
| Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h = if k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k
then if v
x v -> v -> Bool
forall a. a -> a -> Bool
`ptrEq` v
y
then HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v
t
else HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
else HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision Hash
h Leaf k v
l (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
| Bool
otherwise = Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy HashMap k v
t
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: Array (HashMap k v)
ary)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = do
Array (HashMap k v)
ary' <- Array (HashMap k v)
-> Int -> HashMap k v -> ST s (Array (HashMap k v))
forall e s. Array e -> Int -> e -> ST s (Array e)
A.insertM Array (HashMap k v)
ary Int
i (HashMap k v -> ST s (Array (HashMap k v)))
-> HashMap k v -> ST s (Array (HashMap k v))
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m) Array (HashMap k v)
ary'
| Bool
otherwise = do
HashMap k v
st <- Array (HashMap k v) -> Int -> ST s (HashMap k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (HashMap k v)
ary Int
i
HashMap k v
st' <- Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
Array (HashMap k v) -> Int -> HashMap k v -> ST s ()
forall e s. Array e -> Int -> e -> ST s ()
A.unsafeUpdateM Array (HashMap k v)
ary Int
i HashMap k v
st'
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v
t
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Full ary :: Array (HashMap k v)
ary) = do
HashMap k v
st <- Array (HashMap k v) -> Int -> ST s (HashMap k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (HashMap k v)
ary Int
i
HashMap k v
st' <- Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
Array (HashMap k v) -> Int -> HashMap k v -> ST s ()
forall e s. Array e -> Int -> e -> ST s ()
A.unsafeUpdateM Array (HashMap k v)
ary Int
i HashMap k v
st'
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v
t
where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Collision hy :: Hash
hy v :: Array (Leaf k v)
v)
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy = HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h ((v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWith (\a :: v
a _ -> (# v
a #)) k
k v
x Array (Leaf k v)
v)
| Bool
otherwise = Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x Int
s (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$ Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash -> Int -> Hash
mask Hash
hy Int
s) (HashMap k v -> Array (HashMap k v)
forall a. a -> Array a
A.singleton HashMap k v
t)
{-# INLINABLE unsafeInsert #-}
two :: Shift -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
two :: Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
two = Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
go
where
go :: Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
go s :: Int
s h1 :: Hash
h1 k1 :: k
k1 v1 :: v
v1 h2 :: Hash
h2 t2 :: HashMap k v
t2
| Hash
bp1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
bp2 = do
HashMap k v
st <- Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) Hash
h1 k
k1 v
v1 Hash
h2 HashMap k v
t2
Array (HashMap k v)
ary <- HashMap k v -> ST s (Array (HashMap k v))
forall a s. a -> ST s (Array a)
A.singletonM HashMap k v
st
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$ Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
bp1 Array (HashMap k v)
ary
| Bool
otherwise = do
MArray s (HashMap k v)
mary <- Int -> HashMap k v -> ST s (MArray s (HashMap k v))
forall a s. Int -> a -> ST s (MArray s a)
A.new 2 (HashMap k v -> ST s (MArray s (HashMap k v)))
-> HashMap k v -> ST s (MArray s (HashMap k v))
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h1 (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k1 v
v1)
MArray s (HashMap k v) -> Int -> HashMap k v -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (HashMap k v)
mary Int
idx2 HashMap k v
t2
Array (HashMap k v)
ary <- MArray s (HashMap k v) -> ST s (Array (HashMap k v))
forall s a. MArray s a -> ST s (Array a)
A.unsafeFreeze MArray s (HashMap k v)
mary
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$ Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash
bp1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
bp2) Array (HashMap k v)
ary
where
bp1 :: Hash
bp1 = Hash -> Int -> Hash
mask Hash
h1 Int
s
bp2 :: Hash
bp2 = Hash -> Int -> Hash
mask Hash
h2 Int
s
idx2 :: Int
idx2 | Hash -> Int -> Int
index Hash
h1 Int
s Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Hash -> Int -> Int
index Hash
h2 Int
s = 1
| Bool
otherwise = 0
{-# INLINE two #-}
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v
-> HashMap k v
insertWith :: (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
insertWith f :: v -> v -> v
f k :: k
k new :: v
new m :: HashMap k v
m = v -> (v -> (# v #)) -> k -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
v -> (v -> (# v #)) -> k -> HashMap k v -> HashMap k v
insertModifying v
new (\old :: v
old -> (# v -> v -> v
f v
new v
old #)) k
k HashMap k v
m
{-# INLINE insertWith #-}
insertModifying :: (Eq k, Hashable k) => v -> (v -> (# v #)) -> k -> HashMap k v
-> HashMap k v
insertModifying :: v -> (v -> (# v #)) -> k -> HashMap k v -> HashMap k v
insertModifying x :: v
x f :: v -> (# v #)
f k0 :: k
k0 m0 :: HashMap k v
m0 = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 0 HashMap k v
m0
where
!h0 :: Hash
h0 = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k0
go :: Hash -> k -> Int -> HashMap k v -> HashMap k v
go !Hash
h !k
k !Int
_ Empty = Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(Leaf hy :: Hash
hy l :: Leaf k v
l@(L ky :: k
ky y :: v
y))
| Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h = if k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k
then case v -> (# v #)
f v
y of
(# v' :: v
v' #) | v -> v -> Bool
forall a. a -> a -> Bool
ptrEq v
y v
v' -> HashMap k v
t
| Bool
otherwise -> Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k (v
v'))
else Hash -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision Hash
h Leaf k v
l (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
| Bool
otherwise = (forall s. ST s (HashMap k v)) -> HashMap k v
forall a. (forall s. ST s a) -> a
runST (Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy HashMap k v
t)
go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: Array (HashMap k v)
ary)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 =
let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.insert Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m) Array (HashMap k v)
ary'
| Bool
otherwise =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
st'
in if HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
ptrEq HashMap k v
st HashMap k v
st'
then HashMap k v
t
else Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b Array (HashMap k v)
ary'
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(Full ary :: Array (HashMap k v)
ary) =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
update32 Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
st'
in if HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
ptrEq HashMap k v
st HashMap k v
st'
then HashMap k v
t
else Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(Collision hy :: Hash
hy v :: Array (Leaf k v)
v)
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy =
let !v' :: Array (Leaf k v)
v' = v -> (v -> (# v #)) -> k -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
v -> (v -> (# v #)) -> k -> Array (Leaf k v) -> Array (Leaf k v)
insertModifyingArr v
x v -> (# v #)
f k
k Array (Leaf k v)
v
in if Array (Leaf k v) -> Array (Leaf k v) -> Bool
forall a b. Array a -> Array b -> Bool
A.unsafeSameArray Array (Leaf k v)
v Array (Leaf k v)
v'
then HashMap k v
t
else Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h Array (Leaf k v)
v'
| Bool
otherwise = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k Int
s (HashMap k v -> HashMap k v) -> HashMap k v -> HashMap k v
forall a b. (a -> b) -> a -> b
$ Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash -> Int -> Hash
mask Hash
hy Int
s) (HashMap k v -> Array (HashMap k v)
forall a. a -> Array a
A.singleton HashMap k v
t)
{-# INLINABLE insertModifying #-}
insertModifyingArr :: Eq k => v -> (v -> (# v #)) -> k -> A.Array (Leaf k v)
-> A.Array (Leaf k v)
insertModifyingArr :: v -> (v -> (# v #)) -> k -> Array (Leaf k v) -> Array (Leaf k v)
insertModifyingArr x :: v
x f :: v -> (# v #)
f k0 :: k
k0 ary0 :: Array (Leaf k v)
ary0 = k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k0 Array (Leaf k v)
ary0 0 (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary0)
where
go :: k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go !k
k !Array (Leaf k v)
ary !Int
i !Int
n
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall e. (forall s. ST s (MArray s e)) -> Array e
A.run ((forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v))
-> (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall a b. (a -> b) -> a -> b
$ do
MArray s (Leaf k v)
mary <- Int -> ST s (MArray s (Leaf k v))
forall s a. Int -> ST s (MArray s a)
A.new_ (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1)
Array (Leaf k v)
-> Int -> MArray s (Leaf k v) -> Int -> Int -> ST s ()
forall e s. Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
A.copy Array (Leaf k v)
ary 0 MArray s (Leaf k v)
mary 0 Int
n
MArray s (Leaf k v) -> Int -> Leaf k v -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (Leaf k v)
mary Int
n (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
MArray s (Leaf k v) -> ST s (MArray s (Leaf k v))
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s (Leaf k v)
mary
| Bool
otherwise = case Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
ary Int
i of
(L kx :: k
kx y :: v
y) | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx -> case v -> (# v #)
f v
y of
(# y' :: v
y' #) -> if v -> v -> Bool
forall a. a -> a -> Bool
ptrEq v
y v
y'
then Array (Leaf k v)
ary
else Array (Leaf k v) -> Int -> Leaf k v -> Array (Leaf k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (Leaf k v)
ary Int
i (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
y')
| Bool
otherwise -> k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k Array (Leaf k v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
n
{-# INLINE insertModifyingArr #-}
unsafeInsertWith :: forall k v. (Eq k, Hashable k)
=> (v -> v -> v) -> k -> v -> HashMap k v
-> HashMap k v
unsafeInsertWith :: (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWith f :: v -> v -> v
f k0 :: k
k0 v0 :: v
v0 m0 :: HashMap k v
m0 = (k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWithKey ((v -> v -> v) -> k -> v -> v -> v
forall a b. a -> b -> a
const v -> v -> v
f) k
k0 v
v0 HashMap k v
m0
{-# INLINABLE unsafeInsertWith #-}
unsafeInsertWithKey :: forall k v. (Eq k, Hashable k)
=> (k -> v -> v -> v) -> k -> v -> HashMap k v
-> HashMap k v
unsafeInsertWithKey :: (k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWithKey f :: k -> v -> v -> v
f k0 :: k
k0 v0 :: v
v0 m0 :: HashMap k v
m0 = (forall s. ST s (HashMap k v)) -> HashMap k v
forall a. (forall s. ST s a) -> a
runST (Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
forall s.
Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h0 k
k0 v
v0 0 HashMap k v
m0)
where
h0 :: Hash
h0 = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k0
go :: Hash -> k -> v -> Shift -> HashMap k v -> ST s (HashMap k v)
go :: Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go !Hash
h !k
k x :: v
x !Int
_ Empty = HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Leaf hy :: Hash
hy l :: Leaf k v
l@(L ky :: k
ky y :: v
y))
| Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h = if k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k
then HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k (k -> v -> v -> v
f k
k v
x v
y))
else HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision Hash
h Leaf k v
l (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
| Bool
otherwise = Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy HashMap k v
t
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: Array (HashMap k v)
ary)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = do
Array (HashMap k v)
ary' <- Array (HashMap k v)
-> Int -> HashMap k v -> ST s (Array (HashMap k v))
forall e s. Array e -> Int -> e -> ST s (Array e)
A.insertM Array (HashMap k v)
ary Int
i (HashMap k v -> ST s (Array (HashMap k v)))
-> HashMap k v -> ST s (Array (HashMap k v))
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m) Array (HashMap k v)
ary'
| Bool
otherwise = do
HashMap k v
st <- Array (HashMap k v) -> Int -> ST s (HashMap k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (HashMap k v)
ary Int
i
HashMap k v
st' <- Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
forall s.
Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
Array (HashMap k v) -> Int -> HashMap k v -> ST s ()
forall e s. Array e -> Int -> e -> ST s ()
A.unsafeUpdateM Array (HashMap k v)
ary Int
i HashMap k v
st'
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v
t
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Full ary :: Array (HashMap k v)
ary) = do
HashMap k v
st <- Array (HashMap k v) -> Int -> ST s (HashMap k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (HashMap k v)
ary Int
i
HashMap k v
st' <- Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
forall s.
Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
Array (HashMap k v) -> Int -> HashMap k v -> ST s ()
forall e s. Array e -> Int -> e -> ST s ()
A.unsafeUpdateM Array (HashMap k v)
ary Int
i HashMap k v
st'
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v
t
where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Collision hy :: Hash
hy v :: Array (Leaf k v)
v)
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy = HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h ((k -> v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey (\key :: k
key a :: v
a b :: v
b -> (# k -> v -> v -> v
f k
key v
a v
b #) ) k
k v
x Array (Leaf k v)
v)
| Bool
otherwise = Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
forall s.
Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x Int
s (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$ Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash -> Int -> Hash
mask Hash
hy Int
s) (HashMap k v -> Array (HashMap k v)
forall a. a -> Array a
A.singleton HashMap k v
t)
{-# INLINABLE unsafeInsertWithKey #-}
delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
delete :: k -> HashMap k v -> HashMap k v
delete k :: k
k m :: HashMap k v
m = Hash -> k -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> HashMap k v -> HashMap k v
delete' (k -> Hash
forall a. Hashable a => a -> Hash
hash k
k) k
k HashMap k v
m
{-# INLINABLE delete #-}
delete' :: Eq k => Hash -> k -> HashMap k v -> HashMap k v
delete' :: Hash -> k -> HashMap k v -> HashMap k v
delete' h0 :: Hash
h0 k0 :: k
k0 m0 :: HashMap k v
m0 = Hash -> k -> Int -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 0 HashMap k v
m0
where
go :: Hash -> k -> Int -> HashMap k v -> HashMap k v
go !Hash
_ !k
_ !Int
_ Empty = HashMap k v
forall k v. HashMap k v
Empty
go h :: Hash
h k :: k
k _ t :: HashMap k v
t@(Leaf hy :: Hash
hy (L ky :: k
ky _))
| Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h Bool -> Bool -> Bool
&& k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k = HashMap k v
forall k v. HashMap k v
Empty
| Bool
otherwise = HashMap k v
t
go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: Array (HashMap k v)
ary)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = HashMap k v
t
| Bool
otherwise =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
in if HashMap k v
st' HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
`ptrEq` HashMap k v
st
then HashMap k v
t
else case HashMap k v
st' of
Empty | Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1 -> HashMap k v
forall k v. HashMap k v
Empty
| Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 2 ->
case (Int
i, Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary 0, Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary 1) of
(0, _, l :: HashMap k v
l) | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l -> HashMap k v
l
(1, l :: HashMap k v
l, _) | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l -> HashMap k v
l
_ -> HashMap k v
bIndexed
| Bool
otherwise -> HashMap k v
bIndexed
where
bIndexed :: HashMap k v
bIndexed = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Bits a => a -> a
complement Hash
m) (Array (HashMap k v) -> Int -> Array (HashMap k v)
forall e. Array e -> Int -> Array e
A.delete Array (HashMap k v)
ary Int
i)
l :: HashMap k v
l | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l Bool -> Bool -> Bool
&& Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1 -> HashMap k v
l
_ -> Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap k v)
ary Int
i HashMap k v
st')
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(Full ary :: Array (HashMap k v)
ary) =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
in if HashMap k v
st' HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
`ptrEq` HashMap k v
st
then HashMap k v
t
else case HashMap k v
st' of
Empty ->
let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> Array (HashMap k v)
forall e. Array e -> Int -> Array e
A.delete Array (HashMap k v)
ary Int
i
bm :: Hash
bm = Hash
fullNodeMask Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Bits a => a -> a
complement (1 Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` Int
i)
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
bm Array (HashMap k v)
ary'
_ -> Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full (Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap k v)
ary Int
i HashMap k v
st')
where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
go h :: Hash
h k :: k
k _ t :: HashMap k v
t@(Collision hy :: Hash
hy v :: Array (Leaf k v)
v)
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy = case k -> Array (Leaf k v) -> Maybe Int
forall k v. Eq k => k -> Array (Leaf k v) -> Maybe Int
indexOf k
k Array (Leaf k v)
v of
Just i :: Int
i
| Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
v Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 2 ->
if Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0
then Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
v 1)
else Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
v 0)
| Bool
otherwise -> Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Array (Leaf k v) -> Int -> Array (Leaf k v)
forall e. Array e -> Int -> Array e
A.delete Array (Leaf k v)
v Int
i)
Nothing -> HashMap k v
t
| Bool
otherwise = HashMap k v
t
{-# INLINABLE delete' #-}
deleteKeyExists :: Int -> Hash -> k -> HashMap k v -> HashMap k v
deleteKeyExists :: Int -> Hash -> k -> HashMap k v -> HashMap k v
deleteKeyExists !Int
collPos0 !Hash
h0 !k
k0 !HashMap k v
m0 = Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
forall k v. Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
go Int
collPos0 Hash
h0 k
k0 0 HashMap k v
m0
where
go :: Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
go :: Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
go !Int
_collPos !Hash
_h !k
_k !Int
_s (Leaf _ _) = HashMap k v
forall k v. HashMap k v
Empty
go collPos :: Int
collPos h :: Hash
h k :: k
k s :: Int
s (BitmapIndexed b :: Hash
b ary :: Array (HashMap k v)
ary) =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
forall k v. Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
go Int
collPos Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
in case HashMap k v
st' of
Empty | Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1 -> HashMap k v
forall k v. HashMap k v
Empty
| Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 2 ->
case (Int
i, Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary 0, Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary 1) of
(0, _, l :: HashMap k v
l) | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l -> HashMap k v
l
(1, l :: HashMap k v
l, _) | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l -> HashMap k v
l
_ -> HashMap k v
bIndexed
| Bool
otherwise -> HashMap k v
bIndexed
where
bIndexed :: HashMap k v
bIndexed = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Bits a => a -> a
complement Hash
m) (Array (HashMap k v) -> Int -> Array (HashMap k v)
forall e. Array e -> Int -> Array e
A.delete Array (HashMap k v)
ary Int
i)
l :: HashMap k v
l | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l Bool -> Bool -> Bool
&& Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1 -> HashMap k v
l
_ -> Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap k v)
ary Int
i HashMap k v
st')
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go collPos :: Int
collPos h :: Hash
h k :: k
k s :: Int
s (Full ary :: Array (HashMap k v)
ary) =
let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
forall k v. Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
go Int
collPos Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
in case HashMap k v
st' of
Empty ->
let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> Array (HashMap k v)
forall e. Array e -> Int -> Array e
A.delete Array (HashMap k v)
ary Int
i
bm :: Hash
bm = Hash
fullNodeMask Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Bits a => a -> a
complement (1 Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` Int
i)
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
bm Array (HashMap k v)
ary'
_ -> Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full (Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap k v)
ary Int
i HashMap k v
st')
where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
go collPos :: Int
collPos h :: Hash
h _ _ (Collision _hy :: Hash
_hy v :: Array (Leaf k v)
v)
| Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
v Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 2
= if Int
collPos Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0
then Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
v 1)
else Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
v 0)
| Bool
otherwise = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Array (Leaf k v) -> Int -> Array (Leaf k v)
forall e. Array e -> Int -> Array e
A.delete Array (Leaf k v)
v Int
collPos)
go !Int
_ !Hash
_ !k
_ !Int
_ Empty = HashMap k v
forall k v. HashMap k v
Empty
{-# NOINLINE deleteKeyExists #-}
adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v
adjust :: (v -> v) -> k -> HashMap k v -> HashMap k v
adjust f :: v -> v
f k :: k
k m :: HashMap k v
m = (v -> (# v #)) -> k -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(v -> (# v #)) -> k -> HashMap k v -> HashMap k v
adjust# (\v :: v
v -> (# v -> v
f v
v #)) k
k HashMap k v
m
{-# INLINE adjust #-}
adjust# :: (Eq k, Hashable k) => (v -> (# v #)) -> k -> HashMap k v -> HashMap k v
adjust# :: (v -> (# v #)) -> k -> HashMap k v -> HashMap k v
adjust# f :: v -> (# v #)
f k0 :: k
k0 m0 :: HashMap k v
m0 = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 0 HashMap k v
m0
where
h0 :: Hash
h0 = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k0
go :: Hash -> k -> Int -> HashMap k v -> HashMap k v
go !Hash
_ !k
_ !Int
_ Empty = HashMap k v
forall k v. HashMap k v
Empty
go h :: Hash
h k :: k
k _ t :: HashMap k v
t@(Leaf hy :: Hash
hy (L ky :: k
ky y :: v
y))
| Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h Bool -> Bool -> Bool
&& k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k = case v -> (# v #)
f v
y of
(# y' :: v
y' #) | v -> v -> Bool
forall a. a -> a -> Bool
ptrEq v
y v
y' -> HashMap k v
t
| Bool
otherwise -> Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
y')
| Bool
otherwise = HashMap k v
t
go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: Array (HashMap k v)
ary)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = HashMap k v
t
| Bool
otherwise = let !st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
st'
in if HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
ptrEq HashMap k v
st HashMap k v
st'
then HashMap k v
t
else Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b Array (HashMap k v)
ary'
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(Full ary :: Array (HashMap k v)
ary) =
let i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
!st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
!st' :: HashMap k v
st' = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
update32 Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
st'
in if HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
ptrEq HashMap k v
st HashMap k v
st'
then HashMap k v
t
else Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
go h :: Hash
h k :: k
k _ t :: HashMap k v
t@(Collision hy :: Hash
hy v :: Array (Leaf k v)
v)
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy = let !v' :: Array (Leaf k v)
v' = (v -> (# v #)) -> k -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(v -> (# v #)) -> k -> Array (Leaf k v) -> Array (Leaf k v)
updateWith# v -> (# v #)
f k
k Array (Leaf k v)
v
in if Array (Leaf k v) -> Array (Leaf k v) -> Bool
forall a b. Array a -> Array b -> Bool
A.unsafeSameArray Array (Leaf k v)
v Array (Leaf k v)
v'
then HashMap k v
t
else Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h Array (Leaf k v)
v'
| Bool
otherwise = HashMap k v
t
{-# INLINABLE adjust# #-}
update :: (Eq k, Hashable k) => (a -> Maybe a) -> k -> HashMap k a -> HashMap k a
update :: (a -> Maybe a) -> k -> HashMap k a -> HashMap k a
update f :: a -> Maybe a
f = (Maybe a -> Maybe a) -> k -> HashMap k a -> HashMap k a
forall k v.
(Eq k, Hashable k) =>
(Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
alter (Maybe a -> (a -> Maybe a) -> Maybe a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Maybe a
f)
{-# INLINABLE update #-}
alter :: (Eq k, Hashable k) => (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
alter :: (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
alter f :: Maybe v -> Maybe v
f k :: k
k m :: HashMap k v
m =
case Maybe v -> Maybe v
f (k -> HashMap k v -> Maybe v
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k v
m) of
Nothing -> k -> HashMap k v -> HashMap k v
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
delete k
k HashMap k v
m
Just v :: v
v -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k v
v HashMap k v
m
{-# INLINABLE alter #-}
alterF :: (Functor f, Eq k, Hashable k)
=> (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterF :: (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterF f :: Maybe v -> f (Maybe v)
f = \ !k
k !HashMap k v
m ->
let
!h :: Hash
h = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k
mv :: Maybe v
mv = Hash -> k -> HashMap k v -> Maybe v
forall k v. Eq k => Hash -> k -> HashMap k v -> Maybe v
lookup' Hash
h k
k HashMap k v
m
in ((Maybe v -> HashMap k v) -> f (Maybe v) -> f (HashMap k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe v -> f (Maybe v)
f Maybe v
mv) ((Maybe v -> HashMap k v) -> f (HashMap k v))
-> (Maybe v -> HashMap k v) -> f (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \fres :: Maybe v
fres ->
case Maybe v
fres of
Nothing -> HashMap k v -> (v -> HashMap k v) -> Maybe v -> HashMap k v
forall b a. b -> (a -> b) -> Maybe a -> b
maybe HashMap k v
m (HashMap k v -> v -> HashMap k v
forall a b. a -> b -> a
const (Hash -> k -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> HashMap k v -> HashMap k v
delete' Hash
h k
k HashMap k v
m)) Maybe v
mv
Just v' :: v
v' -> Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> v -> HashMap k v -> HashMap k v
insert' Hash
h k
k v
v' HashMap k v
m
{-# INLINABLE [0] alterF #-}
test_bottom :: a
test_bottom :: a
test_bottom = [Char] -> a
forall a. HasCallStack => [Char] -> a
error "Data.HashMap.alterF internal error: hit test_bottom"
bogus# :: (# #) -> (# a #)
bogus# :: (# #) -> (# a #)
bogus# _ = [Char] -> (# a #)
forall a. HasCallStack => [Char] -> a
error "Data.HashMap.alterF internal error: hit bogus#"
{-# RULES
-- We probe the behavior of @f@ by applying it to Nothing and to
-- Just test_bottom. Based on the results, and how they relate to
-- each other, we choose the best implementation.
"alterFWeird" forall f. alterF f =
alterFWeird (f Nothing) (f (Just test_bottom)) f
-- This rule covers situations where alterF is used to simply insert or
-- delete in Identity (most likely via Control.Lens.At). We recognize here
-- (through the repeated @x@ on the LHS) that
--
-- @f Nothing = f (Just bottom)@,
--
-- which guarantees that @f@ doesn't care what its argument is, so
-- we don't have to either.
--
-- Why only Identity? A variant of this rule is actually valid regardless of
-- the functor, but for some functors (e.g., []), it can lead to the
-- same keys being compared multiple times, which is bad if they're
-- ugly things like strings. This is unfortunate, since the rule is likely
-- a good idea for almost all realistic uses, but I don't like nasty
-- edge cases.
"alterFconstant" forall (f :: Maybe a -> Identity (Maybe a)) x.
alterFWeird x x f = \ !k !m ->
Identity (case runIdentity x of {Nothing -> delete k m; Just a -> insert k a m})
-- This rule handles the case where 'alterF' is used to do 'insertWith'-like
-- things. Whenever possible, GHC will get rid of the Maybe nonsense for us.
-- We delay this rule to stage 1 so alterFconstant has a chance to fire.
"alterFinsertWith" [1] forall (f :: Maybe a -> Identity (Maybe a)) x y.
alterFWeird (coerce (Just x)) (coerce (Just y)) f =
coerce (insertModifying x (\mold -> case runIdentity (f (Just mold)) of
Nothing -> bogus# (# #)
Just new -> (# new #)))
-- Handle the case where someone uses 'alterF' instead of 'adjust'. This
-- rule is kind of picky; it will only work if the function doesn't
-- do anything between case matching on the Maybe and producing a result.
"alterFadjust" forall (f :: Maybe a -> Identity (Maybe a)) _y.
alterFWeird (coerce Nothing) (coerce (Just _y)) f =
coerce (adjust# (\x -> case runIdentity (f (Just x)) of
Just x' -> (# x' #)
Nothing -> bogus# (# #)))
-- The simple specialization to Const; in this case we can look up
-- the key without caring what position it's in. This is only a tiny
-- optimization.
"alterFlookup" forall _ign1 _ign2 (f :: Maybe a -> Const r (Maybe a)).
alterFWeird _ign1 _ign2 f = \ !k !m -> Const (getConst (f (lookup k m)))
#-}
alterFWeird
:: (Functor f, Eq k, Hashable k)
=> f (Maybe v)
-> f (Maybe v)
-> (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterFWeird :: f (Maybe v)
-> f (Maybe v)
-> (Maybe v -> f (Maybe v))
-> k
-> HashMap k v
-> f (HashMap k v)
alterFWeird _ _ f :: Maybe v -> f (Maybe v)
f = (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
forall (f :: * -> *) k v.
(Functor f, Eq k, Hashable k) =>
(Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterFEager Maybe v -> f (Maybe v)
f
{-# INLINE [0] alterFWeird #-}
alterFEager :: (Functor f, Eq k, Hashable k)
=> (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterFEager :: (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterFEager f :: Maybe v -> f (Maybe v)
f !k
k m :: HashMap k v
m = ((Maybe v -> HashMap k v) -> f (Maybe v) -> f (HashMap k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe v -> f (Maybe v)
f Maybe v
mv) ((Maybe v -> HashMap k v) -> f (HashMap k v))
-> (Maybe v -> HashMap k v) -> f (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \fres :: Maybe v
fres ->
case Maybe v
fres of
Nothing -> case LookupRes v
lookupRes of
Absent -> HashMap k v
m
Present _ collPos :: Int
collPos -> Int -> Hash -> k -> HashMap k v -> HashMap k v
forall k v. Int -> Hash -> k -> HashMap k v -> HashMap k v
deleteKeyExists Int
collPos Hash
h k
k HashMap k v
m
Just v' :: v
v' -> case LookupRes v
lookupRes of
Absent -> Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v -> HashMap k v
insertNewKey Hash
h k
k v
v' HashMap k v
m
Present v :: v
v collPos :: Int
collPos ->
if v
v v -> v -> Bool
forall a. a -> a -> Bool
`ptrEq` v
v'
then HashMap k v
m
else Int -> Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Int -> Hash -> k -> v -> HashMap k v -> HashMap k v
insertKeyExists Int
collPos Hash
h k
k v
v' HashMap k v
m
where !h :: Hash
h = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k
!lookupRes :: LookupRes v
lookupRes = Hash -> k -> HashMap k v -> LookupRes v
forall k v. Eq k => Hash -> k -> HashMap k v -> LookupRes v
lookupRecordCollision Hash
h k
k HashMap k v
m
!mv :: Maybe v
mv = case LookupRes v
lookupRes of
Absent -> Maybe v
forall a. Maybe a
Nothing
Present v :: v
v _ -> v -> Maybe v
forall a. a -> Maybe a
Just v
v
{-# INLINABLE alterFEager #-}
isSubmapOf :: (Eq k, Hashable k, Eq v) => HashMap k v -> HashMap k v -> Bool
isSubmapOf :: HashMap k v -> HashMap k v -> Bool
isSubmapOf = (((v -> v -> Bool) -> HashMap k v -> HashMap k v -> Bool)
-> (v -> v -> Bool) -> HashMap k v -> HashMap k v -> Bool
forall a. a -> a
Exts.inline (v -> v -> Bool) -> HashMap k v -> HashMap k v -> Bool
forall k v1 v2.
(Eq k, Hashable k) =>
(v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool
isSubmapOfBy) v -> v -> Bool
forall a. Eq a => a -> a -> Bool
(==)
{-# INLINABLE isSubmapOf #-}
isSubmapOfBy :: (Eq k, Hashable k) => (v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool
isSubmapOfBy :: (v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool
isSubmapOfBy comp :: v1 -> v2 -> Bool
comp !HashMap k v1
m1 !HashMap k v2
m2 = Int -> HashMap k v1 -> HashMap k v2 -> Bool
go 0 HashMap k v1
m1 HashMap k v2
m2
where
go :: Int -> HashMap k v1 -> HashMap k v2 -> Bool
go _ Empty _ = Bool
True
go _ _ Empty = Bool
False
go s :: Int
s (Leaf h1 :: Hash
h1 (L k1 :: k
k1 v1 :: v1
v1)) t2 :: HashMap k v2
t2 = ((# #) -> Bool)
-> (v2 -> Int -> Bool) -> Hash -> k -> Int -> HashMap k v2 -> Bool
forall r k v.
Eq k =>
((# #) -> r)
-> (v -> Int -> r) -> Hash -> k -> Int -> HashMap k v -> r
lookupCont (\_ -> Bool
False) (\v2 :: v2
v2 _ -> v1 -> v2 -> Bool
comp v1
v1 v2
v2) Hash
h1 k
k1 Int
s HashMap k v2
t2
go _ (Collision h1 :: Hash
h1 ls1 :: Array (Leaf k v1)
ls1) (Collision h2 :: Hash
h2 ls2 :: Array (Leaf k v2)
ls2) =
Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 Bool -> Bool -> Bool
&& (v1 -> v2 -> Bool)
-> Array (Leaf k v1) -> Array (Leaf k v2) -> Bool
forall k v1 v2.
Eq k =>
(v1 -> v2 -> Bool)
-> Array (Leaf k v1) -> Array (Leaf k v2) -> Bool
subsetArray v1 -> v2 -> Bool
comp Array (Leaf k v1)
ls1 Array (Leaf k v2)
ls2
go s :: Int
s t1 :: HashMap k v1
t1@(Collision h1 :: Hash
h1 _) (BitmapIndexed b :: Hash
b ls2 :: Array (HashMap k v2)
ls2)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = Bool
False
| Bool
otherwise =
Int -> HashMap k v1 -> HashMap k v2 -> Bool
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v1
t1 (Array (HashMap k v2) -> Int -> HashMap k v2
forall a. Array a -> Int -> a
A.index Array (HashMap k v2)
ls2 (Hash -> Hash -> Int
sparseIndex Hash
b Hash
m))
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h1 Int
s
go s :: Int
s t1 :: HashMap k v1
t1@(Collision h1 :: Hash
h1 _) (Full ls2 :: Array (HashMap k v2)
ls2) =
Int -> HashMap k v1 -> HashMap k v2 -> Bool
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v1
t1 (Array (HashMap k v2) -> Int -> HashMap k v2
forall a. Array a -> Int -> a
A.index Array (HashMap k v2)
ls2 (Hash -> Int -> Int
index Hash
h1 Int
s))
go s :: Int
s (BitmapIndexed b1 :: Hash
b1 ls1 :: Array (HashMap k v1)
ls1) (BitmapIndexed b2 :: Hash
b2 ls2 :: Array (HashMap k v2)
ls2) =
(HashMap k v1 -> HashMap k v2 -> Bool)
-> Hash
-> Array (HashMap k v1)
-> Hash
-> Array (HashMap k v2)
-> Bool
forall k v1 v2.
(HashMap k v1 -> HashMap k v2 -> Bool)
-> Hash
-> Array (HashMap k v1)
-> Hash
-> Array (HashMap k v2)
-> Bool
submapBitmapIndexed (Int -> HashMap k v1 -> HashMap k v2 -> Bool
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey)) Hash
b1 Array (HashMap k v1)
ls1 Hash
b2 Array (HashMap k v2)
ls2
go s :: Int
s (BitmapIndexed b1 :: Hash
b1 ls1 :: Array (HashMap k v1)
ls1) (Full ls2 :: Array (HashMap k v2)
ls2) =
(HashMap k v1 -> HashMap k v2 -> Bool)
-> Hash
-> Array (HashMap k v1)
-> Hash
-> Array (HashMap k v2)
-> Bool
forall k v1 v2.
(HashMap k v1 -> HashMap k v2 -> Bool)
-> Hash
-> Array (HashMap k v1)
-> Hash
-> Array (HashMap k v2)
-> Bool
submapBitmapIndexed (Int -> HashMap k v1 -> HashMap k v2 -> Bool
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey)) Hash
b1 Array (HashMap k v1)
ls1 Hash
fullNodeMask Array (HashMap k v2)
ls2
go s :: Int
s (Full ls1 :: Array (HashMap k v1)
ls1) (Full ls2 :: Array (HashMap k v2)
ls2) =
(HashMap k v1 -> HashMap k v2 -> Bool)
-> Hash
-> Array (HashMap k v1)
-> Hash
-> Array (HashMap k v2)
-> Bool
forall k v1 v2.
(HashMap k v1 -> HashMap k v2 -> Bool)
-> Hash
-> Array (HashMap k v1)
-> Hash
-> Array (HashMap k v2)
-> Bool
submapBitmapIndexed (Int -> HashMap k v1 -> HashMap k v2 -> Bool
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey)) Hash
fullNodeMask Array (HashMap k v1)
ls1 Hash
fullNodeMask Array (HashMap k v2)
ls2
go _ (Collision {}) (Leaf {}) = Bool
False
go _ (BitmapIndexed {}) (Leaf {}) = Bool
False
go _ (Full {}) (Leaf {}) = Bool
False
go _ (BitmapIndexed {}) (Collision {}) = Bool
False
go _ (Full {}) (Collision {}) = Bool
False
go _ (Full {}) (BitmapIndexed {}) = Bool
False
{-# INLINABLE isSubmapOfBy #-}
submapBitmapIndexed :: (HashMap k v1 -> HashMap k v2 -> Bool) -> Bitmap -> A.Array (HashMap k v1) -> Bitmap -> A.Array (HashMap k v2) -> Bool
submapBitmapIndexed :: (HashMap k v1 -> HashMap k v2 -> Bool)
-> Hash
-> Array (HashMap k v1)
-> Hash
-> Array (HashMap k v2)
-> Bool
submapBitmapIndexed comp :: HashMap k v1 -> HashMap k v2 -> Bool
comp !Hash
b1 !Array (HashMap k v1)
ary1 !Hash
b2 !Array (HashMap k v2)
ary2 = Bool
subsetBitmaps Bool -> Bool -> Bool
&& Int -> Int -> Hash -> Bool
go 0 0 (Hash
b1Orb2 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Num a => a -> a
negate Hash
b1Orb2)
where
go :: Int -> Int -> Bitmap -> Bool
go :: Int -> Int -> Hash -> Bool
go !Int
i !Int
j !Hash
m
| Hash
m Hash -> Hash -> Bool
forall a. Ord a => a -> a -> Bool
> Hash
b1Orb2 = Bool
True
| Hash
b1Andb2 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
/= 0 = HashMap k v1 -> HashMap k v2 -> Bool
comp (Array (HashMap k v1) -> Int -> HashMap k v1
forall a. Array a -> Int -> a
A.index Array (HashMap k v1)
ary1 Int
i) (Array (HashMap k v2) -> Int -> HashMap k v2
forall a. Array a -> Int -> a
A.index Array (HashMap k v2)
ary2 Int
j) Bool -> Bool -> Bool
&&
Int -> Int -> Hash -> Bool
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Hash
m Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` 1)
| Hash
b2 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
/= 0 = Int -> Int -> Hash -> Bool
go Int
i (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Hash
m Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` 1)
| Bool
otherwise = Int -> Int -> Hash -> Bool
go Int
i Int
j (Hash
m Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` 1)
b1Andb2 :: Hash
b1Andb2 = Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
b2
b1Orb2 :: Hash
b1Orb2 = Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
b2
subsetBitmaps :: Bool
subsetBitmaps = Hash
b1Orb2 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
b2
{-# INLINABLE submapBitmapIndexed #-}
union :: (Eq k, Hashable k) => HashMap k v -> HashMap k v -> HashMap k v
union :: HashMap k v -> HashMap k v -> HashMap k v
union = (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
unionWith v -> v -> v
forall a b. a -> b -> a
const
{-# INLINABLE union #-}
unionWith :: (Eq k, Hashable k) => (v -> v -> v) -> HashMap k v -> HashMap k v
-> HashMap k v
unionWith :: (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
unionWith f :: v -> v -> v
f = (k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
unionWithKey ((v -> v -> v) -> k -> v -> v -> v
forall a b. a -> b -> a
const v -> v -> v
f)
{-# INLINE unionWith #-}
unionWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> HashMap k v -> HashMap k v
-> HashMap k v
unionWithKey :: (k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
unionWithKey f :: k -> v -> v -> v
f = Int -> HashMap k v -> HashMap k v -> HashMap k v
go 0
where
go :: Int -> HashMap k v -> HashMap k v -> HashMap k v
go !Int
_ t1 :: HashMap k v
t1 Empty = HashMap k v
t1
go _ Empty t2 :: HashMap k v
t2 = HashMap k v
t2
go s :: Int
s t1 :: HashMap k v
t1@(Leaf h1 :: Hash
h1 l1 :: Leaf k v
l1@(L k1 :: k
k1 v1 :: v
v1)) t2 :: HashMap k v
t2@(Leaf h2 :: Hash
h2 l2 :: Leaf k v
l2@(L k2 :: k
k2 v2 :: v
v2))
| Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 = if k
k1 k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k2
then Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h1 (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k1 (k -> v -> v -> v
f k
k1 v
v1 v
v2))
else Hash -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision Hash
h1 Leaf k v
l1 Leaf k v
l2
| Bool
otherwise = Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
forall k v.
Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
go s :: Int
s t1 :: HashMap k v
t1@(Leaf h1 :: Hash
h1 (L k1 :: k
k1 v1 :: v
v1)) t2 :: HashMap k v
t2@(Collision h2 :: Hash
h2 ls2 :: Array (Leaf k v)
ls2)
| Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h1 ((k -> v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey (\k :: k
k a :: v
a b :: v
b -> (# k -> v -> v -> v
f k
k v
a v
b #)) k
k1 v
v1 Array (Leaf k v)
ls2)
| Bool
otherwise = Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
forall k v.
Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
go s :: Int
s t1 :: HashMap k v
t1@(Collision h1 :: Hash
h1 ls1 :: Array (Leaf k v)
ls1) t2 :: HashMap k v
t2@(Leaf h2 :: Hash
h2 (L k2 :: k
k2 v2 :: v
v2))
| Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h1 ((k -> v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey (\k :: k
k a :: v
a b :: v
b -> (# k -> v -> v -> v
f k
k v
b v
a #)) k
k2 v
v2 Array (Leaf k v)
ls1)
| Bool
otherwise = Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
forall k v.
Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
go s :: Int
s t1 :: HashMap k v
t1@(Collision h1 :: Hash
h1 ls1 :: Array (Leaf k v)
ls1) t2 :: HashMap k v
t2@(Collision h2 :: Hash
h2 ls2 :: Array (Leaf k v)
ls2)
| Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h1 ((k -> v -> v -> v)
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> v)
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
updateOrConcatWithKey k -> v -> v -> v
f Array (Leaf k v)
ls1 Array (Leaf k v)
ls2)
| Bool
otherwise = Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
forall k v.
Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
go s :: Int
s (BitmapIndexed b1 :: Hash
b1 ary1 :: Array (HashMap k v)
ary1) (BitmapIndexed b2 :: Hash
b2 ary2 :: Array (HashMap k v)
ary2) =
let b' :: Hash
b' = Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
b2
ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey)) Hash
b1 Hash
b2 Array (HashMap k v)
ary1 Array (HashMap k v)
ary2
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull Hash
b' Array (HashMap k v)
ary'
go s :: Int
s (BitmapIndexed b1 :: Hash
b1 ary1 :: Array (HashMap k v)
ary1) (Full ary2 :: Array (HashMap k v)
ary2) =
let ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey)) Hash
b1 Hash
fullNodeMask Array (HashMap k v)
ary1 Array (HashMap k v)
ary2
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
go s :: Int
s (Full ary1 :: Array (HashMap k v)
ary1) (BitmapIndexed b2 :: Hash
b2 ary2 :: Array (HashMap k v)
ary2) =
let ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey)) Hash
fullNodeMask Hash
b2 Array (HashMap k v)
ary1 Array (HashMap k v)
ary2
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
go s :: Int
s (Full ary1 :: Array (HashMap k v)
ary1) (Full ary2 :: Array (HashMap k v)
ary2) =
let ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey)) Hash
fullNodeMask Hash
fullNodeMask
Array (HashMap k v)
ary1 Array (HashMap k v)
ary2
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
go s :: Int
s (BitmapIndexed b1 :: Hash
b1 ary1 :: Array (HashMap k v)
ary1) t2 :: HashMap k v
t2
| Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m2 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.insert Array (HashMap k v)
ary1 Int
i HashMap k v
t2
b' :: Hash
b' = Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m2
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull Hash
b' Array (HashMap k v)
ary'
| Bool
otherwise = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Int -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Int -> (e -> e) -> Array e
A.updateWith' Array (HashMap k v)
ary1 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \st1 :: HashMap k v
st1 ->
Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st1 HashMap k v
t2
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b1 Array (HashMap k v)
ary'
where
h2 :: Hash
h2 = HashMap k v -> Hash
forall k v. HashMap k v -> Hash
leafHashCode HashMap k v
t2
m2 :: Hash
m2 = Hash -> Int -> Hash
mask Hash
h2 Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b1 Hash
m2
go s :: Int
s t1 :: HashMap k v
t1 (BitmapIndexed b2 :: Hash
b2 ary2 :: Array (HashMap k v)
ary2)
| Hash
b2 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.insert Array (HashMap k v)
ary2 Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
t1
b' :: Hash
b' = Hash
b2 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m1
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull Hash
b' Array (HashMap k v)
ary'
| Bool
otherwise = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Int -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Int -> (e -> e) -> Array e
A.updateWith' Array (HashMap k v)
ary2 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \st2 :: HashMap k v
st2 ->
Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
t1 HashMap k v
st2
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b2 Array (HashMap k v)
ary'
where
h1 :: Hash
h1 = HashMap k v -> Hash
forall k v. HashMap k v -> Hash
leafHashCode HashMap k v
t1
m1 :: Hash
m1 = Hash -> Int -> Hash
mask Hash
h1 Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b2 Hash
m1
go s :: Int
s (Full ary1 :: Array (HashMap k v)
ary1) t2 :: HashMap k v
t2 =
let h2 :: Hash
h2 = HashMap k v -> Hash
forall k v. HashMap k v -> Hash
leafHashCode HashMap k v
t2
i :: Int
i = Hash -> Int -> Int
index Hash
h2 Int
s
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Int -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Int -> (e -> e) -> Array e
update32With' Array (HashMap k v)
ary1 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \st1 :: HashMap k v
st1 -> Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st1 HashMap k v
t2
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
go s :: Int
s t1 :: HashMap k v
t1 (Full ary2 :: Array (HashMap k v)
ary2) =
let h1 :: Hash
h1 = HashMap k v -> Hash
forall k v. HashMap k v -> Hash
leafHashCode HashMap k v
t1
i :: Int
i = Hash -> Int -> Int
index Hash
h1 Int
s
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Int -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Int -> (e -> e) -> Array e
update32With' Array (HashMap k v)
ary2 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \st2 :: HashMap k v
st2 -> Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
t1 HashMap k v
st2
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
leafHashCode :: HashMap k v -> Hash
leafHashCode (Leaf h :: Hash
h _) = Hash
h
leafHashCode (Collision h :: Hash
h _) = Hash
h
leafHashCode _ = [Char] -> Hash
forall a. HasCallStack => [Char] -> a
error "leafHashCode"
goDifferentHash :: Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash s :: Int
s h1 :: Hash
h1 h2 :: Hash
h2 t1 :: HashMap k v
t1 t2 :: HashMap k v
t2
| Hash
m1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
m2 = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
m1 (HashMap k v -> Array (HashMap k v)
forall a. a -> Array a
A.singleton (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2)
| Hash
m1 Hash -> Hash -> Bool
forall a. Ord a => a -> a -> Bool
< Hash
m2 = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash
m1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m2) (HashMap k v -> HashMap k v -> Array (HashMap k v)
forall a. a -> a -> Array a
A.pair HashMap k v
t1 HashMap k v
t2)
| Bool
otherwise = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash
m1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m2) (HashMap k v -> HashMap k v -> Array (HashMap k v)
forall a. a -> a -> Array a
A.pair HashMap k v
t2 HashMap k v
t1)
where
m1 :: Hash
m1 = Hash -> Int -> Hash
mask Hash
h1 Int
s
m2 :: Hash
m2 = Hash -> Int -> Hash
mask Hash
h2 Int
s
{-# INLINE unionWithKey #-}
unionArrayBy :: (a -> a -> a) -> Bitmap -> Bitmap -> A.Array a -> A.Array a
-> A.Array a
unionArrayBy :: (a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
unionArrayBy f :: a -> a -> a
f b1 :: Hash
b1 b2 :: Hash
b2 ary1 :: Array a
ary1 ary2 :: Array a
ary2 = (forall s. ST s (MArray s a)) -> Array a
forall e. (forall s. ST s (MArray s e)) -> Array e
A.run ((forall s. ST s (MArray s a)) -> Array a)
-> (forall s. ST s (MArray s a)) -> Array a
forall a b. (a -> b) -> a -> b
$ do
let b' :: Hash
b' = Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
b2
MArray s a
mary <- Int -> ST s (MArray s a)
forall s a. Int -> ST s (MArray s a)
A.new_ (Hash -> Int
forall a. Bits a => a -> Int
popCount Hash
b')
let ba :: Hash
ba = Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
b2
go :: Int -> Int -> Int -> Hash -> ST s ()
go !Int
i !Int
i1 !Int
i2 !Hash
m
| Hash
m Hash -> Hash -> Bool
forall a. Ord a => a -> a -> Bool
> Hash
b' = () -> ST s ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
| Hash
b' Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = Int -> Int -> Int -> Hash -> ST s ()
go Int
i Int
i1 Int
i2 (Hash
m Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` 1)
| Hash
ba Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
/= 0 = do
a
x1 <- Array a -> Int -> ST s a
forall a s. Array a -> Int -> ST s a
A.indexM Array a
ary1 Int
i1
a
x2 <- Array a -> Int -> ST s a
forall a s. Array a -> Int -> ST s a
A.indexM Array a
ary2 Int
i2
MArray s a -> Int -> a -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s a
mary Int
i (a -> ST s ()) -> a -> ST s ()
forall a b. (a -> b) -> a -> b
$! a -> a -> a
f a
x1 a
x2
Int -> Int -> Int -> Hash -> ST s ()
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i1Int -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i2Int -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Hash
m Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` 1)
| Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
/= 0 = do
MArray s a -> Int -> a -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s a
mary Int
i (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Array a -> Int -> ST s a
forall a s. Array a -> Int -> ST s a
A.indexM Array a
ary1 Int
i1
Int -> Int -> Int -> Hash -> ST s ()
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i1Int -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i2 ) (Hash
m Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` 1)
| Bool
otherwise = do
MArray s a -> Int -> a -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s a
mary Int
i (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Array a -> Int -> ST s a
forall a s. Array a -> Int -> ST s a
A.indexM Array a
ary2 Int
i2
Int -> Int -> Int -> Hash -> ST s ()
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i1 ) (Int
i2Int -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Hash
m Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` 1)
Int -> Int -> Int -> Hash -> ST s ()
go 0 0 0 (Hash
b' Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Num a => a -> a
negate Hash
b')
MArray s a -> ST s (MArray s a)
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s a
mary
{-# INLINE unionArrayBy #-}
unions :: (Eq k, Hashable k) => [HashMap k v] -> HashMap k v
unions :: [HashMap k v] -> HashMap k v
unions = (HashMap k v -> HashMap k v -> HashMap k v)
-> HashMap k v -> [HashMap k v] -> HashMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' HashMap k v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
HashMap k v -> HashMap k v -> HashMap k v
union HashMap k v
forall k v. HashMap k v
empty
{-# INLINE unions #-}
compose :: (Eq b, Hashable b) => HashMap b c -> HashMap a b -> HashMap a c
compose :: HashMap b c -> HashMap a b -> HashMap a c
compose bc :: HashMap b c
bc !HashMap a b
ab
| HashMap b c -> Bool
forall k a. HashMap k a -> Bool
null HashMap b c
bc = HashMap a c
forall k v. HashMap k v
empty
| Bool
otherwise = (b -> Maybe c) -> HashMap a b -> HashMap a c
forall v1 v2 k. (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybe (HashMap b c
bc HashMap b c -> b -> Maybe c
forall k v. (Eq k, Hashable k) => HashMap k v -> k -> Maybe v
!?) HashMap a b
ab
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
mapWithKey f :: k -> v1 -> v2
f = HashMap k v1 -> HashMap k v2
go
where
go :: HashMap k v1 -> HashMap k v2
go Empty = HashMap k v2
forall k v. HashMap k v
Empty
go (Leaf h :: Hash
h (L k :: k
k v :: v1
v)) = Hash -> Leaf k v2 -> HashMap k v2
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Leaf k v2 -> HashMap k v2) -> Leaf k v2 -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k (k -> v1 -> v2
f k
k v1
v)
go (BitmapIndexed b :: Hash
b ary :: Array (HashMap k v1)
ary) = Hash -> Array (HashMap k v2) -> HashMap k v2
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v2) -> HashMap k v2)
-> Array (HashMap k v2) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ (HashMap k v1 -> HashMap k v2)
-> Array (HashMap k v1) -> Array (HashMap k v2)
forall a b. (a -> b) -> Array a -> Array b
A.map HashMap k v1 -> HashMap k v2
go Array (HashMap k v1)
ary
go (Full ary :: Array (HashMap k v1)
ary) = Array (HashMap k v2) -> HashMap k v2
forall k v. Array (HashMap k v) -> HashMap k v
Full (Array (HashMap k v2) -> HashMap k v2)
-> Array (HashMap k v2) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ (HashMap k v1 -> HashMap k v2)
-> Array (HashMap k v1) -> Array (HashMap k v2)
forall a b. (a -> b) -> Array a -> Array b
A.map HashMap k v1 -> HashMap k v2
go Array (HashMap k v1)
ary
go (Collision h :: Hash
h ary :: Array (Leaf k v1)
ary) = Hash -> Array (Leaf k v2) -> HashMap k v2
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Array (Leaf k v2) -> HashMap k v2)
-> Array (Leaf k v2) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$
(Leaf k v1 -> Leaf k v2) -> Array (Leaf k v1) -> Array (Leaf k v2)
forall a b. (a -> b) -> Array a -> Array b
A.map' (\ (L k :: k
k v :: v1
v) -> k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k (k -> v1 -> v2
f k
k v1
v)) Array (Leaf k v1)
ary
{-# INLINE mapWithKey #-}
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2
map f :: v1 -> v2
f = (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
forall k v1 v2. (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
mapWithKey ((v1 -> v2) -> k -> v1 -> v2
forall a b. a -> b -> a
const v1 -> v2
f)
{-# INLINE map #-}
traverseWithKey
:: Applicative f
=> (k -> v1 -> f v2)
-> HashMap k v1 -> f (HashMap k v2)
traverseWithKey :: (k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)
traverseWithKey f :: k -> v1 -> f v2
f = HashMap k v1 -> f (HashMap k v2)
go
where
go :: HashMap k v1 -> f (HashMap k v2)
go Empty = HashMap k v2 -> f (HashMap k v2)
forall (f :: * -> *) a. Applicative f => a -> f a
pure HashMap k v2
forall k v. HashMap k v
Empty
go (Leaf h :: Hash
h (L k :: k
k v :: v1
v)) = Hash -> Leaf k v2 -> HashMap k v2
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Leaf k v2 -> HashMap k v2)
-> (v2 -> Leaf k v2) -> v2 -> HashMap k v2
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k (v2 -> HashMap k v2) -> f v2 -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> v1 -> f v2
f k
k v1
v
go (BitmapIndexed b :: Hash
b ary :: Array (HashMap k v1)
ary) = Hash -> Array (HashMap k v2) -> HashMap k v2
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v2) -> HashMap k v2)
-> f (Array (HashMap k v2)) -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (HashMap k v1 -> f (HashMap k v2))
-> Array (HashMap k v1) -> f (Array (HashMap k v2))
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Array a -> f (Array b)
A.traverse HashMap k v1 -> f (HashMap k v2)
go Array (HashMap k v1)
ary
go (Full ary :: Array (HashMap k v1)
ary) = Array (HashMap k v2) -> HashMap k v2
forall k v. Array (HashMap k v) -> HashMap k v
Full (Array (HashMap k v2) -> HashMap k v2)
-> f (Array (HashMap k v2)) -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (HashMap k v1 -> f (HashMap k v2))
-> Array (HashMap k v1) -> f (Array (HashMap k v2))
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Array a -> f (Array b)
A.traverse HashMap k v1 -> f (HashMap k v2)
go Array (HashMap k v1)
ary
go (Collision h :: Hash
h ary :: Array (Leaf k v1)
ary) =
Hash -> Array (Leaf k v2) -> HashMap k v2
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Array (Leaf k v2) -> HashMap k v2)
-> f (Array (Leaf k v2)) -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Leaf k v1 -> f (Leaf k v2))
-> Array (Leaf k v1) -> f (Array (Leaf k v2))
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Array a -> f (Array b)
A.traverse' (\ (L k :: k
k v :: v1
v) -> k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k (v2 -> Leaf k v2) -> f v2 -> f (Leaf k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> v1 -> f v2
f k
k v1
v) Array (Leaf k v1)
ary
{-# INLINE traverseWithKey #-}
mapKeys :: (Eq k2, Hashable k2) => (k1 -> k2) -> HashMap k1 v -> HashMap k2 v
mapKeys :: (k1 -> k2) -> HashMap k1 v -> HashMap k2 v
mapKeys f :: k1 -> k2
f = [(k2, v)] -> HashMap k2 v
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList ([(k2, v)] -> HashMap k2 v)
-> (HashMap k1 v -> [(k2, v)]) -> HashMap k1 v -> HashMap k2 v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k1 -> v -> [(k2, v)] -> [(k2, v)])
-> [(k2, v)] -> HashMap k1 v -> [(k2, v)]
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey (\k :: k1
k x :: v
x xs :: [(k2, v)]
xs -> (k1 -> k2
f k1
k, v
x) (k2, v) -> [(k2, v)] -> [(k2, v)]
forall a. a -> [a] -> [a]
: [(k2, v)]
xs) []
difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v
difference :: HashMap k v -> HashMap k w -> HashMap k v
difference a :: HashMap k v
a b :: HashMap k w
b = (HashMap k v -> k -> v -> HashMap k v)
-> HashMap k v -> HashMap k v -> HashMap k v
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' HashMap k v -> k -> v -> HashMap k v
go HashMap k v
forall k v. HashMap k v
empty HashMap k v
a
where
go :: HashMap k v -> k -> v -> HashMap k v
go m :: HashMap k v
m k :: k
k v :: v
v = case k -> HashMap k w -> Maybe w
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k w
b of
Nothing -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k v
v HashMap k v
m
_ -> HashMap k v
m
{-# INLINABLE difference #-}
differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v
differenceWith :: (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v
differenceWith f :: v -> w -> Maybe v
f a :: HashMap k v
a b :: HashMap k w
b = (HashMap k v -> k -> v -> HashMap k v)
-> HashMap k v -> HashMap k v -> HashMap k v
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' HashMap k v -> k -> v -> HashMap k v
go HashMap k v
forall k v. HashMap k v
empty HashMap k v
a
where
go :: HashMap k v -> k -> v -> HashMap k v
go m :: HashMap k v
m k :: k
k v :: v
v = case k -> HashMap k w -> Maybe w
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k w
b of
Nothing -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k v
v HashMap k v
m
Just w :: w
w -> HashMap k v -> (v -> HashMap k v) -> Maybe v -> HashMap k v
forall b a. b -> (a -> b) -> Maybe a -> b
maybe HashMap k v
m (\y :: v
y -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k v
y HashMap k v
m) (v -> w -> Maybe v
f v
v w
w)
{-# INLINABLE differenceWith #-}
intersection :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v
intersection :: HashMap k v -> HashMap k w -> HashMap k v
intersection a :: HashMap k v
a b :: HashMap k w
b = (HashMap k v -> k -> v -> HashMap k v)
-> HashMap k v -> HashMap k v -> HashMap k v
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' HashMap k v -> k -> v -> HashMap k v
go HashMap k v
forall k v. HashMap k v
empty HashMap k v
a
where
go :: HashMap k v -> k -> v -> HashMap k v
go m :: HashMap k v
m k :: k
k v :: v
v = case k -> HashMap k w -> Maybe w
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k w
b of
Just _ -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k v
v HashMap k v
m
_ -> HashMap k v
m
{-# INLINABLE intersection #-}
intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> HashMap k v1
-> HashMap k v2 -> HashMap k v3
intersectionWith :: (v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3
intersectionWith f :: v1 -> v2 -> v3
f a :: HashMap k v1
a b :: HashMap k v2
b = (HashMap k v3 -> k -> v1 -> HashMap k v3)
-> HashMap k v3 -> HashMap k v1 -> HashMap k v3
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' HashMap k v3 -> k -> v1 -> HashMap k v3
go HashMap k v3
forall k v. HashMap k v
empty HashMap k v1
a
where
go :: HashMap k v3 -> k -> v1 -> HashMap k v3
go m :: HashMap k v3
m k :: k
k v :: v1
v = case k -> HashMap k v2 -> Maybe v2
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k v2
b of
Just w :: v2
w -> k -> v3 -> HashMap k v3 -> HashMap k v3
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k (v1 -> v2 -> v3
f v1
v v2
w) HashMap k v3
m
_ -> HashMap k v3
m
{-# INLINABLE intersectionWith #-}
intersectionWithKey :: (Eq k, Hashable k) => (k -> v1 -> v2 -> v3)
-> HashMap k v1 -> HashMap k v2 -> HashMap k v3
intersectionWithKey :: (k -> v1 -> v2 -> v3)
-> HashMap k v1 -> HashMap k v2 -> HashMap k v3
intersectionWithKey f :: k -> v1 -> v2 -> v3
f a :: HashMap k v1
a b :: HashMap k v2
b = (HashMap k v3 -> k -> v1 -> HashMap k v3)
-> HashMap k v3 -> HashMap k v1 -> HashMap k v3
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' HashMap k v3 -> k -> v1 -> HashMap k v3
go HashMap k v3
forall k v. HashMap k v
empty HashMap k v1
a
where
go :: HashMap k v3 -> k -> v1 -> HashMap k v3
go m :: HashMap k v3
m k :: k
k v :: v1
v = case k -> HashMap k v2 -> Maybe v2
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k v2
b of
Just w :: v2
w -> k -> v3 -> HashMap k v3 -> HashMap k v3
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k (k -> v1 -> v2 -> v3
f k
k v1
v v2
w) HashMap k v3
m
_ -> HashMap k v3
m
{-# INLINABLE intersectionWithKey #-}
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a
foldl' f :: a -> v -> a
f = (a -> k -> v -> a) -> a -> HashMap k v -> a
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' (\ z :: a
z _ v :: v
v -> a -> v -> a
f a
z v
v)
{-# INLINE foldl' #-}
foldr' :: (v -> a -> a) -> a -> HashMap k v -> a
foldr' :: (v -> a -> a) -> a -> HashMap k v -> a
foldr' f :: v -> a -> a
f = (k -> v -> a -> a) -> a -> HashMap k v -> a
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey' (\ _ v :: v
v z :: a
z -> v -> a -> a
f v
v a
z)
{-# INLINE foldr' #-}
foldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' f :: a -> k -> v -> a
f = a -> HashMap k v -> a
go
where
go :: a -> HashMap k v -> a
go !a
z Empty = a
z
go z :: a
z (Leaf _ (L k :: k
k v :: v
v)) = a -> k -> v -> a
f a
z k
k v
v
go z :: a
z (BitmapIndexed _ ary :: Array (HashMap k v)
ary) = (a -> HashMap k v -> a) -> a -> Array (HashMap k v) -> a
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' a -> HashMap k v -> a
go a
z Array (HashMap k v)
ary
go z :: a
z (Full ary :: Array (HashMap k v)
ary) = (a -> HashMap k v -> a) -> a -> Array (HashMap k v) -> a
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' a -> HashMap k v -> a
go a
z Array (HashMap k v)
ary
go z :: a
z (Collision _ ary :: Array (Leaf k v)
ary) = (a -> Leaf k v -> a) -> a -> Array (Leaf k v) -> a
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' (\ z' :: a
z' (L k :: k
k v :: v
v) -> a -> k -> v -> a
f a
z' k
k v
v) a
z Array (Leaf k v)
ary
{-# INLINE foldlWithKey' #-}
foldrWithKey' :: (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey' :: (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey' f :: k -> v -> a -> a
f = (HashMap k v -> a -> a) -> a -> HashMap k v -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip HashMap k v -> a -> a
go
where
go :: HashMap k v -> a -> a
go Empty z :: a
z = a
z
go (Leaf _ (L k :: k
k v :: v
v)) !a
z = k -> v -> a -> a
f k
k v
v a
z
go (BitmapIndexed _ ary :: Array (HashMap k v)
ary) !a
z = (HashMap k v -> a -> a) -> a -> Array (HashMap k v) -> a
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr' HashMap k v -> a -> a
go a
z Array (HashMap k v)
ary
go (Full ary :: Array (HashMap k v)
ary) !a
z = (HashMap k v -> a -> a) -> a -> Array (HashMap k v) -> a
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr' HashMap k v -> a -> a
go a
z Array (HashMap k v)
ary
go (Collision _ ary :: Array (Leaf k v)
ary) !a
z = (Leaf k v -> a -> a) -> a -> Array (Leaf k v) -> a
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr' (\ (L k :: k
k v :: v
v) z' :: a
z' -> k -> v -> a -> a
f k
k v
v a
z') a
z Array (Leaf k v)
ary
{-# INLINE foldrWithKey' #-}
foldr :: (v -> a -> a) -> a -> HashMap k v -> a
foldr :: (v -> a -> a) -> a -> HashMap k v -> a
foldr f :: v -> a -> a
f = (k -> v -> a -> a) -> a -> HashMap k v -> a
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey ((v -> a -> a) -> k -> v -> a -> a
forall a b. a -> b -> a
const v -> a -> a
f)
{-# INLINE foldr #-}
foldl :: (a -> v -> a) -> a -> HashMap k v -> a
foldl :: (a -> v -> a) -> a -> HashMap k v -> a
foldl f :: a -> v -> a
f = (a -> k -> v -> a) -> a -> HashMap k v -> a
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey (\a :: a
a _k :: k
_k v :: v
v -> a -> v -> a
f a
a v
v)
{-# INLINE foldl #-}
foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey f :: k -> v -> a -> a
f = (HashMap k v -> a -> a) -> a -> HashMap k v -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip HashMap k v -> a -> a
go
where
go :: HashMap k v -> a -> a
go Empty z :: a
z = a
z
go (Leaf _ (L k :: k
k v :: v
v)) z :: a
z = k -> v -> a -> a
f k
k v
v a
z
go (BitmapIndexed _ ary :: Array (HashMap k v)
ary) z :: a
z = (HashMap k v -> a -> a) -> a -> Array (HashMap k v) -> a
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr HashMap k v -> a -> a
go a
z Array (HashMap k v)
ary
go (Full ary :: Array (HashMap k v)
ary) z :: a
z = (HashMap k v -> a -> a) -> a -> Array (HashMap k v) -> a
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr HashMap k v -> a -> a
go a
z Array (HashMap k v)
ary
go (Collision _ ary :: Array (Leaf k v)
ary) z :: a
z = (Leaf k v -> a -> a) -> a -> Array (Leaf k v) -> a
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr (\ (L k :: k
k v :: v
v) z' :: a
z' -> k -> v -> a -> a
f k
k v
v a
z') a
z Array (Leaf k v)
ary
{-# INLINE foldrWithKey #-}
foldlWithKey :: (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey :: (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey f :: a -> k -> v -> a
f = a -> HashMap k v -> a
go
where
go :: a -> HashMap k v -> a
go z :: a
z Empty = a
z
go z :: a
z (Leaf _ (L k :: k
k v :: v
v)) = a -> k -> v -> a
f a
z k
k v
v
go z :: a
z (BitmapIndexed _ ary :: Array (HashMap k v)
ary) = (a -> HashMap k v -> a) -> a -> Array (HashMap k v) -> a
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl a -> HashMap k v -> a
go a
z Array (HashMap k v)
ary
go z :: a
z (Full ary :: Array (HashMap k v)
ary) = (a -> HashMap k v -> a) -> a -> Array (HashMap k v) -> a
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl a -> HashMap k v -> a
go a
z Array (HashMap k v)
ary
go z :: a
z (Collision _ ary :: Array (Leaf k v)
ary) = (a -> Leaf k v -> a) -> a -> Array (Leaf k v) -> a
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl (\ z' :: a
z' (L k :: k
k v :: v
v) -> a -> k -> v -> a
f a
z' k
k v
v) a
z Array (Leaf k v)
ary
{-# INLINE foldlWithKey #-}
foldMapWithKey :: Monoid m => (k -> v -> m) -> HashMap k v -> m
foldMapWithKey :: (k -> v -> m) -> HashMap k v -> m
foldMapWithKey f :: k -> v -> m
f = HashMap k v -> m
go
where
go :: HashMap k v -> m
go Empty = m
forall a. Monoid a => a
mempty
go (Leaf _ (L k :: k
k v :: v
v)) = k -> v -> m
f k
k v
v
go (BitmapIndexed _ ary :: Array (HashMap k v)
ary) = (HashMap k v -> m) -> Array (HashMap k v) -> m
forall m a. Monoid m => (a -> m) -> Array a -> m
A.foldMap HashMap k v -> m
go Array (HashMap k v)
ary
go (Full ary :: Array (HashMap k v)
ary) = (HashMap k v -> m) -> Array (HashMap k v) -> m
forall m a. Monoid m => (a -> m) -> Array a -> m
A.foldMap HashMap k v -> m
go Array (HashMap k v)
ary
go (Collision _ ary :: Array (Leaf k v)
ary) = (Leaf k v -> m) -> Array (Leaf k v) -> m
forall m a. Monoid m => (a -> m) -> Array a -> m
A.foldMap (\ (L k :: k
k v :: v
v) -> k -> v -> m
f k
k v
v) Array (Leaf k v)
ary
{-# INLINE foldMapWithKey #-}
mapMaybeWithKey :: (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybeWithKey :: (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybeWithKey f :: k -> v1 -> Maybe v2
f = (HashMap k v1 -> Maybe (HashMap k v2))
-> (Leaf k v1 -> Maybe (Leaf k v2)) -> HashMap k v1 -> HashMap k v2
forall k v1 v2.
(HashMap k v1 -> Maybe (HashMap k v2))
-> (Leaf k v1 -> Maybe (Leaf k v2)) -> HashMap k v1 -> HashMap k v2
filterMapAux HashMap k v1 -> Maybe (HashMap k v2)
onLeaf Leaf k v1 -> Maybe (Leaf k v2)
onColl
where onLeaf :: HashMap k v1 -> Maybe (HashMap k v2)
onLeaf (Leaf h :: Hash
h (L k :: k
k v :: v1
v)) | Just v' :: v2
v' <- k -> v1 -> Maybe v2
f k
k v1
v = HashMap k v2 -> Maybe (HashMap k v2)
forall a. a -> Maybe a
Just (Hash -> Leaf k v2 -> HashMap k v2
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k v2
v'))
onLeaf _ = Maybe (HashMap k v2)
forall a. Maybe a
Nothing
onColl :: Leaf k v1 -> Maybe (Leaf k v2)
onColl (L k :: k
k v :: v1
v) | Just v' :: v2
v' <- k -> v1 -> Maybe v2
f k
k v1
v = Leaf k v2 -> Maybe (Leaf k v2)
forall a. a -> Maybe a
Just (k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k v2
v')
| Bool
otherwise = Maybe (Leaf k v2)
forall a. Maybe a
Nothing
{-# INLINE mapMaybeWithKey #-}
mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybe f :: v1 -> Maybe v2
f = (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
forall k v1 v2.
(k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybeWithKey ((v1 -> Maybe v2) -> k -> v1 -> Maybe v2
forall a b. a -> b -> a
const v1 -> Maybe v2
f)
{-# INLINE mapMaybe #-}
filterWithKey :: forall k v. (k -> v -> Bool) -> HashMap k v -> HashMap k v
filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k v
filterWithKey pred :: k -> v -> Bool
pred = (HashMap k v -> Maybe (HashMap k v))
-> (Leaf k v -> Maybe (Leaf k v)) -> HashMap k v -> HashMap k v
forall k v1 v2.
(HashMap k v1 -> Maybe (HashMap k v2))
-> (Leaf k v1 -> Maybe (Leaf k v2)) -> HashMap k v1 -> HashMap k v2
filterMapAux HashMap k v -> Maybe (HashMap k v)
onLeaf Leaf k v -> Maybe (Leaf k v)
onColl
where onLeaf :: HashMap k v -> Maybe (HashMap k v)
onLeaf t :: HashMap k v
t@(Leaf _ (L k :: k
k v :: v
v)) | k -> v -> Bool
pred k
k v
v = HashMap k v -> Maybe (HashMap k v)
forall a. a -> Maybe a
Just HashMap k v
t
onLeaf _ = Maybe (HashMap k v)
forall a. Maybe a
Nothing
onColl :: Leaf k v -> Maybe (Leaf k v)
onColl el :: Leaf k v
el@(L k :: k
k v :: v
v) | k -> v -> Bool
pred k
k v
v = Leaf k v -> Maybe (Leaf k v)
forall a. a -> Maybe a
Just Leaf k v
el
onColl _ = Maybe (Leaf k v)
forall a. Maybe a
Nothing
{-# INLINE filterWithKey #-}
filterMapAux :: forall k v1 v2
. (HashMap k v1 -> Maybe (HashMap k v2))
-> (Leaf k v1 -> Maybe (Leaf k v2))
-> HashMap k v1
-> HashMap k v2
filterMapAux :: (HashMap k v1 -> Maybe (HashMap k v2))
-> (Leaf k v1 -> Maybe (Leaf k v2)) -> HashMap k v1 -> HashMap k v2
filterMapAux onLeaf :: HashMap k v1 -> Maybe (HashMap k v2)
onLeaf onColl :: Leaf k v1 -> Maybe (Leaf k v2)
onColl = HashMap k v1 -> HashMap k v2
go
where
go :: HashMap k v1 -> HashMap k v2
go Empty = HashMap k v2
forall k v. HashMap k v
Empty
go t :: HashMap k v1
t@Leaf{}
| Just t' :: HashMap k v2
t' <- HashMap k v1 -> Maybe (HashMap k v2)
onLeaf HashMap k v1
t = HashMap k v2
t'
| Bool
otherwise = HashMap k v2
forall k v. HashMap k v
Empty
go (BitmapIndexed b :: Hash
b ary :: Array (HashMap k v1)
ary) = Array (HashMap k v1) -> Hash -> HashMap k v2
filterA Array (HashMap k v1)
ary Hash
b
go (Full ary :: Array (HashMap k v1)
ary) = Array (HashMap k v1) -> Hash -> HashMap k v2
filterA Array (HashMap k v1)
ary Hash
fullNodeMask
go (Collision h :: Hash
h ary :: Array (Leaf k v1)
ary) = Array (Leaf k v1) -> Hash -> HashMap k v2
filterC Array (Leaf k v1)
ary Hash
h
filterA :: Array (HashMap k v1) -> Hash -> HashMap k v2
filterA ary0 :: Array (HashMap k v1)
ary0 b0 :: Hash
b0 =
let !n :: Int
n = Array (HashMap k v1) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v1)
ary0
in (forall s. ST s (HashMap k v2)) -> HashMap k v2
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (HashMap k v2)) -> HashMap k v2)
-> (forall s. ST s (HashMap k v2)) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ do
MArray s (HashMap k v2)
mary <- Int -> ST s (MArray s (HashMap k v2))
forall s a. Int -> ST s (MArray s a)
A.new_ Int
n
Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
forall s.
Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
step Array (HashMap k v1)
ary0 MArray s (HashMap k v2)
mary Hash
b0 0 0 1 Int
n
where
step :: A.Array (HashMap k v1) -> A.MArray s (HashMap k v2)
-> Bitmap -> Int -> Int -> Bitmap -> Int
-> ST s (HashMap k v2)
step :: Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
step !Array (HashMap k v1)
ary !MArray s (HashMap k v2)
mary !Hash
b i :: Int
i !Int
j !Hash
bi n :: Int
n
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = case Int
j of
0 -> HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v2
forall k v. HashMap k v
Empty
1 -> do
HashMap k v2
ch <- MArray s (HashMap k v2) -> Int -> ST s (HashMap k v2)
forall s a. MArray s a -> Int -> ST s a
A.read MArray s (HashMap k v2)
mary 0
case HashMap k v2
ch of
t :: HashMap k v2
t | HashMap k v2 -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v2
t -> HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v2
t
_ -> Hash -> Array (HashMap k v2) -> HashMap k v2
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v2) -> HashMap k v2)
-> ST s (Array (HashMap k v2)) -> ST s (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MArray s (HashMap k v2) -> Int -> ST s (Array (HashMap k v2))
forall s a. MArray s a -> Int -> ST s (Array a)
A.trim MArray s (HashMap k v2)
mary 1
_ -> do
Array (HashMap k v2)
ary2 <- MArray s (HashMap k v2) -> Int -> ST s (Array (HashMap k v2))
forall s a. MArray s a -> Int -> ST s (Array a)
A.trim MArray s (HashMap k v2)
mary Int
j
HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v2 -> ST s (HashMap k v2))
-> HashMap k v2 -> ST s (HashMap k v2)
forall a b. (a -> b) -> a -> b
$! if Int
j Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
maxChildren
then Array (HashMap k v2) -> HashMap k v2
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v2)
ary2
else Hash -> Array (HashMap k v2) -> HashMap k v2
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b Array (HashMap k v2)
ary2
| Hash
bi Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
b Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
forall s.
Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
step Array (HashMap k v1)
ary MArray s (HashMap k v2)
mary Hash
b Int
i Int
j (Hash
bi Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` 1) Int
n
| Bool
otherwise = case HashMap k v1 -> HashMap k v2
go (Array (HashMap k v1) -> Int -> HashMap k v1
forall a. Array a -> Int -> a
A.index Array (HashMap k v1)
ary Int
i) of
Empty -> Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
forall s.
Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
step Array (HashMap k v1)
ary MArray s (HashMap k v2)
mary (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Bits a => a -> a
complement Hash
bi) (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
j
(Hash
bi Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` 1) Int
n
t :: HashMap k v2
t -> do MArray s (HashMap k v2) -> Int -> HashMap k v2 -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (HashMap k v2)
mary Int
j HashMap k v2
t
Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
forall s.
Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
step Array (HashMap k v1)
ary MArray s (HashMap k v2)
mary Hash
b (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Hash
bi Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` 1) Int
n
filterC :: Array (Leaf k v1) -> Hash -> HashMap k v2
filterC ary0 :: Array (Leaf k v1)
ary0 h :: Hash
h =
let !n :: Int
n = Array (Leaf k v1) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v1)
ary0
in (forall s. ST s (HashMap k v2)) -> HashMap k v2
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (HashMap k v2)) -> HashMap k v2)
-> (forall s. ST s (HashMap k v2)) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ do
MArray s (Leaf k v2)
mary <- Int -> ST s (MArray s (Leaf k v2))
forall s a. Int -> ST s (MArray s a)
A.new_ Int
n
Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
forall s.
Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
step Array (Leaf k v1)
ary0 MArray s (Leaf k v2)
mary 0 0 Int
n
where
step :: A.Array (Leaf k v1) -> A.MArray s (Leaf k v2)
-> Int -> Int -> Int
-> ST s (HashMap k v2)
step :: Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
step !Array (Leaf k v1)
ary !MArray s (Leaf k v2)
mary i :: Int
i !Int
j n :: Int
n
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = case Int
j of
0 -> HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v2
forall k v. HashMap k v
Empty
1 -> do Leaf k v2
l <- MArray s (Leaf k v2) -> Int -> ST s (Leaf k v2)
forall s a. MArray s a -> Int -> ST s a
A.read MArray s (Leaf k v2)
mary 0
HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v2 -> ST s (HashMap k v2))
-> HashMap k v2 -> ST s (HashMap k v2)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v2 -> HashMap k v2
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h Leaf k v2
l
_ | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j -> do Array (Leaf k v2)
ary2 <- MArray s (Leaf k v2) -> ST s (Array (Leaf k v2))
forall s a. MArray s a -> ST s (Array a)
A.unsafeFreeze MArray s (Leaf k v2)
mary
HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v2 -> ST s (HashMap k v2))
-> HashMap k v2 -> ST s (HashMap k v2)
forall a b. (a -> b) -> a -> b
$! Hash -> Array (Leaf k v2) -> HashMap k v2
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h Array (Leaf k v2)
ary2
| Bool
otherwise -> do Array (Leaf k v2)
ary2 <- MArray s (Leaf k v2) -> Int -> ST s (Array (Leaf k v2))
forall s a. MArray s a -> Int -> ST s (Array a)
A.trim MArray s (Leaf k v2)
mary Int
j
HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v2 -> ST s (HashMap k v2))
-> HashMap k v2 -> ST s (HashMap k v2)
forall a b. (a -> b) -> a -> b
$! Hash -> Array (Leaf k v2) -> HashMap k v2
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h Array (Leaf k v2)
ary2
| Just el :: Leaf k v2
el <- Leaf k v1 -> Maybe (Leaf k v2)
onColl (Leaf k v1 -> Maybe (Leaf k v2)) -> Leaf k v1 -> Maybe (Leaf k v2)
forall a b. (a -> b) -> a -> b
$! Array (Leaf k v1) -> Int -> Leaf k v1
forall a. Array a -> Int -> a
A.index Array (Leaf k v1)
ary Int
i
= MArray s (Leaf k v2) -> Int -> Leaf k v2 -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (Leaf k v2)
mary Int
j Leaf k v2
el ST s () -> ST s (HashMap k v2) -> ST s (HashMap k v2)
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
forall s.
Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
step Array (Leaf k v1)
ary MArray s (Leaf k v2)
mary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
n
| Bool
otherwise = Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
forall s.
Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
step Array (Leaf k v1)
ary MArray s (Leaf k v2)
mary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
j Int
n
{-# INLINE filterMapAux #-}
filter :: (v -> Bool) -> HashMap k v -> HashMap k v
filter :: (v -> Bool) -> HashMap k v -> HashMap k v
filter p :: v -> Bool
p = (k -> v -> Bool) -> HashMap k v -> HashMap k v
forall k v. (k -> v -> Bool) -> HashMap k v -> HashMap k v
filterWithKey (\_ v :: v
v -> v -> Bool
p v
v)
{-# INLINE filter #-}
keys :: HashMap k v -> [k]
keys :: HashMap k v -> [k]
keys = ((k, v) -> k) -> [(k, v)] -> [k]
forall a b. (a -> b) -> [a] -> [b]
List.map (k, v) -> k
forall a b. (a, b) -> a
fst ([(k, v)] -> [k])
-> (HashMap k v -> [(k, v)]) -> HashMap k v -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap k v -> [(k, v)]
forall k v. HashMap k v -> [(k, v)]
toList
{-# INLINE keys #-}
elems :: HashMap k v -> [v]
elems :: HashMap k v -> [v]
elems = ((k, v) -> v) -> [(k, v)] -> [v]
forall a b. (a -> b) -> [a] -> [b]
List.map (k, v) -> v
forall a b. (a, b) -> b
snd ([(k, v)] -> [v])
-> (HashMap k v -> [(k, v)]) -> HashMap k v -> [v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap k v -> [(k, v)]
forall k v. HashMap k v -> [(k, v)]
toList
{-# INLINE elems #-}
toList :: HashMap k v -> [(k, v)]
toList :: HashMap k v -> [(k, v)]
toList t :: HashMap k v
t = (forall b. ((k, v) -> b -> b) -> b -> b) -> [(k, v)]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
Exts.build (\ c :: (k, v) -> b -> b
c z :: b
z -> (k -> v -> b -> b) -> b -> HashMap k v -> b
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey (((k, v) -> b -> b) -> k -> v -> b -> b
forall a b c. ((a, b) -> c) -> a -> b -> c
curry (k, v) -> b -> b
c) b
z HashMap k v
t)
{-# INLINE toList #-}
fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList :: [(k, v)] -> HashMap k v
fromList = (HashMap k v -> (k, v) -> HashMap k v)
-> HashMap k v -> [(k, v)] -> HashMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\ m :: HashMap k v
m (k :: k
k, v :: v
v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
unsafeInsert k
k v
v HashMap k v
m) HashMap k v
forall k v. HashMap k v
empty
{-# INLINABLE fromList #-}
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWith :: (v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWith f :: v -> v -> v
f = (HashMap k v -> (k, v) -> HashMap k v)
-> HashMap k v -> [(k, v)] -> HashMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\ m :: HashMap k v
m (k :: k
k, v :: v
v) -> (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWith v -> v -> v
f k
k v
v HashMap k v
m) HashMap k v
forall k v. HashMap k v
empty
{-# INLINE fromListWith #-}
fromListWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWithKey :: (k -> v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWithKey f :: k -> v -> v -> v
f = (HashMap k v -> (k, v) -> HashMap k v)
-> HashMap k v -> [(k, v)] -> HashMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\ m :: HashMap k v
m (k :: k
k, v :: v
v) -> (k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWithKey k -> v -> v -> v
f k
k v
v HashMap k v
m) HashMap k v
forall k v. HashMap k v
empty
{-# INLINE fromListWithKey #-}
lookupInArrayCont ::
forall rep (r :: TYPE rep) k v.
Eq k => ((# #) -> r) -> (v -> Int -> r) -> k -> A.Array (Leaf k v) -> r
lookupInArrayCont :: ((# #) -> r) -> (v -> Int -> r) -> k -> Array (Leaf k v) -> r
lookupInArrayCont absent :: (# #) -> r
absent present :: v -> Int -> r
present k0 :: k
k0 ary0 :: Array (Leaf k v)
ary0 = k -> Array (Leaf k v) -> Int -> Int -> r
Eq k => k -> Array (Leaf k v) -> Int -> Int -> r
go k
k0 Array (Leaf k v)
ary0 0 (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary0)
where
go :: Eq k => k -> A.Array (Leaf k v) -> Int -> Int -> r
go :: k -> Array (Leaf k v) -> Int -> Int -> r
go !k
k !Array (Leaf k v)
ary !Int
i !Int
n
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = (# #) -> r
absent (# #)
| Bool
otherwise = case Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
ary Int
i of
(L kx :: k
kx v :: v
v)
| k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx -> v -> Int -> r
present v
v Int
i
| Bool
otherwise -> k -> Array (Leaf k v) -> Int -> Int -> r
Eq k => k -> Array (Leaf k v) -> Int -> Int -> r
go k
k Array (Leaf k v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
n
{-# INLINE lookupInArrayCont #-}
indexOf :: Eq k => k -> A.Array (Leaf k v) -> Maybe Int
indexOf :: k -> Array (Leaf k v) -> Maybe Int
indexOf k0 :: k
k0 ary0 :: Array (Leaf k v)
ary0 = k -> Array (Leaf k v) -> Int -> Int -> Maybe Int
forall t v.
Eq t =>
t -> Array (Leaf t v) -> Int -> Int -> Maybe Int
go k
k0 Array (Leaf k v)
ary0 0 (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary0)
where
go :: t -> Array (Leaf t v) -> Int -> Int -> Maybe Int
go !t
k !Array (Leaf t v)
ary !Int
i !Int
n
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = Maybe Int
forall a. Maybe a
Nothing
| Bool
otherwise = case Array (Leaf t v) -> Int -> Leaf t v
forall a. Array a -> Int -> a
A.index Array (Leaf t v)
ary Int
i of
(L kx :: t
kx _)
| t
k t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
kx -> Int -> Maybe Int
forall a. a -> Maybe a
Just Int
i
| Bool
otherwise -> t -> Array (Leaf t v) -> Int -> Int -> Maybe Int
go t
k Array (Leaf t v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
n
{-# INLINABLE indexOf #-}
updateWith# :: Eq k => (v -> (# v #)) -> k -> A.Array (Leaf k v) -> A.Array (Leaf k v)
updateWith# :: (v -> (# v #)) -> k -> Array (Leaf k v) -> Array (Leaf k v)
updateWith# f :: v -> (# v #)
f k0 :: k
k0 ary0 :: Array (Leaf k v)
ary0 = k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k0 Array (Leaf k v)
ary0 0 (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary0)
where
go :: k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go !k
k !Array (Leaf k v)
ary !Int
i !Int
n
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = Array (Leaf k v)
ary
| Bool
otherwise = case Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
ary Int
i of
(L kx :: k
kx y :: v
y) | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx -> case v -> (# v #)
f v
y of
(# y' :: v
y' #)
| v -> v -> Bool
forall a. a -> a -> Bool
ptrEq v
y v
y' -> Array (Leaf k v)
ary
| Bool
otherwise -> Array (Leaf k v) -> Int -> Leaf k v -> Array (Leaf k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (Leaf k v)
ary Int
i (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
y')
| Bool
otherwise -> k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k Array (Leaf k v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
n
{-# INLINABLE updateWith# #-}
updateOrSnocWith :: Eq k => (v -> v -> (# v #)) -> k -> v -> A.Array (Leaf k v)
-> A.Array (Leaf k v)
updateOrSnocWith :: (v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWith f :: v -> v -> (# v #)
f = (k -> v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey ((v -> v -> (# v #)) -> k -> v -> v -> (# v #)
forall a b. a -> b -> a
const v -> v -> (# v #)
f)
{-# INLINABLE updateOrSnocWith #-}
updateOrSnocWithKey :: Eq k => (k -> v -> v -> (# v #)) -> k -> v -> A.Array (Leaf k v)
-> A.Array (Leaf k v)
updateOrSnocWithKey :: (k -> v -> v -> (# v #))
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey f :: k -> v -> v -> (# v #)
f k0 :: k
k0 v0 :: v
v0 ary0 :: Array (Leaf k v)
ary0 = k -> v -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k0 v
v0 Array (Leaf k v)
ary0 0 (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary0)
where
go :: k -> v -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go !k
k v :: v
v !Array (Leaf k v)
ary !Int
i !Int
n
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall e. (forall s. ST s (MArray s e)) -> Array e
A.run ((forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v))
-> (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall a b. (a -> b) -> a -> b
$ do
MArray s (Leaf k v)
mary <- Int -> ST s (MArray s (Leaf k v))
forall s a. Int -> ST s (MArray s a)
A.new_ (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1)
Array (Leaf k v)
-> Int -> MArray s (Leaf k v) -> Int -> Int -> ST s ()
forall e s. Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
A.copy Array (Leaf k v)
ary 0 MArray s (Leaf k v)
mary 0 Int
n
MArray s (Leaf k v) -> Int -> Leaf k v -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (Leaf k v)
mary Int
n (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
v)
MArray s (Leaf k v) -> ST s (MArray s (Leaf k v))
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s (Leaf k v)
mary
| L kx :: k
kx y :: v
y <- Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
ary Int
i
, k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx
, (# v2 :: v
v2 #) <- k -> v -> v -> (# v #)
f k
k v
v v
y
= Array (Leaf k v) -> Int -> Leaf k v -> Array (Leaf k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (Leaf k v)
ary Int
i (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
v2)
| Bool
otherwise
= k -> v -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k v
v Array (Leaf k v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
n
{-# INLINABLE updateOrSnocWithKey #-}
updateOrConcatWith :: Eq k => (v -> v -> v) -> A.Array (Leaf k v) -> A.Array (Leaf k v) -> A.Array (Leaf k v)
updateOrConcatWith :: (v -> v -> v)
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
updateOrConcatWith f :: v -> v -> v
f = (k -> v -> v -> v)
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> v)
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
updateOrConcatWithKey ((v -> v -> v) -> k -> v -> v -> v
forall a b. a -> b -> a
const v -> v -> v
f)
{-# INLINABLE updateOrConcatWith #-}
updateOrConcatWithKey :: Eq k => (k -> v -> v -> v) -> A.Array (Leaf k v) -> A.Array (Leaf k v) -> A.Array (Leaf k v)
updateOrConcatWithKey :: (k -> v -> v -> v)
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
updateOrConcatWithKey f :: k -> v -> v -> v
f ary1 :: Array (Leaf k v)
ary1 ary2 :: Array (Leaf k v)
ary2 = (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall e. (forall s. ST s (MArray s e)) -> Array e
A.run ((forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v))
-> (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall a b. (a -> b) -> a -> b
$ do
let indices :: Array (Maybe Int)
indices = (Leaf k v -> Maybe Int) -> Array (Leaf k v) -> Array (Maybe Int)
forall a b. (a -> b) -> Array a -> Array b
A.map' (\(L k :: k
k _) -> k -> Array (Leaf k v) -> Maybe Int
forall k v. Eq k => k -> Array (Leaf k v) -> Maybe Int
indexOf k
k Array (Leaf k v)
ary1) Array (Leaf k v)
ary2
let nOnly2 :: Int
nOnly2 = (Int -> Maybe Int -> Int) -> Int -> Array (Maybe Int) -> Int
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' (\n :: Int
n -> Int -> (Int -> Int) -> Maybe Int -> Int
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int -> Int -> Int
forall a b. a -> b -> a
const Int
n)) 0 Array (Maybe Int)
indices
let n1 :: Int
n1 = Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary1
let n2 :: Int
n2 = Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary2
MArray s (Leaf k v)
mary <- Int -> ST s (MArray s (Leaf k v))
forall s a. Int -> ST s (MArray s a)
A.new_ (Int
n1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
nOnly2)
Array (Leaf k v)
-> Int -> MArray s (Leaf k v) -> Int -> Int -> ST s ()
forall e s. Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
A.copy Array (Leaf k v)
ary1 0 MArray s (Leaf k v)
mary 0 Int
n1
let go :: Int -> Int -> ST s ()
go !Int
iEnd !Int
i2
| Int
i2 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n2 = () -> ST s ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
| Bool
otherwise = case Array (Maybe Int) -> Int -> Maybe Int
forall a. Array a -> Int -> a
A.index Array (Maybe Int)
indices Int
i2 of
Just i1 :: Int
i1 -> do
L k :: k
k v1 :: v
v1 <- Array (Leaf k v) -> Int -> ST s (Leaf k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (Leaf k v)
ary1 Int
i1
L _ v2 :: v
v2 <- Array (Leaf k v) -> Int -> ST s (Leaf k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (Leaf k v)
ary2 Int
i2
MArray s (Leaf k v) -> Int -> Leaf k v -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (Leaf k v)
mary Int
i1 (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k (k -> v -> v -> v
f k
k v
v1 v
v2))
Int -> Int -> ST s ()
go Int
iEnd (Int
i2Int -> Int -> Int
forall a. Num a => a -> a -> a
+1)
Nothing -> do
MArray s (Leaf k v) -> Int -> Leaf k v -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (Leaf k v)
mary Int
iEnd (Leaf k v -> ST s ()) -> ST s (Leaf k v) -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Array (Leaf k v) -> Int -> ST s (Leaf k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (Leaf k v)
ary2 Int
i2
Int -> Int -> ST s ()
go (Int
iEndInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i2Int -> Int -> Int
forall a. Num a => a -> a -> a
+1)
Int -> Int -> ST s ()
go Int
n1 0
MArray s (Leaf k v) -> ST s (MArray s (Leaf k v))
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s (Leaf k v)
mary
{-# INLINABLE updateOrConcatWithKey #-}
subsetArray :: Eq k => (v1 -> v2 -> Bool) -> A.Array (Leaf k v1) -> A.Array (Leaf k v2) -> Bool
subsetArray :: (v1 -> v2 -> Bool)
-> Array (Leaf k v1) -> Array (Leaf k v2) -> Bool
subsetArray cmpV :: v1 -> v2 -> Bool
cmpV ary1 :: Array (Leaf k v1)
ary1 ary2 :: Array (Leaf k v2)
ary2 = Array (Leaf k v1) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v1)
ary1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Array (Leaf k v2) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v2)
ary2 Bool -> Bool -> Bool
&& (Leaf k v1 -> Bool) -> Array (Leaf k v1) -> Bool
forall a. (a -> Bool) -> Array a -> Bool
A.all Leaf k v1 -> Bool
inAry2 Array (Leaf k v1)
ary1
where
inAry2 :: Leaf k v1 -> Bool
inAry2 (L k1 :: k
k1 v1 :: v1
v1) = ((# #) -> Bool)
-> (v2 -> Int -> Bool) -> k -> Array (Leaf k v2) -> Bool
forall r k v.
Eq k =>
((# #) -> r) -> (v -> Int -> r) -> k -> Array (Leaf k v) -> r
lookupInArrayCont (\_ -> Bool
False) (\v2 :: v2
v2 _ -> v1 -> v2 -> Bool
cmpV v1
v1 v2
v2) k
k1 Array (Leaf k v2)
ary2
{-# INLINE inAry2 #-}
update32 :: A.Array e -> Int -> e -> A.Array e
update32 :: Array e -> Int -> e -> Array e
update32 ary :: Array e
ary idx :: Int
idx b :: e
b = (forall s. ST s (Array e)) -> Array e
forall a. (forall s. ST s a) -> a
runST (Array e -> Int -> e -> ST s (Array e)
forall e s. Array e -> Int -> e -> ST s (Array e)
update32M Array e
ary Int
idx e
b)
{-# INLINE update32 #-}
update32M :: A.Array e -> Int -> e -> ST s (A.Array e)
update32M :: Array e -> Int -> e -> ST s (Array e)
update32M ary :: Array e
ary idx :: Int
idx b :: e
b = do
MArray s e
mary <- Array e -> ST s (MArray s e)
forall e s. Array e -> ST s (MArray s e)
clone Array e
ary
MArray s e -> Int -> e -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s e
mary Int
idx e
b
MArray s e -> ST s (Array e)
forall s a. MArray s a -> ST s (Array a)
A.unsafeFreeze MArray s e
mary
{-# INLINE update32M #-}
update32With' :: A.Array e -> Int -> (e -> e) -> A.Array e
update32With' :: Array e -> Int -> (e -> e) -> Array e
update32With' ary :: Array e
ary idx :: Int
idx f :: e -> e
f
| (# x :: e
x #) <- Array e -> Int -> (# e #)
forall a. Array a -> Int -> (# a #)
A.index# Array e
ary Int
idx
= Array e -> Int -> e -> Array e
forall e. Array e -> Int -> e -> Array e
update32 Array e
ary Int
idx (e -> Array e) -> e -> Array e
forall a b. (a -> b) -> a -> b
$! e -> e
f e
x
{-# INLINE update32With' #-}
clone :: A.Array e -> ST s (A.MArray s e)
clone :: Array e -> ST s (MArray s e)
clone ary :: Array e
ary =
Array e -> Int -> Int -> ST s (MArray s e)
forall e s. Array e -> Int -> Int -> ST s (MArray s e)
A.thaw Array e
ary 0 (2Int -> Int -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^Int
bitsPerSubkey)
bitsPerSubkey :: Int
bitsPerSubkey :: Int
bitsPerSubkey = 5
maxChildren :: Int
maxChildren :: Int
maxChildren = 1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`unsafeShiftL` Int
bitsPerSubkey
subkeyMask :: Bitmap
subkeyMask :: Hash
subkeyMask = 1 Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` Int
bitsPerSubkey Hash -> Hash -> Hash
forall a. Num a => a -> a -> a
- 1
sparseIndex :: Bitmap -> Bitmap -> Int
sparseIndex :: Hash -> Hash -> Int
sparseIndex b :: Hash
b m :: Hash
m = Hash -> Int
forall a. Bits a => a -> Int
popCount (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. (Hash
m Hash -> Hash -> Hash
forall a. Num a => a -> a -> a
- 1))
{-# INLINE sparseIndex #-}
mask :: Word -> Shift -> Bitmap
mask :: Hash -> Int -> Hash
mask w :: Hash
w s :: Int
s = 1 Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` Hash -> Int -> Int
index Hash
w Int
s
{-# INLINE mask #-}
index :: Hash -> Shift -> Int
index :: Hash -> Int -> Int
index w :: Hash
w s :: Int
s = Hash -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Hash -> Int) -> Hash -> Int
forall a b. (a -> b) -> a -> b
$ (Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
unsafeShiftR Hash
w Int
s) Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
subkeyMask
{-# INLINE index #-}
fullNodeMask :: Bitmap
fullNodeMask :: Hash
fullNodeMask = Hash -> Hash
forall a. Bits a => a -> a
complement (Hash -> Hash
forall a. Bits a => a -> a
complement 0 Hash -> Int -> Hash
forall a. Bits a => a -> Int -> a
`unsafeShiftL` Int
maxChildren)
{-# INLINE fullNodeMask #-}
ptrEq :: a -> a -> Bool
ptrEq :: a -> a -> Bool
ptrEq x :: a
x y :: a
y = Int# -> Bool
Exts.isTrue# (a -> a -> Int#
forall a. a -> a -> Int#
Exts.reallyUnsafePtrEquality# a
x a
y Int# -> Int# -> Int#
==# 1#)
{-# INLINE ptrEq #-}
instance (Eq k, Hashable k) => Exts.IsList (HashMap k v) where
type Item (HashMap k v) = (k, v)
fromList :: [Item (HashMap k v)] -> HashMap k v
fromList = [Item (HashMap k v)] -> HashMap k v
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList
toList :: HashMap k v -> [Item (HashMap k v)]
toList = HashMap k v -> [Item (HashMap k v)]
forall k v. HashMap k v -> [(k, v)]
toList