|
-- | Create a map from two key-value pairs which hashes don't collide. To |
|
-- enhance sharing, the second key-value pair is represented by the hash of its |
|
-- key and a singleton HashMap pairing its key with its value. |
|
-- |
|
-- Note: to avoid silly thunks, this function must be strict in the |
|
-- key. See issue #232. We don't need to force the HashMap argument |
|
-- because it's already in WHNF (having just been matched) and we |
|
-- just put it directly in an array. |
|
two :: Shift -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v) |
This function is currently used in various insert* variants when we encounter a Leaf node that has a different hash, e.g. in insert' on line 783:
|
insert' :: Eq k => Hash -> k -> v -> HashMap k v -> HashMap k v |
|
insert' h0 k0 v0 m0 = go h0 k0 v0 0 m0 |
|
where |
|
go !h !k x !_ Empty = Leaf h (L k x) |
|
go h k x s t@(Leaf hy l@(L ky y)) |
|
| hy == h = if ky == k |
|
then if x `ptrEq` y |
|
then t |
|
else Leaf h (L k x) |
|
else collision h l (L k x) |
|
| otherwise = runST (two s h k x hy t) |
|
go h k x s t@(BitmapIndexed b ary) |
|
| b .&. m == 0 = |
|
let !ary' = A.insert ary i $! Leaf h (L k x) |
|
in bitmapIndexedOrFull (b .|. m) ary' |
|
| otherwise = |
|
let !st = A.index ary i |
|
!st' = go h k x (nextShift s) st |
|
in if st' `ptrEq` st |
|
then t |
|
else BitmapIndexed b (A.update ary i st') |
|
where m = mask h s |
|
i = sparseIndex b m |
|
go h k x s t@(Full ary) = |
|
let !st = A.index ary i |
|
!st' = go h k x (nextShift s) st |
|
in if st' `ptrEq` st |
|
then t |
|
else Full (update32 ary i st') |
|
where i = index h s |
|
go h k x s t@(Collision hy v) |
|
| h == hy = Collision h (updateOrSnocWith (\a _ -> (# a #)) k x v) |
|
| otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t) |
|
{-# INLINABLE insert' #-} |
I think we could also use it when we encounter Collisions with different hashes. In the example above that would be line 805.
That would save some allocations. And maybe reduce code size a bit?!
