diff options
Diffstat (limited to 'shard/lib/data')
-rw-r--r-- | shard/lib/data/data.ex | 22 | ||||
-rw-r--r-- | shard/lib/data/merklelist.ex | 8 | ||||
-rw-r--r-- | shard/lib/data/merklesearchtree.ex | 16 | ||||
-rw-r--r-- | shard/lib/data/merkletree.ex | 14 | ||||
-rw-r--r-- | shard/lib/data/signrev.ex | 2 | ||||
-rw-r--r-- | shard/lib/data/store.ex | 11 |
6 files changed, 50 insertions, 23 deletions
diff --git a/shard/lib/data/data.ex b/shard/lib/data/data.ex index 33dca09..8d2b277 100644 --- a/shard/lib/data/data.ex +++ b/shard/lib/data/data.ex @@ -10,34 +10,46 @@ defmodule SData do These functions must only return :duplicate for equal items. """ - @doc """ + @doc""" Calculate the hash of an Erlang term by first converting it to its - binary representation. + binary representation. Equivalent to `bin_hash(term_bin(term))`. """ def term_hash(term, algo \\ :sha256) do :crypto.hash(algo, (:erlang.term_to_binary term)) end + @doc""" + Convert any Erlang term to a binary representation. + """ def term_bin(term) do :erlang.term_to_binary term end + @doc""" + Calculate the hash of a binary. + """ def bin_hash(bin, algo \\ :sha256) do :crypto.hash(algo, bin) end + @doc""" + Calculate the hash of a file. + """ def file_hash(path, algo \\ :sha256) do File.stream!(path, [], 65536) |> Enum.reduce(:crypto.hash_init(algo), &(:crypto.hash_update(&2, &1))) |> :crypto.hash_final() end + @doc""" + Recover an Erlang term from its binary representation. + """ def term_unbin(bin) do :erlang.binary_to_term(bin, [:safe]) end @doc""" - Compare function for arbitrary terms using the Erlang order + Compare function for arbitrary terms using the Erlang order """ def cmp_term(a, b) do cond do @@ -48,7 +60,7 @@ defmodule SData do end @doc""" - Compare function for timestamped strings + Compare function for timestamped strings """ def cmp_ts_str({ts1, str1}, {ts2, str2}) do cond do @@ -61,7 +73,7 @@ defmodule SData do end @doc""" - Merge function for nils + Merge function for nils """ def merge_true(true, true), do: true end diff --git a/shard/lib/data/merklelist.ex b/shard/lib/data/merklelist.ex index 9b44ee8..c450ca7 100644 --- a/shard/lib/data/merklelist.ex +++ b/shard/lib/data/merklelist.ex @@ -1,12 +1,8 @@ defmodule SData.MerkleList do @moduledoc""" - A simple Merkle list store. + A simple Merkle list store. Not used. - Future improvements: - - When messages are inserted other than at the top, all intermediate hashes - change. Keep track of the mapping from old hashes to new hashes so that get - requests can work even for hashes that are not valid anymore. - - group items in "pages" (bigger bundles) + TODO delete this module """ defstruct [:root, :top, :cmp, :store] diff --git a/shard/lib/data/merklesearchtree.ex b/shard/lib/data/merklesearchtree.ex index e646774..f67843d 100644 --- a/shard/lib/data/merklesearchtree.ex +++ b/shard/lib/data/merklesearchtree.ex @@ -3,15 +3,15 @@ defmodule SData.MerkleSearchTree do A Merkle search tree. A node of the tree is - { - level, - hash_of_node | nil, - [ - { item_low_bound, hash_of_node | nil }, - { item_low_bound, hash_of_node | nil }, - ... + { + level, + hash_of_node | nil, + [ + { item_low_bound, hash_of_node | nil }, + { item_low_bound, hash_of_node | nil }, + ... + } } - } """ alias SData.PageStore, as: Store diff --git a/shard/lib/data/merkletree.ex b/shard/lib/data/merkletree.ex index 73679cf..94bd443 100644 --- a/shard/lib/data/merkletree.ex +++ b/shard/lib/data/merkletree.ex @@ -92,9 +92,17 @@ defmodule SData.MerkleTree do end @doc""" - Get the hashes of all blocks in a range + Get the hashes of all blocks """ - def get_range(mt, range) do - range |> Enum.map(&(get(mt, &1))) # TODO: do this efficiently + def get_all(mt) do + %Page{child_nblk: cn, list: list} = Store.get(mt.store, mt.root) + if cn == 1 do + list + else + list + |> Enum.map(&(%{mt | root: &1})) + |> Enum.map(&get_all/1) + |> Enum.reduce([], &(&2++&1)) + end end end diff --git a/shard/lib/data/signrev.ex b/shard/lib/data/signrev.ex index 6360b53..164df03 100644 --- a/shard/lib/data/signrev.ex +++ b/shard/lib/data/signrev.ex @@ -56,7 +56,7 @@ defmodule SData.SignRev do @doc""" Check that a signed binary is correct and merge it into the SignRev. - Returns {true, new_sr} if an update happenned, {false, sr} otherwise. + Returns `{true, new_sr}` if an update happenned, `{false, sr}` otherwise. """ def merge(sr, signed, pk) do case Shard.Keys.open(pk, signed) do diff --git a/shard/lib/data/store.ex b/shard/lib/data/store.ex index ca12cd0..ce5618c 100644 --- a/shard/lib/data/store.ex +++ b/shard/lib/data/store.ex @@ -24,6 +24,10 @@ defprotocol SData.PageStore do This protocol may also be implemented by store proxies that track operations and implement different synchronization or caching mechanisms. + + A page store is an object that stores data pages (arbitrary Erlang terms) and + identifies them by their hash. Dependencies may exist between pages, in which + case they form a Merkle DAG. """ @doc""" @@ -60,8 +64,15 @@ end defmodule SData.LocalStore do + @moduledoc""" + A page store that saves all pages locally in RAM. The store is basically a dictionnary + of hash to term mappings, which is mutated by put operations. + """ defstruct [:pages] + @doc""" + Create empty LocalStore. + """ def new() do %SData.LocalStore{ pages: %{} } end |