1 #include "test/jemalloc_test.h" 2 3 static rtree_node_elm_t * 4 node_alloc(size_t nelms) 5 { 6 7 return ((rtree_node_elm_t *)calloc(nelms, sizeof(rtree_node_elm_t))); 8 } 9 10 static void 11 node_dalloc(rtree_node_elm_t *node) 12 { 13 14 free(node); 15 } 16 17 TEST_BEGIN(test_rtree_get_empty) 18 { 19 unsigned i; 20 21 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { 22 rtree_t rtree; 23 assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc), 24 "Unexpected rtree_new() failure"); 25 assert_ptr_null(rtree_get(&rtree, 0, false), 26 "rtree_get() should return NULL for empty tree"); 27 rtree_delete(&rtree); 28 } 29 } 30 TEST_END 31 32 TEST_BEGIN(test_rtree_extrema) 33 { 34 unsigned i; 35 extent_node_t node_a, node_b; 36 37 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { 38 rtree_t rtree; 39 assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc), 40 "Unexpected rtree_new() failure"); 41 42 assert_false(rtree_set(&rtree, 0, &node_a), 43 "Unexpected rtree_set() failure"); 44 assert_ptr_eq(rtree_get(&rtree, 0, true), &node_a, 45 "rtree_get() should return previously set value"); 46 47 assert_false(rtree_set(&rtree, ~((uintptr_t)0), &node_b), 48 "Unexpected rtree_set() failure"); 49 assert_ptr_eq(rtree_get(&rtree, ~((uintptr_t)0), true), &node_b, 50 "rtree_get() should return previously set value"); 51 52 rtree_delete(&rtree); 53 } 54 } 55 TEST_END 56 57 TEST_BEGIN(test_rtree_bits) 58 { 59 unsigned i, j, k; 60 61 for (i = 1; i < (sizeof(uintptr_t) << 3); i++) { 62 uintptr_t keys[] = {0, 1, 63 (((uintptr_t)1) << (sizeof(uintptr_t)*8-i)) - 1}; 64 extent_node_t node; 65 rtree_t rtree; 66 67 assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc), 68 "Unexpected rtree_new() failure"); 69 70 for (j = 0; j < sizeof(keys)/sizeof(uintptr_t); j++) { 71 assert_false(rtree_set(&rtree, keys[j], &node), 72 "Unexpected rtree_set() failure"); 73 for (k = 0; k < sizeof(keys)/sizeof(uintptr_t); k++) { 74 assert_ptr_eq(rtree_get(&rtree, keys[k], true), 75 &node, "rtree_get() should return " 76 "previously set value and ignore " 77 "insignificant key bits; i=%u, j=%u, k=%u, " 78 "set key=%#"FMTxPTR", get key=%#"FMTxPTR, i, 79 j, k, keys[j], keys[k]); 80 } 81 assert_ptr_null(rtree_get(&rtree, 82 (((uintptr_t)1) << (sizeof(uintptr_t)*8-i)), false), 83 "Only leftmost rtree leaf should be set; " 84 "i=%u, j=%u", i, j); 85 assert_false(rtree_set(&rtree, keys[j], NULL), 86 "Unexpected rtree_set() failure"); 87 } 88 89 rtree_delete(&rtree); 90 } 91 } 92 TEST_END 93 94 TEST_BEGIN(test_rtree_random) 95 { 96 unsigned i; 97 sfmt_t *sfmt; 98 #define NSET 16 99 #define SEED 42 100 101 sfmt = init_gen_rand(SEED); 102 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { 103 uintptr_t keys[NSET]; 104 extent_node_t node; 105 unsigned j; 106 rtree_t rtree; 107 108 assert_false(rtree_new(&rtree, i, node_alloc, node_dalloc), 109 "Unexpected rtree_new() failure"); 110 111 for (j = 0; j < NSET; j++) { 112 keys[j] = (uintptr_t)gen_rand64(sfmt); 113 assert_false(rtree_set(&rtree, keys[j], &node), 114 "Unexpected rtree_set() failure"); 115 assert_ptr_eq(rtree_get(&rtree, keys[j], true), &node, 116 "rtree_get() should return previously set value"); 117 } 118 for (j = 0; j < NSET; j++) { 119 assert_ptr_eq(rtree_get(&rtree, keys[j], true), &node, 120 "rtree_get() should return previously set value"); 121 } 122 123 for (j = 0; j < NSET; j++) { 124 assert_false(rtree_set(&rtree, keys[j], NULL), 125 "Unexpected rtree_set() failure"); 126 assert_ptr_null(rtree_get(&rtree, keys[j], true), 127 "rtree_get() should return previously set value"); 128 } 129 for (j = 0; j < NSET; j++) { 130 assert_ptr_null(rtree_get(&rtree, keys[j], true), 131 "rtree_get() should return previously set value"); 132 } 133 134 rtree_delete(&rtree); 135 } 136 fini_gen_rand(sfmt); 137 #undef NSET 138 #undef SEED 139 } 140 TEST_END 141 142 int 143 main(void) 144 { 145 146 return (test( 147 test_rtree_get_empty, 148 test_rtree_extrema, 149 test_rtree_bits, 150 test_rtree_random)); 151 } 152
