defmodule SData.MerkleList do
@moduledoc"""
A simple Merkle list store.
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)
"""
defstruct [:root, :top, :cmp, :store]
@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
"""
def new(cmp) do
root_item = :root
root_hash = SData.term_hash root_item
state = %SData.MerkleList{
root: root_hash,
top: root_hash,
cmp: cmp,
store: %{ root_hash => root_item }
}
state
end
defp push(state, item) do
new_item = {item, state.top}
new_item_hash = SData.term_hash new_item
new_store = Map.put(state.store, new_item_hash, new_item)
%{ state | :top => new_item_hash, :store => new_store }
end
defp pop(state) do
if state.top == state.root do
:error
else
{item, next} = Map.get(state.store, state.top)
new_store = Map.delete(state.store, state.top)
new_state = %{ state | :top => next, :store => new_store }
{:ok, item, new_state}
end
end
@doc"""
Insert a list of items in the store.
A callback function may be specified that is called on any item
that is sucessfully added, i.e. that wasn't present in the store before.
"""
def insert_many(state, items, callback \\ (fn _ -> nil end)) do
items_sorted = Enum.sort(items, fn (x, y) -> state.cmp.(x, y) == :after end)
insert_many_aux(state, items_sorted, callback)
end
defp insert_many_aux(state, [], _callback) do
state
end
defp insert_many_aux(state, [item | rest], callback) do
case pop(state) do
:error ->
new_state = push(insert_many_aux(state, rest, callback), item)
callback.(item)
new_state
{:ok, front, state_rest} ->
case state.cmp.(item, front) do
:after ->
new_state = push(insert_many_aux(state, rest, callback), item)
callback.(item)
new_state
:duplicate -> insert_many_aux(state, rest, callback)
:before -> push(insert_many_aux(state_rest, [item | rest], callback), front)
end
end
end
@doc"""
Insert a single item in the store.
A callback function may be specified that is called on the item
if it is sucessfully added, i.e. it wasn't present in the store before.
"""
def insert(state, item, callback \\ (fn _ -> nil end)) do
insert_many(state, [item], callback)
end
@doc"""
Read some items from the state.
The two parameters are optional:
- qbegin : hash of the first item to read
- qlimit : number of items to read
"""
def read(state, qbegin \\ nil, qlimit \\ nil) do
begin = qbegin || state.top
limit = qlimit || 20
get_items_list(state, begin, limit)
end
@doc"""
Get the hash of the last item
"""
def top(state) do
state.top
end
@doc"""
Get the hash of the root item
"""
def root(state) do
state.root
end
@doc"""
Check if the store holds a certain item
"""
def has(state, hash) do
Map.has_key?(state.store, hash)
end
defp get_items_list(state, begin, limit) do
case limit do
0 -> {:ok, [], begin}
_ ->
case Map.fetch(state.store, begin) do
{:ok, :root} ->
{:ok, [], nil }
{:ok, {item, next}} ->
case get_items_list(state, next, limit - 1) do
{:ok, rest, past} ->
{:ok, [ item | rest ], past }
{:error, reason} -> {:error, reason}
end
:error -> {:error, begin}
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
