Remove bisect implementation We're not using this backend, and it requires R17 (we are still supporting R16 as of this writing).
diff --git a/rebar-test.config b/rebar-test.config index 170844e..160b729 100644 --- a/rebar-test.config +++ b/rebar-test.config
@@ -2,8 +2,6 @@ {deps, [ {basho_stats, "", {git, "https://github.com/knutin/basho_stats.git", {branch, "master"}}}, - {bisect, "", - {git, "https://github.com/knutin/bisect.git", {branch, "master"}}}, {proper, "", {git,"https://github.com/manopapad/proper.git", "master"}}, {stdlib2, "",
diff --git a/rebar.config b/rebar.config index 5cf51a1..0382632 100644 --- a/rebar.config +++ b/rebar.config
@@ -1,9 +1,4 @@ {cover_enabled, true}. -{deps, [ - {bisect, "", - {git, "https://github.com/knutin/bisect.git", {branch, "master"}}} - ]}. - {port_specs, [ {"priv/hyper_carray.so", ["c_src/hyper_carray.c"]}
diff --git a/src/hyper_bisect.erl b/src/hyper_bisect.erl deleted file mode 100644 index 2c31521..0000000 --- a/src/hyper_bisect.erl +++ /dev/null
@@ -1,250 +0,0 @@ --module(hyper_bisect). --include_lib("eunit/include/eunit.hrl"). --behaviour(hyper_register). - --export([new/1, - set/3, - max_merge/1, - max_merge/2, - reduce_precision/2, - bytes/1, - register_sum/1, - zero_count/1, - encode_registers/1, - decode_registers/2, - compact/1]). - - --define(KEY_SIZE, 16). --define(VALUE_SIZE, 8). - -%% -%% BEHAVIOUR -%% - -new(P) -> - DenseSize = trunc(math:pow(2, P)), - EntrySize = (?KEY_SIZE + ?VALUE_SIZE) div 8, - Threshold = DenseSize div EntrySize, - {sparse, bisect:new(?KEY_SIZE div 8, ?VALUE_SIZE div 8), P, Threshold}. - - -set(Index, Value, {sparse, B, P, Threshold}) -> - V = <<Value:?VALUE_SIZE/integer>>, - UpdateF = fun (OldValue) when OldValue >= V -> OldValue; - (OldValue) when OldValue < V -> V - end, - NewB = bisect:update(B, <<Index:?KEY_SIZE/integer>>, V, UpdateF), - - case bisect:num_keys(NewB) < Threshold of - true -> - {sparse, NewB, P, Threshold}; - false -> - {dense, bisect2dense(NewB, P)} - end; - -set(Index, Value, {dense, B} = D) -> - case binary:at(B, Index) of - R when R > Value -> - D; - _ -> - <<Left:Index/binary, _:?VALUE_SIZE, Right/binary>> = B, - {dense, iolist_to_binary([Left, <<Value:?VALUE_SIZE/integer>>, Right])} - end. - - - -fold(F, Acc, {sparse, B, _, _}) -> - InterfaceF = fun (<<Index:?KEY_SIZE/integer>>, - <<Value:?VALUE_SIZE/integer>>, - A) -> - F(Index, Value, A) - end, - bisect:foldl(B, InterfaceF, Acc); -fold(F, Acc, {dense, B}) -> - do_dense_fold(F, Acc, B). - - -max_merge(Registers) -> - [First | Rest] = Registers, - lists:foldl(fun max_merge/2, First, Rest). - - - -max_merge({sparse, Small, P, T}, {sparse, Big, P, T}) -> - ToInsert = bisect:foldl(Small, - fun (Index, Value, Acc) -> - case bisect:find(Big, Index) of - not_found -> - [{Index, Value} | Acc]; - V when V >= Value -> - Acc; - V when V < Value -> - [{Index, Value} | Acc] - end - end, - []), - Merged = bisect:bulk_insert(Big, lists:sort(ToInsert)), - {sparse, Merged, P, T}; - - -max_merge({dense, Left}, {dense, Right}) -> - Merged = iolist_to_binary( - do_dense_merge(Left, Right)), - {dense, Merged}; - -max_merge({dense, Dense}, {sparse, Sparse, P, _}) -> - {dense, iolist_to_binary( - do_dense_merge(Dense, bisect2dense(Sparse, P)))}; - -max_merge({sparse, Sparse, P, _}, {dense, Dense}) -> - {dense, iolist_to_binary( - do_dense_merge(Dense, bisect2dense(Sparse, P)))}. - -reduce_precision(_NewP, _B) -> - throw(not_implemented). - -compact(B) -> - B. - -bytes({sparse, Sparse, _, _}) -> bisect:size(Sparse); -bytes({dense, Dense}) -> erlang:byte_size(Dense). - - -register_sum(B) -> - M = case B of - {dense, Bytes} -> erlang:byte_size(Bytes); - {sparse, _, P, _} -> trunc(math:pow(2, P)) - end, - - {MaxI, Sum} = fold(fun (Index, Value, {I, Acc}) -> - Zeros = Index - I - 1, - {Index, Acc + math:pow(2, -Value) - + (math:pow(2, -0) * Zeros)} - end, {-1, 0}, B), - Sum + (M - 1 - MaxI) * math:pow(2, -0). - -zero_count({dense, _} = B) -> - fold(fun (_, 0, Acc) -> Acc + 1; - (_, _, Acc) -> Acc - end, 0, B); -zero_count({sparse, B, P, _}) -> - M = trunc(math:pow(2, P)), - M - bisect:num_keys(B). - -encode_registers({dense, B}) -> - B; -encode_registers({sparse, B, P, _}) -> - M = trunc(math:pow(2, P)), - iolist_to_binary( - do_encode_registers(M-1, B, [])). - - - -decode_registers(AllBytes, P) -> - M = DenseSize = trunc(math:pow(2, P)), - EntrySize = (?KEY_SIZE + ?VALUE_SIZE) div 8, - Threshold = DenseSize div EntrySize, - - Bytes = case AllBytes of - <<B:M/binary>> -> B; - <<B:M/binary, 0>> -> B - end, - - L = do_decode_registers(Bytes, 0), - case length(L) < Threshold of - true -> - New = bisect:new(?KEY_SIZE div 8, ?VALUE_SIZE div 8), - {sparse, bisect:from_orddict(New, L), P, Threshold}; - false -> - {dense, Bytes} - end. - - -%% -%% INTERNAL -%% - -do_dense_merge(<<>>, <<>>) -> - []; -do_dense_merge(<<Left:?VALUE_SIZE/integer, LeftRest/binary>>, - <<Right:?VALUE_SIZE/integer, RightRest/binary>>) -> - [max(Left, Right) | do_dense_merge(LeftRest, RightRest)]. - - - -do_dense_fold(F, Acc, B) -> - do_dense_fold(F, Acc, B, 0). - -do_dense_fold(_, Acc, <<>>, _) -> - Acc; -do_dense_fold(F, Acc, <<Value, Rest/binary>>, Index) -> - do_dense_fold(F, F(Index, Value, Acc), Rest, Index+1). - - - -bisect2dense(B, P) -> - M = trunc(math:pow(2, P)), - {LastI, L} = lists:foldl(fun ({<<Index:?KEY_SIZE/integer>>, V}, {I, Acc}) -> - Index < M orelse throw(index_too_high), - - Fill = case Index - I of - 0 -> - []; - ToFill -> - binary:copy(<<0>>, ToFill - 1) - end, - - {Index, [V, Fill | Acc]} - - end, {-1, []}, bisect:to_orddict(B)), - %% Fill last - Filled = [binary:copy(<<0>>, M - LastI - 1) | L], - - iolist_to_binary(lists:reverse(Filled)). - -do_encode_registers(I, _B, ByteEncoded) when I < 0 -> - ByteEncoded; -do_encode_registers(I, B, ByteEncoded) when I >= 0 -> - Byte = case bisect:find(B, <<I:?KEY_SIZE/integer>>) of - not_found -> - <<0>>; - V -> - V % already encoded - end, - do_encode_registers(I - 1, B, [Byte | ByteEncoded]). - - -do_decode_registers(<<>>, _) -> - []; -do_decode_registers(<<0, Rest/binary>>, I) -> - do_decode_registers(Rest, I+1); -do_decode_registers(<<Value:?VALUE_SIZE, Rest/binary>>, I) -> - [{<<I:?KEY_SIZE/integer>>, <<Value:?VALUE_SIZE/integer>>} - | do_decode_registers(Rest, I+1)]. - - - -%% -%% TESTS -%% - -bisect2dense_test() -> - P = 4, - M = 16, % pow(2, P) - - {sparse, B, _, _} = - lists:foldl(fun ({I, V}, Acc) -> - set(I, V, Acc) - end, new(P), [{2, 1}, {1, 1}, {4, 4}, {15, 5}]), - - Dense = bisect2dense(B, P), - ?assertEqual(M, size(Dense)), - - - Expected = <<0, 1, 1, 0, - 4, 0, 0, 0, - 0, 0, 0, 0, - 0, 0, 0, 5>>, - ?assertEqual(M, size(Expected)), - ?assertEqual(Expected, Dense).