diff options
| -rw-r--r-- | src/ht.erl | 31 |
1 files changed, 20 insertions, 11 deletions
@@ -14,8 +14,8 @@ %%% ceil(lg2(number of leaves)). %%% Let {r,i} denote the hash with index i on layer r. The first leaf %%% is {0,0}, second is {0,1} and n:th is {0,n-1}. -%%% The parent of {r,i} is {r+1,floor(i/2)} (not true bc of -%%% "placeholders", FIXME: doc) +%%% The parent of {r,i} is {r+1,floor(i/2)} (not strictly true because +%%% of "placeholder nodes", see update_parent/4). %%% The sibling of {r,i} is {r,i+1} when i is even and {r,i-1} when i %%% is odd. @@ -96,7 +96,6 @@ handle_call({consistency, _Version1, _Version2}, _From, State) -> get_hash(Tree, Version, IR) -> NewTree = update(Tree, Version), Hash = ts:retrieve_hash(NewTree#tree.store, IR), % TODO: Honour version! - %%io:format("DEBUG: get_hash(Tree=~p,~nVersion=~p,~nIR=~p):~nNewTree=~p~n", [Tree, Version, IR, NewTree]), {NewTree, Hash}. -spec tree_hash(tree(), integer()) -> {tree(), binary()}. @@ -147,29 +146,39 @@ update(Tree = #tree{evaluated = Evaluated}, Version) -> NewTree = update_layer(Tree, 0, Evaluated + 1, Version), NewTree#tree{evaluated = Version}. +%% @doc Update the tree wrt the leaves ICur..ILast. -spec update_layer(tree(), non_neg_integer(), non_neg_integer(), non_neg_integer()) -> tree(). -update_layer(Tree, _Layer, _ICur, 0) -> +update_layer(Tree, _Layer, _ICur, 0) -> % Done Tree; update_layer(Tree, Layer, ICur, ILast) -> - NewTree = Tree#tree{store = update_parent(Tree#tree.store, Layer, - strip_bits_bottom(ICur, 1), ILast)}, - %%io:format("DEBUG: update_layer(~p, ~p, ~p, ~p - update_layer(NewTree, Layer + 1, parent(ICur), parent(ILast)). + %% Update parents on next upper layer, starting with a left + %% child <= ICur and ending with ILast. Recurse with next layer. + NewStore = update_parent(Tree#tree.store, Layer, + strip_bits_bottom(ICur, 1), ILast), + update_layer(Tree#tree{store = NewStore}, Layer + 1, + parent(ICur), parent(ILast)). +%% @doc Update parents of I..ILast, on Layer+1. I has to be a left child. -spec update_parent(ts:tree_store(), non_neg_integer(), non_neg_integer(), non_neg_integer()) -> ts:tree_store(). update_parent(S, Layer, I, ILast) when I >= ILast -> + %% We're done updating parents. If ILast is a left child, copy it + %% to where its parent would've been were it a right child. This + %% is a "placeholder node" which simplifies when creating + %% incomplete ("non-frozen") trees. case right_leaf_p(ILast) of true -> S; _ -> ts:append(S, Layer + 1, ts:retrieve_hash(S, {ILast, Layer})) end; update_parent(S, Layer, I, ILast) -> - %%io:format("DEBUG: update_parent(R=~p, I=~p, ILast=~p): parent(I)=~p~n", [Layer, I, ILast, parent(I)]), - S2 = ts:store(S, {parent(I), Layer + 1}, + false = right_leaf_p(I), % ASSERTION + %% Make an inner node hash of I and sibling. Store it as + %% parent. Recurse with next pair of leaves. + update_parent(ts:store(S, {parent(I), Layer + 1}, mkinnerhash(ts:retrieve_hash(S, {I, Layer}), ts:retrieve_hash(S, {I + 1, Layer}))), - update_parent(S2, Layer, I + 2, ILast). + Layer, I + 2, ILast). parent(I) -> I bsr 1. |