Use PageStore protocol

2 files changed, 132 insertions, 28 deletions

diff --git a/lib/data/merklesearchtree.ex b/lib/data/merklesearchtree.ex
index 29c1dab..963653e 100644
--- a/lib/data/merklesearchtree.ex
+++ b/lib/data/merklesearchtree.ex
@@ -14,12 +14,31 @@ defmodule SData.MerkleSearchTree do
     }
   """
 
+  alias SData.PageStore, as: Store
+
   defstruct [:root, :store]
 
-  def new() do
+  defmodule Page do
+    defstruct [:level, :low, :list]
+  end
+
+  defimpl SData.Page, for: Page do
+    def refs(page) do
+      refs = for {_, _, h} <- page.list, h != nil, do: h
+      if page.low != nil do
+        [ page.low | refs ]
+      else
+        refs
+      end
+    end
+  end
+
+
+  def new(store \\ nil) do
+    store = store || SData.LocalStore.new
     %SData.MerkleSearchTree{
       root:  nil,
-      store: %{}
+      store: store
     }
   end
 
@@ -35,58 +54,54 @@ defmodule SData.MerkleSearchTree do
 
   defp insert_at(store, root, key, level, value) do
     {new_page, store} = if root == nil do
-      { { level, nil, [ { key, value, nil } ] }, store }
+      { %Page{ level: level, low: nil, list: [ { key, value, nil } ] }, store }
     else
-      { plevel, low, lst } = store[root]
+      %Page{ level: plevel, low: low, list: lst } = Store.get(store, root)
       [ { k0, _, _} | _ ] = lst
       cond do
         plevel < level ->
           {low, high, store} = split(store, root, key)
-          { { level, low, [ { key, value, high } ] }, store }
+          { %Page{ level: level, low: low, list: [ { key, value, high } ] }, store }
         plevel == level ->
-          store = Map.delete(store, root)
+          store = Store.free(store, root)
           if key < k0 do
             {low2a, low2b, store} = split(store, low, key)
-            { { level, low2a, [ { key, value, low2b } | lst] }, store }
+            { %Page{ level: level, low: low2a, list: [ { key, value, low2b } | lst] }, store }
           else
             {new_lst, store} = aux_insert_after_first(store, lst, key, value)
-            { { plevel, low, new_lst }, store }
+            { %Page{ level: plevel, low: low, list: new_lst }, store }
           end
         plevel > level ->
-          store = Map.delete(store, root)
+          store = Store.free(store, root)
           if key < k0 do
             {new_low, store} = insert_at(store, low, key, level, value)
-            { { plevel, new_low, lst }, store }
+            { %Page{ level: plevel, low: new_low, list: lst }, store }
           else 
             {new_lst, store} = aux_insert_sub_after_first(store, lst, key, level, value)
-            { { plevel, low, new_lst }, store }
+            { %Page{ level: plevel, low: low, list: new_lst }, store }
           end
       end
     end
-    hash = SData.term_hash new_page
-    store = Map.put(store, hash, new_page)
-    { hash, store }
+    Store.put(store, new_page)    # returns {hash, store}
   end
 
   defp split(store, hash, key) do
     if hash == nil do
       {nil, nil, store}
     else
-      { level, low, lst } = store[hash]
-      store = Map.delete(store, hash)
+      %Page{ level: level, low: low, list: lst } = Store.get(store, hash)
+      store = Store.free(store, hash)
       [ { k0, _, _} | _ ] = lst
       cond do
         key < k0 ->
           {lowlow, lowhi, store} = split(store, low, key)
-          newp2 = { level, lowhi, lst }
-          newp2h = SData.term_hash newp2
-          store = Map.put(store, newp2h, newp2)
+          newp2 = %Page{ level: level, low: lowhi, list: lst }
+          {newp2h, store} = Store.put(store, newp2)
           {lowlow, newp2h, store}
         key > k0 ->
           {lst1, p2, store} = split_aux(store, lst, key, level)
-          newp1 = {level, low, lst1}
-          newp1h = SData.term_hash newp1
-          store = Map.put(store, newp1h, newp1)
+          newp1 = %Page{ level: level, low: low, list: lst1}
+          {newp1h, store} = Store.put(store, newp1)
           {newp1h, p2, store}
       end 
     end
@@ -101,10 +116,8 @@ defmodule SData.MerkleSearchTree do
         { [{k1, v1, r1l}], r1h, store }
       [ {k1, v1, r1}, {k2, v2, r2} | rst ] when key < k2->
         {r1l, r1h, store} = split(store, r1, key)
-        p2 = { level, r1h, [ {k2, v2, r2} | rst ] }
-        p2h = SData.term_hash p2
-        store = store
-          |> Map.put(p2h, p2)
+        p2 = %Page{ level: level, low: r1h, list: [ {k2, v2, r2} | rst ] }
+        {p2h, store} = Store.put(store, p2)
         { [{k1, v1, r1l}], p2h, store }
       [ fst | rst ] ->
         {rst2, hi, store} = split_aux(store, rst, key, level)
@@ -152,7 +165,7 @@ defmodule SData.MerkleSearchTree do
     case root do
       nil -> nil
       _ ->
-        { _, low, lst } = store[root]
+        %Page{ level: _, low: low, list: lst } = Store.get(store, root)
         get_aux(store, low, lst, key)
     end
   end
@@ -179,7 +192,7 @@ defmodule SData.MerkleSearchTree do
       nil ->
         IO.puts(lvl <> "nil")
       _ ->
-        { level, low, lst} = store[root]
+        %Page{ level: level, low: low, list: lst} = Store.get(store, root)
         IO.puts(lvl <> "#{root|>Base.encode16} (#{level})")
         dump(store, low, lvl <> "  ")
         for {k, v, r} <- lst do
diff --git a/lib/data/store.ex b/lib/data/store.ex
new file mode 100644
index 0000000..ca12cd0
--- /dev/null
+++ b/lib/data/store.ex
@@ -0,0 +1,91 @@
+defprotocol SData.Page do
+  @moduledoc"""
+  Protocol to be implemented by objects that are used as data pages
+  in a pagestore and that may reference other data pages by their hash.
+  """
+
+  @fallback_to_any true
+
+  @doc"""
+  Get hashes of all pages referenced by this page.
+  """
+  def refs(page)
+end
+
+defimpl SData.Page, for: Any do
+  def refs(_page), do: []
+end
+
+
+defprotocol SData.PageStore do
+  @moduledoc"""
+  Protocol to be implemented for page stores to allow their
+  manipulation.
+
+  This protocol may also be implemented by store proxies that track
+  operations and implement different synchronization or caching mechanisms.
+  """
+
+  @doc"""
+  Put a page. Argument is the content of the page, returns the
+  hash that the store has associated to it.
+
+  Returns {hash, store}
+  """
+  def put(store, page)
+
+  @doc"""
+  Get a page referenced by its hash.
+
+  Returns page
+  """
+  def get(store, hash)
+
+  @doc"""
+  Copy to the store a page and all its references from the other store.
+  In the case of pages on the network in a distributed store, this may
+  be lazy.
+
+  Returns store
+  """
+  def copy(store, other_store, hash)
+
+  @doc"""
+  Free a page referenced by its hash, marking it as no longer needed.
+
+  Returns store
+  """
+  def free(store, hash)
+end
+
+
+defmodule SData.LocalStore do
+  defstruct [:pages] 
+
+  def new() do
+    %SData.LocalStore{ pages: %{} }
+  end
+end
+
+defimpl SData.PageStore, for: SData.LocalStore do
+  def put(store, page) do
+    hash = SData.term_hash page
+    store = %{ store | pages: Map.put(store.pages, hash, page) }
+    { hash, store }
+  end
+
+  def get(store, hash) do
+    store.pages[hash]
+  end
+
+  def copy(store, other_store, hash) do
+    page = SData.PageStore.get(other_store, hash)
+    refs = SData.Page.refs(page)
+    store = Enum.reduce(refs, store, fn x, acc -> copy(acc, other_store, x) end)
+    %{ store | pages: Map.put(store.pages, hash, page) }
+  end
+
+  def free(store, hash) do
+    %{ store | pages: Map.delete(store.pages, hash) }
+  end
+end