From 4af0661e0612df991e58ae513d756c2ba3abfeaa Mon Sep 17 00:00:00 2001
From: Linus Nordberg <linus@nordberg.se>
Date: Thu, 11 Sep 2014 16:56:13 +0200
Subject: Add some explaining comments. Remove some debugging code.

---
 src/ht.erl | 31 ++++++++++++++++++++-----------
 1 file changed, 20 insertions(+), 11 deletions(-)

(limited to 'src/ht.erl')

diff --git a/src/ht.erl b/src/ht.erl
index 5fa285c..042b969 100644
--- a/src/ht.erl
+++ b/src/ht.erl
@@ -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.
-- 
cgit v1.1