1#include "test/jemalloc_test.h" 2 3TEST_BEGIN(test_rtree_get_empty) 4{ 5 unsigned i; 6 7 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { 8 rtree_t *rtree = rtree_new(i, imalloc, idalloc); 9 assert_u_eq(rtree_get(rtree, 0), 0, 10 "rtree_get() should return NULL for empty tree"); 11 rtree_delete(rtree); 12 } 13} 14TEST_END 15 16TEST_BEGIN(test_rtree_extrema) 17{ 18 unsigned i; 19 20 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { 21 rtree_t *rtree = rtree_new(i, imalloc, idalloc); 22 23 rtree_set(rtree, 0, 1); 24 assert_u_eq(rtree_get(rtree, 0), 1, 25 "rtree_get() should return previously set value"); 26 27 rtree_set(rtree, ~((uintptr_t)0), 1); 28 assert_u_eq(rtree_get(rtree, ~((uintptr_t)0)), 1, 29 "rtree_get() should return previously set value"); 30 31 rtree_delete(rtree); 32 } 33} 34TEST_END 35 36TEST_BEGIN(test_rtree_bits) 37{ 38 unsigned i, j, k; 39 40 for (i = 1; i < (sizeof(uintptr_t) << 3); i++) { 41 uintptr_t keys[] = {0, 1, 42 (((uintptr_t)1) << (sizeof(uintptr_t)*8-i)) - 1}; 43 rtree_t *rtree = rtree_new(i, imalloc, idalloc); 44 45 for (j = 0; j < sizeof(keys)/sizeof(uintptr_t); j++) { 46 rtree_set(rtree, keys[j], 1); 47 for (k = 0; k < sizeof(keys)/sizeof(uintptr_t); k++) { 48 assert_u_eq(rtree_get(rtree, keys[k]), 1, 49 "rtree_get() should return previously set " 50 "value and ignore insignificant key bits; " 51 "i=%u, j=%u, k=%u, set key=%#"PRIxPTR", " 52 "get key=%#"PRIxPTR, i, j, k, keys[j], 53 keys[k]); 54 } 55 assert_u_eq(rtree_get(rtree, 56 (((uintptr_t)1) << (sizeof(uintptr_t)*8-i))), 0, 57 "Only leftmost rtree leaf should be set; " 58 "i=%u, j=%u", i, j); 59 rtree_set(rtree, keys[j], 0); 60 } 61 62 rtree_delete(rtree); 63 } 64} 65TEST_END 66 67TEST_BEGIN(test_rtree_random) 68{ 69 unsigned i; 70 sfmt_t *sfmt; 71#define NSET 100 72#define SEED 42 73 74 sfmt = init_gen_rand(SEED); 75 for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { 76 rtree_t *rtree = rtree_new(i, imalloc, idalloc); 77 uintptr_t keys[NSET]; 78 unsigned j; 79 80 for (j = 0; j < NSET; j++) { 81 keys[j] = (uintptr_t)gen_rand64(sfmt); 82 rtree_set(rtree, keys[j], 1); 83 assert_u_eq(rtree_get(rtree, keys[j]), 1, 84 "rtree_get() should return previously set value"); 85 } 86 for (j = 0; j < NSET; j++) { 87 assert_u_eq(rtree_get(rtree, keys[j]), 1, 88 "rtree_get() should return previously set value"); 89 } 90 91 for (j = 0; j < NSET; j++) { 92 rtree_set(rtree, keys[j], 0); 93 assert_u_eq(rtree_get(rtree, keys[j]), 0, 94 "rtree_get() should return previously set value"); 95 } 96 for (j = 0; j < NSET; j++) { 97 assert_u_eq(rtree_get(rtree, keys[j]), 0, 98 "rtree_get() should return previously set value"); 99 } 100 101 rtree_delete(rtree); 102 } 103 fini_gen_rand(sfmt); 104#undef NSET 105#undef SEED 106} 107TEST_END 108 109int 110main(void) 111{ 112 113 return (test( 114 test_rtree_get_empty, 115 test_rtree_extrema, 116 test_rtree_bits, 117 test_rtree_random)); 118} 119