From 3eabea607e7da4a5e3fa42668f470301d38509c5 Mon Sep 17 00:00:00 2001 From: Linus Nordberg Date: Tue, 16 Sep 2014 16:08:50 +0200 Subject: Rewrite ts to use a list of lists and change its API. We want to get rid of maps because they're a bit too new for some distributions. Replacing the arrays with lists is not necessary and arguably not even the right move -- they're about twice as costly RAM wise and the CPU cost for accesses are O(n). This cleans up the implementation though so let's keep it as a reference implementation. Changes to ht include poping potential placeholders in parent layer before adding and swapping IR -> RI all over, for consistency. --- src/ts.erl | 131 +++++++++++++++++++++++++++++++++---------------------------- 1 file changed, 70 insertions(+), 61 deletions(-) (limited to 'src/ts.erl') diff --git a/src/ts.erl b/src/ts.erl index e60a114..cf71ff5 100644 --- a/src/ts.erl +++ b/src/ts.erl @@ -7,78 +7,87 @@ -module(ts). -include_lib("eunit/include/eunit.hrl"). -export_type([tree_store/0]). --export([new/0, store/3, append/3, truncate/2, retrieve/2, retrieve_hash/2, delete/2]). +-export([new/0, add/3, delete/2, retrieve/2, count/2]). -%% FIXME: swap IR -> RI for consistency with ht - -%% FIXME: Keep the arrays in an array instead of in a map? Or maybe an -%% array of binaries? Hashes do have fixed lenght. --record(tree_store, {arrays :: map()}). % Map of arrays, indexed by layer. +%% FIXME: Keep the entries in binaries instead of lists? Hashes do +%% have fixed lenght. +-record(tree_store, {layers :: list()}). % orddict of lists, keyed on layer. -type tree_store() :: #tree_store{}. +%%%%%%%%%%%%%%%%%%%% +%% Public. new() -> - #tree_store{arrays = #{}}. + #tree_store{layers = orddict:new()}. --spec store(tree_store(), tuple(), binary()) -> tree_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 add(tree_store(), non_neg_integer(), binary()) -> tree_store(). +add(S = #tree_store{layers = Layers}, Layer, Entry) -> + {NewLayers, List} = layer(Layers, rw, Layer), + NewList = [Entry | List], + S#tree_store{layers = orddict:store(Layer, NewList, NewLayers)}. --spec retrieve(tree_store(), tuple()) -> {tuple(), binary()}. -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 delete(tree_store(), non_neg_integer()) -> tree_store(). +delete(S = #tree_store{layers = Layers}, Layer) -> + List = layer(Layers, ro, Layer), + [_ | NewList] = List, + S#tree_store{layers = orddict:store(Layer, NewList, Layers)}. --spec retrieve_hash(tree_store(), tuple()) -> binary(). -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). +-spec retrieve(tree_store(), tuple()) -> binary() | undefined. +retrieve(#tree_store{layers = Layers}, {Layer, Index}) -> + List = layer(Layers, ro, Layer), + Len = length(List), + case Index < Len of + true -> lists:nth(Len - Index, List); + false -> undefined + end. -truncate(S, R) -> - delete(S, {last, R}). +-spec count(tree_store(), non_neg_integer()) -> non_neg_integer(). +count(#tree_store{layers = Layers}, Layer) -> + length(layer(Layers, ro, Layer)). -%% 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)} +%%%%%%%%%%%%%%%%%%%% +%% Private. +-spec layer(list(), rw | ro, non_neg_integer()) -> list() | {list(), list()}. +layer(Layers, Access, Layer) -> + case Access of + rw -> + case orddict:find(Layer, Layers) of + error -> {orddict:store(Layer, [], Layers), []}; + {ok, List} -> {Layers, List} + end; + ro -> + case orddict:find(Layer, Layers) of + error -> []; + {ok, List} -> List + end end. %%%%%%%%%%%%%%%%%%%% %% Testing ts. --define(TEST_VECTOR, {{{0,0}, <<00>>}, - {{0,1}, <<01>>}, - {{1,0}, <<10>>}}). -store_test_() -> - T = ?TEST_VECTOR, +add_retrieve_test_() -> + S = new(), + S0 = add(S, 0, <<00>>), + S1 = add(S0, 0, <<01>>), + S2 = add(S1, 1, <<10>>), + [?_assertEqual(2, count(S2, 0)), + ?_assertEqual(1, count(S2, 1)), + ?_assertEqual(<<10>>, retrieve(S2, {1,0})), + ?_assertEqual(<<00>>, retrieve(S2, {0,0})), + ?_assertEqual(<<01>>, retrieve(S2, {0,1})), + ?_assertEqual(<<00>>, retrieve(S2, {0,0})), + ?_assertEqual(undefined, retrieve(S2, {3,0})), + ?_assertEqual(undefined, retrieve(S1, {1,0}))]. + +delete_test_() -> 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)), - ?_assertEqual(retrieve(S2, {0,1}), element(2, T)), - ?_assertEqual(retrieve(S2, {0,0}), element(1, T)), - ?_assertEqual(retrieve_hash(S2, {3,0}), undefined), - ?_assertEqual(retrieve_hash(S1, {1,0}), undefined) - ]. + S0 = add(S, 0, <<00>>), + S1 = add(S0, 0, <<01>>), + S2 = add(S1, 1, <<10>>), + S3 = delete(S2, 0), + S4 = add(S3, 0, <<99>>), + [?_assertEqual(2, count(S2, 0)), + ?_assertEqual(1, count(S3, 0)), + ?_assertEqual(2, count(S4, 0)), + ?_assertEqual(retrieve(S2, {0,1}), <<01>>), + ?_assertEqual(retrieve(S3, {0,1}), undefined), + ?_assertEqual(retrieve(S3, {0,0}), <<00>>), + ?_assertEqual(retrieve(S4, {0,1}), <<99>>)]. -- cgit v1.1