git init

1 files changed, 129 insertions, 0 deletions

diff --git a/tests/test_augment_rbtree.c b/tests/test_augment_rbtree.c
new file mode 100644
index 0000000..0389405
--- /dev/null
+++ b/tests/test_augment_rbtree.c
@@ -0,0 +1,129 @@
+#include <assert.h>
+#include <stdio.h>
+#include <string.h>
+#include <time.h>
+
+#include "rb_tree.h"
+
+typedef struct {
+    rb_node_t node;
+    int key;
+    int value;
+    int amount;
+} IntIntEntry;
+
+static int cmpfunc(void *x, void *y) {
+    int *a = x, *b = y;
+    return *a < *b ? -1 : *a > *b;
+}
+
+static void augment(void *n) {
+    IntIntEntry *node = n;
+    IntIntEntry *left = rb_tree_left(node);
+    IntIntEntry *right = rb_tree_right(node);
+    node->amount = 1;
+    node->amount += left == NULL ? 0 : left->amount;
+    node->amount += right == NULL ? 0 : right->amount;
+}
+
+static void test_largedata();
+
+static int max(int a, int b) { return a > b ? a : b; }
+
+int depth(void *n) {
+    rb_node_t *node = n;
+    if (node == NULL) return 0;
+    return max(depth(node->entry.rbe_left), depth(node->entry.rbe_right)) + 1;
+}
+
+void checkaugment(IntIntEntry *node) {
+    if (node == NULL) return;
+    IntIntEntry *left = rb_tree_left(node);
+    IntIntEntry *right = rb_tree_right(node);
+    int amount = 1;
+    amount += left == NULL ? 0 : left->amount;
+    amount += right == NULL ? 0 : right->amount;
+    assert(amount == node->amount);
+    checkaugment(left);
+    checkaugment(right);
+}
+
+int main() {
+    printf("[TEST] augment rbtree\n");
+    test_largedata();
+    printf("[PASS] augment rbtree\n");
+    return 0;
+}
+
+#define TESTSZ 10000
+int input[TESTSZ];
+
+void shuffle(int *input, int n) {
+    for (int i = n - 1; i > 0; i--) {
+        int j = rand() % i;
+        int tmp = input[i];
+        input[i] = input[j];
+        input[j] = tmp;
+    }
+}
+
+static void test_largedata() {
+    // generate random input
+    time_t t;
+    srand((unsigned)time(&t));
+    for (int i = 0; i < TESTSZ; i++) {
+        input[i] = i;
+    }
+    shuffle(input, TESTSZ);
+    // insert
+    rb_tree_t tree = {NULL, cmpfunc, augment};
+    IntIntEntry *n;
+    for (int i = 0; i < TESTSZ; i++) {
+        n = malloc(sizeof(*n));
+        n->key = input[i];
+        n->value = input[i];
+        n->amount = 1;
+        rb_tree_insert(&tree, n);
+    }
+    // check tree validity
+    int d = depth(tree.rbh_root);
+    assert(d >= 13 && d <= 28);
+    IntIntEntry *root = (IntIntEntry *)(tree.rbh_root);
+    assert(root->amount == TESTSZ);
+    checkaugment(root);
+    IntIntEntry *iter = rb_tree_min(&tree);
+    int i = 0;
+    for (; iter != NULL; iter = rb_tree_next(&tree, iter)) {
+        assert(iter->key == i);
+        i++;
+    }
+    // delete when: key % 3 != 0
+    memset(input, 0, sizeof(int) * TESTSZ);
+    int count = 0;
+    for (int i = 0; i < TESTSZ; i++) {
+        if (i % 3 != 0) {
+            input[count] = i;
+        } else {
+            continue;
+        }
+        count++;
+    }
+    shuffle(input, count);
+    for (int i = 0; i < count; i++) {
+        IntIntEntry *iter = rb_tree_find(&tree, &input[i]);
+        assert(iter != NULL);
+        rb_tree_remove(&tree, iter);
+    }
+    // check tree validity
+    d = depth(tree.rbh_root);
+    assert(d >= 11 && d <= 24);
+    root = (IntIntEntry *)(tree.rbh_root);
+    assert(root->amount == TESTSZ - count);
+    checkaugment(root);
+    iter = rb_tree_min(&tree);
+    i = 0;
+    for (; iter != NULL; iter = rb_tree_next(&tree, iter)) {
+        assert(iter->key == i * 3);
+        i++;
+    }
+}