couchdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kxe...@apache.org
Subject [08/31] couchdb commit: updated refs/heads/1963-eunit to 16528f8
Date Tue, 03 Jun 2014 04:50:27 GMT
Port 020-btree-basics.t and 021-btree-reductions.t etap suites to eunit

Both merged into single suite since they tests single target and shares
common bits.


Project: http://git-wip-us.apache.org/repos/asf/couchdb/repo
Commit: http://git-wip-us.apache.org/repos/asf/couchdb/commit/6943d645
Tree: http://git-wip-us.apache.org/repos/asf/couchdb/tree/6943d645
Diff: http://git-wip-us.apache.org/repos/asf/couchdb/diff/6943d645

Branch: refs/heads/1963-eunit
Commit: 6943d645c6dacc2a28353c4a70807e9edc411c42
Parents: 0f540bf
Author: Alexander Shorin <kxepal@gmail.com>
Authored: Sat May 17 03:28:14 2014 +0400
Committer: Alexander Shorin <kxepal@gmail.com>
Committed: Tue Jun 3 02:55:24 2014 +0400

----------------------------------------------------------------------
 test/couchdb/Makefile.am           |   1 +
 test/couchdb/couch_btree_tests.erl | 551 ++++++++++++++++++++++++++++++++
 test/etap/020-btree-basics.t       | 265 ---------------
 test/etap/021-btree-reductions.t   | 237 --------------
 test/etap/Makefile.am              |   2 -
 5 files changed, 552 insertions(+), 504 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/couchdb/blob/6943d645/test/couchdb/Makefile.am
----------------------------------------------------------------------
diff --git a/test/couchdb/Makefile.am b/test/couchdb/Makefile.am
index c3d170f..7ad8ae5 100644
--- a/test/couchdb/Makefile.am
+++ b/test/couchdb/Makefile.am
@@ -20,6 +20,7 @@ eunit_files = \
     couchdb_modules_load_tests.erl \
     couch_util_tests.erl \
     couch_file_tests.erl \
+    couch_btree_tests.erl \
     couchdb_tests.hrl
 
 EXTRA_DIST = \

http://git-wip-us.apache.org/repos/asf/couchdb/blob/6943d645/test/couchdb/couch_btree_tests.erl
----------------------------------------------------------------------
diff --git a/test/couchdb/couch_btree_tests.erl b/test/couchdb/couch_btree_tests.erl
new file mode 100644
index 0000000..d909d0a
--- /dev/null
+++ b/test/couchdb/couch_btree_tests.erl
@@ -0,0 +1,551 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+%   http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+-module(couch_btree_tests).
+
+-include_lib("couchdb_tests.hrl").
+-include("../../src/couchdb/couch_db.hrl").
+
+-define(ROWS, 1000).
+
+
+setup() ->
+    {ok, Fd} = couch_file:open(?tempfile(), [create, overwrite]),
+    {ok, Btree} = couch_btree:open(nil, Fd, [{compression, none},
+                                             {reduce, fun reduce_fun/2}]),
+    {Fd, Btree}.
+
+setup_kvs(_) ->
+    setup().
+
+setup_red() ->
+    {_, EvenOddKVs} = lists:foldl(
+        fun(Idx, {Key, Acc}) ->
+            case Key of
+                "even" -> {"odd", [{{Key, Idx}, 1} | Acc]};
+                _ -> {"even", [{{Key, Idx}, 1} | Acc]}
+            end
+        end, {"odd", []}, lists:seq(1, ?ROWS)),
+    {Fd, Btree} = setup(),
+    {ok, Btree1} = couch_btree:add_remove(Btree, EvenOddKVs, []),
+    {Fd, Btree1}.
+setup_red(_) ->
+    setup_red().
+
+teardown(Fd) when is_pid(Fd) ->
+    ok = couch_file:close(Fd);
+teardown({Fd, _}) ->
+    teardown(Fd).
+teardown(_, {Fd, _}) ->
+    teardown(Fd).
+
+
+kvs_test_funs() ->
+    [
+        fun should_set_fd_correctly/2,
+        fun should_set_root_correctly/2,
+        fun should_create_zero_sized_btree/2,
+        fun should_set_reduce_option/2,
+        fun should_fold_over_empty_btree/2,
+        fun should_add_all_keys/2,
+        fun should_continuously_add_new_kv/2,
+        fun should_continuously_remove_keys/2,
+        fun should_insert_keys_in_reversed_order/2,
+        fun should_add_every_odd_key_remove_every_even/2,
+        fun should_add_every_even_key_remove_every_old/2
+    ].
+
+red_test_funs() ->
+    [
+        fun should_reduce_whole_range/2,
+        fun should_reduce_first_half/2,
+        fun should_reduce_second_half/2
+    ].
+
+
+btree_open_test_() ->
+    {ok, Fd} = couch_file:open(?tempfile(), [create, overwrite]),
+    {ok, Btree} = couch_btree:open(nil, Fd, [{compression, none}]),
+    {
+        "Ensure that created btree is really a btree record",
+        ?_assert(is_record(Btree, btree))
+    }.
+
+sorted_kvs_test_() ->
+    Funs = kvs_test_funs(),
+    Sorted = [{Seq, random:uniform()} || Seq <- lists:seq(1, ?ROWS)],
+    {
+        "BTree with sorted keys",
+        {
+            foreachx,
+            fun setup_kvs/1, fun teardown/2,
+            [{Sorted, Fun} || Fun <- Funs]
+        }
+    }.
+
+rsorted_kvs_test_() ->
+    Sorted = [{Seq, random:uniform()} || Seq <- lists:seq(1, ?ROWS)],
+    Funs = kvs_test_funs(),
+    Reversed = Sorted,
+    {
+        "BTree with backward sorted keys",
+        {
+            foreachx,
+            fun setup_kvs/1, fun teardown/2,
+            [{Reversed, Fun} || Fun <- Funs]
+        }
+    }.
+
+shuffled_kvs_test_() ->
+    Funs = kvs_test_funs(),
+    Sorted = [{Seq, random:uniform()} || Seq <- lists:seq(1, ?ROWS)],
+    Shuffled = shuffle(Sorted),
+    {
+        "BTree with shuffled keys",
+        {
+            foreachx,
+            fun setup_kvs/1, fun teardown/2,
+            [{Shuffled, Fun} || Fun <- Funs]
+        }
+    }.
+
+reductions_test_() ->
+    {
+        "BTree reductions",
+        [
+            {
+                "Common tests",
+                {
+                    foreach,
+                    fun setup_red/0, fun teardown/1,
+                    [
+                        fun should_reduce_without_specified_direction/1,
+                        fun should_reduce_forward/1,
+                        fun should_reduce_backward/1
+                    ]
+                }
+            },
+            {
+                "Range requests",
+                [
+                    {
+                        "Forward direction",
+                        {
+                            foreachx,
+                            fun setup_red/1, fun teardown/2,
+                            [{fwd, F} || F <- red_test_funs()]
+                        }
+                    },
+                    {
+                        "Backward direction",
+                        {
+                            foreachx,
+                            fun setup_red/1, fun teardown/2,
+                            [{rev, F} || F <- red_test_funs()]
+                        }
+                    }
+                ]
+            }
+        ]
+    }.
+
+
+should_set_fd_correctly(_, {Fd, Btree}) ->
+    ?_assertMatch(Fd, Btree#btree.fd).
+
+should_set_root_correctly(_, {_, Btree}) ->
+    ?_assertMatch(nil, Btree#btree.root).
+
+should_create_zero_sized_btree(_, {_, Btree}) ->
+    ?_assertMatch(0, couch_btree:size(Btree)).
+
+should_set_reduce_option(_, {_, Btree}) ->
+    ReduceFun = fun reduce_fun/2,
+    Btree1 = couch_btree:set_options(Btree, [{reduce, ReduceFun}]),
+    ?_assertMatch(ReduceFun, Btree1#btree.reduce).
+
+should_fold_over_empty_btree(_, {_, Btree}) ->
+    {ok, _, EmptyRes} = couch_btree:foldl(Btree, fun(_, X) -> {ok, X+1} end, 0),
+    ?_assertEqual(EmptyRes, 0).
+
+should_add_all_keys(KeyValues, {Fd, Btree}) ->
+    {ok, Btree1} = couch_btree:add_remove(Btree, KeyValues, []),
+    [
+        should_return_complete_btree_on_adding_all_keys(KeyValues, Btree1),
+        should_have_non_zero_size(Btree1),
+        should_have_lesser_size_than_file(Fd, Btree1),
+        should_keep_root_pointer_to_kp_node(Fd, Btree1),
+        should_remove_all_keys(KeyValues, Btree1)
+    ].
+
+should_return_complete_btree_on_adding_all_keys(KeyValues, Btree) ->
+    ?_assert(test_btree(Btree, KeyValues)).
+
+should_have_non_zero_size(Btree) ->
+    ?_assert(couch_btree:size(Btree) > 0).
+
+should_have_lesser_size_than_file(Fd, Btree) ->
+    ?_assert((couch_btree:size(Btree) =< couch_file:bytes(Fd))).
+
+should_keep_root_pointer_to_kp_node(Fd, Btree) ->
+    ?_assertMatch({ok, {kp_node, _}},
+                  couch_file:pread_term(Fd, element(1, Btree#btree.root))).
+
+should_remove_all_keys(KeyValues, Btree) ->
+    Keys = keys(KeyValues),
+    {ok, Btree1} = couch_btree:add_remove(Btree, [], Keys),
+    {
+        "Should remove all the keys",
+        [
+            should_produce_valid_btree(Btree1, []),
+            should_be_empty(Btree1)
+        ]
+    }.
+
+should_continuously_add_new_kv(KeyValues, {_, Btree}) ->
+    {Btree1, _} = lists:foldl(
+        fun(KV, {BtAcc, PrevSize}) ->
+            {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [KV], []),
+            ?assert(couch_btree:size(BtAcc2) > PrevSize),
+            {BtAcc2, couch_btree:size(BtAcc2)}
+        end, {Btree, couch_btree:size(Btree)}, KeyValues),
+    {
+        "Should continuously add key-values to btree",
+        [
+            should_produce_valid_btree(Btree1, KeyValues),
+            should_not_be_empty(Btree1)
+        ]
+    }.
+
+should_continuously_remove_keys(KeyValues, {_, Btree}) ->
+    {ok, Btree1} = couch_btree:add_remove(Btree, KeyValues, []),
+    {Btree2, _} = lists:foldl(
+        fun({K, _}, {BtAcc, PrevSize}) ->
+            {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [], [K]),
+            ?assert(couch_btree:size(BtAcc2) < PrevSize),
+            {BtAcc2, couch_btree:size(BtAcc2)}
+        end, {Btree1, couch_btree:size(Btree1)}, KeyValues),
+    {
+        "Should continuously remove keys from btree",
+        [
+            should_produce_valid_btree(Btree2, []),
+            should_be_empty(Btree2)
+        ]
+    }.
+
+should_insert_keys_in_reversed_order(KeyValues, {_, Btree}) ->
+    KeyValuesRev = lists:reverse(KeyValues),
+    {Btree1, _} = lists:foldl(
+        fun(KV, {BtAcc, PrevSize}) ->
+            {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [KV], []),
+            ?assert(couch_btree:size(BtAcc2) > PrevSize),
+            {BtAcc2, couch_btree:size(BtAcc2)}
+        end, {Btree, couch_btree:size(Btree)}, KeyValuesRev),
+    should_produce_valid_btree(Btree1, KeyValues).
+
+should_add_every_odd_key_remove_every_even(KeyValues, {_, Btree}) ->
+    {ok, Btree1} = couch_btree:add_remove(Btree, KeyValues, []),
+    {_, Rem2Keys0, Rem2Keys1} = lists:foldl(fun(X, {Count, Left, Right}) ->
+        case Count rem 2 == 0 of
+            true -> {Count + 1, [X | Left], Right};
+            false -> {Count + 1, Left, [X | Right]}
+        end
+                                            end, {0, [], []}, KeyValues),
+    ?_assert(test_add_remove(Btree1, Rem2Keys0, Rem2Keys1)).
+
+should_add_every_even_key_remove_every_old(KeyValues, {_, Btree}) ->
+    {ok, Btree1} = couch_btree:add_remove(Btree, KeyValues, []),
+    {_, Rem2Keys0, Rem2Keys1} = lists:foldl(fun(X, {Count, Left, Right}) ->
+        case Count rem 2 == 0 of
+            true -> {Count + 1, [X | Left], Right};
+            false -> {Count + 1, Left, [X | Right]}
+        end
+                                            end, {0, [], []}, KeyValues),
+    ?_assert(test_add_remove(Btree1, Rem2Keys1, Rem2Keys0)).
+
+
+should_reduce_without_specified_direction({_, Btree}) ->
+    ?_assertMatch(
+        {ok, [{{"odd", _}, ?ROWS div 2}, {{"even", _}, ?ROWS div 2}]},
+        fold_reduce(Btree, [])).
+
+should_reduce_forward({_, Btree}) ->
+    ?_assertMatch(
+        {ok, [{{"odd", _}, ?ROWS div 2}, {{"even", _}, ?ROWS div 2}]},
+        fold_reduce(Btree, [{dir, fwd}])).
+
+should_reduce_backward({_, Btree}) ->
+    ?_assertMatch(
+        {ok, [{{"even", _}, ?ROWS div 2}, {{"odd", _}, ?ROWS div 2}]},
+        fold_reduce(Btree, [{dir, rev}])).
+
+should_reduce_whole_range(fwd, {_, Btree}) ->
+    {SK, EK} = {{"even", 0}, {"odd", ?ROWS - 1}},
+    [
+        {
+            "include endkey",
+            ?_assertMatch(
+                {ok, [{{"odd", 1}, ?ROWS div 2},
+                      {{"even", 2}, ?ROWS div 2}]},
+                fold_reduce(Btree, [{dir, fwd},
+                                    {start_key, SK},
+                                    {end_key, EK}]))
+        },
+        {
+            "exclude endkey",
+            ?_assertMatch(
+                {ok, [{{"odd", 1}, (?ROWS div 2) - 1},
+                      {{"even", 2}, ?ROWS div 2}]},
+                fold_reduce(Btree, [{dir, fwd},
+                                    {start_key, SK},
+                                    {end_key_gt, EK}]))
+        }
+    ];
+should_reduce_whole_range(rev, {_, Btree}) ->
+    {SK, EK} = {{"odd", ?ROWS - 1}, {"even", 2}},
+    [
+        {
+            "include endkey",
+            ?_assertMatch(
+                {ok, [{{"even", ?ROWS}, ?ROWS div 2},
+                      {{"odd", ?ROWS - 1}, ?ROWS div 2}]},
+                fold_reduce(Btree, [{dir, rev},
+                                    {start_key, SK},
+                                    {end_key, EK}]))
+        },
+        {
+            "exclude endkey",
+            ?_assertMatch(
+                {ok, [{{"even", ?ROWS}, (?ROWS div 2) - 1},
+                      {{"odd", ?ROWS - 1}, ?ROWS div 2}]},
+                fold_reduce(Btree, [{dir, rev},
+                                    {start_key, SK},
+                                    {end_key_gt, EK}]))
+        }
+    ].
+
+should_reduce_first_half(fwd, {_, Btree}) ->
+    {SK, EK} = {{"even", 0}, {"odd", (?ROWS div 2) - 1}},
+    [
+        {
+            "include endkey",
+            ?_assertMatch(
+                {ok, [{{"odd", 1}, ?ROWS div 4},
+                      {{"even", 2}, ?ROWS div 2}]},
+                fold_reduce(Btree, [{dir, fwd},
+                                    {start_key, SK}, {end_key, EK}]))
+        },
+        {
+            "exclude endkey",
+            ?_assertMatch(
+                {ok, [{{"odd", 1}, (?ROWS div 4) - 1},
+                      {{"even", 2}, ?ROWS div 2}]},
+                fold_reduce(Btree, [{dir, fwd},
+                                    {start_key, SK},
+                                    {end_key_gt, EK}]))
+        }
+    ];
+should_reduce_first_half(rev, {_, Btree}) ->
+    {SK, EK} = {{"odd", ?ROWS - 1}, {"even", ?ROWS div 2}},
+    [
+        {
+            "include endkey",
+            ?_assertMatch(
+                {ok, [{{"even", ?ROWS}, (?ROWS div 4) + 1},
+                      {{"odd", ?ROWS - 1}, ?ROWS div 2}]},
+                fold_reduce(Btree, [{dir, rev},
+                                    {start_key, SK},
+                                    {end_key, EK}]))
+        },
+        {
+            "exclude endkey",
+            ?_assertMatch(
+                {ok, [{{"even", ?ROWS}, ?ROWS div 4},
+                      {{"odd", ?ROWS - 1}, ?ROWS div 2}]},
+                fold_reduce(Btree, [{dir, rev},
+                                    {start_key, SK},
+                                    {end_key_gt, EK}]))
+        }
+    ].
+
+should_reduce_second_half(fwd, {_, Btree}) ->
+    {SK, EK} = {{"even", ?ROWS div 2}, {"odd", ?ROWS - 1}},
+    [
+        {
+            "include endkey",
+            ?_assertMatch(
+                {ok, [{{"odd", 1}, ?ROWS div 2},
+                      {{"even", ?ROWS div 2}, (?ROWS div 4) + 1}]},
+                fold_reduce(Btree, [{dir, fwd},
+                                    {start_key, SK},
+                                    {end_key, EK}]))
+        },
+        {
+            "exclude endkey",
+            ?_assertMatch(
+                {ok, [{{"odd", 1}, (?ROWS div 2) - 1},
+                      {{"even", ?ROWS div 2}, (?ROWS div 4) + 1}]},
+                fold_reduce(Btree, [{dir, fwd},
+                                    {start_key, SK},
+                                    {end_key_gt, EK}]))
+        }
+    ];
+should_reduce_second_half(rev, {_, Btree}) ->
+    {SK, EK} = {{"odd", (?ROWS div 2) + 1}, {"even", 2}},
+    [
+        {
+            "include endkey",
+            ?_assertMatch(
+                {ok, [{{"even", ?ROWS}, ?ROWS div 2},
+                      {{"odd", (?ROWS div 2) + 1}, (?ROWS div 4) + 1}]},
+                fold_reduce(Btree, [{dir, rev},
+                                    {start_key, SK},
+                                    {end_key, EK}]))
+        },
+        {
+            "exclude endkey",
+            ?_assertMatch(
+                {ok, [{{"even", ?ROWS}, (?ROWS div 2) - 1},
+                      {{"odd", (?ROWS div 2) + 1}, (?ROWS div 4) + 1}]},
+                fold_reduce(Btree, [{dir, rev},
+                                    {start_key, SK},
+                                    {end_key_gt, EK}]))
+        }
+    ].
+
+should_produce_valid_btree(Btree, KeyValues) ->
+    ?_assert(test_btree(Btree, KeyValues)).
+
+should_be_empty(Btree) ->
+    ?_assertEqual(couch_btree:size(Btree), 0).
+
+should_not_be_empty(Btree) ->
+    ?_assert(couch_btree:size(Btree) > 0).
+
+fold_reduce(Btree, Opts) ->
+    GroupFun = fun({K1, _}, {K2, _}) ->
+        K1 == K2
+    end,
+    FoldFun = fun(GroupedKey, Unreduced, Acc) ->
+        {ok, [{GroupedKey, couch_btree:final_reduce(Btree, Unreduced)} | Acc]}
+    end,
+    couch_btree:fold_reduce(Btree, FoldFun, [],
+                            [{key_group_fun, GroupFun}] ++ Opts).
+
+
+keys(KVs) ->
+    [K || {K, _} <- KVs].
+
+reduce_fun(reduce, KVs) ->
+    length(KVs);
+reduce_fun(rereduce, Reds) ->
+    lists:sum(Reds).
+
+
+shuffle(List) ->
+    randomize(round(math:log(length(List)) + 0.5), List).
+
+randomize(1, List) ->
+    randomize(List);
+randomize(T, List) ->
+    lists:foldl(
+        fun(_E, Acc) ->
+            randomize(Acc)
+        end, randomize(List), lists:seq(1, (T - 1))).
+
+randomize(List) ->
+    D = lists:map(fun(A) -> {random:uniform(), A} end, List),
+    {_, D1} = lists:unzip(lists:keysort(1, D)),
+    D1.
+
+test_btree(Btree, KeyValues) ->
+    ok = test_key_access(Btree, KeyValues),
+    ok = test_lookup_access(Btree, KeyValues),
+    ok = test_final_reductions(Btree, KeyValues),
+    ok = test_traversal_callbacks(Btree, KeyValues),
+    true.
+
+test_add_remove(Btree, OutKeyValues, RemainingKeyValues) ->
+    Btree2 = lists:foldl(
+        fun({K, _}, BtAcc) ->
+            {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [], [K]),
+            BtAcc2
+        end, Btree, OutKeyValues),
+    true = test_btree(Btree2, RemainingKeyValues),
+
+    Btree3 = lists:foldl(
+        fun(KV, BtAcc) ->
+            {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [KV], []),
+            BtAcc2
+        end, Btree2, OutKeyValues),
+    true = test_btree(Btree3, OutKeyValues ++ RemainingKeyValues).
+
+test_key_access(Btree, List) ->
+    FoldFun = fun(Element, {[HAcc|TAcc], Count}) ->
+        case Element == HAcc of
+            true -> {ok, {TAcc, Count + 1}};
+            _ -> {ok, {TAcc, Count + 1}}
+        end
+    end,
+    Length = length(List),
+    Sorted = lists:sort(List),
+    {ok, _, {[], Length}} = couch_btree:foldl(Btree, FoldFun, {Sorted, 0}),
+    {ok, _, {[], Length}} = couch_btree:fold(Btree, FoldFun,
+                                             {Sorted, 0}, [{dir, rev}]),
+    ok.
+
+test_lookup_access(Btree, KeyValues) ->
+    FoldFun = fun({Key, Value}, {Key, Value}) -> {stop, true} end,
+    lists:foreach(
+        fun({Key, Value}) ->
+            [{ok, {Key, Value}}] = couch_btree:lookup(Btree, [Key]),
+            {ok, _, true} = couch_btree:foldl(Btree, FoldFun,
+                                              {Key, Value}, [{start_key, Key}])
+        end, KeyValues).
+
+test_final_reductions(Btree, KeyValues) ->
+    KVLen = length(KeyValues),
+    FoldLFun = fun(_X, LeadingReds, Acc) ->
+        CountToStart = KVLen div 3 + Acc,
+        CountToStart = couch_btree:final_reduce(Btree, LeadingReds),
+        {ok, Acc + 1}
+    end,
+    FoldRFun = fun(_X, LeadingReds, Acc) ->
+        CountToEnd = KVLen - KVLen div 3 + Acc,
+        CountToEnd = couch_btree:final_reduce(Btree, LeadingReds),
+        {ok, Acc + 1}
+    end,
+    {LStartKey, _} = case KVLen of
+        0 -> {nil, nil};
+        _ -> lists:nth(KVLen div 3 + 1, lists:sort(KeyValues))
+    end,
+    {RStartKey, _} = case KVLen of
+        0 -> {nil, nil};
+        _ -> lists:nth(KVLen div 3, lists:sort(KeyValues))
+    end,
+    {ok, _, FoldLRed} = couch_btree:foldl(Btree, FoldLFun, 0,
+                                          [{start_key, LStartKey}]),
+    {ok, _, FoldRRed} = couch_btree:fold(Btree, FoldRFun, 0,
+                                         [{dir, rev}, {start_key, RStartKey}]),
+    KVLen = FoldLRed + FoldRRed,
+    ok.
+
+test_traversal_callbacks(Btree, _KeyValues) ->
+    FoldFun = fun
+        (visit, _GroupedKey, _Unreduced, Acc) ->
+            {ok, Acc andalso false};
+        (traverse, _LK, _Red, Acc) ->
+            {skip, Acc andalso true}
+    end,
+    % With 250 items the root is a kp. Always skipping should reduce to true.
+    {ok, _, true} = couch_btree:fold(Btree, FoldFun, true, [{dir, fwd}]),
+    ok.

http://git-wip-us.apache.org/repos/asf/couchdb/blob/6943d645/test/etap/020-btree-basics.t
----------------------------------------------------------------------
diff --git a/test/etap/020-btree-basics.t b/test/etap/020-btree-basics.t
deleted file mode 100755
index b0fb2d2..0000000
--- a/test/etap/020-btree-basics.t
+++ /dev/null
@@ -1,265 +0,0 @@
-#!/usr/bin/env escript
-%% -*- erlang -*-
-%%! -pa ./src/couchdb -sasl errlog_type error -boot start_sasl -noshell
-
-% Licensed under the Apache License, Version 2.0 (the "License"); you may not
-% use this file except in compliance with the License. You may obtain a copy of
-% the License at
-%
-%   http://www.apache.org/licenses/LICENSE-2.0
-%
-% Unless required by applicable law or agreed to in writing, software
-% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
-% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
-% License for the specific language governing permissions and limitations under
-% the License.
-
-filename() -> test_util:build_file("test/etap/temp.020").
-rows() -> 250.
-
--record(btree, {
-    fd,
-    root,
-    extract_kv,
-    assemble_kv,
-    less,
-    reduce,
-    compression
-}).
-
-main(_) ->
-    test_util:init_code_path(),
-    etap:plan(75),
-    case (catch test()) of
-        ok ->
-            etap:end_tests();
-        Other ->
-            etap:diag(io_lib:format("Test died abnormally: ~p", [Other])),
-            etap:bail()
-    end,
-    ok.
-
-%% @todo Determine if this number should be greater to see if the btree was
-%% broken into multiple nodes. AKA "How do we appropiately detect if multiple
-%% nodes were created."
-test()->
-    Sorted = [{Seq, random:uniform()} || Seq <- lists:seq(1, rows())],
-    etap:ok(test_kvs(Sorted), "Testing sorted keys"),
-    etap:ok(test_kvs(lists:reverse(Sorted)), "Testing reversed sorted keys"),
-    etap:ok(test_kvs(shuffle(Sorted)), "Testing shuffled keys."),
-    ok.
-
-test_kvs(KeyValues) ->
-    ReduceFun = fun
-        (reduce, KVs) ->
-            length(KVs);
-        (rereduce, Reds) ->
-            lists:sum(Reds)
-    end,
-
-    Keys = [K || {K, _} <- KeyValues],
-
-    {ok, Fd} = couch_file:open(filename(), [create,overwrite]),
-    {ok, Btree} = couch_btree:open(nil, Fd, [{compression, none}]),
-    etap:ok(is_record(Btree, btree), "Created btree is really a btree record"),
-    etap:is(Btree#btree.fd, Fd, "Btree#btree.fd is set correctly."),
-    etap:is(Btree#btree.root, nil, "Btree#btree.root is set correctly."),
-    etap:is(0, couch_btree:size(Btree), "Empty btrees have a 0 size."),
-
-    Btree1 = couch_btree:set_options(Btree, [{reduce, ReduceFun}]),
-    etap:is(Btree1#btree.reduce, ReduceFun, "Reduce function was set"),
-    {ok, _, EmptyRes} = couch_btree:foldl(Btree1, fun(_, X) -> {ok, X+1} end, 0),
-    etap:is(EmptyRes, 0, "Folding over an empty btree"),
-
-    {ok, Btree2} = couch_btree:add_remove(Btree1, KeyValues, []),
-    etap:ok(test_btree(Btree2, KeyValues),
-        "Adding all keys at once returns a complete btree."),
-
-    etap:is((couch_btree:size(Btree2) > 0), true,
-            "Non empty btrees have a size > 0."),
-    etap:is((couch_btree:size(Btree2) =< couch_file:bytes(Fd)), true,
-            "Btree size is <= file size."),
-
-    etap:fun_is(
-        fun
-            ({ok, {kp_node, _}}) -> true;
-            (_) -> false
-        end,
-        couch_file:pread_term(Fd, element(1, Btree2#btree.root)),
-        "Btree root pointer is a kp_node."
-    ),
-
-    {ok, Btree3} = couch_btree:add_remove(Btree2, [], Keys),
-    etap:ok(test_btree(Btree3, []),
-        "Removing all keys at once returns an empty btree."),
-
-    etap:is(0, couch_btree:size(Btree3),
-            "After removing all keys btree size is 0."),
-
-    {Btree4, _} = lists:foldl(fun(KV, {BtAcc, PrevSize}) ->
-        {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [KV], []),
-        case couch_btree:size(BtAcc2) > PrevSize of
-        true ->
-            ok;
-        false ->
-            etap:bail("After inserting a value, btree size did not increase.")
-        end,
-        {BtAcc2, couch_btree:size(BtAcc2)}
-    end, {Btree3, couch_btree:size(Btree3)}, KeyValues),
-
-    etap:ok(test_btree(Btree4, KeyValues),
-        "Adding all keys one at a time returns a complete btree."),
-    etap:is((couch_btree:size(Btree4) > 0), true,
-            "Non empty btrees have a size > 0."),
-
-    {Btree5, _} = lists:foldl(fun({K, _}, {BtAcc, PrevSize}) ->
-        {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [], [K]),
-        case couch_btree:size(BtAcc2) < PrevSize of
-        true ->
-            ok;
-        false ->
-            etap:bail("After removing a key, btree size did not decrease.")
-        end,
-        {BtAcc2, couch_btree:size(BtAcc2)}
-    end, {Btree4, couch_btree:size(Btree4)}, KeyValues),
-    etap:ok(test_btree(Btree5, []),
-        "Removing all keys one at a time returns an empty btree."),
-    etap:is(0, couch_btree:size(Btree5),
-            "After removing all keys, one by one, btree size is 0."),
-
-    KeyValuesRev = lists:reverse(KeyValues),
-    {Btree6, _} = lists:foldl(fun(KV, {BtAcc, PrevSize}) ->
-        {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [KV], []),
-        case couch_btree:size(BtAcc2) > PrevSize of
-        true ->
-            ok;
-        false ->
-            etap:is(false, true,
-                   "After inserting a value, btree size did not increase.")
-        end,
-        {BtAcc2, couch_btree:size(BtAcc2)}
-    end, {Btree5, couch_btree:size(Btree5)}, KeyValuesRev),
-    etap:ok(test_btree(Btree6, KeyValues),
-        "Adding all keys in reverse order returns a complete btree."),
-
-    {_, Rem2Keys0, Rem2Keys1} = lists:foldl(fun(X, {Count, Left, Right}) ->
-        case Count rem 2 == 0 of
-            true-> {Count+1, [X | Left], Right};
-            false -> {Count+1, Left, [X | Right]}
-        end
-    end, {0, [], []}, KeyValues),
-
-    etap:ok(test_add_remove(Btree6, Rem2Keys0, Rem2Keys1),
-        "Add/Remove every other key."),
-
-    etap:ok(test_add_remove(Btree6, Rem2Keys1, Rem2Keys0),
-        "Add/Remove opposite every other key."),
-
-    Size1 = couch_btree:size(Btree6),
-    {ok, Btree7} = couch_btree:add_remove(Btree6, [], [K||{K,_}<-Rem2Keys1]),
-    Size2 = couch_btree:size(Btree7),
-    etap:is((Size2 < Size1), true, "Btree size decreased"),
-    {ok, Btree8} = couch_btree:add_remove(Btree7, [], [K||{K,_}<-Rem2Keys0]),
-    Size3 = couch_btree:size(Btree8),
-    etap:is((Size3 < Size2), true, "Btree size decreased"),
-    etap:is(Size3, 0, "Empty btree has size 0."),
-    etap:ok(test_btree(Btree8, []),
-        "Removing both halves of every other key returns an empty btree."),
-
-    %% Third chunk (close out)
-    etap:is(couch_file:close(Fd), ok, "closing out"),
-    true.
-
-test_btree(Btree, KeyValues) ->
-    ok = test_key_access(Btree, KeyValues),
-    ok = test_lookup_access(Btree, KeyValues),
-    ok = test_final_reductions(Btree, KeyValues),
-    ok = test_traversal_callbacks(Btree, KeyValues),
-    true.
-
-test_add_remove(Btree, OutKeyValues, RemainingKeyValues) ->
-    Btree2 = lists:foldl(fun({K, _}, BtAcc) ->
-        {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [], [K]),
-        BtAcc2
-    end, Btree, OutKeyValues),
-    true = test_btree(Btree2, RemainingKeyValues),
-
-    Btree3 = lists:foldl(fun(KV, BtAcc) ->
-        {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [KV], []),
-        BtAcc2
-    end, Btree2, OutKeyValues),
-    true = test_btree(Btree3, OutKeyValues ++ RemainingKeyValues).
-
-test_key_access(Btree, List) ->
-    FoldFun = fun(Element, {[HAcc|TAcc], Count}) ->
-        case Element == HAcc of
-            true -> {ok, {TAcc, Count + 1}};
-            _ -> {ok, {TAcc, Count + 1}}
-        end
-    end,
-    Length = length(List),
-    Sorted = lists:sort(List),
-    {ok, _, {[], Length}} = couch_btree:foldl(Btree, FoldFun, {Sorted, 0}),
-    {ok, _, {[], Length}} = couch_btree:fold(Btree, FoldFun, {Sorted, 0}, [{dir, rev}]),
-    ok.
-
-test_lookup_access(Btree, KeyValues) ->
-    FoldFun = fun({Key, Value}, {Key, Value}) -> {stop, true} end,
-    lists:foreach(fun({Key, Value}) ->
-        [{ok, {Key, Value}}] = couch_btree:lookup(Btree, [Key]),
-        {ok, _, true} = couch_btree:foldl(Btree, FoldFun, {Key, Value}, [{start_key, Key}])
-    end, KeyValues).
-
-test_final_reductions(Btree, KeyValues) ->
-    KVLen = length(KeyValues),
-    FoldLFun = fun(_X, LeadingReds, Acc) ->
-        CountToStart = KVLen div 3 + Acc,
-        CountToStart = couch_btree:final_reduce(Btree, LeadingReds),
-        {ok, Acc+1}
-    end,
-    FoldRFun = fun(_X, LeadingReds, Acc) ->
-        CountToEnd = KVLen - KVLen div 3 + Acc,
-        CountToEnd = couch_btree:final_reduce(Btree, LeadingReds),
-        {ok, Acc+1}
-    end,
-    {LStartKey, _} = case KVLen of
-        0 -> {nil, nil};
-        _ -> lists:nth(KVLen div 3 + 1, lists:sort(KeyValues))
-    end,
-    {RStartKey, _} = case KVLen of
-        0 -> {nil, nil};
-        _ -> lists:nth(KVLen div 3, lists:sort(KeyValues))
-    end,
-    {ok, _, FoldLRed} = couch_btree:foldl(Btree, FoldLFun, 0, [{start_key, LStartKey}]),
-    {ok, _, FoldRRed} = couch_btree:fold(Btree, FoldRFun, 0, [{dir, rev}, {start_key, RStartKey}]),
-    KVLen = FoldLRed + FoldRRed,
-    ok.
-
-test_traversal_callbacks(Btree, _KeyValues) ->
-    FoldFun =
-    fun
-        (visit, _GroupedKey, _Unreduced, Acc) ->
-            {ok, Acc andalso false};
-        (traverse, _LK, _Red, Acc) ->
-            {skip, Acc andalso true}
-    end,
-    % With 250 items the root is a kp. Always skipping should reduce to true.
-    {ok, _, true} = couch_btree:fold(Btree, FoldFun, true, [{dir, fwd}]),
-    ok.
-
-shuffle(List) ->
-   randomize(round(math:log(length(List)) + 0.5), List).
-
-randomize(1, List) ->
-   randomize(List);
-randomize(T, List) ->
-    lists:foldl(fun(_E, Acc) ->
-        randomize(Acc)
-    end, randomize(List), lists:seq(1, (T - 1))).
-
-randomize(List) ->
-    D = lists:map(fun(A) ->
-        {random:uniform(), A}
-    end, List),
-    {_, D1} = lists:unzip(lists:keysort(1, D)),
-    D1.

http://git-wip-us.apache.org/repos/asf/couchdb/blob/6943d645/test/etap/021-btree-reductions.t
----------------------------------------------------------------------
diff --git a/test/etap/021-btree-reductions.t b/test/etap/021-btree-reductions.t
deleted file mode 100755
index e80ac2d..0000000
--- a/test/etap/021-btree-reductions.t
+++ /dev/null
@@ -1,237 +0,0 @@
-#!/usr/bin/env escript
-%% -*- erlang -*-
-%%! -pa ./src/couchdb -sasl errlog_type error -boot start_sasl -noshell
-
-% Licensed under the Apache License, Version 2.0 (the "License"); you may not
-% use this file except in compliance with the License. You may obtain a copy of
-% the License at
-%
-%   http://www.apache.org/licenses/LICENSE-2.0
-%
-% Unless required by applicable law or agreed to in writing, software
-% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
-% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
-% License for the specific language governing permissions and limitations under
-% the License.
-
-filename() -> "./test/etap/temp.021".
-rows() -> 1000.
-
-main(_) ->
-    test_util:init_code_path(),
-    etap:plan(20),
-    case (catch test()) of
-        ok ->
-            etap:end_tests();
-        Other ->
-            etap:diag(io_lib:format("Test died abnormally: ~p", [Other])),
-            etap:bail()
-    end,
-    ok.
-
-test()->
-    ReduceFun = fun
-        (reduce, KVs) -> length(KVs);
-        (rereduce, Reds) -> lists:sum(Reds)
-    end,
-
-    {ok, Fd} = couch_file:open(filename(), [create,overwrite]),
-    {ok, Btree} = couch_btree:open(nil, Fd, [{reduce, ReduceFun}]),
-
-    % Create a list, of {"even", Value} or {"odd", Value} pairs.
-    {_, EvenOddKVs} = lists:foldl(fun(Idx, {Key, Acc}) ->
-        case Key of
-            "even" -> {"odd", [{{Key, Idx}, 1} | Acc]};
-            _ -> {"even", [{{Key, Idx}, 1} | Acc]}
-        end
-    end, {"odd", []}, lists:seq(1, rows())),
-
-    {ok, Btree2} = couch_btree:add_remove(Btree, EvenOddKVs, []),
-
-    GroupFun = fun({K1, _}, {K2, _}) -> K1 == K2 end,
-    FoldFun = fun(GroupedKey, Unreduced, Acc) ->
-        {ok, [{GroupedKey, couch_btree:final_reduce(Btree2, Unreduced)} | Acc]}
-    end,
-
-    {SK1, EK1} = {{"even", -1}, {"even", foo}},
-    {SK2, EK2} = {{"odd", -1}, {"odd", foo}},
-
-    etap:fun_is(
-        fun
-            ({ok, [{{"odd", _}, 500}, {{"even", _}, 500}]}) ->
-                true;
-            (_) ->
-                false
-        end,
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [{key_group_fun, GroupFun}]),
-        "Reduction works with no specified direction, startkey, or endkey."
-    ),
-
-    etap:fun_is(
-        fun
-            ({ok, [{{"odd", _}, 500}, {{"even", _}, 500}]}) ->
-                true;
-            (_) ->
-                false
-        end,
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [{key_group_fun, GroupFun}, {dir, fwd}]),
-        "Reducing forward works with no startkey or endkey."
-    ),
-
-    etap:fun_is(
-        fun
-            ({ok, [{{"even", _}, 500}, {{"odd", _}, 500}]}) ->
-                true;
-            (_) ->
-                false
-        end,
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [{key_group_fun, GroupFun}, {dir, rev}]),
-        "Reducing backwards works with no startkey or endkey."
-    ),
-
-    etap:fun_is(
-        fun
-            ({ok, [{{"odd", _}, 500}, {{"even", _}, 500}]}) ->
-                true;
-            (_) ->
-                false
-        end,
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [{dir, fwd}, {key_group_fun, GroupFun},
{start_key, SK1}, {end_key, EK2}]),
-        "Reducing works over the entire range with startkey and endkey set."
-    ),
-
-    etap:fun_is(
-        fun
-            ({ok, [{{"even", _}, 500}]}) -> true;
-            (_) -> false
-        end,
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [{dir, fwd}, {key_group_fun, GroupFun},
{start_key, SK1}, {end_key, EK1}]),
-        "Reducing forward over first half works with a startkey and endkey."
-    ),
-
-    etap:fun_is(
-        fun
-            ({ok, [{{"odd", _}, 500}]}) -> true;
-            (_) -> false
-        end,
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [{dir, fwd}, {key_group_fun, GroupFun},
{start_key, SK2}, {end_key, EK2}]),
-        "Reducing forward over second half works with second startkey and endkey"
-    ),
-
-    etap:fun_is(
-        fun
-            ({ok, [{{"odd", _}, 500}]}) -> true;
-            (_) -> false
-        end,
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [{dir, rev}, {key_group_fun, GroupFun},
{start_key, EK2}, {end_key, SK2}]),
-        "Reducing in reverse works after swapping the startkey and endkey."
-    ),
-
-    etap:fun_is(
-        fun
-            ({ok, [{{"even", _}, 500}, {{"odd", _}, 500}]}) ->
-                true;
-            (_) ->
-                false
-        end,
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [{dir, rev}, {key_group_fun, GroupFun},
{start_key, EK2}, {end_key, SK1}]),
-        "Reducing in reverse results in reversed accumulator."
-    ),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, fwd}, {key_group_fun, GroupFun},
-            {start_key, {"even", 0}}, {end_key, {"odd", rows() + 1}}
-        ]),
-        {ok, [{{"odd", 1}, 500}, {{"even", 2}, 500}]},
-        "Right fold reduce value for whole range with inclusive end key"),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, fwd}, {key_group_fun, GroupFun},
-            {start_key, {"even", 0}}, {end_key_gt, {"odd", 999}}
-        ]),
-        {ok, [{{"odd", 1}, 499}, {{"even", 2}, 500}]},
-        "Right fold reduce value for whole range without inclusive end key"),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, rev}, {key_group_fun, GroupFun},
-            {start_key, {"odd", 999}}, {end_key, {"even", 2}}
-        ]),
-        {ok, [{{"even", 1000}, 500}, {{"odd", 999}, 500}]},
-        "Right fold reduce value for whole reversed range with inclusive end key"),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, rev}, {key_group_fun, GroupFun},
-            {start_key, {"odd", 999}}, {end_key_gt, {"even", 2}}
-        ]),
-        {ok, [{{"even", 1000}, 499}, {{"odd", 999}, 500}]},
-        "Right fold reduce value for whole reversed range without inclusive end key"),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, fwd}, {key_group_fun, GroupFun},
-            {start_key, {"even", 0}}, {end_key, {"odd", 499}}
-        ]),
-        {ok, [{{"odd", 1}, 250}, {{"even", 2}, 500}]},
-        "Right fold reduce value for first half with inclusive end key"),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, fwd}, {key_group_fun, GroupFun},
-            {start_key, {"even", 0}}, {end_key_gt, {"odd", 499}}
-        ]),
-        {ok, [{{"odd", 1}, 249}, {{"even", 2}, 500}]},
-        "Right fold reduce value for first half without inclusive end key"),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, rev}, {key_group_fun, GroupFun},
-            {start_key, {"odd", 999}}, {end_key, {"even", 500}}
-        ]),
-        {ok, [{{"even", 1000}, 251}, {{"odd", 999}, 500}]},
-        "Right fold reduce value for first half reversed with inclusive end key"),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, rev}, {key_group_fun, GroupFun},
-            {start_key, {"odd", 999}}, {end_key_gt, {"even", 500}}
-        ]),
-        {ok, [{{"even", 1000}, 250}, {{"odd", 999}, 500}]},
-        "Right fold reduce value for first half reversed without inclusive end key"),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, fwd}, {key_group_fun, GroupFun},
-            {start_key, {"even", 500}}, {end_key, {"odd", 999}}
-        ]),
-        {ok, [{{"odd", 1}, 500}, {{"even", 500}, 251}]},
-        "Right fold reduce value for second half with inclusive end key"),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, fwd}, {key_group_fun, GroupFun},
-            {start_key, {"even", 500}}, {end_key_gt, {"odd", 999}}
-        ]),
-        {ok, [{{"odd", 1}, 499}, {{"even", 500}, 251}]},
-        "Right fold reduce value for second half without inclusive end key"),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, rev}, {key_group_fun, GroupFun},
-            {start_key, {"odd", 501}}, {end_key, {"even", 2}}
-        ]),
-        {ok, [{{"even", 1000}, 500}, {{"odd", 501}, 251}]},
-        "Right fold reduce value for second half reversed with inclusive end key"),
-
-    etap:is(
-        couch_btree:fold_reduce(Btree2, FoldFun, [], [
-            {dir, rev}, {key_group_fun, GroupFun},
-            {start_key, {"odd", 501}}, {end_key_gt, {"even", 2}}
-        ]),
-        {ok, [{{"even", 1000}, 499}, {{"odd", 501}, 251}]},
-        "Right fold reduce value for second half reversed without inclusive end key"),
-
-    couch_file:close(Fd).

http://git-wip-us.apache.org/repos/asf/couchdb/blob/6943d645/test/etap/Makefile.am
----------------------------------------------------------------------
diff --git a/test/etap/Makefile.am b/test/etap/Makefile.am
index 7ac28b3..2e86144 100644
--- a/test/etap/Makefile.am
+++ b/test/etap/Makefile.am
@@ -36,8 +36,6 @@ fixture_files = \
     fixtures/test.couch
 
 tap_files = \
-    020-btree-basics.t \
-    021-btree-reductions.t \
     030-doc-from-json.t \
     031-doc-to-json.t \
     040-util.t \


Mime
View raw message