diff options
Diffstat (limited to 'shard/lib/data')
| -rw-r--r-- | shard/lib/data/merklesearchtree.ex | 51 |
1 files changed, 17 insertions, 34 deletions
diff --git a/shard/lib/data/merklesearchtree.ex b/shard/lib/data/merklesearchtree.ex index 039f6ce..49d54a5 100644 --- a/shard/lib/data/merklesearchtree.ex +++ b/shard/lib/data/merklesearchtree.ex @@ -193,21 +193,19 @@ defmodule SData.MerkleSearchTree do The merge is not symmetrical in the sense that: - new pages are added in the store of the first argument - - the callback is called for all items found in the second argument and not the first """ - def merge(to, from, callback \\ fn _, _ -> nil end) do - { store, root } = merge_aux(to, from, to.store, to.root, from.root, callback) + def merge(to, from) do + { store, root } = merge_aux(to, from, to.store, to.root, from.root) %{ to | store: store, root: root } end - defp merge_aux(s1, s2, store, r1, r2, callback) do + defp merge_aux(s1, s2, store, r1, r2) do case {r1, r2} do _ when r1 == r2 -> { store, r1 } {_, nil} -> { store, r1 } {nil, _} -> store = Store.copy(store, s2.store, r2) - rec_callback(store, r2, callback) { store, r2 } _ -> %Page{ level: level1, low: low1, list: lst1 } = Store.get(store, r1) @@ -217,64 +215,49 @@ defmodule SData.MerkleSearchTree do level1 > level2 -> {level1, low1, lst1, r2, []} level2 > level1 -> {level2, r1, [], low2, lst2} end - { store, low, lst } = merge_aux_rec(s1, s2, store, low1, lst1, low2, lst2, callback) + { store, low, lst } = merge_aux_rec(s1, s2, store, low1, lst1, low2, lst2) page = %Page{ level: level, low: low, list: lst } {hash, store} = Store.put(store, page) {store, hash} end end - defp merge_aux_rec(s1, s2, store, low1, lst1, low2, lst2, callback) do + defp merge_aux_rec(s1, s2, store, low1, lst1, low2, lst2) do case {lst1, lst2} do { [], [] } -> - {store, hash} = merge_aux(s1, s2, store, low1, low2, callback) + {store, hash} = merge_aux(s1, s2, store, low1, low2) {store, hash, []} { [], [ {k, v, r} | rst2 ] } -> {low1l, low1h, store} = split(s1, store, low1, k) - {store, newlow} = merge_aux(s1, s2, store, low1l, low2, callback) - callback.(k, v) - {store, newr, newrst} = merge_aux_rec(s1, s2, store, low1h, [], r, rst2, callback) + {store, newlow} = merge_aux(s1, s2, store, low1l, low2) + {store, newr, newrst} = merge_aux_rec(s1, s2, store, low1h, [], r, rst2) {store, newlow, [ {k, v, newr} | newrst ]} { [ {k, v, r} | rst1 ], [] } -> {low2l, low2h, store} = split(s2, store, low2, k) - {store, newlow} = merge_aux(s1, s2, store, low1, low2l, callback) - {store, newr, newrst} = merge_aux_rec(s1, s2, store, r, rst1, low2h, [], callback) + {store, newlow} = merge_aux(s1, s2, store, low1, low2l) + {store, newr, newrst} = merge_aux_rec(s1, s2, store, r, rst1, low2h, []) {store, newlow, [ {k, v, newr} | newrst ]} { [ {k1, v1, r1} | rst1 ], [ {k2, v2, r2} | rst2 ] } -> case s1.cmp.(k1, k2) do :before -> {low2l, low2h, store} = split(s2, store, low2, k1) - {store, newlow} = merge_aux(s1, s2, store, low1, low2l, callback) - {store, newr, newrst} = merge_aux_rec(s1, s2, store, r1, rst1, low2h, lst2, callback) + {store, newlow} = merge_aux(s1, s2, store, low1, low2l) + {store, newr, newrst} = merge_aux_rec(s1, s2, store, r1, rst1, low2h, lst2) {store, newlow, [ {k1, v1, newr} | newrst ]} :after -> {low1l, low1h, store} = split(s1, store, low1, k2) - {store, newlow} = merge_aux(s1, s2, store, low1l, low2, callback) - callback.(k2, v2) - {store, newr, newrst} = merge_aux_rec(s1, s2, store, low1h, lst1, r2, rst2, callback) + {store, newlow} = merge_aux(s1, s2, store, low1l, low2) + {store, newr, newrst} = merge_aux_rec(s1, s2, store, low1h, lst1, r2, rst2) {store, newlow, [ {k2, v2, newr} | newrst ]} :duplicate -> - {store, newlow} = merge_aux(s1, s2, store, low1, low2, callback) - newv = s1.merge.(v1, v2) ## TODO: callback here ?? - {store, newr, newrst} = merge_aux_rec(s1, s2, store, r1, rst1, r2, rst2, callback) + {store, newlow} = merge_aux(s1, s2, store, low1, low2) + newv = s1.merge.(v1, v2) + {store, newr, newrst} = merge_aux_rec(s1, s2, store, r1, rst1, r2, rst2) {store, newlow, [ {k1, newv, newr} | newrst ]} end end end - defp rec_callback(store, root, callback) do - case root do - nil -> nil - _ -> - %Page{ level: _, low: low, list: lst } = Store.get(store, root) - rec_callback(store, low, callback) - for {k, v, rst} <- lst do - callback.(k, v) - rec_callback(store, rst, callback) - end - end - end - @doc""" Get value for a specific key in search tree. """ |