diff options
| -rw-r--r-- | lib/hipe/misc/hipe_sdi.erl | 69 | ||||
| -rw-r--r-- | lib/hipe/misc/hipe_segment_trees.erl | 49 |
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). |