summaryrefslogtreecommitdiff
path: root/test/etap/020-btree-basics.t
diff options
context:
space:
mode:
Diffstat (limited to 'test/etap/020-btree-basics.t')
-rwxr-xr-xtest/etap/020-btree-basics.t218
1 files changed, 0 insertions, 218 deletions
diff --git a/test/etap/020-btree-basics.t b/test/etap/020-btree-basics.t
deleted file mode 100755
index 8ab453ee..00000000
--- a/test/etap/020-btree-basics.t
+++ /dev/null
@@ -1,218 +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}).
-
-main(_) ->
- test_util:init_code_path(),
- etap:plan(48),
- 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),
- 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."),
-
- 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: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."),
-
- Btree4 = lists:foldl(fun(KV, BtAcc) ->
- {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [KV], []),
- BtAcc2
- end, Btree3, KeyValues),
- etap:ok(test_btree(Btree4, KeyValues),
- "Adding all keys one at a time returns a complete btree."),
-
- Btree5 = lists:foldl(fun({K, _}, BtAcc) ->
- {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [], [K]),
- BtAcc2
- end, Btree4, KeyValues),
- etap:ok(test_btree(Btree5, []),
- "Removing all keys one at a time returns an empty btree."),
-
- KeyValuesRev = lists:reverse(KeyValues),
- Btree6 = lists:foldl(fun(KV, BtAcc) ->
- {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [KV], []),
- BtAcc2
- end, 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."),
-
- {ok, Btree7} = couch_btree:add_remove(Btree6, [], [K||{K,_}<-Rem2Keys1]),
- {ok, Btree8} = couch_btree:add_remove(Btree7, [], [K||{K,_}<-Rem2Keys0]),
- 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.
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-03 01:11:38 +0000