Loading...
--- /dev/null
+++ libmalloc/libmalloc-166.220.1/tests/radix_tree_test.m
@@ -0,0 +1,330 @@
+
+
+#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");
+}