1 files changed, 136 insertions, 0 deletions
diff --git a/lib/data/merklelist.ex b/lib/data/merklelist.ex
new file mode 100644
index 0000000..c9e27f6
--- /dev/null
+++ b/lib/data/merklelist.ex
@@ -0,0 +1,136 @@
+defmodule SData.MerkleList do
+  use GenServer
+
+  def start_link([cmp, name: name]) do
+    GenServer.start_link(__MODULE__, cmp, [name: name])
+  end
+
+  defp term_hash(term) do
+    :crypto.hash(:sha256, (:erlang.term_to_binary term))
+  end
+
+  @doc """
+    Initialize a Merkle List storage.
+    `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 init(cmp) do
+    root_item = :root
+    root_hash = 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 = 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