git init

6 files changed, 497 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++;
+    }
+}
diff --git a/tests/test_htable.c b/tests/test_htable.c
new file mode 100644
index 0000000..310d141
--- /dev/null
+++ b/tests/test_htable.c
@@ -0,0 +1,71 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "hash_table.h"
+#include "mmhash.h"
+
+static uint64_t hash(void *i) { return mmhash(i, sizeof(int), 0); }
+
+static bool eq(void *x, void *y) {
+    int *a = x, *b = y;
+    return *a == *b;
+}
+
+bool found[10000];
+
+int main() {
+    printf("[TEST] htable\n");
+
+    hash_table_t ht;
+    init_hash_table(&ht, sizeof(int), -1, hash, eq);
+    for (int i = 0; i < 10000; i++) {
+        hash_table_insert(&ht, &i);
+        assert(ht.size == i + 1);
+        assert(ht.taken == i + 1);
+        assert(ht.cap >= i + 1);
+    }
+
+    for (int i = 0; i < 10000; i++) {
+        assert(hash_table_find(&ht, &i) != NULL);
+        int t = 10000 + i;
+        assert(hash_table_find(&ht, &t) == NULL);
+    }
+
+    memset(found, 0, sizeof(bool) * 10000);
+    int *iter = hash_table_begin(&ht);
+    while (iter != NULL) {
+        found[*iter] = true;
+        iter = hash_table_next(&ht, iter);
+    }
+    for (int i = 0; i < 10000; i++) {
+        assert(found[i]);
+    }
+
+    for (int i = 0; i < 5000; i++) {
+        int *iter = hash_table_find(&ht, &i);
+        hash_table_remove(&ht, iter);
+    }
+    for (int i = 0; i < 5000; i++) {
+        assert(hash_table_find(&ht, &i) == NULL);
+        int t = 5000 + i;
+        assert(hash_table_find(&ht, &t) != NULL);
+    }
+
+    for (int i = 0; i < 5000; i++) {
+        hash_table_insert(&ht, &i);
+    }
+
+    memset(found, 0, sizeof(bool) * 10000);
+    iter = hash_table_begin(&ht);
+    while (iter != NULL) {
+        found[*iter] = true;
+        iter = hash_table_next(&ht, iter);
+    }
+    for (int i = 0; i < 10000; i++) {
+        assert(found[i]);
+    }
+
+    printf("[PASS] htable\n");
+}
diff --git a/tests/test_mmhash.c b/tests/test_mmhash.c
new file mode 100644
index 0000000..3a9895c
--- /dev/null
+++ b/tests/test_mmhash.c
@@ -0,0 +1,15 @@
+#include <assert.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "mmhash.h"
+
+int main() {
+    printf("[TEST] hash\n");
+    char buf[] = "hello, world\n";
+    uint64_t hash0 = mmhash(buf, strlen(buf), 0);
+    uint64_t hash1 = mmhash(buf, 3, 0);
+    assert(hash0 != hash1);
+    printf("[PASS] hash\n");
+    return 0;
+}
diff --git a/tests/test_pque.c b/tests/test_pque.c
new file mode 100644
index 0000000..01e6e1c
--- /dev/null
+++ b/tests/test_pque.c
@@ -0,0 +1,40 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "priority_queue.h"
+
+int intcmp(void *_a, void *_b) {
+    int a = *(int *)_a;
+    int b = *(int *)_b;
+    if (a < b) return 1;
+    if (a > b) return -1;
+    return 0;
+}
+
+int main() {
+    printf("[TEST] pque\n");
+    priority_queue_t pq;
+    init_priority_queue(&pq, 3, sizeof(int), intcmp);
+    int elems[10] = {1, 3, 2, 4, 6, 5, 9, 7, 8, 10};
+    for (int i = 0; i < 10; i++) {
+        int e = elems[i];
+        priority_queue_push(&pq, &e);
+    }
+    for (int i = 1; i < 11; i++) {
+        int *top = priority_queue_top(&pq);
+        assert(i == *top);
+        priority_queue_pop(&pq);
+    }
+    assert(priority_queue_top(&pq) == NULL);
+    int elems2[10] = {10, 8, 7, 9, 5, 6, 4, 2, 3, 1};
+    int expected[10] = {10, 8, 7, 7, 5, 5, 4, 2, 2, 1};
+    for (int i = 0; i < 10; i++) {
+        int e = elems2[i];
+        priority_queue_push(&pq, &e);
+        int *top = priority_queue_top(&pq);
+        assert(*top == expected[i]);
+    }
+    printf("[PASS] pque\n");
+    return 0;
+}
diff --git a/tests/test_rbtree.c b/tests/test_rbtree.c
new file mode 100644
index 0000000..b1fbc32
--- /dev/null
+++ b/tests/test_rbtree.c
@@ -0,0 +1,128 @@
+#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;
+} IntIntEntry;
+
+static int cmpfunc(void *x, void *y) {
+    int *a = x, *b = y;
+    return *a < *b ? -1 : *a > *b;
+}
+
+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;
+}
+
+int main() {
+    printf("[TEST] rbtree\n");
+    rb_tree_t tree = {NULL, cmpfunc, NULL};
+    IntIntEntry *n;
+
+    int a[5] = {1, 2, 3, 4, 5};
+    for (int i = 0; i < 5; i++) {
+        n = malloc(sizeof(*n));
+        n->key = a[i];
+        n->value = i;
+        rb_tree_insert(&tree, n);
+    }
+
+    int find = 3;
+    IntIntEntry *iter;
+    iter = rb_tree_find(&tree, &find);
+    assert(iter->key == 3);
+
+    rb_tree_remove(&tree, iter);
+    free(iter);
+
+    iter = rb_tree_min(&tree);
+    int expected[4] = {1, 2, 4, 5};
+    int i = 0;
+    for (; iter != NULL; iter = rb_tree_next(&tree, iter)) {
+        assert(iter->key == expected[i]);
+        i++;
+    }
+
+    destroy_rb_tree(&tree, NULL);
+    test_largedata();
+    printf("[PASS] 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, NULL};
+    IntIntEntry *n;
+    for (int i = 0; i < TESTSZ; i++) {
+        n = malloc(sizeof(*n));
+        n->key = input[i];
+        n->value = input[i];
+        rb_tree_insert(&tree, n);
+    }
+    // check tree validity
+    int d = depth(tree.rbh_root);
+    assert(d >= 13 && d <= 28);
+    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);
+    iter = rb_tree_min(&tree);
+    i = 0;
+    for (; iter != NULL; iter = rb_tree_next(&tree, iter)) {
+        assert(iter->key == i * 3);
+        i++;
+    }
+}
diff --git a/tests/test_str.c b/tests/test_str.c
new file mode 100644
index 0000000..85e4f31
--- /dev/null
+++ b/tests/test_str.c
@@ -0,0 +1,114 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <str.h>
+
+void test_str_split() {
+    char *s = "abc 123 233 xyz";
+    char **list = str_split(s, ' ');
+    assert(list[4] == NULL);
+    assert(list[3] != NULL);
+    assert(strcmp(list[0], "abc") == 0);
+    assert(strcmp(list[3], "xyz") == 0);
+    destroy_str_list(list);
+
+    s = "abc  123 233 xyz";
+    list = str_split(s, ' ');
+    assert(list[4] == NULL);
+    assert(list[3] != NULL);
+    assert(strcmp(list[0], "abc") == 0);
+    assert(strcmp(list[3], "xyz") == 0);
+    destroy_str_list(list);
+
+    s = "   abc  123 233 xyz";
+    list = str_split(s, ' ');
+    assert(list[4] == NULL);
+    assert(list[3] != NULL);
+    assert(strcmp(list[0], "abc") == 0);
+    assert(strcmp(list[3], "xyz") == 0);
+    destroy_str_list(list);
+
+    s = "   abc \t 123\n 233\nxyz";
+    list = str_split(s, '\0');
+    assert(list[4] == NULL);
+    assert(list[3] != NULL);
+    assert(strcmp(list[0], "abc") == 0);
+    assert(strcmp(list[3], "xyz") == 0);
+    destroy_str_list(list);
+
+    s = "a";
+    list = str_split(s, ' ');
+    assert(list[1] == NULL);
+    assert(list[0] != NULL);
+    assert(strcmp(list[0], "a") == 0);
+    destroy_str_list(list);
+
+    s = "";
+    list = str_split(s, ' ');
+    assert(list[0] == NULL);
+    destroy_str_list(list);
+
+    s = "  ";
+    list = str_split(s, ' ');
+    assert(list[0] == NULL);
+    destroy_str_list(list);
+}
+
+void test_str_strip() {
+    char *s;
+
+    s = str_strip("hello ");
+    assert(strcmp(s, "hello") == 0);
+
+    s = str_strip("hello");
+    assert(strcmp(s, "hello") == 0);
+
+    s = str_strip("\nhello ");
+    assert(strcmp(s, "hello") == 0);
+
+    s = str_strip("\nhello");
+    assert(strcmp(s, "hello") == 0);
+
+    s = str_strip("");
+    assert(strcmp(s, "") == 0);
+
+    s = str_strip("\n\t ");
+    assert(strcmp(s, "") == 0);
+
+    s = str_strip(" ");
+    assert(strcmp(s, "") == 0);
+}
+
+void test_str_bulider() {
+    str_builder_t sb;
+    init_str_builder(&sb);
+
+    str_builder_append(&sb, "%s", "hello");
+    assert(sb.size == 5);
+    assert(strcmp(sb.buf, "hello") == 0);
+    assert(strlen(sb.buf) == 5);
+
+    str_builder_append(&sb, "hello");
+    assert(sb.size == 10);
+    assert(strcmp(sb.buf, "hellohello") == 0);
+
+    str_builder_append(&sb, "%c1", 'c');
+    assert(sb.size == 12);
+    assert(strcmp(sb.buf, "hellohelloc1") == 0);
+
+    str_builder_append_char(&sb, 'x');
+    assert(sb.size == 13);
+    assert(strcmp(sb.buf, "hellohelloc1x") == 0);
+}
+
+int main() {
+    printf("[TEST] str\n");
+
+    test_str_split();
+    test_str_strip();
+
+    printf("[PASS] str\n");
+    return 0;
+}