1 /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 // vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3 #ident "$Id$"
4 /*======
5 This file is part of PerconaFT.
6
7
8 Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22 ----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35 ======= */
36
37 #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39 #include "test.h"
40
41 #include <util/dmt.h>
42
43 typedef void *DMTVALUE;
44
45 class dmtvalue_writer {
tdiff(struct timeval * start,struct timeval * end)46 public:
47 size_t get_size(void) const {
48 return sizeof(DMTVALUE);
49 }
test_compress_buf_method(unsigned char * buf,int i,enum toku_compression_method m)50 void write_to(DMTVALUE *const dest) const {
51 *dest = value;
52 }
53
54 dmtvalue_writer(DMTVALUE _value)
55 : value(_value) {
56 }
57 dmtvalue_writer(const uint32_t size UU(), DMTVALUE *const src)
58 : value(*src) {
59 paranoid_invariant(size == sizeof(DMTVALUE));
60 }
61 private:
62 const DMTVALUE value;
test_compress_i(int i,enum toku_compression_method m,uLongf * compress_size,uLongf * uncompress_size)63 };
64
65 typedef toku::dmt<DMTVALUE, DMTVALUE, dmtvalue_writer> *DMT;
66
67 static int dmt_insert_at(DMT dmt, DMTVALUE value, uint32_t index) {
68 dmtvalue_writer functor(value);
69 return dmt->insert_at(functor, index);
70 }
71
72 static DMT dmt_create_from_sorted_array(DMTVALUE *values, uint32_t numvalues) {
73 DMT XMALLOC(dmt);
74 dmt->create();
75 for (uint32_t i = 0; i < numvalues; i++) {
76 dmt_insert_at(dmt, values[i], i);
77 }
78 return dmt;
79 }
test_compress(enum toku_compression_method m,uLongf * compress_size,uLongf * uncompress_size)80
81 struct heftor {
82 int (*h)(DMTVALUE, void *v);
83 void *v;
84 };
85
86 int call_heftor(const uint32_t size, const DMTVALUE &v, const heftor &htor);
87 int call_heftor(const uint32_t size, const DMTVALUE &v, const heftor &htor) {
88 invariant(size == sizeof(DMTVALUE));
89 return htor.h(const_cast<DMTVALUE>(v), htor.v);
test_compress_methods()90 }
91
92 static int dmt_insert(DMT dmt, DMTVALUE value, int(*h)(DMTVALUE, void*v), void *v, uint32_t *index) {
93 struct heftor htor = { .h = h, .v = v };
94 dmtvalue_writer functor(value);
95 return dmt->insert<heftor, call_heftor>(functor, htor, index);
96 }
97
98 static int dmt_find_zero(DMT V, int (*h)(DMTVALUE, void*extra), void*extra, DMTVALUE *value, uint32_t *index) {
99 struct heftor htor = { .h = h, .v = extra };
100 uint32_t ignore;
101 return V->find_zero<heftor, call_heftor>(htor, &ignore, value, index);
102 }
103
104 static int dmt_find(DMT V, int (*h)(DMTVALUE, void*extra), void*extra, int direction, DMTVALUE *value, uint32_t *index) {
105 struct heftor htor = { .h = h, .v = extra };
106 uint32_t ignore;
107 return V->find<heftor, call_heftor>(htor, direction, &ignore, value, index);
108 }
109
110 static int dmt_split_at(DMT dmt, DMT *newdmtp, uint32_t index) {
111 if (index > dmt->size()) { return EINVAL; }
112 DMT XMALLOC(newdmt);
113 newdmt->create();
114 int r;
115
116 for (uint32_t i = index; i < dmt->size(); i++) {
117 DMTVALUE v;
118 r = dmt->fetch(i, nullptr, &v);
119 invariant_zero(r);
120 r = dmt_insert_at(newdmt, v, i-index);
121 invariant_zero(r);
122 }
123 if (dmt->size() > 0) {
124 for (uint32_t i = dmt->size(); i > index; i--) {
125 r = dmt->delete_at(i - 1);
126 invariant_zero(r);
127 }
128 }
129 r = 0;
130
131 if (r != 0) {
132 toku_free(newdmt);
133 } else {
134 *newdmtp = newdmt;
135 }
136 return r;
137 }
138
test_main(int argc,const char * argv[])139 static void
140 parse_args (int argc, const char *argv[]) {
141 const char *argv0=argv[0];
142 while (argc>1) {
143 int resultcode=0;
144 if (strcmp(argv[1], "-v")==0) {
145 verbose++;
146 } else if (strcmp(argv[1], "-q")==0) {
147 verbose = 0;
148 } else if (strcmp(argv[1], "-h")==0) {
149 do_usage:
150 fprintf(stderr, "Usage:\n%s [-v|-h]\n", argv0);
151 exit(resultcode);
152 } else {
153 resultcode=1;
154 goto do_usage;
155 }
156 argc--;
157 argv++;
158 }
159 }
160 /* End ".h like" stuff. */
161
162 struct value {
163 uint32_t number;
164 };
165 #define V(x) ((struct value *)(x))
166
167 enum rand_type {
168 TEST_RANDOM,
169 TEST_SORTED,
170 TEST_IDENTITY
171 };
172 enum close_when_done {
173 CLOSE_WHEN_DONE,
174 KEEP_WHEN_DONE
175 };
176 enum create_type {
177 BATCH_INSERT,
178 INSERT_AT,
179 INSERT_AT_ALMOST_RANDOM,
180 };
181
182 /* Globals */
183 DMT global_dmt;
184 DMTVALUE* values = nullptr;
185 struct value* nums = nullptr;
186 uint32_t length;
187
188 static void
189 cleanup_globals (void) {
190 assert(values);
191 toku_free(values);
192 values = nullptr;
193 assert(nums);
194 toku_free(nums);
195 nums = nullptr;
196 }
197
198 const unsigned int random_seed = 0xFEADACBA;
199
200 static void
201 init_init_values (unsigned int seed, uint32_t num_elements) {
202 srandom(seed);
203
204 cleanup_globals();
205
206 MALLOC_N(num_elements, values);
207 assert(values);
208 MALLOC_N(num_elements, nums);
209 assert(nums);
210 length = num_elements;
211 }
212
213 static void
214 init_identity_values (unsigned int seed, uint32_t num_elements) {
215 uint32_t i;
216
217 init_init_values(seed, num_elements);
218
219 for (i = 0; i < length; i++) {
220 nums[i].number = i;
221 values[i] = (DMTVALUE)&nums[i];
222 }
223 }
224
225 static void
226 init_distinct_sorted_values (unsigned int seed, uint32_t num_elements) {
227 uint32_t i;
228
229 init_init_values(seed, num_elements);
230
231 uint32_t number = 0;
232
233 for (i = 0; i < length; i++) {
234 number += (uint32_t)(random() % 32) + 1;
235 nums[i].number = number;
236 values[i] = (DMTVALUE)&nums[i];
237 }
238 }
239
240 static void
241 init_distinct_random_values (unsigned int seed, uint32_t num_elements) {
242 init_distinct_sorted_values(seed, num_elements);
243
244 uint32_t i;
245 uint32_t choice;
246 uint32_t choices;
247 struct value temp;
248 for (i = 0; i < length - 1; i++) {
249 choices = length - i;
250 choice = random() % choices;
251 if (choice != i) {
252 temp = nums[i];
253 nums[i] = nums[choice];
254 nums[choice] = temp;
255 }
256 }
257 }
258
259 static void
260 init_globals (void) {
261 MALLOC_N(1, values);
262 assert(values);
263 MALLOC_N(1, nums);
264 assert(nums);
265 length = 1;
266 }
267
268 static void
269 test_close (enum close_when_done do_close) {
270 if (do_close == KEEP_WHEN_DONE) return;
271 assert(do_close == CLOSE_WHEN_DONE);
272 global_dmt->destroy();
273 toku_free(global_dmt);
274 global_dmt = nullptr;
275 }
276
277 static void
278 test_create (enum close_when_done do_close) {
279 XMALLOC(global_dmt);
280 global_dmt->create();
281 test_close(do_close);
282 }
283
284 static void
285 test_create_size (enum close_when_done do_close) {
286 test_create(KEEP_WHEN_DONE);
287 assert(global_dmt->size() == 0);
288 test_close(do_close);
289 }
290
291 static void
292 test_create_insert_at_almost_random (enum close_when_done do_close) {
293 uint32_t i;
294 int r;
295 uint32_t size = 0;
296
297 test_create(KEEP_WHEN_DONE);
298 r = dmt_insert_at(global_dmt, values[0], global_dmt->size()+1);
299 CKERR2(r, EINVAL);
300 r = dmt_insert_at(global_dmt, values[0], global_dmt->size()+2);
301 CKERR2(r, EINVAL);
302 for (i = 0; i < length/2; i++) {
303 assert(size==global_dmt->size());
304 r = dmt_insert_at(global_dmt, values[i], i);
305 CKERR(r);
306 assert(++size==global_dmt->size());
307 r = dmt_insert_at(global_dmt, values[length-1-i], i+1);
308 CKERR(r);
309 assert(++size==global_dmt->size());
310 }
311 r = dmt_insert_at(global_dmt, values[0], global_dmt->size()+1);
312 CKERR2(r, EINVAL);
313 r = dmt_insert_at(global_dmt, values[0], global_dmt->size()+2);
314 CKERR2(r, EINVAL);
315 assert(size==global_dmt->size());
316 test_close(do_close);
317 }
318
319 static void
320 test_create_insert_at_sequential (enum close_when_done do_close) {
321 uint32_t i;
322 int r;
323 uint32_t size = 0;
324
325 test_create(KEEP_WHEN_DONE);
326 r = dmt_insert_at(global_dmt, values[0], global_dmt->size()+1);
327 CKERR2(r, EINVAL);
328 r = dmt_insert_at(global_dmt, values[0], global_dmt->size()+2);
329 CKERR2(r, EINVAL);
330 for (i = 0; i < length; i++) {
331 assert(size==global_dmt->size());
332 r = dmt_insert_at(global_dmt, values[i], i);
333 CKERR(r);
334 assert(++size==global_dmt->size());
335 }
336 r = dmt_insert_at(global_dmt, values[0], global_dmt->size()+1);
337 CKERR2(r, EINVAL);
338 r = dmt_insert_at(global_dmt, values[0], global_dmt->size()+2);
339 CKERR2(r, EINVAL);
340 assert(size==global_dmt->size());
341 test_close(do_close);
342 }
343
344 static void
345 test_create_from_sorted_array (enum create_type create_choice, enum close_when_done do_close) {
346 global_dmt = nullptr;
347
348 if (create_choice == BATCH_INSERT) {
349 global_dmt = dmt_create_from_sorted_array(values, length);
350 }
351 else if (create_choice == INSERT_AT) {
352 test_create_insert_at_sequential(KEEP_WHEN_DONE);
353 }
354 else if (create_choice == INSERT_AT_ALMOST_RANDOM) {
355 test_create_insert_at_almost_random(KEEP_WHEN_DONE);
356 }
357 else {
358 assert(false);
359 }
360
361 assert(global_dmt!=nullptr);
362 test_close(do_close);
363 }
364
365 static void
366 test_create_from_sorted_array_size (enum create_type create_choice, enum close_when_done do_close) {
367 test_create_from_sorted_array(create_choice, KEEP_WHEN_DONE);
368 assert(global_dmt->size()==length);
369 test_close(do_close);
370 }
371
372 static void
373 test_fetch_verify (DMT dmtree, DMTVALUE* val, uint32_t len ) {
374 uint32_t i;
375 int r;
376 DMTVALUE v = (DMTVALUE)&i;
377 DMTVALUE oldv = v;
378
379 assert(len == dmtree->size());
380 for (i = 0; i < len; i++) {
381 assert(oldv!=val[i]);
382 v = nullptr;
383 r = dmtree->fetch(i, nullptr, &v);
384 CKERR(r);
385 assert(v != nullptr);
386 assert(v != oldv);
387 assert(v == val[i]);
388 assert(V(v)->number == V(val[i])->number);
389 v = oldv;
390 }
391
392 for (i = len; i < len*2; i++) {
393 v = oldv;
394 r = dmtree->fetch(i, nullptr, &v);
395 CKERR2(r, EINVAL);
396 assert(v == oldv);
397 }
398
399 }
400
401 static void
402 test_create_fetch_verify (enum create_type create_choice, enum close_when_done do_close) {
403 test_create_from_sorted_array(create_choice, KEEP_WHEN_DONE);
404 test_fetch_verify(global_dmt, values, length);
405 test_close(do_close);
406 }
407
408 static int iterate_helper_error_return = 1;
409
410 static int
411 iterate_helper (DMTVALUE v, uint32_t idx, void* extra) {
412 if (extra == nullptr) return iterate_helper_error_return;
413 DMTVALUE* vals = (DMTVALUE *)extra;
414 assert(v != nullptr);
415 assert(v == vals[idx]);
416 assert(V(v)->number == V(vals[idx])->number);
417 return 0;
418 }
419 struct functor {
420 int (*f)(DMTVALUE, uint32_t, void *);
421 void *v;
422 };
423
424 int call_functor(const uint32_t size, const DMTVALUE &v, uint32_t idx, functor *const ftor);
425 int call_functor(const uint32_t size, const DMTVALUE &v, uint32_t idx, functor *const ftor) {
426 invariant(size == sizeof(DMTVALUE));
427 return ftor->f(const_cast<DMTVALUE>(v), idx, ftor->v);
428 }
429
430 static int dmt_iterate(DMT dmt, int (*f)(DMTVALUE, uint32_t, void*), void*v) {
431 struct functor ftor = { .f = f, .v = v };
432 return dmt->iterate<functor, call_functor>(&ftor);
433 }
434
435 static void
436 test_iterate_verify (DMT dmtree, DMTVALUE* vals, uint32_t len) {
437 int r;
438 iterate_helper_error_return = 0;
439 r = dmt_iterate(dmtree, iterate_helper, (void*)vals);
440 CKERR(r);
441 iterate_helper_error_return = 0xFEEDABBA;
442 r = dmt_iterate(dmtree, iterate_helper, nullptr);
443 if (!len) {
444 CKERR2(r, 0);
445 }
446 else {
447 CKERR2(r, iterate_helper_error_return);
448 }
449 }
450
451 static void
452 test_create_iterate_verify (enum create_type create_choice, enum close_when_done do_close) {
453 test_create_from_sorted_array(create_choice, KEEP_WHEN_DONE);
454 test_iterate_verify(global_dmt, values, length);
455 test_close(do_close);
456 }
457
458
459 static void
460 permute_array (uint32_t* arr, uint32_t len) {
461 //
462 // create a permutation of 0...size-1
463 //
464 uint32_t i = 0;
465 for (i = 0; i < len; i++) {
466 arr[i] = i;
467 }
468 for (i = 0; i < len - 1; i++) {
469 uint32_t choices = len - i;
470 uint32_t choice = random() % choices;
471 if (choice != i) {
472 uint32_t temp = arr[i];
473 arr[i] = arr[choice];
474 arr[choice] = temp;
475 }
476 }
477 }
478
479 static int
480 dmt_set_at (DMT dmt, DMTVALUE value, uint32_t index) {
481 int r = dmt->delete_at(index);
482 if (r!=0) return r;
483 return dmt_insert_at(dmt, value, index);
484 }
485
486 static void
487 test_create_set_at (enum create_type create_choice, enum close_when_done do_close) {
488 uint32_t i = 0;
489
490 struct value* old_nums = nullptr;
491 MALLOC_N(length, old_nums);
492 assert(nums);
493
494 uint32_t* perm = nullptr;
495 MALLOC_N(length, perm);
496 assert(perm);
497
498 DMTVALUE* old_values = nullptr;
499 MALLOC_N(length, old_values);
500 assert(old_values);
501
502 permute_array(perm, length);
503
504 //
505 // These are going to be the new values
506 //
507 for (i = 0; i < length; i++) {
508 old_nums[i] = nums[i];
509 old_values[i] = &old_nums[i];
510 values[i] = &old_nums[i];
511 }
512 test_create_from_sorted_array(create_choice, KEEP_WHEN_DONE);
513 int r;
514 r = dmt_set_at (global_dmt, values[0], length);
515 CKERR2(r,EINVAL);
516 r = dmt_set_at (global_dmt, values[0], length+1);
517 CKERR2(r,EINVAL);
518 for (i = 0; i < length; i++) {
519 uint32_t choice = perm[i];
520 values[choice] = &nums[choice];
521 nums[choice].number = (uint32_t)random();
522 r = dmt_set_at (global_dmt, values[choice], choice);
523 CKERR(r);
524 test_iterate_verify(global_dmt, values, length);
525 test_fetch_verify(global_dmt, values, length);
526 }
527 r = dmt_set_at (global_dmt, values[0], length);
528 CKERR2(r,EINVAL);
529 r = dmt_set_at (global_dmt, values[0], length+1);
530 CKERR2(r,EINVAL);
531
532 toku_free(perm);
533 toku_free(old_values);
534 toku_free(old_nums);
535
536 test_close(do_close);
537 }
538
539 static int
540 insert_helper (DMTVALUE value, void* extra_insert) {
541 DMTVALUE to_insert = (DMTVALUE)extra_insert;
542 assert(to_insert);
543
544 if (V(value)->number < V(to_insert)->number) return -1;
545 if (V(value)->number > V(to_insert)->number) return +1;
546 return 0;
547 }
548
549 static void
550 test_create_insert (enum close_when_done do_close) {
551 uint32_t i = 0;
552
553 uint32_t* perm = nullptr;
554 MALLOC_N(length, perm);
555 assert(perm);
556
557 permute_array(perm, length);
558
559 test_create(KEEP_WHEN_DONE);
560 int r;
561 uint32_t size = length;
562 length = 0;
563 while (length < size) {
564 uint32_t choice = perm[length];
565 DMTVALUE to_insert = &nums[choice];
566 uint32_t idx = UINT32_MAX;
567
568 assert(length==global_dmt->size());
569 r = dmt_insert(global_dmt, to_insert, insert_helper, to_insert, &idx);
570 CKERR(r);
571 assert(idx <= length);
572 if (idx > 0) {
573 assert(V(to_insert)->number > V(values[idx-1])->number);
574 }
575 if (idx < length) {
576 assert(V(to_insert)->number < V(values[idx])->number);
577 }
578 length++;
579 assert(length==global_dmt->size());
580 /* Make room */
581 for (i = length-1; i > idx; i--) {
582 values[i] = values[i-1];
583 }
584 values[idx] = to_insert;
585 test_fetch_verify(global_dmt, values, length);
586 test_iterate_verify(global_dmt, values, length);
587
588 idx = UINT32_MAX;
589 r = dmt_insert(global_dmt, to_insert, insert_helper, to_insert, &idx);
590 CKERR2(r, DB_KEYEXIST);
591 assert(idx < length);
592 assert(V(values[idx])->number == V(to_insert)->number);
593 assert(length==global_dmt->size());
594
595 test_iterate_verify(global_dmt, values, length);
596 test_fetch_verify(global_dmt, values, length);
597 }
598
599 toku_free(perm);
600
601 test_close(do_close);
602 }
603
604 static void
605 test_create_delete_at (enum create_type create_choice, enum close_when_done do_close) {
606 uint32_t i = 0;
607 int r = ENOSYS;
608 test_create_from_sorted_array(create_choice, KEEP_WHEN_DONE);
609
610 assert(length == global_dmt->size());
611 r = global_dmt->delete_at(length);
612 CKERR2(r,EINVAL);
613 assert(length == global_dmt->size());
614 r = global_dmt->delete_at(length+1);
615 CKERR2(r,EINVAL);
616 while (length > 0) {
617 assert(length == global_dmt->size());
618 uint32_t index_to_delete = random()%length;
619 r = global_dmt->delete_at(index_to_delete);
620 CKERR(r);
621 for (i = index_to_delete+1; i < length; i++) {
622 values[i-1] = values[i];
623 }
624 length--;
625 test_fetch_verify(global_dmt, values, length);
626 test_iterate_verify(global_dmt, values, length);
627 }
628 assert(length == 0);
629 assert(length == global_dmt->size());
630 r = global_dmt->delete_at(length);
631 CKERR2(r, EINVAL);
632 assert(length == global_dmt->size());
633 r = global_dmt->delete_at(length+1);
634 CKERR2(r, EINVAL);
635 test_close(do_close);
636 }
637
638 static int dmt_merge(DMT leftdmt, DMT rightdmt, DMT *newdmtp) {
639 DMT XMALLOC(newdmt);
640 newdmt->create();
641 int r;
642 for (uint32_t i = 0; i < leftdmt->size(); i++) {
643 DMTVALUE v;
644 r = leftdmt->fetch(i, nullptr, &v);
645 invariant_zero(r);
646 r = newdmt->insert_at(v, i);
647 invariant_zero(r);
648 }
649 uint32_t offset = leftdmt->size();
650 for (uint32_t i = 0; i < rightdmt->size(); i++) {
651 DMTVALUE v;
652 r = rightdmt->fetch(i, nullptr, &v);
653 invariant_zero(r);
654 r = newdmt->insert_at(v, i+offset);
655 invariant_zero(r);
656 }
657 leftdmt->destroy();
658 rightdmt->destroy();
659 toku_free(leftdmt);
660 toku_free(rightdmt);
661 *newdmtp = newdmt;
662 return 0;
663 }
664
665 static void
666 test_split_merge (enum create_type create_choice, enum close_when_done do_close) {
667 int r = ENOSYS;
668 uint32_t i = 0;
669 DMT left_split = nullptr;
670 DMT right_split = nullptr;
671 test_create_from_sorted_array(create_choice, KEEP_WHEN_DONE);
672
673 for (i = 0; i <= length; i++) {
674 r = dmt_split_at(global_dmt, &right_split, length+1);
675 CKERR2(r,EINVAL);
676 r = dmt_split_at(global_dmt, &right_split, length+2);
677 CKERR2(r,EINVAL);
678
679 //
680 // test successful split
681 //
682 r = dmt_split_at(global_dmt, &right_split, i);
683 CKERR(r);
684 left_split = global_dmt;
685 global_dmt = nullptr;
686 assert(left_split->size() == i);
687 assert(right_split->size() == length - i);
688 test_fetch_verify(left_split, values, i);
689 test_iterate_verify(left_split, values, i);
690 test_fetch_verify(right_split, &values[i], length - i);
691 test_iterate_verify(right_split, &values[i], length - i);
692 //
693 // verify that new global_dmt's cannot do bad splits
694 //
695 r = dmt_split_at(left_split, &global_dmt, i+1);
696 CKERR2(r,EINVAL);
697 assert(left_split->size() == i);
698 assert(right_split->size() == length - i);
699 r = dmt_split_at(left_split, &global_dmt, i+2);
700 CKERR2(r,EINVAL);
701 assert(left_split->size() == i);
702 assert(right_split->size() == length - i);
703 r = dmt_split_at(right_split, &global_dmt, length - i + 1);
704 CKERR2(r,EINVAL);
705 assert(left_split->size() == i);
706 assert(right_split->size() == length - i);
707 r = dmt_split_at(right_split, &global_dmt, length - i + 1);
708 CKERR2(r,EINVAL);
709 assert(left_split->size() == i);
710 assert(right_split->size() == length - i);
711
712 //
713 // test merge
714 //
715 r = dmt_merge(left_split,right_split,&global_dmt);
716 CKERR(r);
717 left_split = nullptr;
718 right_split = nullptr;
719 assert(global_dmt->size() == length);
720 test_fetch_verify(global_dmt, values, length);
721 test_iterate_verify(global_dmt, values, length);
722 }
723 test_close(do_close);
724 }
725
726
727 static void
728 init_values (enum rand_type rand_choice) {
729 const uint32_t test_size = 100;
730 if (rand_choice == TEST_RANDOM) {
731 init_distinct_random_values(random_seed, test_size);
732 }
733 else if (rand_choice == TEST_SORTED) {
734 init_distinct_sorted_values(random_seed, test_size);
735 }
736 else if (rand_choice == TEST_IDENTITY) {
737 init_identity_values( random_seed, test_size);
738 }
739 else assert(false);
740 }
741
742 static void
743 test_create_array (enum create_type create_choice, enum rand_type rand_choice) {
744 /* ********************************************************************** */
745 init_values(rand_choice);
746 test_create_from_sorted_array( create_choice, CLOSE_WHEN_DONE);
747 test_create_from_sorted_array_size(create_choice, CLOSE_WHEN_DONE);
748 /* ********************************************************************** */
749 init_values(rand_choice);
750 test_create_fetch_verify( create_choice, CLOSE_WHEN_DONE);
751 /* ********************************************************************** */
752 init_values(rand_choice);
753 test_create_iterate_verify( create_choice, CLOSE_WHEN_DONE);
754 /* ********************************************************************** */
755 init_values(rand_choice);
756 test_create_set_at( create_choice, CLOSE_WHEN_DONE);
757 /* ********************************************************************** */
758 init_values(rand_choice);
759 test_create_delete_at( create_choice, CLOSE_WHEN_DONE);
760 /* ********************************************************************** */
761 init_values(rand_choice);
762 test_create_insert( CLOSE_WHEN_DONE);
763 /* ********************************************************************** */
764 init_values(rand_choice);
765 test_split_merge( create_choice, CLOSE_WHEN_DONE);
766 }
767
768 typedef struct {
769 uint32_t first_zero;
770 uint32_t first_pos;
771 } h_extra;
772
773
774 static int
775 test_heaviside (DMTVALUE v_dmt, void* x) {
776 DMTVALUE v = (DMTVALUE) v_dmt;
777 h_extra* extra = (h_extra*)x;
778 assert(v && x);
779 assert(extra->first_zero <= extra->first_pos);
780
781 uint32_t value = V(v)->number;
782 if (value < extra->first_zero) return -1;
783 if (value < extra->first_pos) return 0;
784 return 1;
785 }
786
787 static void
788 heavy_extra (h_extra* extra, uint32_t first_zero, uint32_t first_pos) {
789 extra->first_zero = first_zero;
790 extra->first_pos = first_pos;
791 }
792
793 static void
794 test_find_dir (int dir, void* extra, int (*h)(DMTVALUE, void*),
795 int r_expect, bool idx_will_change, uint32_t idx_expect,
796 uint32_t number_expect, bool UU(cursor_valid)) {
797 uint32_t idx = UINT32_MAX;
798 uint32_t old_idx = idx;
799 DMTVALUE dmt_val;
800 int r;
801
802 dmt_val = nullptr;
803
804 /* Verify we can pass nullptr value. */
805 dmt_val = nullptr;
806 idx = old_idx;
807 if (dir == 0) {
808 r = dmt_find_zero(global_dmt, h, extra, nullptr, &idx);
809 }
810 else {
811 r = dmt_find( global_dmt, h, extra, dir, nullptr, &idx);
812 }
813 CKERR2(r, r_expect);
814 if (idx_will_change) {
815 assert(idx == idx_expect);
816 }
817 else {
818 assert(idx == old_idx);
819 }
820 assert(dmt_val == nullptr);
821
822 /* Verify we can pass nullptr idx. */
823 dmt_val = nullptr;
824 idx = old_idx;
825 if (dir == 0) {
826 r = dmt_find_zero(global_dmt, h, extra, &dmt_val, 0);
827 }
828 else {
829 r = dmt_find( global_dmt, h, extra, dir, &dmt_val, 0);
830 }
831 CKERR2(r, r_expect);
832 assert(idx == old_idx);
833 if (r == DB_NOTFOUND) {
834 assert(dmt_val == nullptr);
835 }
836 else {
837 assert(V(dmt_val)->number == number_expect);
838 }
839
840 /* Verify we can pass nullptr both. */
841 dmt_val = nullptr;
842 idx = old_idx;
843 if (dir == 0) {
844 r = dmt_find_zero(global_dmt, h, extra, nullptr, 0);
845 }
846 else {
847 r = dmt_find( global_dmt, h, extra, dir, nullptr, 0);
848 }
849 CKERR2(r, r_expect);
850 assert(idx == old_idx);
851 assert(dmt_val == nullptr);
852 }
853
854 static void
855 test_find (enum create_type create_choice, enum close_when_done do_close) {
856 h_extra extra;
857 init_identity_values(random_seed, 100);
858 test_create_from_sorted_array(create_choice, KEEP_WHEN_DONE);
859
860 /*
861 -...-
862 A
863 */
864 heavy_extra(&extra, length, length);
865 test_find_dir(-1, &extra, test_heaviside, 0, true, length-1, length-1, true);
866 test_find_dir(+1, &extra, test_heaviside, DB_NOTFOUND, false, 0, 0, false);
867 test_find_dir(0, &extra, test_heaviside, DB_NOTFOUND, true, length, length, false);
868
869
870 /*
871 +...+
872 B
873 */
874 heavy_extra(&extra, 0, 0);
875 test_find_dir(-1, &extra, test_heaviside, DB_NOTFOUND, false, 0, 0, false);
876 test_find_dir(+1, &extra, test_heaviside, 0, true, 0, 0, true);
877 test_find_dir(0, &extra, test_heaviside, DB_NOTFOUND, true, 0, 0, false);
878
879 /*
880 0...0
881 C
882 */
883 heavy_extra(&extra, 0, length);
884 test_find_dir(-1, &extra, test_heaviside, DB_NOTFOUND, false, 0, 0, false);
885 test_find_dir(+1, &extra, test_heaviside, DB_NOTFOUND, false, 0, 0, false);
886 test_find_dir(0, &extra, test_heaviside, 0, true, 0, 0, true);
887
888 /*
889 -...-0...0
890 AC
891 */
892 heavy_extra(&extra, length/2, length);
893 test_find_dir(-1, &extra, test_heaviside, 0, true, length/2-1, length/2-1, true);
894 test_find_dir(+1, &extra, test_heaviside, DB_NOTFOUND, false, 0, 0, false);
895 test_find_dir(0, &extra, test_heaviside, 0, true, length/2, length/2, true);
896
897 /*
898 0...0+...+
899 C B
900 */
901 heavy_extra(&extra, 0, length/2);
902 test_find_dir(-1, &extra, test_heaviside, DB_NOTFOUND, false, 0, 0, false);
903 test_find_dir(+1, &extra, test_heaviside, 0, true, length/2, length/2, true);
904 test_find_dir(0, &extra, test_heaviside, 0, true, 0, 0, true);
905
906 /*
907 -...-+...+
908 AB
909 */
910 heavy_extra(&extra, length/2, length/2);
911 test_find_dir(-1, &extra, test_heaviside, 0, true, length/2-1, length/2-1, true);
912 test_find_dir(+1, &extra, test_heaviside, 0, true, length/2, length/2, true);
913 test_find_dir(0, &extra, test_heaviside, DB_NOTFOUND, true, length/2, length/2, false);
914
915 /*
916 -...-0...0+...+
917 AC B
918 */
919 heavy_extra(&extra, length/3, 2*length/3);
920 test_find_dir(-1, &extra, test_heaviside, 0, true, length/3-1, length/3-1, true);
921 test_find_dir(+1, &extra, test_heaviside, 0, true, 2*length/3, 2*length/3, true);
922 test_find_dir(0, &extra, test_heaviside, 0, true, length/3, length/3, true);
923
924 /* Cleanup */
925 test_close(do_close);
926 }
927
928 static void
929 runtests_create_choice (enum create_type create_choice) {
930 test_create_array(create_choice, TEST_SORTED);
931 test_create_array(create_choice, TEST_RANDOM);
932 test_create_array(create_choice, TEST_IDENTITY);
933 test_find( create_choice, CLOSE_WHEN_DONE);
934 }
935
936 static void
937 test_clone(uint32_t nelts)
938 // Test that each clone operation gives the right data back. If nelts is
939 // zero, also tests that you still get a valid DMT back and that the way
940 // to deallocate it still works.
941 {
942 DMT src = nullptr, dest = nullptr;
943 int r = 0;
944
945 XMALLOC(src);
946 src->create();
947 for (long i = 0; i < nelts; ++i) {
948 r = dmt_insert_at(src, (DMTVALUE) i, i);
949 assert_zero(r);
950 }
951
952 XMALLOC(dest);
953 dest->clone(*src);
954 assert(dest->size() == nelts);
955 for (long i = 0; i < nelts; ++i) {
956 DMTVALUE v;
957 long l;
958 r = dest->fetch(i, nullptr, &v);
959 assert_zero(r);
960 l = (long) v;
961 assert(l == i);
962 }
963 dest->destroy();
964 toku_free(dest);
965 src->destroy();
966 toku_free(src);
967 }
968
969 int
970 test_main(int argc, const char *argv[]) {
971 parse_args(argc, argv);
972 init_globals();
973 test_create( CLOSE_WHEN_DONE);
974 test_create_size( CLOSE_WHEN_DONE);
975 runtests_create_choice(BATCH_INSERT);
976 runtests_create_choice(INSERT_AT);
977 runtests_create_choice(INSERT_AT_ALMOST_RANDOM);
978 test_clone(0);
979 test_clone(1);
980 test_clone(1000);
981 test_clone(10000);
982 cleanup_globals();
983 return 0;
984 }
985
986