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 "hbtrie.h"
23 #include "test.h"
24 #include "btreeblock.h"
25 #include "docio.h"
26 #include "filemgr.h"
27 #include "filemgr_ops.h"
28 #include "common.h"
29 #include "list.h"
30 
_set_doc(struct docio_object *doc, char *key, char *meta, char *body)31 uint32_t _set_doc(struct docio_object *doc, char *key, char *meta, char *body)
32 {
33     strcpy((char*)doc->key, key);
34     doc->length.keylen = strlen((char*)doc->key);
35     strcpy((char*)doc->meta, meta);
36     doc->length.metalen = strlen((char*)doc->meta);
37     strcpy((char*)doc->body, body);
38     doc->length.bodylen = strlen((char*)doc->body);
39 
40     return sizeof(struct docio_length) + doc->length.keylen +
41            doc->length.metalen + doc->length.bodylen;
42 }
43 
_readkey_wrap(void *handle, uint64_t offset, void *buf)44 size_t _readkey_wrap(void *handle, uint64_t offset, void *buf)
45 {
46     keylen_t keylen;
47     offset = _endian_decode(offset);
48     docio_read_doc_key((struct docio_handle * )handle, offset, &keylen, buf);
49     return keylen;
50 }
51 
hbtrie_key_test()52 void hbtrie_key_test()
53 {
54     TEST_INIT();
55 
56     struct hbtrie trie;
57     int i,j;
58 
59     trie.chunksize = 4;
60 
61     const char *key[] = {"abc", "abcd", "abcde", "abcdef", "abcdefg", "abcdefgh"};
62     char buf[256];
63     int keylen;
64 
65     for (i=0;i<6;++i){
66         keylen = _hbtrie_reform_key(&trie, (void*)key[i], strlen(key[i]), (void*)buf);
67 
68         DBG("keylen: %2d , ", keylen);
69         for (j=0;j<keylen;++j) {
70             printf("%02x ", (uint8_t)buf[j]);
71         }
72         printf("\n");
73     }
74 
75     TEST_RESULT("hbtrie key test");
76 }
77 
_key_expand(char *key_ori, char *key_out, int rpt)78 void _key_expand(char *key_ori, char *key_out, int rpt)
79 {
80     size_t i;
81     for (i=0;i<strlen(key_ori);++i){
82         memset(key_out + i*rpt, *(key_ori + i), rpt-1);
83         memset(key_out + (i+1)*rpt - 1, '_', 1);
84     }
85     memset(key_out + i*rpt, 0, 1);
86 }
87 
basic_test()88 void basic_test()
89 {
90     TEST_INIT();
91 
92     int blocksize = 256;
93     struct btreeblk_handle bhandle;
94     struct docio_handle dhandle;
95     struct filemgr *file;
96     struct hbtrie trie;
97     struct docio_object doc;
98     struct filemgr_config config;
99     uint64_t offset, offset_old, _offset;
100     uint32_t docsize;
101     char keybuf[256], metabuf[256], bodybuf[256];
102     char dockey[256], meta[256], body[256];
103     uint8_t valuebuf[8];
104     hbtrie_result r;
105     struct hbtrie_iterator it;
106     size_t keylen;
107 
108     int i, n=7, rr;
109     char **key = alca(char*, n);
110     const char *key_ori[] = {"aaaa", "aaab", "aaac", "aba", "aaba", "bbbb", "aaac"};
111     for (i=0;i<n;++i) {
112         key[i] = alca(char, 256);
113     }
114 
115     rr = system(SHELL_DEL " hbtrie_testfile");
116     (void)rr;
117 
118     memset(&doc, 0, sizeof(struct docio_object));
119     doc.key = (void*)keybuf;
120     doc.meta = (void*)metabuf;
121     doc.body = (void*)bodybuf;
122 
123     memset(&config, 0, sizeof(config));
124     config.blocksize = blocksize;
125     config.ncacheblock = 0;
126     config.flag = 0x0;
127     config.options = FILEMGR_CREATE;
128     config.chunksize = sizeof(uint64_t);
129     config.num_wal_shards = 8;
130 
131     filemgr_open_result result = filemgr_open((char *) "./hbtrie_testfile",
132                                               get_filemgr_ops(), &config, NULL);
133     file = result.file;
134     docio_init(&dhandle, file, false);
135     btreeblk_init(&bhandle, file, blocksize);
136 
137     hbtrie_init(&trie, 8, 8, blocksize, BLK_NOT_FOUND,
138         (void*)&bhandle, btreeblk_get_ops(), (void*)&dhandle, _readkey_wrap);
139     for (i=0;i<n;++i){
140         _key_expand((char *) key_ori[i], key[i], 8);
141         sprintf(dockey, "%s", key[i]);
142         sprintf(meta, "metadata_%03d", i);
143         sprintf(body, "body_%03d", i);
144         docsize = _set_doc(&doc, dockey, meta, body);
145         TEST_CHK(docsize != 0);
146         offset = docio_append_doc(&dhandle, &doc, 0, 0);
147         _offset = _endian_encode(offset);
148         hbtrie_insert(&trie, (void*)key[i], strlen(key[i]),
149                       (void*)&_offset, (void*)&offset_old);
150         btreeblk_end(&bhandle);
151     }
152 
153     hbtrie_remove(&trie, (void*)key[0], strlen(key[0]));
154     btreeblk_end(&bhandle);
155 
156     filemgr_commit(file, true, NULL);
157 
158     for (i=0;i<n;++i) {
159         if (i!=2) {
160             r = hbtrie_find(&trie, (void*)key[i], strlen(key[i]), (void*)valuebuf);
161             if (i>0) {
162                 TEST_CHK(r != HBTRIE_RESULT_FAIL);
163 
164                 memcpy(&offset, valuebuf, 8);
165                 offset = _endian_decode(offset);
166                 docio_read_doc(&dhandle, offset, &doc, true);
167                 sprintf(meta, "metadata_%03d", i);
168                 sprintf(body, "body_%03d", i);
169                 TEST_CHK(!memcmp(doc.key, key[i], doc.length.keylen));
170                 TEST_CHK(!memcmp(doc.meta, meta, doc.length.metalen));
171                 TEST_CHK(!memcmp(doc.body, body, doc.length.bodylen));
172             }else{
173                 TEST_CHK(r == HBTRIE_RESULT_FAIL);
174             }
175         }
176     }
177 
178     DBG("trie root bid %" _F64 "\n", trie.root_bid);
179 
180     hbtrie_iterator_init(&trie, &it, NULL, 0);
181     while(1){
182         r = hbtrie_next(&it, (void*)keybuf, &keylen, (void*)&offset);
183         if (r==HBTRIE_RESULT_FAIL) break;
184         offset = _endian_decode(offset);
185         docio_read_doc(&dhandle, offset, &doc, true);
186         keybuf[keylen] = 0;
187         DBG("%s\n", keybuf);
188     }
189     hbtrie_iterator_free(&it);
190 
191     filemgr_close(file, true, NULL, NULL);
192     filemgr_shutdown();
193 
194     TEST_RESULT("basic test");
195 }
196 
_set_random_key(char *key, int len)197 void _set_random_key(char *key, int len)
198 {
199     key[len--] = 0;
200     do {
201         key[len] = '!' + random('~'-'!');
202     } while(len--);
203 }
204 
large_test()205 void large_test()
206 {
207     TEST_INIT();
208 
209     int blocksize = 4096 * 1;
210     struct btreeblk_handle bhandle;
211     struct docio_handle dhandle;
212     struct filemgr *file;
213     struct hbtrie trie;
214     struct docio_object doc;
215     struct filemgr_config config;
216     uint32_t docsize;
217     char keybuf[256], metabuf[256], bodybuf[256];
218     char dockey[256], meta[256], body[256];
219     uint8_t valuebuf[8];
220     hbtrie_result r;
221 
222     int i, k, n=100000, m=1, rr;
223     size_t keylen = 8;
224     char **key;
225     uint64_t *offset;
226     uint64_t _offset;
227 
228     key = (char **)malloc(sizeof(char*) * n);
229     offset = (uint64_t *)malloc(sizeof(uint64_t) * n);
230 
231     doc.key = (void*)keybuf;
232     doc.meta = (void*)metabuf;
233     doc.body = (void*)bodybuf;
234 
235     memset(&config, 0, sizeof(config));
236     config.blocksize = blocksize;
237     config.ncacheblock = 0 * 1024 * 128;
238     config.flag = 0;
239     config.options = FILEMGR_CREATE;
240     config.chunksize = sizeof(uint64_t);
241     config.num_wal_shards = 8;
242 
243     DBG("filemgr, bcache init .. \n");
244     rr = system(SHELL_DEL" hbtrie_testfile");
245     (void)rr;
246     filemgr_open_result result = filemgr_open((char *) "./hbtrie_testfile",
247                                               get_filemgr_ops(), &config, NULL);
248     file = result.file;
249     docio_init(&dhandle, file, false);
250     btreeblk_init(&bhandle, file, blocksize);
251 
252     hbtrie_init(&trie, 8, 8, blocksize, BLK_NOT_FOUND,
253         (void*)&bhandle, btreeblk_get_ops(), (void*)&dhandle, _readkey_wrap);
254     TEST_TIME();
255 
256     for (k=0;k<m;++k) {
257         DBG("doc append .. \n");
258         for (i=(n/m)*k;i<(n/m)*(k+1);++i){
259             key[i] = (char *)malloc(keylen+1);
260             _set_random_key(key[i], keylen);
261 
262             //DBG("%s\n", key[i]);
263             sprintf(dockey, "%s", key[i]);
264             sprintf(meta, "m");
265             sprintf(body, "body_%3d", i);
266             docsize = _set_doc(&doc, dockey, meta, body);
267             TEST_CHK(docsize != 0);
268             offset[i] = docio_append_doc(&dhandle, &doc, 0, 0);
269         }
270         TEST_TIME();
271 
272         DBG("hbtrie update .. \n");
273         for (i=(n/m)*k;i<(n/m)*(k+1);++i){
274             hbtrie_insert(&trie, (void*)key[i], strlen(key[i]),
275                           (void*)&offset[i], (void*)&_offset);
276             btreeblk_end(&bhandle);
277         }
278         TEST_TIME();
279 
280         DBG("filemgr commit .. \n");
281         filemgr_commit(file, true, NULL);
282         TEST_TIME();
283     }
284 
285     for (k=0;k<m;++k) {
286         DBG("doc append .. \n");
287         for (i=(n/m)*k;i<(n/m)*(k+1);++i){
288             sprintf(dockey, "%s", key[i]);
289             sprintf(meta, "me");
290             sprintf(body, "body2_%3d", i);
291             docsize = _set_doc(&doc, dockey, meta, body);
292             TEST_CHK(docsize != 0);
293             offset[i] = docio_append_doc(&dhandle, &doc, 0, 0);
294         }
295         TEST_TIME();
296 
297         DBG("hbtrie update .. \n");
298         for (i=(n/m)*k;i<(n/m)*(k+1);++i){
299             hbtrie_insert(&trie, (void*)key[i], strlen(key[i]),
300                           (void*)&offset[i], (void*)&_offset);
301             btreeblk_end(&bhandle);
302         }
303         TEST_TIME();
304 
305         DBG("filemgr commit .. \n");
306         filemgr_commit(file, true, NULL);
307         TEST_TIME();
308     }
309 
310     DBG("hbtrie search .. \n");
311     for (i=0;i<n;++i) {
312         //DBG("key %s\n", key[i]);
313         r = hbtrie_find(&trie, (void*)key[i], strlen(key[i]), (void*)valuebuf);
314         btreeblk_end(&bhandle);
315         TEST_CHK(r != HBTRIE_RESULT_FAIL);
316 
317         if (r != HBTRIE_RESULT_FAIL) {
318             memcpy(&_offset, valuebuf, 8);
319             docio_read_doc(&dhandle, _offset, &doc, true);
320 
321             sprintf(meta, "me");
322             sprintf(body, "body2_%3d", i);
323             TEST_CHK(!memcmp(doc.key, key[i], doc.length.keylen));
324             TEST_CHK(!memcmp(doc.meta, meta, doc.length.metalen));
325             TEST_CHK(!memcmp(doc.body, body, doc.length.bodylen));
326 
327         }
328     }
329     TEST_TIME();
330 
331     DBG("hbtrie iterator ..\n");
332     struct hbtrie_iterator it;
333     hbtrie_iterator_init(&trie, &it, NULL, 0);
334     for (i=0;i<n;++i){
335         r = hbtrie_next(&it, (void*)keybuf, &keylen, (void*)&_offset);
336         TEST_CHK(r != HBTRIE_RESULT_FAIL);
337         btreeblk_end(&bhandle);
338         docio_read_doc(&dhandle, _offset, &doc, true);
339         /*
340         keybuf[keylen] = 0;
341         DBG("%s\n", keybuf);*/
342     }
343     hbtrie_iterator_free(&it);
344 
345 
346     TEST_TIME();
347 
348     DBG("trie root bid %" _F64 "\n", trie.root_bid);
349 
350     filemgr_close(file, true, NULL, NULL);
351     filemgr_shutdown();
352 
353     TEST_RESULT("large test");
354 }
355 
356 char **_skew_key_ptr;
_readkey_wrap_memory(void *handle, uint64_t offset, void *buf)357 size_t _readkey_wrap_memory(void *handle, uint64_t offset, void *buf)
358 {
359     keylen_t keylen;
360     offset = _endian_decode(offset);
361     keylen = strlen(_skew_key_ptr[offset]);
362     memcpy(buf, _skew_key_ptr[offset], keylen);
363     return keylen;
364 }
365 
skew_basic_test()366 void skew_basic_test()
367 {
368     TEST_INIT();
369 
370     int blocksize = 256;
371     struct btreeblk_handle bhandle;
372     struct docio_handle dhandle;
373     struct filemgr *file;
374     struct hbtrie trie;
375     struct filemgr_config config;
376     uint8_t value_buf[8];
377     struct hbtrie_iterator it;
378     hbtrie_result hr;
379     size_t keylen;
380     uint64_t offset, _offset;
381 
382     memleak_start();
383 
384     int i, n=22, rr;
385     const char *key_const[] = {
386         "aaaaaaa_",
387         "aaaaaaa_aaaaaaa_",
388         "aaaaaaa_aaaaaaa_aaaaaaa_",
389         "bbbbbbb_",
390         "bbbbbbb_bbbbbbb_",
391         "bbbbbbb_bbbbccc_",
392         "ccccccc_",
393         "ccccccc_aaa",
394         "ccccccc_aa",
395         "dddddd_d",
396         //"dddddd_dddaddd_d",
397         "dddddd_ddddddd_d",
398         "dddddd_ddddddd_ddddddd_ddddaaa_",
399         "dddddd_ddddddd_dbddddb_",
400         "dddddd_ddddddd_dcddddc_",
401         "dddddd_ddddddd_ddddddd_ddddbbb_",
402         "dddddd_ddddddd_dedddde_temp1",
403         "dddddd_ddddddd_dfddddf_temp2",
404         "dddddd_ddddddd_dgddddg_temp3",
405         "dddddd_ddddddd_dhddddh_temp4",
406         "dddddd_ddddddd_diddddi_",
407         "dddddd_ddddddd_djddddj_",
408         "dddddd_ddddddd_dkddddk_",
409         };
410     char **key_cpy = alca(char *, n);
411     char key_buf[256];
412 
413     for (i=0;i<n;++i){
414         key_cpy[i] = alca(char, strlen(key_const[i])+1);
415         strcpy(key_cpy[i], key_const[i]);
416     }
417     _skew_key_ptr = key_cpy;
418 
419     rr = system(SHELL_DEL " hbtrie_testfile");
420     (void)rr;
421 
422     memset(&config, 0, sizeof(config));
423     config.blocksize = blocksize;
424     config.ncacheblock = 0;
425     config.flag = 0x0;
426     config.options = FILEMGR_CREATE;
427     config.chunksize = sizeof(uint64_t);
428     config.num_wal_shards = 8;
429 
430     filemgr_open_result result = filemgr_open((char*)"./hbtrie_testfile",
431                                               get_filemgr_ops(), &config, NULL);
432     file = result.file;
433     docio_init(&dhandle, file, false);
434     btreeblk_init(&bhandle, file, blocksize);
435 
436     hbtrie_init(&trie, 8, 8, blocksize, BLK_NOT_FOUND,
437         (void *)&bhandle, btreeblk_get_ops(), (void *)&dhandle, _readkey_wrap_memory);
438     hbtrie_set_flag(&trie, HBTRIE_FLAG_COMPACT);
439     hbtrie_set_leaf_height_limit(&trie, 1);
440 
441     for (i=0;i<n;++i){
442         offset = i;
443         _offset = _endian_encode(offset);
444         hbtrie_insert(&trie, (void *)key_cpy[i], strlen(key_cpy[i]),
445                       (void *)&_offset, (void *)value_buf);
446         btreeblk_end(&bhandle);
447     }
448 
449     // find all keys
450     for (i=0;i<n;++i){
451         hbtrie_find(&trie, (void *)key_cpy[i], strlen(key_cpy[i]),
452                     (void *)&offset);
453         btreeblk_end(&bhandle);
454         offset = _endian_decode(offset);
455         printf("%s\n", key_cpy[offset]);
456     }
457 
458     // range scan from the beginning
459     printf("\n");
460     hr = hbtrie_iterator_init(&trie, &it, NULL, 0);
461     while (hr == HBTRIE_RESULT_SUCCESS) {
462         hr = hbtrie_next(&it, (void *)key_buf, &keylen, (void *)&offset);
463         btreeblk_end(&bhandle);
464         if (hr != HBTRIE_RESULT_SUCCESS) break;
465         key_buf[keylen]=0;
466         printf("%s %d\n", key_buf, (int)keylen);
467     }
468     hbtrie_iterator_free(&it);
469 
470     // range scan from the middle
471     printf("\n");
472     sprintf(key_buf, "aaaaaaa_aaaaaaa_a");
473     hr = hbtrie_iterator_init(&trie, &it, (void*)key_buf, strlen(key_buf));
474     while (hr == HBTRIE_RESULT_SUCCESS) {
475         hr = hbtrie_next(&it, (void*)key_buf, &keylen, (void*)&offset);
476         btreeblk_end(&bhandle);
477         if (hr != HBTRIE_RESULT_SUCCESS) break;
478         key_buf[keylen]=0;
479         printf("%s %d\n", key_buf, (int)keylen);
480     }
481     hbtrie_iterator_free(&it);
482 
483     // remove metasection key
484     hr = hbtrie_remove(&trie, (void*)key_cpy[6], strlen(key_cpy[6]));
485     TEST_CHK(hr == HBTRIE_RESULT_SUCCESS);
486     btreeblk_end(&bhandle);
487     sprintf(key_buf, "aaaaaaa_a");  // not exist key
488     hr = hbtrie_remove(&trie, (void*)key_buf, strlen(key_buf));    // must fail
489     TEST_CHK(hr != HBTRIE_RESULT_SUCCESS);
490     btreeblk_end(&bhandle);
491     hr = hbtrie_remove(&trie, (void*)key_cpy[4], strlen(key_cpy[4]));
492     TEST_CHK(hr == HBTRIE_RESULT_SUCCESS);
493     btreeblk_end(&bhandle);
494 
495     // update metasection key
496     offset = 3;
497     _offset = _endian_encode(offset);
498     hr = hbtrie_insert(&trie, (void*)key_cpy[offset], strlen(key_cpy[offset]),
499                        (void*)&_offset, (void*)value_buf);
500     TEST_CHK(hr == HBTRIE_RESULT_SUCCESS);
501     btreeblk_end(&bhandle);
502 
503     char ff_str[8];
504     memset(ff_str, 0xff, 8);
505 
506     // update leaf tree key
507     offset = 1;
508     _offset = _endian_encode(offset);
509     hr = hbtrie_insert(&trie, (void*)key_cpy[offset], strlen(key_cpy[offset]),
510                        (void*)&_offset, (void*)value_buf);
511     TEST_CHK(hr == HBTRIE_RESULT_SUCCESS);
512     TEST_CHK(memcmp(value_buf, ff_str, 8)); // should not be 0xff..
513     btreeblk_end(&bhandle);
514 
515     // update normal tree key
516     offset = 16;
517     _offset = _endian_encode(offset);
518     hr = hbtrie_insert(&trie, (void*)key_cpy[offset], strlen(key_cpy[offset]),
519                        (void*)&_offset, (void*)value_buf);
520     TEST_CHK(hr == HBTRIE_RESULT_SUCCESS);
521     TEST_CHK(memcmp(value_buf, ff_str, 8)); // should not be 0xff..
522     btreeblk_end(&bhandle);
523 
524     // range scan from the beginning
525     printf("\n");
526     hr = hbtrie_iterator_init(&trie, &it, NULL, 0);
527     while (hr == HBTRIE_RESULT_SUCCESS) {
528         hr = hbtrie_next(&it, (void*)key_buf, &keylen, (void*)&offset);
529         btreeblk_end(&bhandle);
530         if (hr != HBTRIE_RESULT_SUCCESS) break;
531         key_buf[keylen]=0;
532         printf("%s %d\n", key_buf, (int)keylen);
533     }
534     hbtrie_iterator_free(&it);
535 
536     // range scan from the beginning (using wo key API)
537     printf("\n");
538     hr = hbtrie_iterator_init(&trie, &it, NULL, 0);
539     while (hr == HBTRIE_RESULT_SUCCESS) {
540         hr = hbtrie_next_value_only(&it, (void*)&offset);
541         btreeblk_end(&bhandle);
542         if (hr != HBTRIE_RESULT_SUCCESS) break;
543         key_buf[keylen]=0;
544         offset = _endian_decode(offset);
545         printf("%s %d\n", key_cpy[offset], (int)offset);
546     }
547     hbtrie_iterator_free(&it);
548 
549     filemgr_commit(file, true, NULL);
550 
551     hbtrie_free(&trie);
552     docio_free(&dhandle);
553     btreeblk_free(&bhandle);
554     filemgr_close(file, true, NULL, NULL);
555     filemgr_shutdown();
556 
557     memleak_end();
558 
559     TEST_RESULT("skew basic test");
560 }
561 
562 #define HB_KEYSTR "key%06d"
_readkey_wrap_memory_itr(void *handle, uint64_t offset, void *buf)563 size_t _readkey_wrap_memory_itr(void *handle, uint64_t offset, void *buf)
564 {
565     offset = _endian_decode(offset);
566     memset(buf, 0, 16);
567     sprintf((char*)buf, HB_KEYSTR, (int)offset);
568     return strlen((char*)buf);
569 }
570 
hbtrie_reverse_iterator_test()571 void hbtrie_reverse_iterator_test()
572 {
573     TEST_INIT();
574 
575     int ksize = 8, vsize = 8, r, n=30, c;
576     int nodesize = 256;
577     uint64_t i, v, v_out;
578     char key[256], key_temp[256];
579     size_t keylen;
580     struct filemgr *file;
581     struct btreeblk_handle bhandle;
582     struct hbtrie trie;
583     struct hbtrie_iterator hit;
584     struct filemgr_config config;
585     hbtrie_result hr;
586     filemgr_open_result fr;
587     char *fname = (char *) "./hbtrie_testfile";
588 
589     r = system(SHELL_DEL" hbtrie_testfile");
590     (void)r;
591     memleak_start();
592 
593     memset(&config, 0, sizeof(config));
594     config.blocksize = nodesize;
595     config.options = FILEMGR_CREATE;
596     config.chunksize = ksize;
597     config.num_wal_shards = 8;
598 
599     fr = filemgr_open(fname, get_filemgr_ops(), &config, NULL);
600     file = fr.file;
601 
602     btreeblk_init(&bhandle, file, nodesize);
603     hbtrie_init(&trie, ksize, vsize, nodesize, BLK_NOT_FOUND,
604         &bhandle, btreeblk_get_ops(), NULL, _readkey_wrap_memory_itr);
605 
606     for (i=0;i<(uint64_t)n;++i){
607         v = _endian_encode(i);
608         sprintf(key, HB_KEYSTR, (int)i);
609         hbtrie_insert(&trie, key, strlen(key), &v, &v_out);
610         btreeblk_end(&bhandle);
611     }
612 
613     c = 0;
614     hbtrie_iterator_init(&trie, &hit, NULL, 0);
615     while( (hr=hbtrie_next(&hit, key, &keylen, &v)) == HBTRIE_RESULT_SUCCESS) {
616         btreeblk_end(&bhandle);
617         v = _endian_decode(v);
618         sprintf(key_temp, HB_KEYSTR, (int)c);
619         TEST_CHK(!memcmp(key, key_temp, keylen));
620         TEST_CHK(v == (uint64_t)c);
621         c++;
622     }
623     btreeblk_end(&bhandle);
624     hbtrie_iterator_free(&hit);
625     TEST_CHK(c == n);
626 
627     c = 0;
628     hbtrie_iterator_init(&trie, &hit, NULL, 0);
629     while(1) {
630         hr=hbtrie_prev(&hit, key, &keylen, &v);
631         btreeblk_end(&bhandle);
632         if (hr != HBTRIE_RESULT_SUCCESS) break;
633         v = _endian_decode(v);
634         c++;
635     }
636     btreeblk_end(&bhandle);
637     hbtrie_iterator_free(&hit);
638     TEST_CHK(c == 0);
639 
640     c = 0;
641     sprintf(key, HB_KEYSTR, (int)n*2);
642     hbtrie_iterator_init(&trie, &hit, key, strlen(key));
643     while(1) {
644         hr=hbtrie_prev(&hit, key, &keylen, &v);
645         btreeblk_end(&bhandle);
646         if (hr != HBTRIE_RESULT_SUCCESS) break;
647         v = _endian_decode(v);
648         sprintf(key_temp, HB_KEYSTR, (int)(n-c-1));
649         TEST_CHK(!memcmp(key, key_temp, keylen));
650         TEST_CHK(v == (uint64_t)n-c-1);
651         c++;
652     }
653     btreeblk_end(&bhandle);
654     hbtrie_iterator_free(&hit);
655     TEST_CHK(c == n);
656 
657     c = 0;
658     sprintf(key, HB_KEYSTR"xx", (int)n/2);
659     hbtrie_iterator_init(&trie, &hit, key, strlen(key));
660     while(1) {
661         hr=hbtrie_prev(&hit, key, &keylen, &v);
662         btreeblk_end(&bhandle);
663         if (hr != HBTRIE_RESULT_SUCCESS) break;
664         v = _endian_decode(v);
665         sprintf(key_temp, HB_KEYSTR, (int)((n/2)-c));
666         TEST_CHK(!memcmp(key, key_temp, keylen));
667         TEST_CHK(v == (uint64_t)(n/2)-c);
668         c++;
669     }
670     btreeblk_end(&bhandle);
671     hbtrie_iterator_free(&hit);
672     TEST_CHK(c == (n/2)+1);
673 
674     c = -1;
675     hbtrie_iterator_init(&trie, &hit, NULL, 0);
676     for (i=0;i<21;++i){
677         c++;
678         hr=hbtrie_next(&hit, key, &keylen, &v);
679         TEST_CHK(hr != HBTRIE_RESULT_FAIL);
680         btreeblk_end(&bhandle);
681         v = _endian_decode(v);
682         sprintf(key_temp, HB_KEYSTR, (int)c);
683         TEST_CHK(!memcmp(key, key_temp, keylen));
684         TEST_CHK(v == (uint64_t)c);
685     }
686     for (i=0;i<10;++i){
687         c--;
688         hr=hbtrie_prev(&hit, key, &keylen, &v);
689         TEST_CHK(hr != HBTRIE_RESULT_FAIL);
690         btreeblk_end(&bhandle);
691         v = _endian_decode(v);
692         sprintf(key_temp, HB_KEYSTR, (int)c);
693         TEST_CHK(!memcmp(key, key_temp, keylen));
694         TEST_CHK(v == (uint64_t)c);
695     }
696     for (i=0;i<19;++i){
697         c++;
698         hr=hbtrie_next(&hit, key, &keylen, &v);
699         TEST_CHK(hr != HBTRIE_RESULT_FAIL);
700         btreeblk_end(&bhandle);
701         v = _endian_decode(v);
702         sprintf(key_temp, HB_KEYSTR, (int)c);
703         TEST_CHK(!memcmp(key, key_temp, keylen));
704         TEST_CHK(v == (uint64_t)c);
705     }
706     hr=hbtrie_next(&hit, key, &keylen, &v);
707     btreeblk_end(&bhandle);
708     TEST_CHK(hr == HBTRIE_RESULT_FAIL);
709     hbtrie_iterator_free(&hit);
710 
711     hbtrie_free(&trie);
712     btreeblk_free(&bhandle);
713     filemgr_close(file, true, NULL, NULL);
714     filemgr_shutdown();
715     memleak_end();
716 
717     TEST_RESULT("HB+trie reverse iterator test");
718 }
719 
_key_wrap_partial_update(void *handle, uint64_t offset, void *buf)720 size_t _key_wrap_partial_update(void *handle, uint64_t offset, void *buf)
721 {
722     char keystr[] = "key%05d%08d%08d";
723     offset = _endian_decode(offset);
724     offset = offset % 100; // to handle same key different value
725     memset(buf, 0, strlen(keystr)+1);
726     sprintf((char*)buf, keystr, (int)(offset/9), (int)((offset/3)%3), (int)(offset%3));
727     return strlen((char*)buf);
728 }
729 
hbtrie_partial_update_test()730 void hbtrie_partial_update_test()
731 {
732     TEST_INIT();
733 
734     int ksize = 8, vsize = 8, r, n=27;
735     int nodesize = 256;
736     uint64_t i, v, v_out;
737     uint64_t v1[3], v2[9];
738     char key[256];
739     char keystr[] = "key%05d%08d%08d";
740     struct filemgr *file;
741     struct btreeblk_handle bhandle;
742     struct hbtrie trie;
743     struct filemgr_config config;
744     hbtrie_result hr;
745     filemgr_open_result fr;
746     char *fname = (char *) "./hbtrie_testfile";
747 
748     memleak_start();
749 
750     r = system(SHELL_DEL" hbtrie_testfile");
751     (void)r;
752 
753     memset(&config, 0, sizeof(config));
754     config.blocksize = nodesize;
755     config.options = FILEMGR_CREATE;
756     config.chunksize = ksize;
757     config.num_wal_shards = 8;
758 
759     fr = filemgr_open(fname, get_filemgr_ops(), &config, NULL);
760     file = fr.file;
761 
762     btreeblk_init(&bhandle, file, nodesize);
763     hbtrie_init(&trie, ksize, vsize, nodesize, BLK_NOT_FOUND,
764         &bhandle, btreeblk_get_ops(), NULL, _key_wrap_partial_update);
765 
766     for (i=0;i<(uint64_t)n;++i) {
767         v = _endian_encode(i);
768         sprintf(key, keystr, (int)(i/9), (int)((i/3)%3), (int)(i%3));
769         hbtrie_insert(&trie, key, strlen(key), &v, &v_out);
770         btreeblk_end(&bhandle);
771     }
772     filemgr_commit(file, true, NULL);
773     //printf("root: %lx\n", trie.root_bid);
774 
775     // retrieve check
776     for (i=0;i<(uint64_t)n;++i) {
777         sprintf(key, keystr, (int)(i/9), (int)((i/3)%3), (int)(i%3));
778         hbtrie_find(&trie, key, strlen(key), &v);
779         btreeblk_end(&bhandle);
780         v = _endian_decode(v);
781         TEST_CHK(v == i);
782     }
783 
784     // retrieve partial key & temporarily save
785     for (i=0;i<3;++i){
786         sprintf(key, "key%05d", (int)i);
787         hbtrie_find_partial(&trie, key, strlen(key), &v);
788         btreeblk_end(&bhandle);
789         v1[i] = v;
790         v = _endian_decode(v);
791     }
792     for (i=0;i<9;++i){
793         sprintf(key, "key%05d%08d", (int)(i/3), (int)(i%3));
794         hbtrie_find_partial(&trie, key, strlen(key), &v);
795         btreeblk_end(&bhandle);
796         v2[i] = v;
797         v = _endian_decode(v);
798     }
799 
800     // update: using value + 100 (will point to same key)
801     for (i=0;i<(uint64_t)n;++i) {
802         v = _endian_encode(i+100);
803         sprintf(key, keystr, (int)(i/9), (int)((i/3)%3), (int)(i%3));
804         hbtrie_insert(&trie, key, strlen(key), &v, &v_out);
805         btreeblk_end(&bhandle);
806     }
807     filemgr_commit(file, true, NULL);
808 
809     // replace the first-level chunks by old values
810     for (i=0;i<3;++i){
811         sprintf(key, "key%05d", (int)i);
812         hbtrie_insert_partial(&trie, key, strlen(key), &v1[i], &v_out);
813         btreeblk_end(&bhandle);
814     }
815     filemgr_commit(file, true, NULL);
816 
817     // retrieve check
818     for (i=0;i<(uint64_t)n;++i) {
819         sprintf(key, keystr, (int)(i/9), (int)((i/3)%3), (int)(i%3));
820         hbtrie_find(&trie, key, strlen(key), &v);
821         btreeblk_end(&bhandle);
822         v = _endian_decode(v);
823         TEST_CHK(v == i);
824     }
825 
826     // update again: using value + 200 (will point to same key)
827     for (i=0;i<(uint64_t)n;++i) {
828         v = _endian_encode(i+200);
829         sprintf(key, keystr, (int)(i/9), (int)((i/3)%3), (int)(i%3));
830         hbtrie_insert(&trie, key, strlen(key), &v, &v_out);
831         btreeblk_end(&bhandle);
832     }
833     filemgr_commit(file, true, NULL);
834 
835     // replace the second-level chunks by old values
836     for (i=0;i<9;++i){
837         sprintf(key, "key%05d%08d", (int)(i/3), (int)(i%3));
838         hbtrie_insert_partial(&trie, key, strlen(key), &v2[i], &v_out);
839         btreeblk_end(&bhandle);
840     }
841     filemgr_commit(file, true, NULL);
842 
843     // retrieve check
844     for (i=0;i<(uint64_t)n;++i) {
845         sprintf(key, keystr, (int)(i/9), (int)((i/3)%3), (int)(i%3));
846         hbtrie_find(&trie, key, strlen(key), &v);
847         btreeblk_end(&bhandle);
848         v = _endian_decode(v);
849         TEST_CHK(v == i);
850     }
851 
852     // partially remove
853     i = 1;
854     sprintf(key, "key%05d%08d", (int)(i/3), (int)(i%3));
855     hbtrie_remove_partial(&trie, key, strlen(key));
856     btreeblk_end(&bhandle);
857 
858     i = 1;
859     sprintf(key, "key%05d", (int)i);
860     hbtrie_remove_partial(&trie, key, strlen(key));
861     btreeblk_end(&bhandle);
862     filemgr_commit(file, true, NULL);
863 
864     // retrieve check
865     for (i=0;i<(uint64_t)n;++i) {
866         sprintf(key, keystr, (int)(i/9), (int)((i/3)%3), (int)(i%3));
867         hr = hbtrie_find(&trie, key, strlen(key), &v);
868         btreeblk_end(&bhandle);
869         v = _endian_decode(v);
870 
871         if ( ((i/9) == 0 && ((i/3)%3) == 1) ||
872               (i/9) == 1) {
873             TEST_CHK(hr != HBTRIE_RESULT_SUCCESS);
874         } else {
875             TEST_CHK(hr == HBTRIE_RESULT_SUCCESS);
876         }
877     }
878 
879     hbtrie_free(&trie);
880     btreeblk_free(&bhandle);
881     filemgr_close(file, true, NULL, NULL);
882     filemgr_shutdown();
883     memleak_end();
884 
885     TEST_RESULT("HB+trie partial update test");
886 }
887 
main()888 int main(){
889 #ifdef _MEMPOOL
890     mempool_init();
891 #endif
892 
893     //hbtrie_key_test();
894     basic_test();
895     skew_basic_test();
896     hbtrie_reverse_iterator_test();
897     hbtrie_partial_update_test();
898     //large_test();
899 
900     return 0;
901 }
902