projects
/
ghc-hetmet.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Simon's big boxy-type commit
[ghc-hetmet.git]
/
ghc
/
compiler
/
utils
/
UniqFM.lhs
diff --git
a/ghc/compiler/utils/UniqFM.lhs
b/ghc/compiler/utils/UniqFM.lhs
index
18efa0e
..
84294aa
100644
(file)
--- a/
ghc/compiler/utils/UniqFM.lhs
+++ b/
ghc/compiler/utils/UniqFM.lhs
@@
-1,4
+1,4
@@
-%
+%ilter
% (c) The AQUA Project, Glasgow University, 1994-1998
%
\section[UniqFM]{Specialised finite maps, for things with @Uniques@}
% (c) The AQUA Project, Glasgow University, 1994-1998
%
\section[UniqFM]{Specialised finite maps, for things with @Uniques@}
@@
-19,7
+19,7
@@
module UniqFM (
unitDirectlyUFM,
listToUFM,
listToUFM_Directly,
unitDirectlyUFM,
listToUFM,
listToUFM_Directly,
- addToUFM,addToUFM_C,
+ addToUFM,addToUFM_C,addToUFM_Acc,
addListToUFM,addListToUFM_C,
addToUFM_Directly,
addListToUFM_Directly,
addListToUFM,addListToUFM_C,
addToUFM_Directly,
addListToUFM_Directly,
@@
-33,8
+33,8
@@
module UniqFM (
intersectUFM_C,
foldUFM,
mapUFM,
intersectUFM_C,
foldUFM,
mapUFM,
- elemUFM,
- filterUFM,
+ elemUFM, elemUFM_Directly,
+ filterUFM, filterUFM_Directly,
sizeUFM,
hashUFM,
isNullUFM,
sizeUFM,
hashUFM,
isNullUFM,
@@
-46,10
+46,8
@@
module UniqFM (
#include "HsVersions.h"
#include "HsVersions.h"
-import {-# SOURCE #-} Name ( Name )
-
import Unique ( Uniquable(..), Unique, getKey#, mkUniqueGrimily )
import Unique ( Uniquable(..), Unique, getKey#, mkUniqueGrimily )
-import Panic
+import Maybes ( maybeToBool )
import FastTypes
import Outputable
import FastTypes
import Outputable
@@
-84,6
+82,13
@@
addToUFM_C :: Uniquable key => (elt -> elt -> elt) -- old -> new -> result
-> key -> elt -- new
-> UniqFM elt -- result
-> key -> elt -- new
-> UniqFM elt -- result
+addToUFM_Acc :: Uniquable key =>
+ (elt -> elts -> elts) -- Add to existing
+ -> (elt -> elts) -- New element
+ -> UniqFM elts -- old
+ -> key -> elt -- new
+ -> UniqFM elts -- result
+
addListToUFM_C :: Uniquable key => (elt -> elt -> elt)
-> UniqFM elt -> [(key,elt)]
-> UniqFM elt
addListToUFM_C :: Uniquable key => (elt -> elt -> elt)
-> UniqFM elt -> [(key,elt)]
-> UniqFM elt
@@
-105,10
+110,12
@@
intersectUFM_C :: (elt1 -> elt2 -> elt3)
foldUFM :: (elt -> a -> a) -> a -> UniqFM elt -> a
mapUFM :: (elt1 -> elt2) -> UniqFM elt1 -> UniqFM elt2
filterUFM :: (elt -> Bool) -> UniqFM elt -> UniqFM elt
foldUFM :: (elt -> a -> a) -> a -> UniqFM elt -> a
mapUFM :: (elt1 -> elt2) -> UniqFM elt1 -> UniqFM elt2
filterUFM :: (elt -> Bool) -> UniqFM elt -> UniqFM elt
+filterUFM_Directly :: (Unique -> elt -> Bool) -> UniqFM elt -> UniqFM elt
sizeUFM :: UniqFM elt -> Int
hashUFM :: UniqFM elt -> Int
elemUFM :: Uniquable key => key -> UniqFM elt -> Bool
sizeUFM :: UniqFM elt -> Int
hashUFM :: UniqFM elt -> Int
elemUFM :: Uniquable key => key -> UniqFM elt -> Bool
+elemUFM_Directly:: Unique -> UniqFM elt -> Bool
lookupUFM :: Uniquable key => UniqFM elt -> key -> Maybe elt
lookupUFM_Directly -- when you've got the Unique already
lookupUFM :: Uniquable key => UniqFM elt -> key -> Maybe elt
lookupUFM_Directly -- when you've got the Unique already
@@
-194,6
+201,7
@@
data UniqFM ele
FastInt -- the delta
(UniqFM ele)
(UniqFM ele)
FastInt -- the delta
(UniqFM ele)
(UniqFM ele)
+-- INVARIANT: the children of a NodeUFM are never EmptyUFMs
{-
-- for debugging only :-)
{-
-- for debugging only :-)
@@
-245,6
+253,11
@@
addToUFM_Directly fm u elt = insert_ele use_snd fm (getKey# u) elt
addToUFM_C combiner fm key elt
= insert_ele combiner fm (getKey# (getUnique key)) elt
addToUFM_C combiner fm key elt
= insert_ele combiner fm (getKey# (getUnique key)) elt
+addToUFM_Acc add unit fm key item
+ = insert_ele combiner fm (getKey# (getUnique key)) (unit item)
+ where
+ combiner old _unit_item = add item old
+
addListToUFM fm key_elt_pairs = addListToUFM_C use_snd fm key_elt_pairs
addListToUFM_Directly fm uniq_elt_pairs = addListToUFM_directly_C use_snd fm uniq_elt_pairs
addListToUFM fm key_elt_pairs = addListToUFM_C use_snd fm key_elt_pairs
addListToUFM_Directly fm uniq_elt_pairs = addListToUFM_directly_C use_snd fm uniq_elt_pairs
@@
-334,25
+347,25
@@
plusUFM_C f fm1 fm2 = mix_trees fm1 fm2
-- t1 t2 t1' t2' t1 t2 + j'
-- / \
-- t1' t2'
-- t1 t2 t1' t2' t1 t2 + j'
-- / \
-- t1' t2'
- mix_branches (LeftRoot Leftt) -- | trace "LL" True
+ mix_branches (LeftRoot Leftt) -- | trace "LL" True
= mkSLNodeUFM
(NodeUFMData j p)
(mix_trees t1 right_t)
t2
= mkSLNodeUFM
(NodeUFMData j p)
(mix_trees t1 right_t)
t2
- mix_branches (LeftRoot Rightt) -- | trace "LR" True
+ mix_branches (LeftRoot Rightt) -- | trace "LR" True
= mkLSNodeUFM
(NodeUFMData j p)
t1
(mix_trees t2 right_t)
= mkLSNodeUFM
(NodeUFMData j p)
t1
(mix_trees t2 right_t)
- mix_branches (RightRoot Leftt) -- | trace "RL" True
+ mix_branches (RightRoot Leftt) -- | trace "RL" True
= mkSLNodeUFM
(NodeUFMData j' p')
(mix_trees left_t t1')
t2'
= mkSLNodeUFM
(NodeUFMData j' p')
(mix_trees left_t t1')
t2'
- mix_branches (RightRoot Rightt) -- | trace "RR" True
+ mix_branches (RightRoot Rightt) -- | trace "RR" True
= mkLSNodeUFM
(NodeUFMData j' p')
t1'
= mkLSNodeUFM
(NodeUFMData j' p')
t1'
@@
-514,7
+527,14
@@
mapUFM fn EmptyUFM = EmptyUFM
mapUFM fn fm = map_tree fn fm
filterUFM fn EmptyUFM = EmptyUFM
mapUFM fn fm = map_tree fn fm
filterUFM fn EmptyUFM = EmptyUFM
-filterUFM fn fm = filter_tree fn fm
+filterUFM fn fm = filter_tree pred fm
+ where
+ pred (i::FastInt) e = fn e
+
+filterUFM_Directly fn EmptyUFM = EmptyUFM
+filterUFM_Directly fn fm = filter_tree pred fm
+ where
+ pred i e = fn (mkUniqueGrimily (iBox i)) e
\end{code}
Note, this takes a long time, O(n), but
\end{code}
Note, this takes a long time, O(n), but
@@
-541,9
+561,8
@@
looking up in a hurry is the {\em whole point} of this binary tree lark.
Lookup up a binary tree is easy (and fast).
\begin{code}
Lookup up a binary tree is easy (and fast).
\begin{code}
-elemUFM key fm = case lookUp fm (getKey# (getUnique key)) of
- Nothing -> False
- Just _ -> True
+elemUFM key fm = maybeToBool (lookupUFM fm key)
+elemUFM_Directly key fm = maybeToBool (lookupUFM_Directly fm key)
lookupUFM fm key = lookUp fm (getKey# (getUnique key))
lookupUFM_Directly fm key = lookUp fm (getKey# key)
lookupUFM fm key = lookUp fm (getKey# (getUnique key))
lookupUFM_Directly fm key = lookUp fm (getKey# key)
@@
-652,7
+671,7
@@
and if necessary do $\lambda$ lifting on our functions that are bound.
\begin{code}
insert_ele
\begin{code}
insert_ele
- :: (a -> a -> a)
+ :: (a -> a -> a) -- old -> new -> result
-> UniqFM a
-> FastInt
-> a
-> UniqFM a
-> FastInt
-> a
@@
-698,19
+717,20
@@
insert_ele f n@(NodeUFM j p t1 t2) i a
\begin{code}
map_tree f (NodeUFM j p t1 t2)
\begin{code}
map_tree f (NodeUFM j p t1 t2)
- = mkSSNodeUFM (NodeUFMData j p) (map_tree f t1) (map_tree f t2)
+ = mkLLNodeUFM (NodeUFMData j p) (map_tree f t1) (map_tree f t2)
+ -- NB. lazy! we know the tree is well-formed.
map_tree f (LeafUFM i obj)
= mkLeafUFM i (f obj)
map_tree f (LeafUFM i obj)
= mkLeafUFM i (f obj)
-
map_tree f _ = panic "map_tree failed"
\end{code}
\begin{code}
map_tree f _ = panic "map_tree failed"
\end{code}
\begin{code}
+filter_tree :: (FastInt -> a -> Bool) -> UniqFM a -> UniqFM a
filter_tree f nd@(NodeUFM j p t1 t2)
= mkSSNodeUFM (NodeUFMData j p) (filter_tree f t1) (filter_tree f t2)
filter_tree f lf@(LeafUFM i obj)
filter_tree f nd@(NodeUFM j p t1 t2)
= mkSSNodeUFM (NodeUFMData j p) (filter_tree f t1) (filter_tree f t2)
filter_tree f lf@(LeafUFM i obj)
- | f obj = lf
+ | f i obj = lf
| otherwise = EmptyUFM
filter_tree f _ = panic "filter_tree failed"
\end{code}
| otherwise = EmptyUFM
filter_tree f _ = panic "filter_tree failed"
\end{code}