From 9e97754f5e005f80c64b7889c280f78b63d47b5b Mon Sep 17 00:00:00 2001
From: Magnus Ahltorp <map@kth.se>
Date: Mon, 27 Oct 2014 01:32:24 +0100
Subject: Optimize ts by storing tree in array of arrays.

---
 src/ts.erl | 51 ++++++++++++++++++++++++---------------------------
 1 file changed, 24 insertions(+), 27 deletions(-)

(limited to 'src/ts.erl')

diff --git a/src/ts.erl b/src/ts.erl
index cf71ff5..07edbf6 100644
--- a/src/ts.erl
+++ b/src/ts.erl
@@ -9,56 +9,53 @@
 -export_type([tree_store/0]).
 -export([new/0, add/3, delete/2, retrieve/2, count/2]).
 
-%% 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.
+-record(tree_store, {layers :: array:array(array:array(binary()))}). % array of arrays, keyed on layer.
 -type tree_store() :: #tree_store{}.
 
 %%%%%%%%%%%%%%%%%%%%
 %% Public.
 new() ->
-    #tree_store{layers = orddict:new()}.
+    #tree_store{layers = array:new()}.
 
 -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)}.
+    {NewLayers, List} = layer_rw(Layers, Layer),
+    NewList = array:set(array:size(List), Entry, List),
+    S#tree_store{layers = array:set(Layer, NewList, NewLayers)}.
 
 -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)}.
+    List = layer_ro(Layers, Layer),
+    NewList = array:resize(array:size(List) - 1, List),
+    S#tree_store{layers = array:set(Layer, NewList, Layers)}.
 
 -spec retrieve(tree_store(), tuple()) -> binary() | undefined.
 retrieve(#tree_store{layers = Layers}, {Layer, Index}) ->
-    List = layer(Layers, ro, Layer),
-    Len = length(List),
+    List = layer_ro(Layers, Layer),
+    Len = array:size(List),
     case Index < Len of
-        true -> lists:nth(Len - Index, List);
+        true -> array:get(Index, List);
         false -> undefined
     end.
 
 -spec count(tree_store(), non_neg_integer()) -> non_neg_integer().
 count(#tree_store{layers = Layers}, Layer) ->
-    length(layer(Layers, ro, Layer)).
+    array:size(layer_ro(Layers, Layer)).
 
 %%%%%%%%%%%%%%%%%%%%
 %% 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
+-spec layer_ro(array:array(array:array(binary())), non_neg_integer()) -> array:array(binary).
+layer_ro(Layers, Layer) ->
+    case array:get(Layer, Layers) of
+        undefined -> array:new();
+        List -> List
+    end.
+
+-spec layer_rw(array:array(array:array(binary())), non_neg_integer()) -> {array:array(), array:array(binary)}.
+layer_rw(Layers, Layer) ->
+    case array:get(Layer, Layers) of
+        undefined -> {array:set(Layer, array:new(), Layers), array:new()};
+        List -> {Layers, List}
     end.
 
 %%%%%%%%%%%%%%%%%%%%
-- 
cgit v1.1