From c83ba74012e38c2fd1c46c063c9c094a78bf9680 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Fri, 31 Aug 2018 20:05:27 +0200 Subject: Custom compare and merge functions for Merkle search tree --- lib/app/chat.ex | 13 ++- lib/data/data.ex | 35 ++++++++ lib/data/merklelist.ex | 19 +---- lib/data/merklesearchtree.ex | 189 +++++++++++++++++++++++++------------------ test/conn_test.exs | 5 +- test/mkllst_test.exs | 2 +- test/mst_test.exs | 79 ++++++++++++++++-- 7 files changed, 231 insertions(+), 111 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 diff --git a/test/conn_test.exs b/test/conn_test.exs index d2431d7..275f6dd 100644 --- a/test/conn_test.exs +++ b/test/conn_test.exs @@ -56,10 +56,7 @@ defmodule ShardTest.Conn do GenServer.cast(pid1, {:chat_send, "test msg 1"}) GenServer.cast(pid2, {:chat_send, "test msg 2"}) - receive do after 100 -> nil end - {:ok, pid3} = DynamicSupervisor.start_child(Shard.DynamicSupervisor, {SApp.Chat, "test"}) - receive do after 100 -> nil end - assert not Process.alive?(pid3) + {:error, :redundant} = DynamicSupervisor.start_child(Shard.DynamicSupervisor, {SApp.Chat, "test"}) end end diff --git a/test/mkllst_test.exs b/test/mkllst_test.exs index ac13795..68dacf3 100644 --- a/test/mkllst_test.exs +++ b/test/mkllst_test.exs @@ -5,7 +5,7 @@ defmodule ShardTest.MklLst do test "merkle list" do alias SData.MerkleList, as: ML - mkl = ML.new(&ML.cmp_ts_str/2) + mkl = ML.new(&SData.cmp_ts_str/2) {:ok, [], nil} = ML.read(mkl) diff --git a/test/mst_test.exs b/test/mst_test.exs index 6615b6e..73b4f63 100644 --- a/test/mst_test.exs +++ b/test/mst_test.exs @@ -4,16 +4,16 @@ defmodule ShardTest.MST do doctest Shard.Application test "merkle search tree 1" do - y = Enum.reduce(0..1000, MST.new(), - fn i, acc -> MST.insert(acc, i, i) end) + y = Enum.reduce(0..1000, %MST{}, + fn i, acc -> MST.insert(acc, i) end) - z = Enum.reduce(Enum.shuffle(0..1000), MST.new(), - fn i, acc -> MST.insert(acc, i, i) end) + z = Enum.reduce(Enum.shuffle(0..1000), %MST{}, + fn i, acc -> MST.insert(acc, i) end) for i <- 0..1000 do - assert MST.get(y, i) == i - assert MST.get(z, i) == i + assert MST.get(y, i) == true + assert MST.get(z, i) == true end assert MST.get(y, 9999) == nil assert MST.get(z, -1001) == nil @@ -30,10 +30,12 @@ defmodule ShardTest.MST do {h, SData.term_hash h} end - y = Enum.reduce(items, MST.new(), + merge = fn a, b -> if a > b do a else b end end + + y = Enum.reduce(items, %MST{merge: merge}, fn {k, v}, acc -> MST.insert(acc, k, v) end) - z = Enum.reduce(Enum.shuffle(items), MST.new(), + z = Enum.reduce(Enum.shuffle(items), %MST{merge: merge}, fn {k, v}, acc -> MST.insert(acc, k, v) end) for {k, v} <- items do @@ -45,4 +47,65 @@ defmodule ShardTest.MST do IO.puts "z.root: #{z.root|>Base.encode16}" assert y.root == z.root end + + test "merkle search tree 3" do + merge = fn a, b -> if a > b do a else b end end + + y = Enum.reduce(0..1000, %MST{merge: merge}, + fn i, acc -> MST.insert(acc, i, i) end) + y = Enum.reduce(0..1000, y, + fn i, acc -> MST.insert(acc, i, i + 2 * rem(i, 2) - 1) end) + + + z = Enum.reduce(Enum.shuffle(0..1000), %MST{merge: merge}, + fn i, acc -> MST.insert(acc, i, i) end) + z = Enum.reduce(Enum.shuffle(0..1000), z, + fn i, acc -> MST.insert(acc, i, i + 2 * rem(i, 2) - 1) end) + + for i <- 0..1000 do + val = if rem(i, 2) == 1 do i+1 else i end + assert MST.get(y, i) == val + assert MST.get(z, i) == val + end + assert MST.get(y, 9999) == nil + assert MST.get(z, -1001) == nil + assert MST.get(z, 1.01) == nil + + IO.puts "y.root: #{y.root|>Base.encode16}" + IO.puts "z.root: #{z.root|>Base.encode16}" + assert y.root == z.root + end + + test "merkle search tree 4" do + items = for i <- 0..1000 do + h = SData.term_hash i + {h, SData.term_hash h} + end + + cmp = fn {a1, b1}, {a2, b2} -> + cond do + a1 < a2 -> :before + a1 > a2 -> :after + b1 > b2 -> :before + b1 < b2 -> :after + true -> :duplicate + end + end + + y = Enum.reduce(items, %MST{cmp: cmp}, + fn {a, b}, acc -> MST.insert(acc, {a, b}) end) + + z = Enum.reduce(Enum.shuffle(items), %MST{cmp: cmp}, + fn {a, b}, acc -> MST.insert(acc, {a, b}) end) + + for {k, v} <- items do + assert MST.get(y, {k, v}) == true + assert MST.get(z, {k, v}) == true + end + assert MST.get(z, {"foo", "bar"}) == nil + + IO.puts "y.root: #{y.root|>Base.encode16}" + IO.puts "z.root: #{z.root|>Base.encode16}" + assert y.root == z.root + end end -- cgit v1.2.3