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)
"""
use GenServer
@doc """
Start a Merkle List storage process.
`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 start_link(cmp) do
GenServer.start_link(__MODULE__, cmp)
end
def init(cmp) do
root_item = :root
root_hash = SData.term_hash root_item
state = %{
root: root_hash,
top: root_hash,
cmp: cmp,
store: %{ root_hash => root_item }
}
{:ok, state}
end
defp state_push(item, state) 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 state_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
defp insert_many(state, [], _callback) do
state
end
defp insert_many(state, [item | rest], callback) do
case state_pop(state) do
:error ->
new_state = state_push(item, insert_many(state, rest, callback))
callback.(item)
new_state
{:ok, front, state_rest} ->
case state.cmp.(item, front) do
:after ->
new_state = state_push(item, insert_many(state, rest, callback))
callback.(item)
new_state
:duplicate -> insert_many(state, rest, callback)
:before -> state_push(front, insert_many(state_rest, [item | rest], callback))
end
end
end
def handle_cast({:insert, item}, state) do
handle_cast({:insert_many, [item]}, state)
end
def handle_cast({:insert_many, items}, state) do
handle_cast({:insert_many, items, fn _ -> nil end}, state)
end
def handle_cast({:insert_many, items, callback}, state) do
items_sorted = Enum.sort(items, fn (x, y) -> state.cmp.(x, y) == :after end)
new_state = insert_many(state, items_sorted, callback)
{:noreply, new_state}
end
def handle_call({:read, qbegin, qlimit}, _from, state) do
begin = qbegin || state.top
limit = qlimit || 20
items = get_items_list(state, begin, limit)
{:reply, items, state}
end
def handle_call(:top, _from, state) do
{:reply, state.top, state}
end
def handle_call(:root, _from, state) do
{:reply, state.root, state}
end
def handle_call({:has, hash}, _from, state) do
{:reply, Map.has_key?(state.store, hash), state}
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
