xref: /6.6.0/geocouch/vtree/test/010-delete.t (revision 92def13f)
1#!/usr/bin/env escript
2%% -*- erlang -*-
3%%! -na me insert@127.0.0.1
4
5% Licensed under the Apache License, Version 2.0 (the "License"); you may not
6% use this file except in compliance with the License. You may obtain a copy of
7% the License at
8%
9%   http://www.apache.org/licenses/LICENSE-2.0
10%
11% Unless required by applicable law or agreed to in writing, software
12% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
13% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
14% License for the specific language governing permissions and limitations under
15% the License.
16
17-include_lib("../include/vtree.hrl").
18
19-define(MOD, vtree_delete).
20-define(FILENAME, "/tmp/vtree_delete_vtree.bin").
21
22main(_) ->
23    % Set the random seed once. It might be reset a certain tests
24    rand:seed(exrop, {1, 11, 91}),
25
26    % Apache CouchDB doesn't have the couch_file_write_guard module
27    try
28        couch_file_write_guard:sup_start_link()
29    catch error:undef ->
30        ok
31    end,
32
33    code:add_pathz(filename:dirname(escript:script_name())),
34    etap:plan(47),
35    case (catch test()) of
36        ok ->
37            etap:end_tests();
38        Other ->
39            % Somehow etap:diag/1 and etap:bail/1 don't work properly
40            %etap:diag(io_lib:format("Test died abnormally: ~p", [Other])),
41            %etap:bail(Other),
42            io:format(standard_error, "Test died abnormally:~n~p~n", [Other])
43     end.
44
45
46test() ->
47    test_delete(),
48    test_delete_multiple(),
49    test_delete_nodes(),
50    test_member_of_nodes(),
51    test_partition_nodes(),
52    ok.
53
54
55test_delete() ->
56    % There are not many tests in here, the mjority of the functionality
57    % is already tested with test_delete_multiple/1.
58    Fd = vtree_test_util:create_file(?FILENAME),
59    Nodes1 = vtree_test_util:generate_kvnodes(6),
60
61    Vtree1 = #vtree{
62                fd = Fd,
63                kp_chunk_threshold = 2000,
64                kv_chunk_threshold = 2000,
65                min_fill_rate = 0.4,
66                less = fun(A, B) -> A < B end
67               },
68
69    Vtree2 = vtree_insert:insert(Vtree1, Nodes1),
70    ToDelete3 = lists:sublist(Nodes1, 2, 3),
71    Vtree3 = #vtree{root=Root3} = ?MOD:delete(Vtree2, ToDelete3),
72    {Depths3, KvNodes3} = vtree_test_util:get_kvnodes(
73                            Vtree3#vtree.fd, Root3#kp_node.childpointer),
74    etap:is(sets:size(sets:from_list(Depths3)), 1, "Tree is balanced"),
75    etap:is(hd(Depths3), 0, "Tree has expected depth"),
76    etap:is(lists:sort(KvNodes3), lists:sort(Nodes1 -- ToDelete3),
77            "6 nodes inserted, 3 deleted"),
78
79    Vtree4 = ?MOD:delete(Vtree2, Nodes1),
80    etap:is(Vtree4#vtree.root, nil, "6 nodes inserted, all deleted"),
81
82
83    Nodes2 = vtree_test_util:generate_kvnodes(174),
84    Vtree5 = vtree_insert:insert(Vtree1, Nodes2),
85    ToDelete6 = lists:sublist(Nodes2, 23, 107),
86    Vtree6 = #vtree{root=Root6} = ?MOD:delete(Vtree5, ToDelete6),
87    {Depths6, KvNodes6} = vtree_test_util:get_kvnodes(
88                            Vtree6#vtree.fd, Root6#kp_node.childpointer),
89    etap:is(sets:size(sets:from_list(Depths6)), 1, "Tree is balanced"),
90    etap:is(hd(Depths6), 2, "Tree has expected depth"),
91    etap:is(lists:sort(KvNodes6), lists:sort(Nodes2 -- ToDelete6),
92            "174 nodes inserted, 107 deleted"),
93
94    Vtree7 = ?MOD:delete(Vtree5, Nodes2),
95    etap:is(Vtree4#vtree.root, nil, "174 nodes inserted, all deleted"),
96
97    etap:is(?MOD:delete(Vtree2, []), Vtree2,
98            "Not deleting any nodes returns the original tree"),
99    etap:is(?MOD:delete(Vtree1, Nodes1), Vtree1,
100            "Deleting something from an empty tree, returns the original "
101            "empty tree"),
102
103    couch_file:close(Fd).
104
105
106test_delete_multiple() ->
107    rand:seed(exrop, {1, 11, 91}),
108    Fd = vtree_test_util:create_file(?FILENAME),
109
110    Vtree1 = #vtree{
111                fd = Fd,
112                kp_chunk_threshold = 1200,
113                kv_chunk_threshold = 1200,
114                min_fill_rate = 0.4,
115                less = fun(A, B) -> A < B end
116               },
117
118    Tests = [
119             {Vtree1, 18, 4, 14, 1},
120             {Vtree1, 50, 29, 12, 2},
121             {Vtree1, 50, 29, 1, 2},
122             {Vtree1, 4, 1, 1, 0},
123             {Vtree1, 4, 1, 4, 1},
124             {Vtree1, 37, 1, 37, 1},
125             {Vtree1, 37, 1, 36, 1}
126            ],
127    lists:foreach(fun({Vtree, NumNodes, From, To, Depth}) ->
128                          delete_multiple(Vtree, NumNodes, From, To, Depth)
129                  end, Tests),
130
131    couch_file:close(Fd).
132
133delete_multiple(Vtree0, NumNodes, From, NumDelete, Depth) ->
134    Nodes = vtree_test_util:generate_kvnodes(NumNodes),
135    Vtree = #vtree{root=Root} = vtree_insert:insert(Vtree0, Nodes),
136    ToDelete = lists:sublist(Nodes, From, NumDelete),
137    case ?MOD:delete_multiple(Vtree, [ToDelete], [Root]) of
138        [KpNode] ->
139            {Depths, KvNodes} = vtree_test_util:get_kvnodes(
140                                  Vtree#vtree.fd, KpNode#kp_node.childpointer),
141            etap:is(sets:size(sets:from_list(Depths)), 1, "Tree is balanced"),
142            etap:is(hd(Depths), Depth, "Tree has expected depth"),
143            etap:is(lists:sort(KvNodes), lists:sort(Nodes -- ToDelete),
144                    io_lib:format("Deleted ~p node(s) out of ~p node(s)",
145                                  [NumDelete, NumNodes]));
146        [] ->
147            etap:is(NumNodes, NumDelete, "All nodes were deleted")
148    end.
149
150
151test_delete_nodes() ->
152    [Node1, Node2, Node3, Node4, Node5] = Nodes =
153        vtree_test_util:generate_kvnodes(5),
154    etap:is(?MOD:delete_nodes([Node1], Nodes), [Node2, Node3, Node4, Node5],
155            "First node got delete"),
156    etap:is(?MOD:delete_nodes([Node2], Nodes), [Node1, Node3, Node4, Node5],
157            "Second node got delete"),
158    etap:is(?MOD:delete_nodes([Node5], Nodes), [Node1, Node2, Node3, Node4],
159            "Last node got delete"),
160    etap:is(?MOD:delete_nodes([Node5, Node2], Nodes), [Node1, Node3, Node4],
161            "Two nodes got delete"),
162    etap:is(?MOD:delete_nodes([Node4, Node1, Node3], Nodes), [Node2, Node5],
163            "Three nodes got delete"),
164    etap:is(lists:sort(?MOD:delete_nodes(Nodes, Nodes)), [],
165            "All nodes got delete").
166
167
168test_member_of_nodes() ->
169    Nodes1 = vtree_test_util:generate_kvnodes(10),
170    [NoMember1, NoMember2] = vtree_test_util:generate_kvnodes(2),
171    etap:ok(?MOD:member_of_nodes(lists:nth(1, Nodes1), Nodes1),
172            "Node is a member (a)"),
173    etap:ok(?MOD:member_of_nodes(lists:nth(5, Nodes1), Nodes1),
174            "Node is a member (b)"),
175    etap:ok(?MOD:member_of_nodes(lists:nth(8, Nodes1), Nodes1),
176            "Node is a member (c)"),
177    etap:not_ok(?MOD:member_of_nodes(NoMember1, Nodes1),
178                "Node is not a member (a)"),
179    etap:not_ok(?MOD:member_of_nodes(NoMember2, Nodes1),
180                "Node is not a member (b)"),
181
182    Nodes2 = vtree_test_util:generate_kvnodes(4),
183    [NoMember3] = vtree_test_util:generate_kvnodes(1),
184    etap:ok(?MOD:member_of_nodes(lists:nth(1, Nodes2), Nodes2),
185            "Node is a member (d)"),
186    etap:ok(?MOD:member_of_nodes(lists:nth(2, Nodes2), Nodes2),
187            "Node is a member (e)"),
188    etap:ok(?MOD:member_of_nodes(lists:nth(3, Nodes2), Nodes2),
189            "Node is a member (f)"),
190    etap:ok(?MOD:member_of_nodes(lists:nth(4, Nodes2), Nodes2),
191            "Node is a member (g)"),
192    etap:not_ok(?MOD:member_of_nodes(NoMember3, Nodes2),
193                "Node is not a member (c)").
194
195
196test_partition_nodes() ->
197    Less = fun(A, B) -> A < B end,
198
199    Mbb1 = [{-700, -600}, {-30, -25}],
200    Mbb2 = [{-800, -500}, {-55, -10}],
201    Mbb3 = [{-550, -400}, {-10, 0}],
202    Mbb4 = [{-300, -200}, {0, 40}],
203    Mbb5 = [{-450, -250}, {-20, 80}],
204
205    Mbb6 = [{-640, -620}, {-30, -25}],
206    Mbb7 = [{-700, -600}, {-21, -20}],
207    Mbb8 = [{-550, -450}, {-5, 0}],
208    Mbb9 = [{-450, -400}, {-10, 0}],
209    Mbb10 = [{-450, -400}, {-10, 50}],
210
211    KpNodes = [#kp_node{key=Mbb} || Mbb <- [Mbb3, Mbb1, Mbb2]],
212    ToPartition = [#kv_node{key=Mbb} || Mbb <- [Mbb6, Mbb7]],
213
214    Partitioned1 = ?MOD:partition_nodes(ToPartition, KpNodes, Less),
215    etap:is(lists:usort(lists:append(Partitioned1)),
216            lists:sort(ToPartition),
217            "All nodes were partitioned (a)"),
218    etap:is(Partitioned1,
219            [[], [#kv_node{key=Mbb6}],
220             [#kv_node{key=Mbb6}, #kv_node{key=Mbb7}]],
221            "All nodes were correctly partitioned (a)"),
222
223    KpNodes2 = [#kp_node{key=Mbb} || Mbb <- [Mbb2, Mbb3, Mbb4, Mbb5]],
224    ToPartition2 = [#kv_node{key=Mbb} || Mbb <- [Mbb8, Mbb6, Mbb9, Mbb10]],
225
226    Partitioned2 = ?MOD:partition_nodes(ToPartition2, KpNodes2, Less),
227    etap:is(lists:usort(lists:append(Partitioned2)),
228            lists:sort(ToPartition2),
229            "All nodes were partitioned (b)"),
230    etap:is(Partitioned2,
231            [[#kv_node{key=Mbb6}], [#kv_node{key=Mbb8}, #kv_node{key=Mbb9}],
232             [], [#kv_node{key=Mbb9}, #kv_node{key=Mbb10}]],
233            "All nodes were correctly partitioned (b)").
234