From d8294b2eb95858818a0ce1d5fe3e980aadf7ce53 Mon Sep 17 00:00:00 2001
From: Linus Nordberg <linus@nordberg.se>
Date: Thu, 11 Sep 2014 11:54:10 +0200
Subject: Another hashtree implementation, first cut.

This one stores the tree in arrays, one per layer in the tree.
It's implemented as gen_server.
---
 src/ts.erl | 81 ++++++++++++++++++++++++++++++++++++++++++++------------------
 1 file changed, 58 insertions(+), 23 deletions(-)

(limited to 'src/ts.erl')

diff --git a/src/ts.erl b/src/ts.erl
index 345ed66..a4d8107 100644
--- a/src/ts.erl
+++ b/src/ts.erl
@@ -2,36 +2,71 @@
 -module(ts).
 -include_lib("eunit/include/eunit.hrl").
 -export_type([tree_store/0]).
--export([new/0, delete/1, size/1, store/3, retrieve/2, retrieve_hash/2]).
+-export([new/0, store/3, append/3, truncate/2, retrieve/2, retrieve_hash/2, delete/2]).
 
-%% -record(tree_store, {warm :: ets:tid(),
-%%                      frozen :: list()}).  % [ets:tid()]
--record(tree_store, {table :: ets:tid()}).
+%% FIXME: keep the arrays in an array? or maybe an array of binaries?
+%% hashes do have fixed lenght.
+-record(tree_store, {arrays :: map()}). % Map of arrays, indexed by layer.
 -type tree_store() :: #tree_store{}.
 
 new() ->
-    %% tree_store#{warm = ets:new(nil, [{read_concurrency, true}]),
-    %%             frozen = ets:new(nil, [{read_concurrency, true}])}.
-    #tree_store{table = ets:new(nil, [{read_concurrency, true}])}.
-
-delete(Store) ->
-    ets:delete(Store#tree_store.table).
-
-size(Store) ->
-    ets:info(Store#tree_store.table, size).
+    #tree_store{arrays = #{}}.
 
 -spec store(tree_store(), tuple(), binary()) -> tree_store().
-store(Store, IR, Hash) ->
-    ets:insert(Store#tree_store.table, {IR, Hash}),
-    Store.
+store(S = #tree_store{arrays = Arrays}, {I, R}, Hash) ->
+    {A, NewArrays} = get_array(R, Arrays),
+    Index = case I of
+                append -> array:size(A);
+                N -> N
+            end,
+    S#tree_store{arrays = maps:put(R, array:set(Index, Hash, A), NewArrays)}.
 
 -spec retrieve(tree_store(), tuple()) -> {tuple(), binary()}.
-retrieve(#tree_store{table = Tab}, IR) ->
-    case ets:lookup(Tab, IR) of
-        [] -> exit(IR);
-        [R] -> R
-    end.
+retrieve(#tree_store{arrays = Arrays}, {I, R}) ->
+    {{I, R},
+     case maps:get(R, Arrays, undefined) of
+         undefined -> undefined;
+         A -> array:get(I, A)
+     end}.
 
 -spec retrieve_hash(tree_store(), tuple()) -> binary().
-retrieve_hash(#tree_store{table = Tab}, IR) ->
-    ets:lookup_element(Tab, IR, 2).
+retrieve_hash(S, IR) ->
+    element(2, retrieve(S, IR)).
+
+-spec delete(tree_store(), tuple()) -> tree_store().
+delete(S, {I, R}) ->
+    {A, NewArrays} = get_array(R, S#tree_store.arrays),
+    Index = case I of
+                last -> array:size(A) - 1;
+                N -> N
+            end,
+    S#tree_store{arrays = maps:put(R,
+                                   array:reset(Index, A),
+                                   NewArrays)}.
+append(S, R, Hash) ->
+    store(S, {append, R}, Hash).
+
+truncate(S, R) ->
+    delete(S, {last, R}).
+
+%% Private
+get_array(Layer, Arrays) ->
+    case maps:is_key(Layer, Arrays) of
+        true -> {maps:get(Layer, Arrays), Arrays} ;
+        false ->
+            NewArray = array:new(),
+            {NewArray, maps:put(Layer, NewArray, Arrays)}
+    end.
+
+%%%%%%%%%%%%%%%%%%%%
+%% Testing ts.
+-define(TEST_VECTOR, {{{0,0}, <<00>>},
+                      {{0,1}, <<01>>},
+                      {{1,0}, <<10>>}}).
+store_test_() ->
+    T = ?TEST_VECTOR,
+    S = new(),
+    S0 = store(S, {0,0}, <<00>>),
+    S1 = store(S0, {0,1}, <<01>>),
+    S2 = store(S1, {1,0}, <<10>>),
+    [?_assertEqual(retrieve(S2, {1,0}), element(3, T))].
-- 
cgit v1.1