aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/misc
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/misc')
-rw-r--r--lib/hipe/misc/hipe_sdi.erl69
-rw-r--r--lib/hipe/misc/hipe_segment_trees.erl49
2 files changed, 82 insertions, 36 deletions
diff --git a/lib/hipe/misc/hipe_sdi.erl b/lib/hipe/misc/hipe_sdi.erl
index 38a798875c..5ca64bc669 100644
--- a/lib/hipe/misc/hipe_sdi.erl
+++ b/lib/hipe/misc/hipe_sdi.erl
@@ -195,17 +195,27 @@ initSPAN(SdiNr, N, SDIS, SPAN) ->
-spec mk_parents(non_neg_integer(), tuple()) -> parents().
mk_parents(N, SDIS) ->
- Ranges = parents_generate_ranges(N-1, SDIS, []),
- hipe_segment_trees:build(Ranges).
+ PrevSDIS = vector_from_list(select_prev_sdis(N-1, SDIS, [])),
+ Ranges = parents_generate_ranges(N-1, PrevSDIS, []),
+ {PrevSDIS, hipe_segment_trees:build(Ranges)}.
-parents_generate_ranges(-1, _SDIS, Acc) -> Acc;
-parents_generate_ranges(SdiNr, SDIS, Acc) ->
+select_prev_sdis(-1, _SDIS, Acc) -> Acc;
+select_prev_sdis(SdiNr, SDIS, Acc) ->
#sdi_data{prevSdi=PrevSdi} = vector_sub(SDIS, SdiNr),
- {LO,HI} = % inclusive
- if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi}; % forwards
- true -> {PrevSdi+1, SdiNr-1} % backwards
- end,
- parents_generate_ranges(SdiNr-1, SDIS, [{LO,HI}|Acc]).
+ select_prev_sdis(SdiNr-1, SDIS, [PrevSdi|Acc]).
+
+parents_generate_ranges(-1, _PrevSDIS, Acc) -> Acc;
+parents_generate_ranges(SdiNr, PrevSDIS, Acc) ->
+ %% inclusive
+ {LO,HI} = parents_generate_range(SdiNr, PrevSDIS),
+ parents_generate_ranges(SdiNr-1, PrevSDIS, [{LO,HI}|Acc]).
+
+-compile({inline, parents_generate_range/2}).
+parents_generate_range(SdiNr, PrevSDIS) ->
+ PrevSdi = vector_sub(PrevSDIS, SdiNr),
+ if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi}; % forwards
+ true -> {PrevSdi+1, SdiNr-1} % backwards
+ end.
%%% "After the structure is built we process it as follows.
%%% For any node i whose listed span exceeds the architectural
@@ -244,27 +254,30 @@ initWKL(SdiNr, SDIS, SPAN, WKL) ->
-spec processWKL([non_neg_integer()], tuple(), hipe_array(),
parents(), hipe_array()) -> 'ok'.
processWKL([], _SDIS, _SPAN, _PARENTS, _LONG) -> ok;
-processWKL([Child|WKL], SDIS, SPAN, PARENTS, LONG) ->
- WKL2 = updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG),
+processWKL([Child|WKL], SDIS, SPAN, PARENTS0, LONG) ->
+ {WKL2, PARENTS} =
+ case array_sub(SPAN, Child) of
+ 0 -> {WKL, PARENTS0}; % removed
+ _ ->
+ SdiData = vector_sub(SDIS, Child),
+ Incr = sdiLongIncr(SdiData),
+ array_update(LONG, Child, Incr),
+ array_update(SPAN, Child, 0), % remove child
+ PARENTS1 = deleteParent(PARENTS0, Child),
+ PS = parentsOfChild(PARENTS1, Child),
+ {updateParents(PS, Child, Incr, SDIS, SPAN, WKL), PARENTS1}
+ end,
processWKL(WKL2, SDIS, SPAN, PARENTS, LONG).
--spec updateChild(non_neg_integer(), [non_neg_integer()], tuple(), hipe_array(),
- parents(), hipe_array()) -> [non_neg_integer()].
-updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG) ->
- case array_sub(SPAN, Child) of
- 0 -> WKL; % removed
- _ ->
- SdiData = vector_sub(SDIS, Child),
- Incr = sdiLongIncr(SdiData),
- array_update(LONG, Child, Incr),
- array_update(SPAN, Child, 0), % remove child
- PS = parentsOfChild(PARENTS, Child),
- updateParents(PS, Child, Incr, SDIS, SPAN, WKL)
- end.
-
-spec parentsOfChild(parents(), non_neg_integer()) -> [non_neg_integer()].
-parentsOfChild(IntervalTree, Child) ->
- hipe_segment_trees:intersect(Child, IntervalTree).
+parentsOfChild({_PrevSDIS, SegTree}, Child) ->
+ hipe_segment_trees:intersect(Child, SegTree).
+
+-spec deleteParent(parents(), non_neg_integer()) -> parents().
+deleteParent({PrevSDIS, SegTree0}, Parent) ->
+ {LO,HI} = parents_generate_range(Parent, PrevSDIS),
+ SegTree = hipe_segment_trees:delete(Parent, LO, HI, SegTree0),
+ {PrevSDIS, SegTree}.
-spec updateParents([non_neg_integer()], non_neg_integer(),
byte(), tuple(), hipe_array(),
@@ -297,10 +310,12 @@ updateWKL(SdiNr, SDIS, SdiSpan, WKL) ->
false -> [SdiNr|WKL]
end.
+-compile({inline, sdiSpanIsShort/2}). %% Only called once
-spec sdiSpanIsShort(#sdi_data{}, integer()) -> boolean().
sdiSpanIsShort(#sdi_data{si = #sdi_info{lb = LB, ub = UB}}, SdiSpan) ->
SdiSpan >= LB andalso SdiSpan =< UB.
+-compile({inline, sdiLongIncr/1}). %% Only called once
-spec sdiLongIncr(#sdi_data{}) -> byte().
sdiLongIncr(#sdi_data{si = #sdi_info{incr = Incr}}) -> Incr.
diff --git a/lib/hipe/misc/hipe_segment_trees.erl b/lib/hipe/misc/hipe_segment_trees.erl
index cbee328125..22146396c3 100644
--- a/lib/hipe/misc/hipe_segment_trees.erl
+++ b/lib/hipe/misc/hipe_segment_trees.erl
@@ -17,19 +17,16 @@
%%%
%%% %CopyrightEnd%
%%%
-%%% Segment trees.
+%%% Segment trees, with a delete operation.
%%%
%%% Keys are the (0-based) indices into the list passed to build/1.
%%%
%%% Range bounds are inclusive.
%%%
-%%% TODO: Change the shape of the tree to a perfect binary tree, and pack it as
-%%% an implicit data structure into tuples (like a binary heap would be) for
-%%% improved efficiency.
-module(hipe_segment_trees).
--export([build/1, intersect/2]).
+-export([build/1, intersect/2, delete/4]).
-record(segment_tree, {
lo :: integer(),
@@ -75,9 +72,7 @@ empty_tree_from_endpoints(Endpoints) ->
leaves([Endpoint]) -> [?POINT_LEAF(Endpoint)];
leaves([A | [B|_] = Tail]) ->
- %% We could omit the range leaf if it's empty, but we want to pack this data
- %% structure into an array (tuple) eventually, and then we *really* want
- %% every other leaf to be a range
+ %% We omit the range leaf if it's empty
case A<B-1 of
true -> [?POINT_LEAF(A),?RANGE_LEAF(A+1,B-1) | leaves(Tail)];
false -> [?POINT_LEAF(A) | leaves(Tail)]
@@ -121,7 +116,7 @@ insert_interval(I, {_Lo,_Hi}, _NLo, _NHi, Leaf) -> [I|Leaf].
intervals_intersect(ALo, AHi, BLo, BHi) ->
(ALo =< AHi) andalso (BLo =< BHi) %% both nonempty
- andalso (BLo =< AHi) andalso (ALo =< BHi).
+ andalso nonempty_intervals_intersect(ALo, AHi, BLo, BHi).
%% Purely optional optimisation
squash_empty_subtrees(?NODE(Left0, Right0, Mid, Segs)) ->
@@ -148,3 +143,39 @@ intersect_1(Point, ?NODE(Left, Right, Mid, Segs), Acc0) ->
Child = if Point =< Mid -> Left; true -> Right end,
intersect_1(Point, Child, Segs ++ Acc0);
intersect_1(_, LeafSegs, Acc) -> LeafSegs ++ Acc.
+
+%% @doc Deletes the interval {Lo, Hi}, which had index Index in the list passed
+%% to build/1.
+-spec delete(non_neg_integer(), integer(), integer(), tree()) -> tree().
+delete(_, _, _, nil) -> nil;
+delete(_, Lo, Hi, Tree) when Lo > Hi -> Tree;
+delete(_, Lo, Hi, Tree = #segment_tree{lo=TLo, hi=THi})
+ when Hi < TLo; Lo > THi -> Tree;
+delete(Index, Lo, Hi, Tree = #segment_tree{lo=TLo, hi=THi, root=Root0})
+ when is_integer(Lo), is_integer(Hi) ->
+ Root = delete_1(Index, Lo, Hi, TLo, THi, Root0),
+ Tree#segment_tree{root=Root}.
+
+delete_1(I, Lo, Hi, NLo, NHi, ?NODE(Left0, Right0, Mid, Segments)) ->
+ if Lo =< NLo, NHi =< Hi ->
+ ?NODE(Left0, Right0, Mid, delete_2(Segments, I));
+ true ->
+ Left = case nonempty_intervals_intersect(Lo, Hi, NLo, Mid) of
+ true -> delete_1(I, Lo, Hi, NLo, Mid, Left0);
+ false -> Left0
+ end,
+ Right = case nonempty_intervals_intersect(Lo, Hi, Mid+1, NHi) of
+ true -> delete_1(I, Lo, Hi, Mid+1, NHi, Right0);
+ false -> Right0
+ end,
+ %% We could do build_squash_node here, is it worth it?
+ ?NODE(Left, Right, Mid, Segments)
+ end;
+delete_1(I, _Lo, _Hi, _NLo, _NHi, Leaf) -> delete_2(Leaf, I).
+
+delete_2([I|Segs], I) -> Segs;
+delete_2([S|Segs], I) -> [S|delete_2(Segs,I)].
+
+-compile({inline,nonempty_intervals_intersect/4}).
+nonempty_intervals_intersect(ALo, AHi, BLo, BHi) ->
+ (BLo =< AHi) andalso (ALo =< BHi).
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-12 00:01:42 +0000