diff options
Diffstat (limited to 'deps/jemalloc/test/unit/rtree.c')
-rw-r--r-- | deps/jemalloc/test/unit/rtree.c | 118 |
1 files changed, 118 insertions, 0 deletions
diff --git a/deps/jemalloc/test/unit/rtree.c b/deps/jemalloc/test/unit/rtree.c new file mode 100644 index 000000000..5463055fe --- /dev/null +++ b/deps/jemalloc/test/unit/rtree.c @@ -0,0 +1,118 @@ +#include "test/jemalloc_test.h" + +TEST_BEGIN(test_rtree_get_empty) +{ + unsigned i; + + for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { + rtree_t *rtree = rtree_new(i, imalloc, idalloc); + assert_u_eq(rtree_get(rtree, 0), 0, + "rtree_get() should return NULL for empty tree"); + rtree_delete(rtree); + } +} +TEST_END + +TEST_BEGIN(test_rtree_extrema) +{ + unsigned i; + + for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { + rtree_t *rtree = rtree_new(i, imalloc, idalloc); + + rtree_set(rtree, 0, 1); + assert_u_eq(rtree_get(rtree, 0), 1, + "rtree_get() should return previously set value"); + + rtree_set(rtree, ~((uintptr_t)0), 1); + assert_u_eq(rtree_get(rtree, ~((uintptr_t)0)), 1, + "rtree_get() should return previously set value"); + + rtree_delete(rtree); + } +} +TEST_END + +TEST_BEGIN(test_rtree_bits) +{ + unsigned i, j, k; + + for (i = 1; i < (sizeof(uintptr_t) << 3); i++) { + uintptr_t keys[] = {0, 1, + (((uintptr_t)1) << (sizeof(uintptr_t)*8-i)) - 1}; + rtree_t *rtree = rtree_new(i, imalloc, idalloc); + + for (j = 0; j < sizeof(keys)/sizeof(uintptr_t); j++) { + rtree_set(rtree, keys[j], 1); + for (k = 0; k < sizeof(keys)/sizeof(uintptr_t); k++) { + assert_u_eq(rtree_get(rtree, keys[k]), 1, + "rtree_get() should return previously set " + "value and ignore insignificant key bits; " + "i=%u, j=%u, k=%u, set key=%#"PRIxPTR", " + "get key=%#"PRIxPTR, i, j, k, keys[j], + keys[k]); + } + assert_u_eq(rtree_get(rtree, + (((uintptr_t)1) << (sizeof(uintptr_t)*8-i))), 0, + "Only leftmost rtree leaf should be set; " + "i=%u, j=%u", i, j); + rtree_set(rtree, keys[j], 0); + } + + rtree_delete(rtree); + } +} +TEST_END + +TEST_BEGIN(test_rtree_random) +{ + unsigned i; + sfmt_t *sfmt; +#define NSET 100 +#define SEED 42 + + sfmt = init_gen_rand(SEED); + for (i = 1; i <= (sizeof(uintptr_t) << 3); i++) { + rtree_t *rtree = rtree_new(i, imalloc, idalloc); + uintptr_t keys[NSET]; + unsigned j; + + for (j = 0; j < NSET; j++) { + keys[j] = (uintptr_t)gen_rand64(sfmt); + rtree_set(rtree, keys[j], 1); + assert_u_eq(rtree_get(rtree, keys[j]), 1, + "rtree_get() should return previously set value"); + } + for (j = 0; j < NSET; j++) { + assert_u_eq(rtree_get(rtree, keys[j]), 1, + "rtree_get() should return previously set value"); + } + + for (j = 0; j < NSET; j++) { + rtree_set(rtree, keys[j], 0); + assert_u_eq(rtree_get(rtree, keys[j]), 0, + "rtree_get() should return previously set value"); + } + for (j = 0; j < NSET; j++) { + assert_u_eq(rtree_get(rtree, keys[j]), 0, + "rtree_get() should return previously set value"); + } + + rtree_delete(rtree); + } + fini_gen_rand(sfmt); +#undef NSET +#undef SEED +} +TEST_END + +int +main(void) +{ + + return (test( + test_rtree_get_empty, + test_rtree_extrema, + test_rtree_bits, + test_rtree_random)); +} |