diff options
Diffstat (limited to 'src/ht.erl')
| -rw-r--r-- | src/ht.erl | 51 |
1 files changed, 24 insertions, 27 deletions
@@ -127,7 +127,7 @@ consistency(Tree, V1, V2) -> UpdTree = update(Tree, V2), First = case StartIndex of 0 -> []; - _ -> [get_hash(UpdTree, {StartIndex, StartLayer})] + _ -> [get_hash(UpdTree, {StartLayer, StartIndex})] end, %% Get path from first left child to head of V2. {_, Path} = path(UpdTree, StartLayer, StartIndex, V2), @@ -164,23 +164,23 @@ path(Tree, Layer, I, ILast, Version, Acc) -> [old_version_tree_head(Tree, Version, Layer) | Acc]; Sib when Sib < ILast -> %% Just use sibling. - [get_hash(Tree, {Sib, Layer}) | Acc]; + [get_hash(Tree, {Layer, Sib}) | Acc]; _ -> %% Sibling is larger than ILast so doesn't exist. Acc end). -%% @doc updates the tree and returns new tree plus hash for IR -spec get_hash(tree(), tuple()) -> binary(). -get_hash(Tree, IR) -> - ts:retrieve_hash(Tree#tree.store, IR). +get_hash(Tree, {R, I}) -> + true = Tree#tree.evaluated >= I, % ASSERTION + ts:retrieve(Tree#tree.store, {R, I}). -spec head(tree(), integer()) -> {tree(), binary()}. head(Tree, -1) -> {Tree, hash(<<"">>)}; head(Tree = #tree{version = V}, Version) when Version == V -> NewTree = update(Tree), - {NewTree, get_hash(NewTree, {0, depth(Tree) - 1})}; + {NewTree, get_hash(NewTree, {depth(Tree) - 1, 0})}; head(Tree = #tree{version = V}, Version) when Version > V -> {Tree, enotimetravel}; head(Tree, Version) -> @@ -203,7 +203,7 @@ old_version_tree_head(Tree, Version, BreakAtLayer) -> %% the last right node, rehashing as we go. Calculate the parent %% hash of that node and its sibling. Return that hash. last_right_node_rehash(Tree, Version, FirstLeftR, FirstLeftI, - get_hash(Tree, {FirstLeftI, FirstLeftR}), + get_hash(Tree, {FirstLeftR, FirstLeftI}), BreakAtLayer). -spec last_right_node_rehash(tree(), non_neg_integer(), non_neg_integer(), @@ -221,7 +221,7 @@ last_right_node_rehash(Tree, Version, Layer, Index, RightNodeHash, BAL) -> case right_node_p(Index) of true -> %% Rehash parent using sibling. - mkinnerhash(get_hash(Tree, {Index - 1, Layer}), RightNodeHash); + mkinnerhash(get_hash(Tree, {Layer, Index - 1}), RightNodeHash); false -> %% Just use the incoming hash. RightNodeHash @@ -246,11 +246,8 @@ first_left_node(Layer, Index, BAL) -> %% @doc Add an entry but don't update the tree. -spec add(tree(), binary()) -> tree(). add(Tree = #tree{version = V, store = Store}, Entry) -> - NewVersion = V + 1, - LeafIndex = NewVersion, - LeafHash = mkleafhash(Entry), - Tree#tree{version = NewVersion, - store = ts:store(Store, {LeafIndex, 0}, LeafHash)}. + Tree#tree{version = V + 1, + store = ts:add(Store, 0, mkleafhash(Entry))}. %% @doc Return a new tree. -spec new(list()) -> tree(). @@ -296,10 +293,16 @@ update(Tree = #tree{evaluated = Evaluated}, Version) -> non_neg_integer()) -> tree(). update_layer(Tree, _Layer, _ICur, 0) -> % Done Tree; -update_layer(Tree, Layer, ICur, ILast) -> +update_layer(Tree = #tree{store = S}, Layer, ICur, ILast) -> + %% Before updating parent layer, delete potential placeholder. + Store = case ts:count(S, Layer + 1) == parent(ICur) + 1 of + true -> ts:delete(S, Layer + 1); + false -> S + end, + %% 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, + NewStore = update_parent(Store, Layer, strip_bits_bottom(ICur, 1), ILast), update_layer(Tree#tree{store = NewStore}, Layer + 1, parent(ICur), parent(ILast)). @@ -314,24 +317,18 @@ update_parent(S, Layer, I, ILast) when I >= ILast -> %% ("non-frozen") trees. case right_node_p(ILast) of true -> S; - _ -> ts:append(S, Layer + 1, ts:retrieve_hash(S, {ILast, Layer})) + _ -> ts:add(S, Layer + 1, ts:retrieve(S, {Layer, ILast})) end; update_parent(S, Layer, I, ILast) -> false = right_node_p(I), % ASSERTION %% Make an inner node hash of I and its sibling. Store it as %% parent. Recurse with next pair of leaves. - %% TODO: This is the only place where we store rather than - %% append. Consider changing this to an append. This would make it - %% possible for ts to use other data structures for the storage - %% (like a binary per layer). If so, don't forget to truncate - %% Layer+1 before appending if there's already a parent for I - %% there. - 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(ts:add(S, Layer + 1, + mkinnerhash(ts:retrieve(S, {Layer, I}), + ts:retrieve(S, {Layer, I + 1}))), Layer, I + 2, ILast). -%% @doc Parent of {i, r} is at {i/2, r+1} (unless it's a "placeholder"). +%% @doc Parent of {r, i} is at {r+1, i/2} (unless it's a placeholder). parent(I) -> I bsr 1. @@ -398,7 +395,7 @@ print_layer(Tree, HashOutputLen, Layer, ILast) -> fun(I) -> io:format("~s ", [string:substr( hex:bin_to_hexstr( - get_hash(Tree, {I, Layer})), 1, HashOutputLen)]) + get_hash(Tree, {I, Layer})), HashOutputLen, 1)]) end, lists:seq(0, ILast)), io:format("~n"). |