diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/app/chat.ex | 13 | ||||
-rw-r--r-- | lib/data/data.ex | 35 | ||||
-rw-r--r-- | lib/data/merklelist.ex | 19 | ||||
-rw-r--r-- | lib/data/merklesearchtree.ex | 189 |
4 files changed, 158 insertions, 98 deletions
diff --git a/lib/app/chat.ex b/lib/app/chat.ex index 85f5265..e28e896 100644 --- a/lib/app/chat.ex +++ b/lib/app/chat.ex @@ -49,7 +49,7 @@ defmodule SApp.Chat do } } :redundant -> - exit(:normal) + exit(:redundant) end end @@ -171,7 +171,14 @@ defmodule SApp.Chat do end defp msg_cmp({ts1, nick1, msg1}, {ts2, nick2, msg2}) do - SData.MerkleList.cmp_ts_str({ts1, nick1<>"|"<>msg1}, - {ts2, nick2<>"|"<>msg2}) + cond do + ts1 > ts2 -> :after + ts1 < ts2 -> :before + nick1 > nick2 -> :after + nick1 < nick2 -> :before + msg1 > msg2 -> :after + msg1 < msg2 -> :before + true -> :duplicate + end end end diff --git a/lib/data/data.ex b/lib/data/data.ex index 428957c..c2c659d 100644 --- a/lib/data/data.ex +++ b/lib/data/data.ex @@ -1,6 +1,13 @@ defmodule SData do @moduledoc """ Utility functions + + Compare functions are functions that compares stored items and provides a total order. + They must return: + - `:after` if the first argument is more recent + - `:duplicate` if the two items are the same + - `:before` if the first argument is older + These functions must only return :duplicate for equal items. """ @doc """ @@ -11,4 +18,32 @@ defmodule SData do :crypto.hash(algo, (:erlang.term_to_binary term)) end + @doc""" + Compare function for arbitrary terms using the Erlang order + """ + def cmp_term(a, b) do + cond do + a > b -> :after + a < b -> :before + a == b -> :duplicate + end + end + + @doc""" + Compare function for timestamped strings + """ + def cmp_ts_str({ts1, str1}, {ts2, str2}) do + cond do + ts1 > ts2 -> :after + ts1 < ts2 -> :before + str1 > str2 -> :after + str1 < str2 -> :before + true -> :duplicate + end + end + + @doc""" + Merge function for nils + """ + def merge_true(true, true), do: true end diff --git a/lib/data/merklelist.ex b/lib/data/merklelist.ex index 357f336..9b44ee8 100644 --- a/lib/data/merklelist.ex +++ b/lib/data/merklelist.ex @@ -14,11 +14,7 @@ defmodule SData.MerkleList do @doc""" Create a Merkle list store. - `cmp` is a function that compares stored items and provides a total order. - It must return: - - `:after` if the first argument is more recent - - `:duplicate` if the two items are the same - - `:before` if the first argument is older + `cmp` is a compare function that respects the interface defined in module `SData`. """ def new(cmp) do root_item = :root @@ -144,17 +140,4 @@ defmodule SData.MerkleList do end end end - - @doc""" - Compare function for timestamped strings - """ - def cmp_ts_str({ts1, str1}, {ts2, str2}) do - cond do - ts1 > ts2 -> :after - ts1 < ts2 -> :before - str1 == str2 -> :duplicate - str1 > str2 -> :after - str1 < str2 -> :before - end - end end diff --git a/lib/data/merklesearchtree.ex b/lib/data/merklesearchtree.ex index 963653e..0554f82 100644 --- a/lib/data/merklesearchtree.ex +++ b/lib/data/merklesearchtree.ex @@ -7,8 +7,8 @@ defmodule SData.MerkleSearchTree do level, hash_of_node | nil, [ - { k_low_bound, v, hash_of_node | nil }, - { k_low_bound, v, hash_of_node | nil }, + { item_low_bound, hash_of_node | nil }, + { item_low_bound, hash_of_node | nil }, ... } } @@ -16,8 +16,22 @@ defmodule SData.MerkleSearchTree do alias SData.PageStore, as: Store - defstruct [:root, :store] + @doc""" + Create a new Merkle search tree. + This structure can be used as a set with only true keys, + or as a map if a merge function is given. + + `cmp` is a compare function for keys as defined in module `SData`. + + `merge` is a function for merging two items that have the same key. + """ + defstruct root: nil, + store: SData.LocalStore.new, + cmp: &SData.cmp_term/2, + merge: &SData.merge_true/2 + + defmodule Page do defstruct [:level, :low, :list] end @@ -34,17 +48,10 @@ defmodule SData.MerkleSearchTree do end - def new(store \\ nil) do - store = store || SData.LocalStore.new - %SData.MerkleSearchTree{ - root: nil, - store: store - } - end - def insert(state, key, value) do + def insert(state, key, value \\ true) do level = calc_level(key) - {hash, store} = insert_at(state.store, state.root, key, level, value) + {hash, store} = insert_at(state, state.store, state.root, key, level, value) %{ state | root: hash, store: store } end @@ -52,7 +59,7 @@ defmodule SData.MerkleSearchTree do # TODO end - defp insert_at(store, root, key, level, value) do + defp insert_at(s, store, root, key, level, value) do {new_page, store} = if root == nil do { %Page{ level: level, low: nil, list: [ { key, value, nil } ] }, store } else @@ -60,46 +67,48 @@ defmodule SData.MerkleSearchTree do [ { k0, _, _} | _ ] = lst cond do plevel < level -> - {low, high, store} = split(store, root, key) + {low, high, store} = split(s, store, root, key) { %Page{ level: level, low: low, list: [ { key, value, high } ] }, store } plevel == level -> store = Store.free(store, root) - if key < k0 do - {low2a, low2b, store} = split(store, low, key) - { %Page{ level: level, low: low2a, list: [ { key, value, low2b } | lst] }, store } - else - {new_lst, store} = aux_insert_after_first(store, lst, key, value) - { %Page{ level: plevel, low: low, list: new_lst }, store } + case s.cmp.(key, k0) do + :before -> + {low2a, low2b, store} = split(s, store, low, key) + { %Page{ level: level, low: low2a, list: [ { key, value, low2b } | lst] }, store } + _ -> + {new_lst, store} = aux_insert_after_first(s, store, lst, key, value) + { %Page{ level: plevel, low: low, list: new_lst }, store } end plevel > level -> store = Store.free(store, root) - if key < k0 do - {new_low, store} = insert_at(store, low, key, level, value) - { %Page{ level: plevel, low: new_low, list: lst }, store } - else - {new_lst, store} = aux_insert_sub_after_first(store, lst, key, level, value) - { %Page{ level: plevel, low: low, list: new_lst }, store } + case s.cmp.(key, k0) do + :before -> + {new_low, store} = insert_at(s, store, low, key, level, value) + { %Page{ level: plevel, low: new_low, list: lst }, store } + :after -> + {new_lst, store} = aux_insert_sub_after_first(s, store, lst, key, level, value) + { %Page{ level: plevel, low: low, list: new_lst }, store } end end end Store.put(store, new_page) # returns {hash, store} end - defp split(store, hash, key) do + defp split(s, store, hash, key) do if hash == nil do {nil, nil, store} else %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) + case s.cmp.(key, k0) do + :before -> + {lowlow, lowhi, store} = split(s, store, low, key) 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) + :after -> + {lst1, p2, store} = split_aux(s, store, lst, key, level) newp1 = %Page{ level: level, low: low, list: lst1} {newp1h, store} = Store.put(store, newp1) {newp1h, p2, store} @@ -107,79 +116,105 @@ defmodule SData.MerkleSearchTree do end end - defp split_aux(store, lst, key, level) do + defp split_aux(s, store, lst, key, level) do case lst do - [ {k1, _, _} | _ ] when k1 == key -> - raise "Bad logic" [ {k1, v1, r1} ] -> - {r1l, r1h, store} = split(store, r1, key) + if s.cmp.(k1, key) == :duplicate do + raise "Bad logic" + end + {r1l, r1h, store} = split(s, store, r1, key) { [{k1, v1, r1l}], r1h, store } - [ {k1, v1, r1}, {k2, v2, r2} | rst ] when key < k2-> - {r1l, r1h, store} = split(store, r1, key) - 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) - { [ fst | rst2 ], hi, store } + [ {k1, v1, r1} = fst, {k2, v2, r2} = rst1 | rst ] -> + case s.cmp.(key, k2) do + :before -> + {r1l, r1h, store} = split(s, store, r1, key) + p2 = %Page{ level: level, low: r1h, list: [ {k2, v2, r2} | rst ] } + {p2h, store} = Store.put(store, p2) + { [{k1, v1, r1l}], p2h, store } + :after -> + {rst2, hi, store} = split_aux(s, store, [rst1 | rst], key, level) + { [ fst | rst2 ], hi, store } + :duplicate -> + raise "Bad logic" + end end end - defp aux_insert_after_first(store, lst, key, value) do + defp aux_insert_after_first(s, store, lst, key, value) do case lst do - [ {k1, _old_value, r1} | rst ] when k1 == key -> - { [ {k1, value, r1} | rst ], store } [ {k1, v1, r1} ] -> - {r1a, r1b, new_store} = split(store, r1, key) - { [ {k1, v1, r1a}, {key, value, r1b} ], new_store } - [ {k1, v1, r1}, {k2, v2, r2} | rst ] when key < k2-> - {r1a, r1b, new_store} = split(store, r1, key) - { [ {k1, v1, r1a}, {key, value, r1b}, {k2, v2, r2} | rst ], new_store } - [ fst | rst ] -> - {rst2, new_store} = aux_insert_after_first(store, rst, key, value) - { [ fst | rst2 ], new_store } + case s.cmp.(k1, key) do + :duplicate -> + { [ {k1, s.merge.(v1, value), r1} ], store } + :before -> + {r1a, r1b, new_store} = split(s, store, r1, key) + { [ {k1, v1, r1a}, {key, value, r1b} ], new_store } + end + [ {k1, v1, r1} = fst, {k2, v2, r2} = rst1 | rst ] -> + case s.cmp.(k1, key) do + :duplicate -> + { [ {k1, s.merge.(v1, value), r1}, rst1 | rst ], store } + :before -> + case s.cmp.(k2, key) do + :after -> + {r1a, r1b, new_store} = split(s, store, r1, key) + { [ {k1, v1, r1a}, {key, value, r1b}, {k2, v2, r2} | rst ], new_store } + _ -> + {rst2, new_store} = aux_insert_after_first(s, store, [rst1 | rst], key, value) + { [ fst | rst2 ], new_store } + end + end + end end - end - defp aux_insert_sub_after_first(store, lst, key, level, value) do + defp aux_insert_sub_after_first(s, store, lst, key, level, value) do case lst do - [ {k1, _, _} | _ ] when k1 == key -> - raise "Bad logic" [ {k1, v1, r1} ] -> - {r1new, store_new} = insert_at(store, r1, key, level, value) + if s.cmp.(k1, key) == :duplicate do + raise "Bad logic" + end + {r1new, store_new} = insert_at(s, store, r1, key, level, value) { [{k1, v1, r1new}], store_new } - [ {k1, v1, r1}, {k2, v2, r2} | rst ] when key < k2-> - {r1new, store_new} = insert_at(store, r1, key, level, value) - { [{k1, v1, r1new}, {k2, v2, r2} | rst], store_new } - [ fst | rst ] -> - {rst2, new_store} = aux_insert_sub_after_first(store, rst, key, level, value) - { [ fst | rst2 ], new_store } + [ {k1, v1, r1} = fst, {k2, _, _} = rst1 | rst ] -> + if s.cmp.(k1, key) == :duplicate do + raise "Bad logic" + end + case s.cmp.(key, k2) do + :before -> + {r1new, store_new} = insert_at(s, store, r1, key, level, value) + { [{k1, v1, r1new}, rst1 | rst], store_new } + _ -> + {rst2, new_store} = aux_insert_sub_after_first(s, store, [rst1 |rst], key, level, value) + { [ fst | rst2 ], new_store } + end end end def get(state, key) do - get(state.store, state.root, key) + get(state, state.store, state.root, key) end - defp get(store, root, key) do + defp get(s, store, root, key) do case root do nil -> nil _ -> %Page{ level: _, low: low, list: lst } = Store.get(store, root) - get_aux(store, low, lst, key) + get_aux(s, store, low, lst, key) end end - defp get_aux(store, low, lst, key) do + defp get_aux(s, 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) + get(s, store, low, key) + [ {k, v, low2} | rst ] -> + case s.cmp.(key, k) do + :duplicate -> v + :before -> + get(s, store, low, key) + :after -> + get_aux(s, store, low2, rst, key) + end end end |