1 files changed, 143 insertions, 0 deletions
diff --git a/shard/lib/data/merklelist.ex b/shard/lib/data/merklelist.ex
new file mode 100644
index 0000000..9b44ee8
--- /dev/null
+++ b/shard/lib/data/merklelist.ex
@@ -0,0 +1,143 @@
+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