diff options
| -rw-r--r-- | lib/data/merklesearchtree.ex | 69 | ||||
| -rw-r--r-- | lib/data/store.ex | 91 |
2 files changed, 132 insertions, 28 deletions
diff --git a/lib/data/merklesearchtree.ex b/lib/data/merklesearchtree.ex index 29c1dab..963653e 100644 --- a/lib/data/merklesearchtree.ex +++ b/lib/data/merklesearchtree.ex @@ -14,12 +14,31 @@ defmodule SData.MerkleSearchTree do } """ + alias SData.PageStore, as: Store + defstruct [:root, :store] - def new() do + defmodule Page do + defstruct [:level, :low, :list] + end + + defimpl SData.Page, for: Page do + def refs(page) do + refs = for {_, _, h} <- page.list, h != nil, do: h + if page.low != nil do + [ page.low | refs ] + else + refs + end + end + end + + + def new(store \\ nil) do + store = store || SData.LocalStore.new %SData.MerkleSearchTree{ root: nil, - store: %{} + store: store } end @@ -35,58 +54,54 @@ defmodule SData.MerkleSearchTree do defp insert_at(store, root, key, level, value) do {new_page, store} = if root == nil do - { { level, nil, [ { key, value, nil } ] }, store } + { %Page{ level: level, low: nil, list: [ { key, value, nil } ] }, store } else - { plevel, low, lst } = store[root] + %Page{ level: plevel, low: low, list: lst } = Store.get(store, root) [ { k0, _, _} | _ ] = lst cond do plevel < level -> {low, high, store} = split(store, root, key) - { { level, low, [ { key, value, high } ] }, store } + { %Page{ level: level, low: low, list: [ { key, value, high } ] }, store } plevel == level -> - store = Map.delete(store, root) + store = Store.free(store, root) if key < k0 do {low2a, low2b, store} = split(store, low, key) - { { level, low2a, [ { key, value, low2b } | lst] }, store } + { %Page{ level: level, low: low2a, list: [ { key, value, low2b } | lst] }, store } else {new_lst, store} = aux_insert_after_first(store, lst, key, value) - { { plevel, low, new_lst }, store } + { %Page{ level: plevel, low: low, list: new_lst }, store } end plevel > level -> - store = Map.delete(store, root) + store = Store.free(store, root) if key < k0 do {new_low, store} = insert_at(store, low, key, level, value) - { { plevel, new_low, lst }, store } + { %Page{ level: plevel, low: new_low, list: lst }, store } else {new_lst, store} = aux_insert_sub_after_first(store, lst, key, level, value) - { { plevel, low, new_lst }, store } + { %Page{ level: plevel, low: low, list: new_lst }, store } end end end - hash = SData.term_hash new_page - store = Map.put(store, hash, new_page) - { hash, store } + Store.put(store, new_page) # returns {hash, store} end defp split(store, hash, key) do if hash == nil do {nil, nil, store} else - { level, low, lst } = store[hash] - store = Map.delete(store, hash) + %Page{ level: level, low: low, list: lst } = Store.get(store, hash) + store = Store.free(store, hash) [ { k0, _, _} | _ ] = lst cond do key < k0 -> {lowlow, lowhi, store} = split(store, low, key) - newp2 = { level, lowhi, lst } - newp2h = SData.term_hash newp2 - store = Map.put(store, newp2h, newp2) + newp2 = %Page{ level: level, low: lowhi, list: lst } + {newp2h, store} = Store.put(store, newp2) {lowlow, newp2h, store} key > k0 -> {lst1, p2, store} = split_aux(store, lst, key, level) - newp1 = {level, low, lst1} - newp1h = SData.term_hash newp1 - store = Map.put(store, newp1h, newp1) + newp1 = %Page{ level: level, low: low, list: lst1} + {newp1h, store} = Store.put(store, newp1) {newp1h, p2, store} end end @@ -101,10 +116,8 @@ defmodule SData.MerkleSearchTree do { [{k1, v1, r1l}], r1h, store } [ {k1, v1, r1}, {k2, v2, r2} | rst ] when key < k2-> {r1l, r1h, store} = split(store, r1, key) - p2 = { level, r1h, [ {k2, v2, r2} | rst ] } - p2h = SData.term_hash p2 - store = store - |> Map.put(p2h, p2) + p2 = %Page{ level: level, low: r1h, list: [ {k2, v2, r2} | rst ] } + {p2h, store} = Store.put(store, p2) { [{k1, v1, r1l}], p2h, store } [ fst | rst ] -> {rst2, hi, store} = split_aux(store, rst, key, level) @@ -152,7 +165,7 @@ defmodule SData.MerkleSearchTree do case root do nil -> nil _ -> - { _, low, lst } = store[root] + %Page{ level: _, low: low, list: lst } = Store.get(store, root) get_aux(store, low, lst, key) end end @@ -179,7 +192,7 @@ defmodule SData.MerkleSearchTree do nil -> IO.puts(lvl <> "nil") _ -> - { level, low, lst} = store[root] + %Page{ level: level, low: low, list: lst} = Store.get(store, root) IO.puts(lvl <> "#{root|>Base.encode16} (#{level})") dump(store, low, lvl <> " ") for {k, v, r} <- lst do diff --git a/lib/data/store.ex b/lib/data/store.ex new file mode 100644 index 0000000..ca12cd0 --- /dev/null +++ b/lib/data/store.ex @@ -0,0 +1,91 @@ +defprotocol SData.Page do + @moduledoc""" + Protocol to be implemented by objects that are used as data pages + in a pagestore and that may reference other data pages by their hash. + """ + + @fallback_to_any true + + @doc""" + Get hashes of all pages referenced by this page. + """ + def refs(page) +end + +defimpl SData.Page, for: Any do + def refs(_page), do: [] +end + + +defprotocol SData.PageStore do + @moduledoc""" + Protocol to be implemented for page stores to allow their + manipulation. + + This protocol may also be implemented by store proxies that track + operations and implement different synchronization or caching mechanisms. + """ + + @doc""" + Put a page. Argument is the content of the page, returns the + hash that the store has associated to it. + + Returns {hash, store} + """ + def put(store, page) + + @doc""" + Get a page referenced by its hash. + + Returns page + """ + def get(store, hash) + + @doc""" + Copy to the store a page and all its references from the other store. + In the case of pages on the network in a distributed store, this may + be lazy. + + Returns store + """ + def copy(store, other_store, hash) + + @doc""" + Free a page referenced by its hash, marking it as no longer needed. + + Returns store + """ + def free(store, hash) +end + + +defmodule SData.LocalStore do + defstruct [:pages] + + def new() do + %SData.LocalStore{ pages: %{} } + end +end + +defimpl SData.PageStore, for: SData.LocalStore do + def put(store, page) do + hash = SData.term_hash page + store = %{ store | pages: Map.put(store.pages, hash, page) } + { hash, store } + end + + def get(store, hash) do + store.pages[hash] + end + + def copy(store, other_store, hash) do + page = SData.PageStore.get(other_store, hash) + refs = SData.Page.refs(page) + store = Enum.reduce(refs, store, fn x, acc -> copy(acc, other_store, x) end) + %{ store | pages: Map.put(store.pages, hash, page) } + end + + def free(store, hash) do + %{ store | pages: Map.delete(store.pages, hash) } + end +end |