xref: /6.6.0/geocouch/vtree/test/006-insert.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_insert).
20-define(FILENAME, "/tmp/vtree_insert_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(43),
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_insert(),
48    test_insert_in_bulks(),
49    test_insert_multiple(),
50    test_insert_nodes(),
51    test_partition_nodes(),
52    test_add_to_nth(),
53    ok.
54
55
56test_insert() ->
57    Fd = vtree_test_util:create_file(?FILENAME),
58    Nodes1 = vtree_test_util:generate_kvnodes(6),
59    Vtree1 = #vtree{
60                fd = Fd,
61                kv_chunk_threshold = 3000,
62                kp_chunk_threshold = 3000,
63                min_fill_rate = 0.3,
64                less = fun(A, B) -> A < B end
65     },
66
67    NewVtree1 = ?MOD:insert(Vtree1, [hd(Nodes1)]),
68    Root1 = NewVtree1#vtree.root,
69    [InsertedNodes1] = vtree_io:read_node(Fd, Root1#kp_node.childpointer),
70    etap:is(InsertedNodes1, hd(Nodes1),
71            "Inserted single node into emtpy tree: node got inserted"),
72
73    NewVtree2 = ?MOD:insert(Vtree1, Nodes1),
74    Root2 = NewVtree2#vtree.root,
75    InsertedNodes2 = vtree_io:read_node(Fd, Root2#kp_node.childpointer),
76    etap:is(InsertedNodes2, Nodes1,
77            "Inserted into 6 nodes into emtpy tree: all nodes got inserted"),
78
79    Nodes3 = vtree_test_util:generate_kvnodes(500),
80    NewVtree3 = ?MOD:insert(Vtree1, Nodes3),
81    Root3 = NewVtree3#vtree.root,
82    {Depths3, KvNodes3} = vtree_test_util:get_kvnodes(
83                            Fd, Root3#kp_node.childpointer),
84    etap:is(sets:size(sets:from_list(Depths3)), 1,
85            "Inserted 500 nodes into emtpy tree: tree is balanced"),
86    etap:is(hd(Depths3), 2, "Tree has expected depth"),
87    etap:is(lists:sort(KvNodes3), lists:sort(Nodes3),
88            "Inserted 500 nodes into emtpy tree: all nodes got inserted"),
89
90    Nodes4 = vtree_test_util:generate_kvnodes(223),
91    NewVtree4 = ?MOD:insert(NewVtree3, Nodes4),
92    Root4 = NewVtree4#vtree.root,
93    {Depths4, KvNodes4} = vtree_test_util:get_kvnodes(
94                            Fd, Root4#kp_node.childpointer),
95    etap:is(sets:size(sets:from_list(Depths4)), 1,
96            "Inserted 223 nodes into existing tree: tree is balanced"),
97    etap:is(hd(Depths4), 2, "Tree has expected depth"),
98    etap:is(lists:sort(KvNodes4), lists:sort(Nodes3 ++ Nodes4),
99            "Inserted 223 nodes into existing tree: all nodes got inserted"),
100
101    Nodes5 = vtree_test_util:generate_kvnodes(1),
102    NewVtree5 = ?MOD:insert(NewVtree1, Nodes5),
103    Root5 = NewVtree5#vtree.root,
104    {Depths5, KvNodes5} = vtree_test_util:get_kvnodes(
105                            Fd, Root5#kp_node.childpointer),
106    etap:is(sets:size(sets:from_list(Depths5)), 1,
107            "Inserted single node into existing single node tree: tree is "
108            "balanced. Root has < kp_chunk_threshold nodes"),
109    etap:is(hd(Depths5), 0, "Tree has expected depth"),
110    etap:is(lists:sort(KvNodes5), lists:sort([hd(Nodes1)|Nodes5]),
111            "Inserted single node into existing tree: node got inserted. "
112            "Root has < kp_chunk_threshold nodes"),
113
114    etap:is(?MOD:insert(NewVtree2, []), NewVtree2,
115            "Not adding any nodes returns the original tree"),
116
117    couch_file:close(Fd).
118
119
120test_insert_in_bulks()->
121    Less = fun(A, B) -> A < B end,
122    Fd = vtree_test_util:create_file(?FILENAME),
123
124    Vtree0 = #vtree{
125                fd = Fd,
126                kv_chunk_threshold = 1600,
127                kp_chunk_threshold = 1600,
128                min_fill_rate = 0.4,
129                less = Less
130               },
131    Nodes0 = vtree_test_util:generate_kvnodes(1),
132    % `insert_in_bulks/3` is never called on an empty tree
133    Vtree1 = ?MOD:insert(Vtree0, Nodes0),
134
135    Nodes1 = vtree_test_util:generate_kvnodes(20),
136    Nodes2 = vtree_test_util:generate_kvnodes(100),
137    Nodes3 = vtree_test_util:generate_kvnodes(50),
138
139    #vtree{root=Root1} = ?MOD:insert_in_bulks(Vtree1, Nodes1, 7),
140    {Depths1, KvNodes1} = vtree_test_util:get_kvnodes(
141                            Fd, Root1#kp_node.childpointer),
142    etap:is(sets:size(sets:from_list(Depths1)), 1,
143            "Tree is balanced (originally empty) (a)"),
144    etap:is(hd(Depths1), 1, "Tree has expected depth (a)"),
145    etap:is(lists:sort(KvNodes1), lists:sort(Nodes1 ++ Nodes0),
146            "All nodes were inserted (originally empty) (a)"),
147
148    #vtree{root=Root2} = ?MOD:insert_in_bulks(Vtree1, Nodes2, 9),
149    {Depths2, KvNodes2} = vtree_test_util:get_kvnodes(
150                            Fd, Root2#kp_node.childpointer),
151    etap:is(sets:size(sets:from_list(Depths2)), 1,
152            "Tree is balanced (originally empty) (b)"),
153    etap:is(hd(Depths2), 2, "Tree has expected depth (b)"),
154    etap:is(lists:sort(KvNodes2), lists:sort(Nodes2 ++ Nodes0),
155            "All nodes were inserted (originally empty) (b)"),
156
157    #vtree{root=Root3} = ?MOD:insert_in_bulks(Vtree1#vtree{root=Root1},
158                                              Nodes3, 10),
159    {Depths3, KvNodes3} = vtree_test_util:get_kvnodes(
160                            Fd, Root3#kp_node.childpointer),
161    etap:is(sets:size(sets:from_list(Depths3)), 1,
162            "Tree is balanced (originally not empty)"),
163    etap:is(hd(Depths3), 2, "Tree has expected depth (originally not empty"),
164    etap:is(lists:sort(KvNodes3), lists:sort(Nodes1 ++ Nodes3 ++ Nodes0),
165            "All nodes were inserted (originally not empty)"),
166
167    couch_file:close(Fd).
168
169
170test_insert_multiple() ->
171    Less = fun(A, B) -> A < B end,
172    Fd = vtree_test_util:create_file(?FILENAME),
173
174    Vtree1 = #vtree{
175                fd = Fd,
176                kv_chunk_threshold = 1600,
177                kp_chunk_threshold = 1600,
178                min_fill_rate = 0.4,
179                less = Less
180     },
181
182    Nodes1 = vtree_test_util:generate_kvnodes(20),
183    Nodes2 = vtree_test_util:generate_kvnodes(10),
184    Nodes3 = vtree_test_util:generate_kvnodes(100),
185    Vtree2 = #vtree{root=Root} = ?MOD:insert(Vtree1, Nodes1),
186
187    PartitionedNodes1 = ?MOD:partition_nodes(Nodes2, [Root], Less),
188    [KpNode1] = ?MOD:insert_multiple(Vtree2, PartitionedNodes1, [Root]),
189    {Depths1, KvNodes1} = vtree_test_util:get_kvnodes(
190                            Fd, KpNode1#kp_node.childpointer),
191    etap:is(sets:size(sets:from_list(Depths1)), 1, "Tree is balanced (a)"),
192    etap:is(hd(Depths1), 1, "Tree has expected depth"),
193    etap:is(lists:sort(KvNodes1), lists:sort(Nodes1 ++ Nodes2),
194            "All nodes were inserted (a)"),
195
196    PartitionedNodes2 = ?MOD:partition_nodes(Nodes3, [Root], Less),
197    KpNodes2 = ?MOD:insert_multiple(Vtree2, PartitionedNodes2, [Root]),
198    KpNode2 = vtree_modify:write_new_root(Vtree2, KpNodes2),
199    {Depths2, KvNodes2} = vtree_test_util:get_kvnodes(
200                            Fd, KpNode2#kp_node.childpointer),
201    etap:is(sets:size(sets:from_list(Depths2)), 1, "Tree is balanced (b)"),
202    etap:is(hd(Depths2), 2, "Tree has expected depth"),
203    etap:is(lists:sort(KvNodes2), lists:sort(Nodes1 ++ Nodes3),
204            "All nodes were inserted (b)"),
205
206    couch_file:close(Fd).
207
208
209test_insert_nodes() ->
210    etap:is(lists:sort(?MOD:insert_nodes([d], [a, b, c])), [a, b, c ,d],
211            "Single item got inserted"),
212    etap:is(lists:sort(?MOD:insert_nodes([d, e], [a, b, c])), [a, b, c, d, e],
213            "Two items got inserted"),
214    etap:is(lists:sort(?MOD:insert_nodes([d, e], [])), [d, e],
215            "Two items got inserted into empty list").
216
217
218test_partition_nodes() ->
219    Less = fun(A, B) -> A < B end,
220
221    Mbb1 = [{-700, -600}, {-30, -20}],
222    Mbb2 = [{-600, -500}, {-25, -10}],
223    Mbb3 = [{-550, -400}, {-10, 0}],
224    Mbb4 = [{-300, -200}, {0, 40}],
225    Mbb5 = [{-200, -150}, {30, 80}],
226
227    Mbb6 = [{-740, -720}, {-30, -25}],
228    Mbb7 = [{-600, -500}, {-20, -15}],
229    Mbb8 = [{-550, -450}, {-25, 10}],
230    Mbb9 = [{-150, -120}, {50, 60}],
231
232    Mbb10 = [{300, 500}, {500, 600}],
233    Mbb11 = [{-1000, 0}, {-50, 50}],
234
235    Mbb12 = [{5000, 9000}, {7000, 9000}],
236    Mbb13 = [{0, 1}, {100, 101}],
237    Mbb14 = [{-5000, -9000}, {-7000, -9000}],
238
239
240    KpNodes = [#kp_node{key=Mbb} || Mbb <- [Mbb1, Mbb2, Mbb3, Mbb4, Mbb5]],
241    ToPartition = [#kv_node{key=Mbb} || Mbb <- [Mbb7, Mbb9, Mbb8, Mbb6]],
242
243    Partitioned1 = ?MOD:partition_nodes(ToPartition, KpNodes, Less),
244    etap:is(lists:sort(lists:append(Partitioned1)),
245            lists:sort(ToPartition),
246            "All nodes were partitioned"),
247    etap:is(Partitioned1,
248            [[#kv_node{key=Mbb6}], [#kv_node{key=Mbb8}, #kv_node{key=Mbb7}],
249             [], [], [#kv_node{key=Mbb9}]],
250            "All nodes were correctly partitioned (a)"),
251    etap:is(?MOD:partition_nodes([#kv_node{key=Mbb8}], KpNodes, Less),
252            [[], [#kv_node{key=Mbb8}], [], [], []],
253            "One node was correctly partitioned"),
254
255    KpNodes2 = [#kp_node{key=Mbb} || Mbb <- [Mbb10, Mbb11]],
256    [H, Partitioned2] = ?MOD:partition_nodes(ToPartition, KpNodes2, Less),
257    etap:is(H, [], "All nodes were correctly partitioned (b1)"),
258    etap:is(lists:sort(Partitioned2), lists:sort(ToPartition),
259            "All nodes were correctly partitioned (b2)"),
260
261    KpNodes3 = [#kp_node{key=Mbb} || Mbb <- [Mbb12, Mbb13, Mbb14]],
262    Partitioned3 = ?MOD:partition_nodes(ToPartition, KpNodes3, Less),
263    etap:is(lists:nth(1, Partitioned3), [],
264            "All nodes were correctly partitioned (c1)"),
265    etap:is(lists:sort(lists:nth(2, Partitioned3)), lists:sort(ToPartition),
266            "All nodes were correctly partitioned (c2)"),
267    etap:is(lists:nth(1, Partitioned3), [],
268            "All nodes were correctly partitioned (c3)").
269
270
271test_add_to_nth() ->
272    ListOfLists = [[a, b], [c, d, e], [f, g], [h]],
273    etap:is(?MOD:add_to_nth(3, z, ListOfLists),
274            [[a, b], [c, d, e], [z, f, g], [h]],
275            "Element was added succesfully (a)"),
276    etap:is(?MOD:add_to_nth(1, y, ListOfLists),
277            [[y, a, b], [c, d, e], [f, g], [h]],
278            "Element was added succesfully (b)"),
279    etap:is(?MOD:add_to_nth(2, x, ListOfLists),
280            [[a, b], [x, c, d, e], [f, g], [h]],
281            "Element was added succesfully (c)"),
282    etap:is(?MOD:add_to_nth(4, w, ListOfLists),
283            [[a, b], [c, d, e], [f, g], [w, h]],
284            "Element was added succesfully (d)"),
285    try
286        ?MOD:add_to_nth(10, w, ListOfLists)
287    catch
288        error:badarg ->
289            etap:ok(true, "Error was thrown")
290    end.
291