aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/misc
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/misc')
-rw-r--r--lib/hipe/misc/Makefile2
-rw-r--r--lib/hipe/misc/hipe_consttab.erl6
-rw-r--r--lib/hipe/misc/hipe_consttab.hrl6
-rw-r--r--lib/hipe/misc/hipe_data_pp.erl7
-rw-r--r--lib/hipe/misc/hipe_gensym.erl8
-rw-r--r--lib/hipe/misc/hipe_pack_constants.erl8
-rw-r--r--lib/hipe/misc/hipe_sdi.erl109
-rw-r--r--lib/hipe/misc/hipe_sdi.hrl8
-rw-r--r--lib/hipe/misc/hipe_segment_trees.erl174
9 files changed, 236 insertions, 92 deletions
diff --git a/lib/hipe/misc/Makefile b/lib/hipe/misc/Makefile
index 72cfff21a8..e5033e444b 100644
--- a/lib/hipe/misc/Makefile
+++ b/lib/hipe/misc/Makefile
@@ -44,7 +44,7 @@ RELSYSDIR = $(RELEASE_PATH)/lib/hipe-$(VSN)
# Target Specs
# ----------------------------------------------------
ifdef HIPE_ENABLED
-HIPE_MODULES = hipe_data_pp hipe_pack_constants hipe_sdi
+HIPE_MODULES = hipe_data_pp hipe_pack_constants hipe_sdi hipe_segment_trees
else
HIPE_MODULES =
endif
diff --git a/lib/hipe/misc/hipe_consttab.erl b/lib/hipe/misc/hipe_consttab.erl
index 226b20fa46..64e3d3ccaa 100644
--- a/lib/hipe/misc/hipe_consttab.erl
+++ b/lib/hipe/misc/hipe_consttab.erl
@@ -1,9 +1,5 @@
%% -*- erlang-indent-level: 2 -*-
%%
-%% %CopyrightBegin%
-%%
-%% Copyright Ericsson AB 2001-2016. All Rights Reserved.
-%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
@@ -15,8 +11,6 @@
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
-%%
-%% %CopyrightEnd%
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% @doc
diff --git a/lib/hipe/misc/hipe_consttab.hrl b/lib/hipe/misc/hipe_consttab.hrl
index 550da0455c..4d2d357a0b 100644
--- a/lib/hipe/misc/hipe_consttab.hrl
+++ b/lib/hipe/misc/hipe_consttab.hrl
@@ -1,9 +1,5 @@
%% -*- erlang-indent-level: 2 -*-
%%
-%% %CopyrightBegin%
-%%
-%% Copyright Ericsson AB 2008-2016. All Rights Reserved.
-%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
@@ -15,8 +11,6 @@
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
-%%
-%% %CopyrightEnd%
%%
%%-----------------------------------------------------------------------------
diff --git a/lib/hipe/misc/hipe_data_pp.erl b/lib/hipe/misc/hipe_data_pp.erl
index 6cdc6c5ad2..2c737b6d78 100644
--- a/lib/hipe/misc/hipe_data_pp.erl
+++ b/lib/hipe/misc/hipe_data_pp.erl
@@ -1,9 +1,5 @@
%% -*- erlang-indent-level: 2 -*-
%%
-%% %CopyrightBegin%
-%%
-%% Copyright Ericsson AB 2001-2016. All Rights Reserved.
-%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
@@ -15,12 +11,9 @@
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
-%%
-%% %CopyrightEnd%
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Copyright (c) 2001 by Erik Johansson. All Rights Reserved
-%% Time-stamp: <2008-04-20 14:57:08 richard>
%% ====================================================================
%% Module : hipe_data_pp
%% Purpose :
diff --git a/lib/hipe/misc/hipe_gensym.erl b/lib/hipe/misc/hipe_gensym.erl
index da7c4f9a5d..548071fd8f 100644
--- a/lib/hipe/misc/hipe_gensym.erl
+++ b/lib/hipe/misc/hipe_gensym.erl
@@ -1,9 +1,5 @@
%% -*- erlang-indent-level: 2 -*-
%%
-%% %CopyrightBegin%
-%%
-%% Copyright Ericsson AB 2001-2016. All Rights Reserved.
-%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
@@ -15,16 +11,12 @@
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
-%%
-%% %CopyrightEnd%
%%
%%=======================================================================
%% File : hipe_gensym.erl
%% Author : Eric Johansson and Kostis Sagonas
%% Description : Generates unique symbols and fresh integer counts.
%%=======================================================================
-%% $Id$
-%%=======================================================================
%% Notes: Written while we were in Montreal, Canada for PPDP-2000 as an
%% exercise in Principles and Practice of Declarative Programming!
%%=======================================================================
diff --git a/lib/hipe/misc/hipe_pack_constants.erl b/lib/hipe/misc/hipe_pack_constants.erl
index b54830dd57..9dd18bce0f 100644
--- a/lib/hipe/misc/hipe_pack_constants.erl
+++ b/lib/hipe/misc/hipe_pack_constants.erl
@@ -1,10 +1,5 @@
%% -*- erlang-indent-level: 2 -*-
-%%=============================================================================
%%
-%% %CopyrightBegin%
-%%
-%% Copyright Ericsson AB 2003-2016. All Rights Reserved.
-%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
@@ -16,9 +11,6 @@
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
-%%
-%% %CopyrightEnd%
-%%
-module(hipe_pack_constants).
-export([pack_constants/2, slim_refs/1, slim_constmap/1,
diff --git a/lib/hipe/misc/hipe_sdi.erl b/lib/hipe/misc/hipe_sdi.erl
index fbb4b105f6..9a60382686 100644
--- a/lib/hipe/misc/hipe_sdi.erl
+++ b/lib/hipe/misc/hipe_sdi.erl
@@ -1,10 +1,6 @@
%%% -*- erlang-indent-level: 2 -*-
%%%======================================================================
%%%
-%%% %CopyrightBegin%
-%%%
-%%% Copyright Ericsson AB 2004-2016. All Rights Reserved.
-%%%
%%% Licensed under the Apache License, Version 2.0 (the "License");
%%% you may not use this file except in compliance with the License.
%%% You may obtain a copy of the License at
@@ -16,8 +12,6 @@
%%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%%% See the License for the specific language governing permissions and
%%% limitations under the License.
-%%%
-%%% %CopyrightEnd%
%%%
%%% An implementation of the algorithm described in:
%%% "Assembling Code for Machines with Span-Dependent Instructions",
@@ -36,10 +30,13 @@
%%------------------------------------------------------------------------
-type hipe_array() :: integer(). % declare this in hipe.hrl or builtin?
+-type hipe_vector(E) :: {} | {E} | {E, E} | {E, E, E} | tuple().
-type label() :: non_neg_integer().
-type address() :: non_neg_integer().
+-type parents() :: {hipe_vector(_ :: integer()), hipe_segment_trees:tree()}.
+
%%------------------------------------------------------------------------
-record(label_data, {address :: address(),
@@ -168,9 +165,11 @@ mk_long(N) ->
%%% - Since the graph is traversed from child to parent nodes in
%%% Step 3, the edges are represented by a vector PARENTS[0..n-1]
%%% such that PARENTS[j] = { i | i is a parent of j }.
-%%% - An explicit PARENTS graph would have size O(n^2). Instead we
-%%% compute PARENTS[j] from the SDI vector when needed. This
-%%% reduces memory overheads, and may reduce time overheads too.
+%%% - An explicit PARENTS graph would have size O(n^2). Instead, we
+%%% observe that (i is a parent of j) iff (j \in range(i)), where
+%%% range(i) is a constant function. We can thus precompute all the
+%%% ranges i and insert them into a data structure built for such
+%%% queries. In this case, we use a segment tree.
-spec mk_span(non_neg_integer(), tuple()) -> hipe_array().
mk_span(N, SDIS) ->
@@ -188,7 +187,29 @@ initSPAN(SdiNr, N, SDIS, SPAN) ->
initSPAN(SdiNr+1, N, SDIS, SPAN)
end.
-mk_parents(N, SDIS) -> {N,SDIS}.
+-spec mk_parents(non_neg_integer(), tuple()) -> parents().
+mk_parents(N, SDIS) ->
+ PrevSDIS = vector_from_list(select_prev_sdis(N-1, SDIS, [])),
+ Ranges = parents_generate_ranges(N-1, PrevSDIS, []),
+ {PrevSDIS, hipe_segment_trees:build(Ranges)}.
+
+select_prev_sdis(-1, _SDIS, Acc) -> Acc;
+select_prev_sdis(SdiNr, SDIS, Acc) ->
+ #sdi_data{prevSdi=PrevSdi} = vector_sub(SDIS, SdiNr),
+ 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
@@ -209,7 +230,7 @@ mk_parents(N, SDIS) -> {N,SDIS}.
%%% and PARENTS are no longer useful.
-spec update_long(non_neg_integer(), tuple(), hipe_array(),
- {non_neg_integer(),tuple()},hipe_array()) -> 'ok'.
+ parents(),hipe_array()) -> 'ok'.
update_long(N, SDIS, SPAN, PARENTS, LONG) ->
WKL = initWKL(N-1, SDIS, SPAN, []),
processWKL(WKL, SDIS, SPAN, PARENTS, LONG).
@@ -225,46 +246,32 @@ initWKL(SdiNr, SDIS, SPAN, WKL) ->
end.
-spec processWKL([non_neg_integer()], tuple(), hipe_array(),
- {non_neg_integer(), tuple()}, hipe_array()) -> 'ok'.
+ 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(),
- {non_neg_integer(),tuple()}, 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({_PrevSDIS, SegTree}, Child) ->
+ hipe_segment_trees:intersect(Child, SegTree).
--spec parentsOfChild({non_neg_integer(),tuple()},
- non_neg_integer()) -> [non_neg_integer()].
-parentsOfChild({N,SDIS}, Child) ->
- parentsOfChild(N-1, SDIS, Child, []).
-
--spec parentsOfChild(integer(), tuple(), non_neg_integer(),
- [non_neg_integer()]) -> [non_neg_integer()].
-parentsOfChild(-1, _SDIS, _Child, PS) -> PS;
-parentsOfChild(SdiNr, SDIS, Child, PS) ->
- SdiData = vector_sub(SDIS, SdiNr),
- #sdi_data{prevSdi=PrevSdi} = SdiData,
- {LO,HI} = % inclusive
- if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi}; % forwards
- true -> {PrevSdi+1, SdiNr-1} % backwards
- end,
- NewPS =
- if LO =< Child, Child =< HI -> [SdiNr | PS];
- true -> PS
- end,
- parentsOfChild(SdiNr-1, SDIS, Child, NewPS).
+-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 +304,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.
@@ -361,9 +370,11 @@ applyIncr([{Label,LabelData}|List], INCREMENT, LabelMap) ->
%%% Currently implemented as tuples.
%%% Used for the 'SDIS' and 'PARENTS' vectors.
--spec vector_from_list([#sdi_data{}]) -> tuple().
+-spec vector_from_list([E]) -> hipe_vector(E).
vector_from_list(Values) -> list_to_tuple(Values).
+-compile({inline, vector_sub/2}).
+-spec vector_sub(hipe_vector(E), non_neg_integer()) -> V when V :: E.
vector_sub(Vec, I) -> element(I+1, Vec).
%%% ADT for mutable integer arrays, indexed from 0 to N-1.
@@ -373,8 +384,10 @@ vector_sub(Vec, I) -> element(I+1, Vec).
-spec mk_array_of_zeros(non_neg_integer()) -> hipe_array().
mk_array_of_zeros(N) -> hipe_bifs:array(N, 0).
+-compile({inline, array_update/3}).
-spec array_update(hipe_array(), non_neg_integer(), integer()) -> hipe_array().
array_update(A, I, V) -> hipe_bifs:array_update(A, I, V).
+-compile({inline, array_sub/2}).
-spec array_sub(hipe_array(), non_neg_integer()) -> integer().
array_sub(A, I) -> hipe_bifs:array_sub(A, I).
diff --git a/lib/hipe/misc/hipe_sdi.hrl b/lib/hipe/misc/hipe_sdi.hrl
index a1e12f9df2..def697549c 100644
--- a/lib/hipe/misc/hipe_sdi.hrl
+++ b/lib/hipe/misc/hipe_sdi.hrl
@@ -1,9 +1,5 @@
%% -*- erlang-indent-level: 2 -*-
%%
-%% %CopyrightBegin%
-%%
-%% Copyright Ericsson AB 2004-2016. All Rights Reserved.
-%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
@@ -15,10 +11,6 @@
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
-%%
-%% %CopyrightEnd%
-%%
-
-record(sdi_info,
{lb :: integer(), % span lower bound for short form
diff --git a/lib/hipe/misc/hipe_segment_trees.erl b/lib/hipe/misc/hipe_segment_trees.erl
new file mode 100644
index 0000000000..3d6a7487ec
--- /dev/null
+++ b/lib/hipe/misc/hipe_segment_trees.erl
@@ -0,0 +1,174 @@
+%%% Licensed under the Apache License, Version 2.0 (the "License");
+%%% you may not use this file except in compliance with the License.
+%%% You may obtain a copy of the License at
+%%%
+%%% http://www.apache.org/licenses/LICENSE-2.0
+%%%
+%%% Unless required by applicable law or agreed to in writing, software
+%%% distributed under the License is distributed on an "AS IS" BASIS,
+%%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+%%% See the License for the specific language governing permissions and
+%%% limitations under the License.
+%%%
+%%% Segment trees, with a delete operation.
+%%%
+%%% Keys are the (0-based) indices into the list passed to build/1.
+%%%
+%%% Range bounds are inclusive.
+%%%
+
+-module(hipe_segment_trees).
+
+-export([build/1, intersect/2, delete/4]).
+
+-record(segment_tree, {
+ lo :: integer(),
+ hi :: integer(),
+ root :: tnode()
+ }).
+
+%% X =< Mid belongs in Left
+-define(NODE(Left, Right, Mid, Segments), {Left, Right, Mid, Segments}).
+
+-define(POINT_LEAF(Val), Val).
+-define(RANGE_LEAF(Lo, Hi), {Lo, Hi}).
+
+-type segments() :: [non_neg_integer()].
+-type leaf() :: segments().
+-type tnode() :: ?NODE(tnode(), tnode(), integer(), segments()) | leaf().
+
+-opaque tree() :: #segment_tree{} | nil.
+-export_type([tree/0]).
+
+%% @doc Builds a segment tree of the given intervals.
+-spec build([{integer(), integer()}]) -> tree().
+build(ListOfIntervals) ->
+ case
+ lists:usort(
+ lists:append(
+ [[Lo, Hi] || {Lo, Hi} <- ListOfIntervals, Lo =< Hi]))
+ of
+ [] -> nil;
+ Endpoints ->
+ Tree0 = empty_tree_from_endpoints(Endpoints),
+ [Lo|_] = Endpoints,
+ Hi = lists:last(Endpoints),
+ Tree1 = insert_intervals(0, ListOfIntervals, Lo, Hi, Tree0),
+ Tree = squash_empty_subtrees(Tree1),
+ #segment_tree{lo=Lo, hi=Hi, root=Tree}
+ end.
+
+empty_tree_from_endpoints(Endpoints) ->
+ Leaves = leaves(Endpoints),
+ {T, [], _, _} = balanced_bst(Leaves, length(Leaves)),
+ T.
+
+leaves([Endpoint]) -> [?POINT_LEAF(Endpoint)];
+leaves([A | [B|_] = Tail]) ->
+ %% 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)]
+ end.
+
+balanced_bst(L, S) when S > 1 ->
+ Sm = S, %% - 1
+ S2 = Sm div 2,
+ S1 = Sm - S2,
+ {Left, L1, LeftLo, LeftHi} = balanced_bst(L, S1),
+ {Right, L2, _, RightHi} = balanced_bst(L1, S2),
+ T = ?NODE(Left, Right, LeftHi, []),
+ {T, L2, LeftLo, RightHi};
+balanced_bst([?RANGE_LEAF(Lo, Hi) | L], 1) ->
+ {[], L, Lo, Hi};
+balanced_bst([?POINT_LEAF(Val) | L], 1) ->
+ {[], L, Val, Val}.
+
+insert_intervals(_Ix, [], _Lo, _Hi, Tree) -> Tree;
+insert_intervals(Ix, [Int|Ints], Lo, Hi, Tree) ->
+ insert_intervals(Ix + 1, Ints, Lo, Hi,
+ insert_interval(Ix, Int, Lo, Hi, Tree)).
+
+insert_interval(_, {Lo, Hi}, _, _, Node) when Lo > Hi -> Node;
+insert_interval(I, Int={Lo,Hi}, NLo, NHi,
+ ?NODE(Left0, Right0, Mid, Segments)) ->
+ if Lo =< NLo, NHi =< Hi ->
+ ?NODE(Left0, Right0, Mid, [I|Segments]);
+ true ->
+ Left = case intervals_intersect(Lo, Hi, NLo, Mid) of
+ true -> insert_interval(I, Int, NLo, Mid, Left0);
+ false -> Left0
+ end,
+ Right = case intervals_intersect(Lo, Hi, Mid+1, NHi) of
+ true -> insert_interval(I, Int, Mid+1, NHi, Right0);
+ false -> Right0
+ end,
+ ?NODE(Left, Right, Mid, Segments)
+ end;
+insert_interval(I, {_Lo,_Hi}, _NLo, _NHi, Leaf) -> [I|Leaf].
+
+intervals_intersect(ALo, AHi, BLo, BHi) ->
+ (ALo =< AHi) andalso (BLo =< BHi) %% both nonempty
+ andalso nonempty_intervals_intersect(ALo, AHi, BLo, BHi).
+
+%% Purely optional optimisation
+squash_empty_subtrees(?NODE(Left0, Right0, Mid, Segs)) ->
+ build_squash_node(squash_empty_subtrees(Left0),
+ squash_empty_subtrees(Right0),
+ Mid, Segs);
+squash_empty_subtrees(Leaf) -> Leaf.
+
+build_squash_node([], [], _, Segs) -> Segs;
+build_squash_node(Left, Right, Mid, Segs) ->
+ ?NODE(Left, Right, Mid, Segs).
+
+%% @doc Returns the indices of the intervals in the tree that contains Point.
+-spec intersect(integer(), tree()) -> [non_neg_integer()].
+intersect(Point, nil) when is_integer(Point) -> [];
+intersect(Point, #segment_tree{lo=Lo, hi=Hi, root=Root})
+ when is_integer(Point) ->
+ case Lo =< Point andalso Point =< Hi of
+ false -> [];
+ true -> intersect_1(Point, Root, [])
+ end.
+
+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-11 07:32:21 +0000