aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorAlex Auvolat <alex@adnab.me>2018-07-20 16:07:13 +0200
committerAlex Auvolat <alex@adnab.me>2018-07-20 16:07:13 +0200
commit87a35ab4741eaf78ec3eddc8c7452ef2a32477b7 (patch)
treea7624aca36ca772d808a49d701cad860a065ff91 /lib
parenta624a8504c722a2c561ce147f64c2a1a0bb6f4b0 (diff)
downloadshard-87a35ab4741eaf78ec3eddc8c7452ef2a32477b7.tar.gz
shard-87a35ab4741eaf78ec3eddc8c7452ef2a32477b7.zip
Add get call and associated test
Diffstat (limited to 'lib')
-rw-r--r--lib/data/merklesearchtree.ex28
1 files changed, 27 insertions, 1 deletions
diff --git a/lib/data/merklesearchtree.ex b/lib/data/merklesearchtree.ex
index d23e8a7..29c1dab 100644
--- a/lib/data/merklesearchtree.ex
+++ b/lib/data/merklesearchtree.ex
@@ -114,7 +114,7 @@ defmodule SData.MerkleSearchTree do
defp aux_insert_after_first(store, lst, key, value) do
case lst do
- [ {k1, _, r1} | rst ] when k1 == key ->
+ [ {k1, _old_value, r1} | rst ] when k1 == key ->
{ [ {k1, value, r1} | rst ], store }
[ {k1, v1, r1} ] ->
{r1a, r1b, new_store} = split(store, r1, key)
@@ -144,6 +144,32 @@ defmodule SData.MerkleSearchTree do
end
end
+ def get(state, key) do
+ get(state.store, state.root, key)
+ end
+
+ defp get(store, root, key) do
+ case root do
+ nil -> nil
+ _ ->
+ { _, low, lst } = store[root]
+ get_aux(store, low, lst, key)
+ end
+ end
+
+ defp get_aux(store, low, lst, key) do
+ case lst do
+ [] ->
+ get(store, low, key)
+ [ {k, v, _} | _ ] when key == k ->
+ v
+ [ {k, _, _} | _ ] when key < k ->
+ get(store, low, key)
+ [ {k, _, low2} | rst ] when key > k ->
+ get_aux(store, low2, rst, key)
+ end
+ end
+
def dump(state) do
dump(state.store, state.root, "")
end