← Back to branch summary

~rdoering/ubuntu/karmic/erlang/fix-535090

« back to all changes in this revision

Viewing changes to lib/hipe/util/hipe_digraph.erl

  • Committer: Bazaar Package Importer
  • Author(s): Sergei Golovan
  • Date: 2009-02-15 16:42:52 UTC
  • mfrom: (3.1.2 squeeze)
  • Revision ID: james.westby@ubuntu.com-20090215164252-q5x4rcf8a5pbesb1
Tags: 1:12.b.5-dfsg-2
Upload to unstable after lenny is released.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/hipe/util/hipe_digraph.erl
14
14
 
15
15
%%------------------------------------------------------------------------
16
16
 
17
 
-type(set()     :: tuple()).  % XXX: temporarily
18
 
-type(dict()    :: tuple()).  % XXX: temporarily
19
 
-type(ordset(T) :: [T]).      % XXX: temporarily
 
17
-type set()     :: tuple().  % XXX: temporarily
 
18
-type dict()    :: tuple().  % XXX: temporarily
 
19
-type ordset(T) :: [T].      % XXX: temporarily
20
20
 
21
21
-include("hipe_digraph.hrl").
22
22
 
23
23
%%------------------------------------------------------------------------
24
24
 
25
 
-spec(new/0 :: () -> #hipe_digraph{}).
 
25
-spec new() -> #hipe_digraph{}.
26
26
 
27
27
new() ->
28
28
  #hipe_digraph{edges=dict:new(), rev_edges=dict:new(), 
29
29
                leaves=ordsets:new(), nodes=sets:new()}.
30
30
 
31
 
-spec(from_list/1 :: ([_]) -> #hipe_digraph{}).
 
31
-spec from_list([_]) -> #hipe_digraph{}.
32
32
 
33
33
from_list(List) ->
34
34
  Edges = lists:foldl(fun({From, To}, Dict) -> 
49
49
  Nodes = sets:union(Keys1, Keys2),
50
50
  #hipe_digraph{edges=Edges, leaves=[], rev_edges=RevEdges, nodes=Nodes}.
51
51
 
52
 
-spec(to_list/1 :: (#hipe_digraph{}) -> [_]).
 
52
-spec to_list(#hipe_digraph{}) -> [_].
53
53
 
54
54
to_list(#hipe_digraph{edges=Edges}) ->
55
55
  List1 = dict:to_list(Edges),
58
58
                      end, [], List1),
59
59
  lists:flatten(List2).
60
60
 
61
 
-spec(add_node/2 :: (_, #hipe_digraph{}) -> #hipe_digraph{}).
 
61
-spec add_node(_, #hipe_digraph{}) -> #hipe_digraph{}.
62
62
 
63
63
add_node(NewNode, DG = #hipe_digraph{nodes=Nodes}) ->
64
64
  DG#hipe_digraph{nodes=sets:add_element(NewNode, Nodes)}.
65
65
 
66
 
-spec(add_node_list/2 :: ([_], #hipe_digraph{}) -> #hipe_digraph{}).
 
66
-spec add_node_list([_], #hipe_digraph{}) -> #hipe_digraph{}.
67
67
 
68
68
add_node_list(NewNodes, DG = #hipe_digraph{nodes=Nodes}) ->
69
69
  Set = sets:from_list(NewNodes),
70
70
  DG#hipe_digraph{nodes=sets:union(Set, Nodes)}.
71
71
 
72
 
-spec(add_edge/3 :: (_, _, #hipe_digraph{}) -> #hipe_digraph{}).
 
72
-spec add_edge(_, _, #hipe_digraph{}) -> #hipe_digraph{}.
73
73
 
74
74
add_edge(From, To, #hipe_digraph{edges=Edges, rev_edges=RevEdges, 
75
75
                                 leaves=Leaves, nodes=Nodes}) ->
85
85
 
86
86
%%-------------------------------------------------------------------------
87
87
 
88
 
-spec(take_indep_scc/1 ::
89
 
      (#hipe_digraph{}) -> 'none' | {'ok', [_], #hipe_digraph{}}).
 
88
-spec take_indep_scc(#hipe_digraph{}) -> 'none' | {'ok', [_], #hipe_digraph{}}.
90
89
 
91
90
take_indep_scc(DG = #hipe_digraph{edges=Edges, rev_edges=RevEdges, 
92
91
                                  leaves=Leaves, nodes=Nodes}) ->
159
158
 
160
159
%%---------------------------------------------------------------------
161
160
 
162
 
-spec(reverse_preorder_sccs/1 :: (#hipe_digraph{}) -> [[_]]).
 
161
-spec reverse_preorder_sccs(#hipe_digraph{}) -> [[_]].
163
162
 
164
163
reverse_preorder_sccs(DG) ->
165
164
  reverse_preorder_sccs(DG, []).
172
171
 
173
172
%%---------------------------------------------------------------------
174
173
 
175
 
-spec(get_parents/2 :: (_, #hipe_digraph{}) -> [_]).
 
174
-spec get_parents(_, #hipe_digraph{}) -> [_].
176
175
 
177
176
get_parents(Node, #hipe_digraph{rev_edges=RevEdges}) ->
178
177
  case dict:is_key(Node, RevEdges) of
180
179
    false -> []
181
180
  end.
182
181
 
183
 
-spec(get_children/2 :: (_, #hipe_digraph{}) -> [_]).
 
182
-spec get_children(_, #hipe_digraph{}) -> [_].
184
183
 
185
184
get_children(Node, #hipe_digraph{edges=Edges}) ->
186
185
  case dict:is_key(Node, Edges) of