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 compare function that respects the interface defined in module `SData`.
"""
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
end
