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 "filemgr.h"
23 #include "filemgr_ops.h"
24 #include "btreeblock.h"
25 #include "btree.h"
26 #include "btree_kv.h"
27 #include "test.h"
28 
29 #include "memleak.h"
30 
print_btree(struct btree *btree, void *key, void *value)31 void print_btree(struct btree *btree, void *key, void *value)
32 {
33     fprintf(stderr, "(%" _F64 " %" _F64 ")", *(uint64_t*)key, *(uint64_t*)value);
34 }
35 
basic_test()36 void basic_test()
37 {
38     TEST_INIT();
39 
40     int ksize = 8;
41     int vsize = 8;
42     int nodesize = (ksize + vsize)*4 + sizeof(struct bnode);
43     int blocksize = nodesize * 2;
44     struct filemgr *file;
45     struct btreeblk_handle btree_handle;
46     struct btree btree;
47     struct filemgr_config config;
48     int i, r;
49     uint64_t k,v;
50     char *fname = (char *) "./btreeblock_testfile";
51 
52     r = system(SHELL_DEL" btreeblock_testfile");
53     (void)r;
54     memset(&config, 0, sizeof(config));
55     config.blocksize = blocksize;
56     config.ncacheblock = 0;
57     config.flag = 0x0;
58     config.options = FILEMGR_CREATE;
59     config.num_wal_shards = 8;
60     r = system(SHELL_DEL" btreeblock_testfile");
61     (void)r;
62     filemgr_open_result result = filemgr_open(fname, get_filemgr_ops(), &config, NULL);
63     file = result.file;
64     btreeblk_init(&btree_handle, file, nodesize);
65 
66     btree_init(&btree, (void*)&btree_handle, btreeblk_get_ops(),
67                btree_kv_get_ku64_vu64(), nodesize, ksize, vsize, 0x0, NULL);
68 
69     for (i=0;i<6;++i) {
70         k = i; v = i*10;
71         btree_insert(&btree, (void*)&k, (void*)&v);
72     }
73 
74     btree_print_node(&btree, print_btree);
75     //btree_operation_end(&btree);
76 
77     for (i=6;i<12;++i) {
78         k = i; v = i*10;
79         btree_insert(&btree, (void*)&k, (void*)&v);
80     }
81 
82     btree_print_node(&btree, print_btree);
83     btreeblk_end(&btree_handle);
84     //btree_operation_end(&btree);
85 
86     k = 4;
87     v = 44;
88     btree_insert(&btree, (void*)&k, (void*)&v);
89     btree_print_node(&btree, print_btree);
90     //btree_operation_end(&btree);
91 
92     btreeblk_end(&btree_handle);
93     filemgr_commit(file, true, NULL);
94 
95     k = 5;
96     v = 55;
97     btree_insert(&btree, (void*)&k, (void*)&v);
98     btree_print_node(&btree, print_btree);
99     //btree_operation_end(&btree);
100 
101     btreeblk_end(&btree_handle);
102     filemgr_commit(file, true, NULL);
103 
104     k = 5;
105     v = 59;
106     btree_insert(&btree, (void*)&k, (void*)&v);
107     btree_print_node(&btree, print_btree);
108     //btree_operation_end(&btree);
109 
110     btreeblk_end(&btree_handle);
111     filemgr_commit(file, true, NULL);
112 
113 
114     struct btree btree2;
115 
116     DBG("re-read using root bid %" _F64 "\n", btree.root_bid);
117     btree_init_from_bid(&btree2, (void*)&btree_handle, btreeblk_get_ops(),
118                         btree_kv_get_ku64_vu64(), nodesize, btree.root_bid);
119     btree_print_node(&btree2, print_btree);
120 
121     btreeblk_free(&btree_handle);
122 
123     filemgr_close(file, true, NULL, NULL);
124     filemgr_shutdown();
125 
126     TEST_RESULT("basic test");
127 }
128 
iterator_test()129 void iterator_test()
130 {
131     TEST_INIT();
132 
133     int ksize = 8;
134     int vsize = 8;
135     int nodesize = (ksize + vsize)*4 + sizeof(struct bnode);
136     int blocksize = nodesize * 2;
137     struct filemgr *file;
138     struct btreeblk_handle btree_handle;
139     struct btree btree;
140     struct btree_iterator bi;
141     struct filemgr_config config;
142     btree_result br;
143     int i, r;
144     uint64_t k,v;
145     char *fname = (char *) "./btreeblock_testfile";
146 
147     memset(&config, 0, sizeof(config));
148     config.blocksize = blocksize;
149     config.ncacheblock = 0;
150     config.flag = 0x0;
151     config.options = FILEMGR_CREATE;
152     config.num_wal_shards = 8;
153     r = system(SHELL_DEL" btreeblock_testfile");
154     (void)r;
155     filemgr_open_result result = filemgr_open(fname, get_filemgr_ops(), &config, NULL);
156     file = result.file;
157     btreeblk_init(&btree_handle, file, nodesize);
158 
159     btree_init(&btree, (void*)&btree_handle, btreeblk_get_ops(),
160                btree_kv_get_ku64_vu64(), nodesize, ksize, vsize, 0x0, NULL);
161 
162     for (i=0;i<6;++i) {
163         k = i*2; v = i*10;
164         btree_insert(&btree, (void*)&k, (void*)&v);
165     }
166 
167     btree_print_node(&btree, print_btree);
168     //btree_operation_end(&btree);
169 
170     for (i=6;i<12;++i) {
171         k = i*2; v = i*10;
172         btree_insert(&btree, (void*)&k, (void*)&v);
173     }
174 
175     btree_print_node(&btree, print_btree);
176     btreeblk_end(&btree_handle);
177     //btree_operation_end(&btree);
178 
179     filemgr_commit(file, true, NULL);
180 
181     k = 4;
182     btree_iterator_init(&btree, &bi, (void*)&k);
183     for (i=0;i<3;++i){
184         btree_next(&bi, (void*)&k, (void*)&v);
185         DBG("%" _F64 " , %" _F64 "\n", k, v);
186     }
187     btree_iterator_free(&bi);
188 
189     DBG("\n");
190     k = 7;
191     btree_iterator_init(&btree, &bi, (void*)&k);
192     for (i=0;i<3;++i){
193         btree_next(&bi, (void*)&k, (void*)&v);
194         DBG("%" _F64 " , %" _F64 "\n", k, v);
195     }
196     btree_iterator_free(&bi);
197 
198     DBG("\n");
199     btree_iterator_init(&btree, &bi, NULL);
200     for (i=0;i<30;++i){
201         br = btree_next(&bi, (void*)&k, (void*)&v);
202         if (br == BTREE_RESULT_FAIL) break;
203         DBG("%" _F64 " , %" _F64 "\n", k, v);
204     }
205     btree_iterator_free(&bi);
206 
207     filemgr_close(file, true, NULL, NULL);
208     filemgr_shutdown();
209 
210     TEST_RESULT("iterator test");
211 }
212 
213 
two_btree_test()214 void two_btree_test()
215 {
216     TEST_INIT();
217 
218     int i;
219     int nodesize = sizeof(struct bnode) + 16*4;
220     int blocksize = nodesize * 4;
221     struct filemgr *file;
222     struct btreeblk_handle btreeblk_handle;
223     struct btree btree_a, btree_b;
224     struct filemgr_config config;
225     uint64_t k,v;
226     char *fname = (char *) "./btreeblock_testfile";
227     int r = system(SHELL_DEL" btreeblock_testfile");
228     (void)r;
229 
230     memset(&config, 0, sizeof(config));
231     config.blocksize = blocksize;
232     config.ncacheblock = 1024;
233     config.options = FILEMGR_CREATE;
234     config.num_wal_shards = 8;
235     filemgr_open_result result = filemgr_open(fname, get_filemgr_ops(), &config, NULL);
236     file = result.file;
237     btreeblk_init(&btreeblk_handle, file, nodesize);
238 
239     btree_init(&btree_a, (void*)&btreeblk_handle, btreeblk_get_ops(),
240                btree_kv_get_ku64_vu64(), nodesize, 8, 8, 0x0, NULL);
241     btree_init(&btree_b, (void*)&btreeblk_handle, btreeblk_get_ops(),
242                btree_kv_get_ku64_vu64(), nodesize, 8, 8, 0x0, NULL);
243 
244     for (i=0;i<12;++i){
245         k = i*2; v = k * 10;
246         btree_insert(&btree_a, (void*)&k, (void*)&v);
247 
248         k = i*2 + 1; v = k*10 + 5;
249         btree_insert(&btree_b, (void*)&k, (void*)&v);
250     }
251 
252     filemgr_commit(file, true, NULL);
253     filemgr_close(file, true, NULL, NULL);
254     filemgr_shutdown();
255 
256     btree_print_node(&btree_a, print_btree);
257     btree_print_node(&btree_b, print_btree);
258 
259     TEST_RESULT("two btree test");
260 }
261 
range_test()262 void range_test()
263 {
264     TEST_INIT();
265 
266     int i, r, n=16, den=5;
267     int blocksize = 512;
268     struct filemgr *file;
269     struct btreeblk_handle bhandle;
270     struct btree btree;
271     struct filemgr_config fconfig;
272     uint64_t key, value, key_end;
273     char *fname = (char *) "./btreeblock_testfile";
274 
275     memset(&fconfig, 0, sizeof(fconfig));
276     fconfig.blocksize = blocksize;
277     fconfig.ncacheblock = 0;
278     fconfig.options = FILEMGR_CREATE;
279     fconfig.num_wal_shards = 8;
280 
281     r = system(SHELL_DEL" btreeblock_testfile");
282     (void)r;
283     filemgr_open_result result = filemgr_open(fname, get_filemgr_ops(), &fconfig, NULL);
284     file = result.file;
285     btreeblk_init(&bhandle, file, blocksize);
286 
287     btree_init(&btree, (void*)&bhandle, btreeblk_get_ops(), btree_kv_get_ku64_vu64(),
288                blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, NULL);
289 
290     for (i=0;i<n;++i){
291         key = i;
292         value = i*10;
293         btree_insert(&btree, (void*)&key, (void*)&value);
294         btreeblk_end(&bhandle);
295     }
296 
297     for (i=0;i<den;++i){
298         btree_get_key_range(&btree, i, den, (void*)&key, (void*)&key_end);
299         DBG("%d %d\n", (int)key, (int)key_end);
300     }
301 
302     btreeblk_free(&bhandle);
303     filemgr_close(file, true, NULL, NULL);
304     filemgr_shutdown();
305 
306     TEST_RESULT("range test");
307 }
308 
is_subblock(bid_t subbid)309 INLINE int is_subblock(bid_t subbid)
310 {
311     uint8_t flag;
312     flag = (subbid >> (8 * (sizeof(bid_t)-2))) & 0x00ff;
313     return flag;
314 }
315 
subbid2bid(bid_t subbid, size_t *subblock_no, size_t *idx, bid_t *bid)316 INLINE void subbid2bid(bid_t subbid, size_t *subblock_no, size_t *idx, bid_t *bid)
317 {
318     uint8_t flag;
319     flag = (subbid >> (8 * (sizeof(bid_t)-2))) & 0x00ff;
320     *subblock_no = flag >> 5;
321     // to distinguish subblock_no==0 to non-subblock
322     *subblock_no -= 1;
323     *idx = flag & (0x20 - 0x01);
324     *bid = ((bid_t)(subbid << 16)) >> 16;
325 }
326 
subblock_test()327 void subblock_test()
328 {
329     TEST_INIT();
330 
331     int i, j, k, r, nbtrees;
332     int nodesize;
333     int blocksize = 4096;
334     char *fname = (char *) "./btreeblock_testfile";
335     char keybuf[256], valuebuf[256], temp[256];
336     filemgr_open_result result;
337     btree_result br;
338     bid_t bid;
339     size_t subblock_no, idx;
340     struct filemgr *file;
341     struct btreeblk_handle bhandle;
342     struct btree_kv_ops *ops;
343     struct btree btree, btree_arr[64];
344     struct filemgr_config fconfig;
345     struct btree_meta meta;
346 
347     memset(&fconfig, 0, sizeof(fconfig));
348     fconfig.blocksize = blocksize;
349     fconfig.ncacheblock = 0;
350     fconfig.options = FILEMGR_CREATE;
351     fconfig.num_wal_shards = 8;
352     ops = btree_kv_get_kb64_vb64(NULL);
353 
354     // btree initialization using large metadata test
355     r = system(SHELL_DEL" btreeblock_testfile");
356     (void)r;
357     result = filemgr_open(fname, get_filemgr_ops(), &fconfig, NULL);
358     file = result.file;
359     meta.data = (void*)malloc(4096);
360 
361     meta.size = 120;
362     btreeblk_init(&bhandle, file, blocksize);
363     btree_init(&btree, (void*)&bhandle, btreeblk_get_ops(), ops,
364                blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, &meta);
365     TEST_CHK(is_subblock(btree.root_bid));
366     subbid2bid(btree.root_bid, &subblock_no, &idx, &bid);
367     TEST_CHK(subblock_no == 1);
368     btreeblk_free(&bhandle);
369 
370     meta.size = 250;
371     btreeblk_init(&bhandle, file, blocksize);
372     btree_init(&btree, (void*)&bhandle, btreeblk_get_ops(), ops,
373                blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, &meta);
374     TEST_CHK(is_subblock(btree.root_bid));
375     subbid2bid(btree.root_bid, &subblock_no, &idx, &bid);
376     TEST_CHK(subblock_no == 2);
377     btreeblk_free(&bhandle);
378 
379     meta.size = 510;
380     btreeblk_init(&bhandle, file, blocksize);
381     btree_init(&btree, (void*)&bhandle, btreeblk_get_ops(), ops,
382                blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, &meta);
383     TEST_CHK(is_subblock(btree.root_bid));
384     subbid2bid(btree.root_bid, &subblock_no, &idx, &bid);
385     TEST_CHK(subblock_no == 3);
386     btreeblk_free(&bhandle);
387 
388     meta.size = 1020;
389     btreeblk_init(&bhandle, file, blocksize);
390     btree_init(&btree, (void*)&bhandle, btreeblk_get_ops(), ops,
391                blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, &meta);
392     TEST_CHK(is_subblock(btree.root_bid));
393     subbid2bid(btree.root_bid, &subblock_no, &idx, &bid);
394     TEST_CHK(subblock_no == 4);
395     btreeblk_free(&bhandle);
396 
397     meta.size = 2040;
398     btreeblk_init(&bhandle, file, blocksize);
399     btree_init(&btree, (void*)&bhandle, btreeblk_get_ops(), ops,
400                blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, &meta);
401     TEST_CHK(!is_subblock(btree.root_bid));
402     btreeblk_free(&bhandle);
403 
404     meta.size = 4090;
405     btreeblk_init(&bhandle, file, blocksize);
406     br = btree_init(&btree, (void*)&bhandle, btreeblk_get_ops(), ops,
407                blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, &meta);
408     TEST_CHK(br == BTREE_RESULT_FAIL);
409 
410     btreeblk_free(&bhandle);
411     filemgr_close(file, true, NULL, NULL);
412     filemgr_shutdown();
413     free(meta.data);
414 
415     // coverage: enlarge case 1-1
416     r = system(SHELL_DEL" btreeblock_testfile");
417     (void)r;
418     result = filemgr_open(fname, get_filemgr_ops(), &fconfig, NULL);
419     file = result.file;
420     btreeblk_init(&bhandle, file, blocksize);
421     btree_init(&btree, (void*)&bhandle, btreeblk_get_ops(), ops,
422                blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, NULL);
423     for (i=0;i<256;++i){
424         sprintf(keybuf, "%08d", i);
425         sprintf(valuebuf, "%08x", i);
426         btree_insert(&btree, (void*)keybuf, (void*)valuebuf);
427         btreeblk_end(&bhandle);
428         for (j=0;j<=i;++j){
429             sprintf(keybuf, "%08d", j);
430             sprintf(valuebuf, "%08x", j);
431             btree_find(&btree, (void*)keybuf, (void*)temp);
432             btreeblk_end(&bhandle);
433             TEST_CHK(!memcmp(valuebuf, temp, strlen(valuebuf)));
434         }
435     }
436     btreeblk_free(&bhandle);
437     filemgr_close(file, true, NULL, NULL);
438     filemgr_shutdown();
439 
440     // coverage: enlarge case 1-2, move case 1
441     r = system(SHELL_DEL" btreeblock_testfile");
442     (void)r;
443     result = filemgr_open(fname, get_filemgr_ops(), &fconfig, NULL);
444     file = result.file;
445     btreeblk_init(&bhandle, file, blocksize);
446     btree_init(&btree, (void*)&bhandle, btreeblk_get_ops(), ops,
447                blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, NULL);
448     for (i=0;i<256;++i){
449         sprintf(keybuf, "%08d", i);
450         sprintf(valuebuf, "%08x", i);
451         btree_insert(&btree, (void*)keybuf, (void*)valuebuf);
452         btreeblk_end(&bhandle);
453         filemgr_commit(file, true, NULL);
454         for (j=0;j<=i;++j){
455             sprintf(keybuf, "%08d", j);
456             sprintf(valuebuf, "%08x", j);
457             btree_find(&btree, (void*)keybuf, (void*)temp);
458             btreeblk_end(&bhandle);
459             TEST_CHK(!memcmp(valuebuf, temp, strlen(valuebuf)));
460         }
461     }
462     btreeblk_free(&bhandle);
463     filemgr_close(file, true, NULL, NULL);
464     filemgr_shutdown();
465 
466     // coverage: enlarge case 1-1, 2-1, 2-2, 3-1
467     nbtrees = 2;
468     r = system(SHELL_DEL" btreeblock_testfile");
469     (void)r;
470     result = filemgr_open(fname, get_filemgr_ops(), &fconfig, NULL);
471     file = result.file;
472     btreeblk_init(&bhandle, file, blocksize);
473     for (i=0;i<nbtrees;++i){
474         btree_init(&btree_arr[i], (void*)&bhandle, btreeblk_get_ops(), ops,
475                    blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, NULL);
476     }
477     for (i=0;i<256;++i){
478         for (j=0;j<nbtrees;++j){
479             sprintf(keybuf, "%02d%06d", j, i);
480             sprintf(valuebuf, "%02d%06x", j, i);
481             btree_insert(&btree_arr[j], (void*)keybuf, (void*)valuebuf);
482             btreeblk_end(&bhandle);
483             for (k=0;k<=i;++k){
484                 sprintf(keybuf, "%02d%06d", j, k);
485                 sprintf(valuebuf, "%02d%06x", j, k);
486                 btree_find(&btree_arr[j], (void*)keybuf, (void*)temp);
487                 btreeblk_end(&bhandle);
488                 TEST_CHK(!memcmp(valuebuf, temp, strlen(valuebuf)));
489             }
490         }
491     }
492     btreeblk_free(&bhandle);
493     filemgr_close(file, true, NULL, NULL);
494     filemgr_shutdown();
495 
496     // coverage: enlarge case 1-2, 2-1, 3-1, move case 1, 2-1, 2-2
497     nbtrees = 2;
498     r = system(SHELL_DEL" btreeblock_testfile");
499     (void)r;
500     result = filemgr_open(fname, get_filemgr_ops(), &fconfig, NULL);
501     file = result.file;
502     btreeblk_init(&bhandle, file, blocksize);
503     for (i=0;i<nbtrees;++i){
504         btree_init(&btree_arr[i], (void*)&bhandle, btreeblk_get_ops(), ops,
505                    blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, NULL);
506     }
507     for (i=0;i<256;++i){
508         for (j=0;j<nbtrees;++j){
509             sprintf(keybuf, "%02d%06d", j, i);
510             sprintf(valuebuf, "%02d%06x", j, i);
511             btree_insert(&btree_arr[j], (void*)keybuf, (void*)valuebuf);
512             btreeblk_end(&bhandle);
513         }
514         filemgr_commit(file, true, NULL);
515         for (j=0;j<nbtrees;++j){
516             for (k=0;k<=i;++k){
517                 sprintf(keybuf, "%02d%06d", j, k);
518                 sprintf(valuebuf, "%02d%06x", j, k);
519                 btree_find(&btree_arr[j], (void*)keybuf, (void*)temp);
520                 btreeblk_end(&bhandle);
521                 TEST_CHK(!memcmp(valuebuf, temp, strlen(valuebuf)));
522             }
523         }
524     }
525     btreeblk_free(&bhandle);
526     filemgr_close(file, true, NULL, NULL);
527     filemgr_shutdown();
528 
529     // coverage: enlarge case 1-1, 2-1, 3-2, move case 1, 2-1
530     nbtrees = 7;
531     r = system(SHELL_DEL" btreeblock_testfile");
532     (void)r;
533     result = filemgr_open(fname, get_filemgr_ops(), &fconfig, NULL);
534     file = result.file;
535     btreeblk_init(&bhandle, file, blocksize);
536     for (i=0;i<nbtrees;++i){
537         btree_init(&btree_arr[i], (void*)&bhandle, btreeblk_get_ops(), ops,
538                    blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, NULL);
539     }
540     for (j=0;j<nbtrees;++j){
541         nodesize = 128 * (1<<j);
542         for (i=0;i<(nodesize-16)/16;++i){
543             sprintf(keybuf, "%02d%06d", j, i);
544             sprintf(valuebuf, "%02d%06x", j, i);
545             btree_insert(&btree_arr[j], (void*)keybuf, (void*)valuebuf);
546             btreeblk_end(&bhandle);
547         }
548         filemgr_commit(file, true, NULL);
549     }
550     btreeblk_free(&bhandle);
551     filemgr_close(file, true, NULL, NULL);
552     filemgr_shutdown();
553 
554     // coverage: enlarge case 1-1, 1-2, 2-1, 3-2, move case 1, 2-1
555     nbtrees = 7;
556     r = system(SHELL_DEL" btreeblock_testfile");
557     (void)r;
558     result = filemgr_open(fname, get_filemgr_ops(), &fconfig, NULL);
559     file = result.file;
560     btreeblk_init(&bhandle, file, blocksize);
561     for (i=0;i<nbtrees;++i){
562         btree_init(&btree_arr[i], (void*)&bhandle, btreeblk_get_ops(), ops,
563                    blocksize, sizeof(uint64_t), sizeof(uint64_t), 0x0, NULL);
564     }
565     for (j=0;j<nbtrees;++j){
566         nodesize = 128 * (1<<j);
567         for (i=0;i<(nodesize-16)/16;++i){
568             sprintf(keybuf, "%02d%06d", j, i);
569             sprintf(valuebuf, "%02d%06x", j, i);
570             btree_insert(&btree_arr[j], (void*)keybuf, (void*)valuebuf);
571             btreeblk_end(&bhandle);
572             filemgr_commit(file, true, NULL);
573         }
574     }
575     btreeblk_free(&bhandle);
576     filemgr_close(file, true, NULL, NULL);
577     filemgr_shutdown();
578 
579     free(ops);
580     TEST_RESULT("subblock test");
581 }
582 
btree_reverse_iterator_test()583 void btree_reverse_iterator_test()
584 {
585     TEST_INIT();
586 
587     int ksize = 8, vsize = 8, r, c;
588     int nodesize = 256;
589     struct filemgr *file;
590     struct btreeblk_handle bhandle;
591     struct btree btree;
592     struct btree_iterator bi;
593     struct filemgr_config config;
594     struct btree_kv_ops *kv_ops;
595     btree_result br;
596     filemgr_open_result fr;
597     uint64_t i;
598     uint64_t k,v;
599     char *fname = (char *) "./btreeblock_testfile";
600 
601     r = system(SHELL_DEL" btreeblock_testfile");
602     (void)r;
603 
604     memleak_start();
605 
606     memset(&config, 0, sizeof(config));
607     config.blocksize = nodesize;
608     config.options = FILEMGR_CREATE;
609     config.num_wal_shards = 8;
610     fr = filemgr_open(fname, get_filemgr_ops(), &config, NULL);
611     file = fr.file;
612 
613     btreeblk_init(&bhandle, file, nodesize);
614     kv_ops = btree_kv_get_kb64_vb64(NULL);
615     btree_init(&btree, (void*)&bhandle,
616                btreeblk_get_ops(), kv_ops,
617                nodesize, ksize, vsize, 0x0, NULL);
618 
619     for (i=10;i<40;++i) {
620         k = _endian_encode(i*0x10);
621         v = _endian_encode(i*0x100);
622         btree_insert(&btree, (void*)&k, (void*)&v);
623         btreeblk_end(&bhandle);
624     }
625 
626     c = 0;
627     btree_iterator_init(&btree, &bi, NULL);
628     while ((br=btree_next(&bi, &k, &v)) == BTREE_RESULT_SUCCESS) {
629         btreeblk_end(&bhandle);
630         k = _endian_decode(k);
631         v = _endian_decode(v);
632         TEST_CHK(k == (uint64_t)(c+10)*0x10);
633         TEST_CHK(v == (uint64_t)(c+10)*0x100);
634         c++;
635     }
636     btreeblk_end(&bhandle);
637     btree_iterator_free(&bi);
638     TEST_CHK(c == 30);
639 
640     c = 0;
641     i=10000;
642     k = _endian_encode(i);
643     btree_iterator_init(&btree, &bi, &k);
644     while ((br=btree_next(&bi, &k, &v)) == BTREE_RESULT_SUCCESS) {
645         btreeblk_end(&bhandle);
646         k = _endian_decode(k);
647         v = _endian_decode(v);
648     }
649     btreeblk_end(&bhandle);
650     btree_iterator_free(&bi);
651     TEST_CHK(c == 0);
652 
653     // reverse iteration with NULL initial key
654     c = 0;
655     btree_iterator_init(&btree, &bi, NULL);
656     while ((br=btree_prev(&bi, &k, &v)) == BTREE_RESULT_SUCCESS) {
657         btreeblk_end(&bhandle);
658         k = _endian_decode(k);
659         v = _endian_decode(v);
660     }
661     btreeblk_end(&bhandle);
662     btree_iterator_free(&bi);
663     TEST_CHK(c == 0);
664 
665     c = 0;
666     i=10000;
667     k = _endian_encode(i);
668     btree_iterator_init(&btree, &bi, &k);
669     while ((br=btree_prev(&bi, &k, &v)) == BTREE_RESULT_SUCCESS) {
670         btreeblk_end(&bhandle);
671         k = _endian_decode(k);
672         v = _endian_decode(v);
673         TEST_CHK(k == (uint64_t)(39-c)*0x10);
674         TEST_CHK(v == (uint64_t)(39-c)*0x100);
675         c++;
676     }
677     btreeblk_end(&bhandle);
678     btree_iterator_free(&bi);
679     TEST_CHK(c == 30);
680 
681     c = 0;
682     i=0x175;
683     k = _endian_encode(i);
684     btree_iterator_init(&btree, &bi, &k);
685     while ((br=btree_prev(&bi, &k, &v)) == BTREE_RESULT_SUCCESS) {
686         btreeblk_end(&bhandle);
687         k = _endian_decode(k);
688         v = _endian_decode(v);
689         TEST_CHK(k == (uint64_t)(0x17-c)*0x10);
690         TEST_CHK(v == (uint64_t)(0x17-c)*0x100);
691         c++;
692     }
693     btreeblk_end(&bhandle);
694     btree_iterator_free(&bi);
695     TEST_CHK(c == 14);
696 
697     c = 0xa0 - 0x10;
698     btree_iterator_init(&btree, &bi, NULL);
699     for (i=0;i<15;++i){
700         c += 0x10;
701         br = btree_next(&bi, &k, &v);
702         TEST_CHK(br == BTREE_RESULT_SUCCESS);
703         btreeblk_end(&bhandle);
704         k = _endian_decode(k);
705         v = _endian_decode(v);
706         TEST_CHK(k == (uint64_t)c);
707         TEST_CHK(v == (uint64_t)c*0x10);
708     }
709     for (i=0;i<7;++i){
710         c -= 0x10;
711         br = btree_prev(&bi, &k, &v);
712         TEST_CHK(br == BTREE_RESULT_SUCCESS);
713         btreeblk_end(&bhandle);
714         k = _endian_decode(k);
715         v = _endian_decode(v);
716         TEST_CHK(k == (uint64_t)c);
717         TEST_CHK(v == (uint64_t)c*0x10);
718     }
719     for (i=0;i<10;++i){
720         c += 0x10;
721         br = btree_next(&bi, &k, &v);
722         TEST_CHK(br == BTREE_RESULT_SUCCESS);
723         btreeblk_end(&bhandle);
724         k = _endian_decode(k);
725         v = _endian_decode(v);
726         TEST_CHK(k == (uint64_t)c);
727         TEST_CHK(v == (uint64_t)c*0x10);
728     }
729     for (i=0;i<17;++i){
730         c -= 0x10;
731         br = btree_prev(&bi, &k, &v);
732         TEST_CHK(br == BTREE_RESULT_SUCCESS);
733         btreeblk_end(&bhandle);
734         k = _endian_decode(k);
735         v = _endian_decode(v);
736         TEST_CHK(k == (uint64_t)c);
737         TEST_CHK(v == (uint64_t)c*0x10);
738     }
739     br = btree_prev(&bi, &k, &v);
740     btreeblk_end(&bhandle);
741     TEST_CHK(br == BTREE_RESULT_FAIL);
742 
743     btree_iterator_free(&bi);
744 
745     free(kv_ops);
746     btreeblk_free(&bhandle);
747     filemgr_close(file, true, NULL, NULL);
748     filemgr_shutdown();
749 
750     memleak_end();
751 
752     TEST_RESULT("btree reverse iterator test");
753 }
754 
main()755 int main()
756 {
757 #ifdef _MEMPOOL
758     mempool_init();
759 #endif
760 
761     basic_test();
762     iterator_test();
763     two_btree_test();
764     range_test();
765     subblock_test();
766     btree_reverse_iterator_test();
767 
768     return 0;
769 }
770