xref: /6.0.3/forestdb/tests/unit/btree_test.cc (revision 5a5f326f)
1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3  *     Copyright 2010 Couchbase, Inc
4  *
5  *   Licensed under the Apache License, Version 2.0 (the "License");
6  *   you may not use this file except in compliance with the License.
7  *   You may obtain a copy of 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,
13  *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *   See the License for the specific language governing permissions and
15  *   limitations under the License.
16  */
17 
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21 
22 #include "btree.h"
23 #include "btree_kv.h"
24 #include "test.h"
25 #include "blk_dummy.h"
26 
27 
print_btree(struct btree * btree,void * key,void * value)28 void print_btree(struct btree *btree, void *key, void *value)
29 {
30     DBG("(%"_F64" %"_F64")", *(uint64_t*)key, *(uint64_t*)value);
31 }
32 
getsetkv_test()33 void getsetkv_test()
34 {
35     TEST_INIT();
36 
37     int i;
38     int a,b,c;
39     struct btree btree;
40     struct bnode node;
41     struct btree_blk_ops *blk_ops;
42     struct btree_kv_ops *kv_ops;
43 
44     dummy_init(4096, 10);
45     blk_ops = dummy_get_ops();
46     kv_ops = btree_kv_get_ku64_vu64();
47 
48     btree_init(&btree, NULL, blk_ops, kv_ops, 4096, 4, 8, 0x0, NULL);
49 
50     node.data = (void *)malloc(4096);
51     node.kvsize = 0x88;
52 
53     // basic test
54     a = b = c = 0;
55     for (i=0;i<10;++i) {
56         a = i;
57         b += i;
58         btree.kv_ops->set_kv(&node, i, &a, &b);
59     }
60     for (i=0;i<10;++i) {
61         c += i;
62         btree.kv_ops->get_kv(&node, i, &a, &b);
63 
64         #ifdef __DEBUG
65             fprintf(stderr, "%d %d\n", a, b);
66         #endif
67 
68         TEST_CHK(a==i);
69         TEST_CHK(b==c);
70     }
71 
72     dummy_close();
73 
74     TEST_RESULT("get set kv test");
75 }
76 
basic_test()77 void basic_test()
78 {
79     TEST_INIT();
80 
81     btree_result r;
82     struct btree btree;
83     uint64_t a,b;
84     struct btree_blk_ops *blk_ops;
85     struct btree_kv_ops *kv_ops;
86 
87     dummy_init(sizeof(struct bnode) + 16*4, 10);
88     blk_ops = dummy_get_ops();
89     kv_ops = btree_kv_get_ku64_vu64();
90 
91     btree_init(&btree, NULL, blk_ops, kv_ops, sizeof(struct bnode) + 16*4, 8, 8, 0x0, NULL);
92 
93     a = b = 1;
94     r = btree_insert(&btree, &a, &b);
95     a = b = 2;
96     r = btree_insert(&btree, &a, &b);
97 
98     r = btree_find(&btree, &a, &b);
99     TEST_CHK(b==2);
100 
101     a = 1;
102     r = btree_find(&btree, &a, &b);
103     TEST_CHK(b==1);
104 
105     a = 3;
106     r = btree_find(&btree, &a, &b);
107     TEST_CHK(r==BTREE_RESULT_FAIL);
108 
109     // update value
110     a = 1; b = 99;
111     r = btree_insert(&btree, &a, &b);
112     TEST_CHK(r!=BTREE_RESULT_FAIL);
113     b = 0;
114     r = btree_find(&btree, &a, &b);
115     TEST_CHK(r!=BTREE_RESULT_FAIL && b==99);
116 
117     btree_print_node(&btree, print_btree);
118 
119     dummy_close();
120 
121     TEST_RESULT("basic test");
122 }
123 
split_test()124 void split_test()
125 {
126     TEST_INIT();
127 
128     struct btree btree;
129     btree_result r;
130     struct btree_blk_ops *blk_ops;
131     struct btree_kv_ops *kv_ops;
132     int i;
133     uint64_t a,b,c;
134 
135     dummy_init(sizeof(struct bnode) + 16*4, 100);
136     blk_ops = dummy_get_ops();
137     kv_ops = btree_kv_get_ku64_vu64();
138 
139     // maximum 4 kv-pairs per node
140     btree_init(&btree, NULL, blk_ops, kv_ops, sizeof(struct bnode) + 16*4, 8, 8, 0x0, NULL);
141 
142     for (i=10;i<17;++i){
143         a = i*2; b = i*10;
144         r = btree_insert(&btree, &a, &b);
145         TEST_CHK(r != BTREE_RESULT_FAIL);
146     }
147 
148     btree_print_node(&btree, print_btree);
149 
150     for (i=9;i>=5;--i) {
151         a = i*2; b = i*10;
152         r = btree_insert(&btree, &a, &b);
153         TEST_CHK(r != BTREE_RESULT_FAIL);
154     }
155 
156     btree_print_node(&btree, print_btree);
157 
158     a = 9; b=99;
159     r = btree_insert(&btree, &a, &b);
160 
161     btree_print_node(&btree, print_btree);
162 
163     for (i=5;i<17;++i){
164         a = i*2;
165         r = btree_find(&btree, &a, &b);
166         TEST_CHK(r != BTREE_RESULT_FAIL);
167         TEST_CHK(b == i*10);
168     }
169 
170     TEST_RESULT("split test");
171 }
172 
remove_test()173 void remove_test()
174 {
175     TEST_INIT();
176 
177     struct btree btree;
178     btree_result r;
179     struct btree_blk_ops *blk_ops;
180     struct btree_kv_ops *kv_ops;
181     int i;
182     uint64_t a,b,c;
183 
184     dummy_init(sizeof(struct bnode) + 16*4, 100);
185     blk_ops = dummy_get_ops();
186     kv_ops = btree_kv_get_ku64_vu64();
187 
188     // maximum 4 kv-pairs per node
189     btree_init(&btree, NULL, blk_ops, kv_ops, sizeof(struct bnode) + 16*4, 8, 8, 0x0, NULL);
190 
191     for (i=0;i<12;++i) {
192         a = i; b = i*10;
193         r = btree_insert(&btree, &a, &b);
194         TEST_CHK(r != BTREE_RESULT_FAIL);
195     }
196 
197     btree_print_node(&btree, print_btree);
198 
199     for (i=2;i<=5;++i){
200         a = i; b = i*10;
201         r = btree_remove(&btree, &a);
202         btree_print_node(&btree, print_btree);
203     }
204     for (i=0;i<2;++i) {
205         a = i; b = i*10;
206         r = btree_remove(&btree, &a);
207         btree_print_node(&btree, print_btree);
208     }
209 
210     for (i=0;i<=5;++i){
211         a = i;
212         r = btree_find(&btree, &a, &b);
213         TEST_CHK(r == BTREE_RESULT_FAIL);
214     }
215     for (i=6;i<12;++i){
216         a = i;
217         r = btree_find(&btree, &a, &b);
218         TEST_CHK(b == i*10);
219     }
220 
221     TEST_RESULT("remove test");
222 }
223 
flush_test()224 void flush_test()
225 {
226     TEST_INIT();
227 
228     struct btree btree;
229     btree_result r;
230     struct btree_blk_ops *blk_ops;
231     struct btree_kv_ops *kv_ops;
232     int i;
233     uint64_t a,b,c;
234 
235     dummy_init(sizeof(struct bnode) + 16*4, 100);
236     blk_ops = dummy_get_ops();
237     kv_ops = btree_kv_get_ku64_vu64();
238 
239     // maximum 4 kv-pairs per node
240     btree_init(&btree, NULL, blk_ops, kv_ops, sizeof(struct bnode) + 16*4, 8, 8, 0x0, NULL);
241 
242     for (i=0;i<12;++i){
243         a = i; b = i*10;
244         r = btree_insert(&btree, &a, &b);
245         TEST_CHK(r != BTREE_RESULT_FAIL);
246     }
247     dummy_flush();
248 
249     btree_print_node(&btree, print_btree);
250 
251     // update one entry and flush
252     a = 10; b = 99;
253     r = btree_insert(&btree, &a, &b);
254     dummy_flush();
255 
256     btree_print_node(&btree, print_btree);
257 
258     // update two entries and flush
259     a = 5; b=55;
260     r = btree_insert(&btree, &a, &b);
261     a = 3; b=33;
262     r = btree_insert(&btree, &a, &b);
263     dummy_flush();
264 
265     btree_print_node(&btree, print_btree);
266 
267     // remove one entry and flush
268     a = 0;
269     r = btree_remove(&btree, &a);
270     dummy_flush();
271     btree_print_node(&btree, print_btree);
272 
273     TEST_RESULT("flush test");
274 }
275 
metadata_test()276 void metadata_test()
277 {
278     TEST_INIT();
279 
280     struct btree btree;
281     btree_result r;
282     struct btree_blk_ops *blk_ops;
283     struct btree_kv_ops *kv_ops;
284     struct btree_meta meta, meta2;
285     uint8_t buf[1024];
286     char *prefix="testprefix";
287     int i;
288     uint64_t a,b,c;
289 
290     dummy_init(sizeof(struct bnode) + 16*4, 100);
291     blk_ops = dummy_get_ops();
292     kv_ops = btree_kv_get_ku64_vu64();
293 
294     // maximum 4 kv-pairs per node
295     meta.data = prefix;
296     meta.size = strlen(prefix);
297     btree_init(&btree, NULL, blk_ops, kv_ops, sizeof(struct bnode) + 16*4, 8, 8, 0x0, &meta);
298 
299     for (i=0;i<4;++i) {
300         a = i; b = i*10;
301         r = btree_insert(&btree, &a, &b);
302         if (i==2) btree_print_node(&btree, print_btree);
303     }
304     r = btree_find(&btree, &a, &c);
305 
306     TEST_CHK(c == b);
307 
308     btree_print_node(&btree, print_btree);
309 
310     meta2.size = btree_read_meta(&btree, buf);
311     TEST_CHK(meta2.size == meta.size);
312     TEST_CHK(!strncmp((char*)buf, prefix, strlen(prefix)));
313 
314     TEST_RESULT("metadata test");
315 }
316 
seqtree_test()317 void seqtree_test()
318 {
319     TEST_INIT();
320 
321     struct btree btree;
322     btree_result r;
323     struct btree_blk_ops *blk_ops;
324     struct btree_kv_ops *kv_ops;
325     int i;
326     uint64_t a,b,c;
327 
328     dummy_init(sizeof(struct bnode) + 16*4, 100);
329     blk_ops = dummy_get_ops();
330     kv_ops = btree_kv_get_ku64_vu64();
331 
332     // maximum 4 kv-pairs per node
333     btree_init(&btree, NULL, blk_ops, kv_ops, sizeof(struct bnode) + 16*4, 8, 8, BNODE_MASK_SEQTREE, NULL);
334 
335     for (i=0;i<17;++i){
336         a = i*2; b = i*10;
337         r = btree_insert(&btree, &a, &b);
338         TEST_CHK(r != BTREE_RESULT_FAIL);
339     }
340 
341     btree_print_node(&btree, print_btree);
342 
343     TEST_RESULT("split test");
344 }
345 
main()346 int main(){
347     getsetkv_test();
348     basic_test();
349     split_test();
350     remove_test();
351     flush_test();
352     metadata_test();
353     seqtree_test();
354 
355     return 0;
356 }
357