Loading...
--- libmalloc/libmalloc-140.40.1/tests/radix_tree_test.m
+++ /dev/null
@@ -1,330 +0,0 @@
-
-
-#import <Foundation/Foundation.h>
-
-#include <stdio.h>
-#include <stdlib.h>
-
-#include <assert.h>
-#include <stdbool.h>
-#include <string.h>
-
-#include <radix_tree.h>
-#include <radix_tree_internal.h>
-
-#include <darwintest.h>
-
-#include "../src/radix_tree_debug.c"
-
-bool failed = false;
-
-#if 0
-
-#define ASSERT(x) \
- if (!(x)) { \
- abort(); \
- }
-#define ASSERT_EQ(x, y) \
- if ((x) != (y)) { \
- abort(); \
- }
-
-#else
-
-#define ASSERT(x) \
- if (!(x)) { \
- failed = true; \
- }
-#define ASSERT_EQ(x, y) \
- if ((x) != (y)) { \
- failed = true; \
- }
-
-#endif
-
-static int
-log2i(uint64_t x)
-{
- if (x == 1) {
- return 0;
- }
- if (x & 1) {
- abort();
- }
- return 1 + log2(x >> 1);
-}
-
-T_DECL(radix_tree_test, "radix_tree_test")
-{
- bool ok;
-
- // size_t size = 100 * 4096;
- // void *buf = malloc(size);
- // memset(buf, 0xde, size);
- // struct radix_tree *tree = radix_tree_init(buf, size);
-
- struct radix_tree *tree = radix_tree_create();
- ASSERT(tree);
-
- const int n = 999;
-
- uint64_t minsize = 4096;
-
- for (uint64_t i = 0; i < n * minsize; i += minsize) {
- ok = radix_tree_insert(&tree, i, minsize, 3 * i);
- ASSERT(ok);
-
- /* printf("@@@@@@@@@@@--------\n"); */
- /* radix_tree_print(tree); */
- /* printf("@@@@@@@@@@---------\n"); */
-
- for (uint64_t j = 0; j < n * minsize; j += minsize) {
- // printf ("testing %lld %lld\n", i, j);
- if (j <= i) {
- ASSERT(radix_tree_lookup(tree, j) == 3 * j);
- } else {
- ASSERT(radix_tree_lookup(tree, j) == radix_tree_invalid_value);
- }
- }
- }
-
- T_EXPECT_FALSE(failed, "insert 1 to n");
-
- for (uint64_t i = 0; i < n * minsize; i += minsize) {
- ok = radix_tree_delete(&tree, i, minsize);
- ASSERT(ok);
- for (uint64_t j = 0; j < n * minsize; j += minsize) {
- if (j > i) {
- ASSERT(radix_tree_lookup(tree, j) == 3 * j);
- } else {
- ASSERT(radix_tree_lookup(tree, j) == radix_tree_invalid_value);
- }
- }
- }
-
- T_EXPECT_FALSE(failed, "delete 1 to n");
-
- for (uint64_t i = 0; i < n * minsize; i += minsize) {
- ok = radix_tree_insert(&tree, i, minsize, 3 * i);
- ASSERT(ok);
- }
-
- for (uint64_t i = n * minsize; i > 0;) {
- i -= minsize;
-
- // printf("@@@@@@@@@@@--------\n");
- // radix_tree_print(tree);
- // printf("@@@@@@@@@@---------\n");
-
- ok = radix_tree_delete(&tree, i, minsize);
-
- ASSERT(ok);
- for (uint64_t j = 0; j < n * minsize; j += minsize) {
- if (j < i) {
- ASSERT_EQ(radix_tree_lookup(tree, j), 3 * j);
- } else {
- ASSERT_EQ(radix_tree_lookup(tree, j), radix_tree_invalid_value);
- }
- }
- }
-
- T_EXPECT_FALSE(failed, "delete n to 1");
-
- srand(12345);
-
- NSMutableDictionary *d = [[NSMutableDictionary alloc] init];
-
- for (uint64_t i = 0; i < n; i++) {
- @autoreleasepool {
- for (int j = 0; j < 3; j++) {
- uint64_t key = minsize * (rand() + ((uint64_t)rand() << 32));
- uint64_t value = rand();
-
- // printf("@@@@@@@@@@@--------\n");
- // radix_tree_print(tree);
- // printf("@@@@@@@@@@---------inserting %llx\n", key);
-
- ok = radix_tree_insert(&tree, key, minsize, value);
-
- // printf("@@@@@@@@@@---------ok\n");
-
- ASSERT(ok);
-
- d[@(key)] = @(value);
- }
-
- NSArray *array = [d allKeys];
- id k = [array objectAtIndex:rand() % [array count]];
-
- ok = radix_tree_delete(&tree, [k unsignedLongLongValue], minsize);
- ASSERT(ok);
- [d removeObjectForKey:k];
-
- for (id k in d) {
- ASSERT_EQ(radix_tree_lookup(tree, [k unsignedLongLongValue]), [d[k] unsignedLongLongValue]);
- }
-
- uint64_t count = radix_tree_count(tree);
-
- // for (id k in d) {
- // printf("key %llx -> %llx\n", [k unsignedLongLongValue], [d[k] unsignedLongLongValue]);
- // }
- // radix_tree_print(tree);
-
- ASSERT_EQ((long)(count % minsize), 0l);
- ASSERT_EQ([[d allKeys] count], (long)(count / minsize));
- }
- }
-
- T_EXPECT_FALSE(failed, "random");
-
- for (id k in d) {
- radix_tree_delete(&tree, [k unsignedLongLongValue], minsize);
- }
- T_EXPECT_EQ_ULLONG(0ull, radix_tree_count(tree), "delete randoms");
-
- ASSERT_EQ(radix_tree_lookup(tree, 0), -1);
- ASSERT_EQ(radix_tree_lookup(tree, minsize - 1), -1);
- ASSERT_EQ(radix_tree_lookup(tree, minsize), -1);
-
- ok = radix_tree_insert(&tree, 0, minsize, 0xf00);
- ASSERT(ok);
- ASSERT_EQ(radix_tree_lookup(tree, 0), 0xf00);
- ASSERT_EQ(radix_tree_lookup(tree, minsize - 1), 0xf00);
- ASSERT_EQ(radix_tree_lookup(tree, minsize), -1);
-
- // this would abort:
- // ok = radix_tree_insert(&tree, -minsize, minsize, 0xb00);
- // ASSERT(!ok);
-
- ok = radix_tree_insert(&tree, -2 * minsize, minsize, 0xb00);
- ASSERT(ok);
-
- ASSERT_EQ(radix_tree_lookup(tree, -2 * minsize), 0xb00);
- ASSERT_EQ(radix_tree_lookup(tree, -2 * minsize - 1), -1);
- ASSERT_EQ(radix_tree_lookup(tree, -2 * minsize + 1), 0xb00);
- ASSERT_EQ(radix_tree_lookup(tree, -2 * minsize + minsize - 1), 0xb00);
- ASSERT_EQ(radix_tree_lookup(tree, -1 * minsize), -1);
- ASSERT_EQ(radix_tree_lookup(tree, minsize), -1);
-
- radix_tree_delete(&tree, -2 * minsize, minsize);
- radix_tree_delete(&tree, 0, minsize);
- ASSERT_EQ(radix_tree_count(tree), 0);
-
- T_EXPECT_FALSE(failed, "off by 1");
-
- int modelsize = 1024;
- uint32_t model[modelsize];
-
- while (log2i(modelsize) + log2i(minsize) <= 64) {
- memset(model, 0xff, sizeof(model));
-
- for (int i = 0; i < n; i++) {
- uint64_t start = rand() % modelsize;
- if (start == modelsize - 1 && log2i(modelsize) + log2i(minsize) == 64) {
- start = modelsize - 2;
- }
- uint64_t maxsize = modelsize - start;
- uint64_t size;
- if (maxsize / 4 > 1) {
- size = (rand() % (maxsize / 4)) + (rand() % (maxsize / 4)) + (rand() % (maxsize / 4)) + (rand() % (maxsize / 4));
- } else if (maxsize > 1) {
- size = rand() % maxsize;
- } else {
- size = 1;
- }
- if (size == 0) {
- size = 1;
- }
- if (minsize * start + minsize * size < minsize * start) {
- size--;
- }
- if (minsize * start + minsize * size < minsize * start) {
- abort();
- }
- if (size == 0) {
- abort();
- }
- uint32_t value = rand();
-
- // printf("inserting %llx, %llx\n", start*minsize, size*minsize);
- // radix_tree_print(tree);
-
- ok = radix_tree_insert(&tree, start * minsize, size * minsize, value);
- ASSERT(ok);
-
- // radix_tree_print(tree);
- ASSERT(radix_tree_fsck(tree));
-
- for (uint64_t i = start; i < start + size; i++) {
- model[i] = value;
- }
-
- for (uint64_t j = 0; j < modelsize; j++) {
- uint64_t expected;
- if (model[j] == (uint32_t)-1) {
- expected = (uint64_t)-1;
- } else {
- expected = model[j];
- }
-
- // radix_tree_print(tree);
- uint64_t ans = radix_tree_lookup(tree, j * minsize);
- // printf("j*minsize=%llx expected=%llx ans=%llx\n", j*minsize, expected, ans);
- ASSERT_EQ(expected, ans);
- }
- }
-
- T_EXPECT_FALSE(failed, "model %d", log2i(minsize) + log2i(modelsize));
-
- radix_tree_delete(&tree, 0, -1);
- T_EXPECT_EQ_ULLONG(0ull, radix_tree_count(tree), "delete model");
-
- minsize *= 2;
- tree->leaf_size_shift++;
- }
-}
-
-T_DECL(radix_tree_holes, "radix_tree_holes_test")
-{
- bool ok;
- struct radix_tree *tree = radix_tree_create();
- T_ASSERT_NOTNULL(tree, "radix_tree_create()");
-
- uint64_t size = 0xff00000;
- uint64_t minsize = 0x1000;
- uint64_t start = 0x10303c000;
-
- ok = radix_tree_insert(&tree, start, size, 0xf00ba);
-
- T_ASSERT_TRUE(ok, "created region");
-
- ok = radix_tree_fsck(tree);
- T_QUIET;
- T_ASSERT_TRUE(ok, "fsck");
-
- for (uint64_t addr = start; addr < start + size; addr += minsize) {
- T_QUIET;
- T_ASSERT_EQ_ULLONG(radix_tree_lookup(tree, addr), 0xf00ball, "stackid");
- uint64_t index = (addr - start) / minsize;
- if (index % 2) {
- ok = radix_tree_delete(&tree, addr, minsize);
- T_QUIET;
- T_ASSERT_TRUE(ok, "deleted odd %lld", index);
- }
- }
-
- for (uint64_t addr = start; addr < start + size; addr += minsize) {
- uint64_t index = (addr - start) / minsize;
- T_QUIET;
- T_ASSERT_EQ_ULLONG(radix_tree_lookup(tree, addr), index % 2 ? -1 : 0xf00ball, "stackid");
- if (!(index % 2)) {
- ok = radix_tree_delete(&tree, addr, minsize);
- T_QUIET;
- T_ASSERT_TRUE(ok, "deleted even, %lld", index);
- }
- }
-
- ok = radix_tree_fsck(tree);
- T_ASSERT_TRUE(ok, "fsck");
-}