22 files changed, 1520 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..4bb912d
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,7 @@
+/test_*
+*.o
+*.d
+build/
+*.bin
+*.a
+doing/
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..3f409e9
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,37 @@
+cc = gcc
+src = $(shell ls src/*.c)
+obj = $(src:.c=.o)
+
+tests=$(shell ls tests/*.c)
+tests_bin=$(tests:.c=.bin)
+
+all: libalgds.a
+	-rm -rf build/
+	-@mkdir -p build/include/algds/
+	-@mkdir -p build/lib
+	mv libalgds.a build/lib/
+	cp src/*.h build/include/algds
+
+libalgds.a: $(obj)
+	ar cr $@ $^
+
+test: $(tests_bin)
+	@echo
+	@echo "Run tests:"
+	@scripts/runall.sh $^
+
+$(obj):%.o:%.c
+	$(cc) -c -g $< -MD -MF $@.d -o $@
+
+$(tests_bin):%.bin:%.c libalgds.a
+	$(cc) -g -Isrc/ $< libalgds.a -MD -MF $@.d -o $@
+
+clean:
+	-rm $(shell find tests/ -name '*.bin')
+	-rm $(shell find . -name '*.o' -or -name '*.a' -or -name '*.d')
+	-rm -rf build
+
+DEPS := $(shell find . -name *.d)
+ifneq ($(DEPS),)
+include $(DEPS)
+endif
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..f990225
--- /dev/null
+++ b/README.md
@@ -0,0 +1,17 @@
+# Algorithms and Data Structures
+
+- Red-black tree
+- Augmented red-black tree
+- Priority queue
+- Murmur Hash
+- Hash Table
+- String utilities
+- Region-based memory management
+
+## Build
+
+    make
+
+## Run Tests
+
+    make test
diff --git a/scripts/runall.sh b/scripts/runall.sh
new file mode 100755
index 0000000..3fdc745
--- /dev/null
+++ b/scripts/runall.sh
@@ -0,0 +1,9 @@
+#!/usr/bin/env bash
+
+for var in "$@"; do
+    ./$var
+    if [ $? -ne 0 ]; then
+        exit 255
+    fi
+done
+
diff --git a/src/arena.c b/src/arena.c
new file mode 100644
index 0000000..f45d11b
--- /dev/null
+++ b/src/arena.c
@@ -0,0 +1,40 @@
+#include "arena.h"
+
+#include <stdlib.h>
+
+void init_arena(arena_t *r, int blocksz) {
+    if (blocksz < 4096) blocksz = 4096;
+    r->head = (struct memblock){NULL, 0, blocksz};
+    r->head.buf = malloc(blocksz);
+    r->current = &(r->head);
+    r->blocksz = blocksz;
+}
+
+void destroy_arena(arena_t *r) {
+    free(r->head.buf);
+    struct memblock *cur = r->head.next;
+    while (cur != NULL) {
+        struct memblock *prev = cur;
+        cur = cur->next;
+        free(prev->buf);
+        free(prev);
+    }
+}
+
+void *arena_alloc(arena_t *r, int sz) {
+    int remain = r->current->cap - r->current->sz;
+    if (remain >= sz) {
+        void *ptr = r->current->buf + r->current->sz;
+        r->current->sz += sz;
+        return ptr;
+    }
+    int blocksz = sz > blocksz ? sz : blocksz;
+    struct memblock *nextblock = malloc(sizeof(struct memblock));
+    void *ptr = malloc(blocksz);
+    nextblock->buf = ptr;
+    nextblock->cap = blocksz;
+    nextblock->sz = sz;
+    r->current->next = nextblock;
+    r->current = nextblock;
+    return ptr;
+}
diff --git a/src/arena.h b/src/arena.h
new file mode 100644
index 0000000..80636e2
--- /dev/null
+++ b/src/arena.h
@@ -0,0 +1,23 @@
+#ifndef ALGDS_ARENA_H_
+#define ALGDS_ARENA_H_
+
+struct memblock {
+    void *buf;
+    int sz;
+    int cap;
+    struct memblock *next;
+};
+typedef struct memblock memblock_t;
+
+struct arena {
+    struct memblock head;
+    struct memblock *current;
+    int blocksz;
+};
+typedef struct arena arena_t;
+
+void init_arena(arena_t *r, int blocksz);
+void destroy_arena(arena_t *r);
+void *arena_alloc(arena_t *r, int sz);
+
+#endif
diff --git a/src/hash_table.c b/src/hash_table.c
new file mode 100644
index 0000000..3b635f4
--- /dev/null
+++ b/src/hash_table.c
@@ -0,0 +1,99 @@
+#include "hash_table.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#define HTFL_NUL 0
+#define HTFL_VAL 1
+#define HTFL_DEL 2
+
+static void *hash_table_end(hash_table_t *ht) {
+    return ht->buf + ht->cap * (ht->elemsz + 1);
+}
+
+static void rebuild(hash_table_t *ht) {
+    hash_table_t newht;
+    init_hash_table(&newht, ht->elemsz, ht->size * 6, ht->hash, ht->eq);
+    void *iter = hash_table_begin(ht);
+    while (iter != NULL) {
+        hash_table_insert(&newht, iter);
+        iter = hash_table_next(ht, iter);
+    }
+    free(ht->buf);
+    *ht = newht;
+}
+
+static uint8_t getflag(void *iter) { return *(uint8_t *)(iter - 1); }
+
+static void setflag(void *iter, uint8_t flag) { *(uint8_t *)(iter - 1) = flag; }
+
+void init_hash_table(hash_table_t *ht, int64_t elemsz, int64_t cap,
+                     uint64_t (*hash)(void *), bool (*eq)(void *, void *)) {
+    if (cap < 16) cap = 16;
+    ht->buf = malloc(cap * (elemsz + 1));
+    memset(ht->buf, 0, cap * (elemsz + 1));
+    ht->size = 0;
+    ht->cap = cap;
+    ht->taken = 0;
+    ht->begin = NULL;
+    ht->elemsz = elemsz;
+    ht->hash = hash;
+    ht->eq = eq;
+}
+
+bool hash_table_insert(hash_table_t *ht, void *elem) {
+    if (ht->taken + 1 > ht->cap / 2) {
+        rebuild(ht);
+    }
+    ht->taken++;
+    ht->size++;
+    int64_t hashcode = ht->hash(elem) % ht->cap;
+    void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
+    while (getflag(pos) != HTFL_NUL) {
+        if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) return false;
+        pos += ht->elemsz + 1;
+        if (pos >= hash_table_end(ht)) { // arrived end, restart from beginning
+            pos = ht->buf + 1;
+        }
+    }
+    memcpy(pos, elem, ht->elemsz);
+    setflag(pos, HTFL_VAL);
+    if (pos < ht->begin || ht->begin == NULL) {
+        ht->begin = pos;
+    }
+    return true;
+}
+
+void hash_table_remove(hash_table_t *ht, void *iter) {
+    ht->size--;
+    setflag(iter, HTFL_DEL);
+    if (iter == ht->begin) {
+        ht->begin = hash_table_next(ht, iter);
+    }
+}
+
+void *hash_table_find(hash_table_t *ht, void *elem) {
+    int64_t hashcode = ht->hash(elem) % ht->cap;
+    void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
+    while (getflag(pos) != HTFL_NUL) {
+        if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) return pos;
+        pos += ht->elemsz + 1;
+        if (pos >= hash_table_end(ht)) { // arrived end, restart from beginning
+            pos = ht->buf + 1;
+        }
+    }
+    return NULL;
+}
+
+void *hash_table_begin(hash_table_t *ht) { return ht->begin; }
+
+void *hash_table_next(hash_table_t *ht, void *iter) {
+    void *pos = iter;
+    do {
+        pos += ht->elemsz + 1;
+        if (pos >= hash_table_end(ht)) {
+            return NULL;
+        }
+    } while (getflag(pos) != HTFL_VAL);
+    return pos;
+}
diff --git a/src/hash_table.h b/src/hash_table.h
new file mode 100644
index 0000000..1bf6cfe
--- /dev/null
+++ b/src/hash_table.h
@@ -0,0 +1,29 @@
+#ifndef HTABLE_H_
+#define HTABLE_H_
+
+#include <stdbool.h>
+#include <stdint.h>
+
+struct hash_table {
+    void *buf;
+    int64_t size;
+    int64_t cap;
+    int64_t taken;
+    void *begin;
+    int64_t elemsz;
+    uint64_t (*hash)(void *);
+    bool (*eq)(void *, void *);
+};
+typedef struct hash_table hash_table_t;
+
+void init_hash_table(hash_table_t *ht, int64_t elemsz, int64_t cap,
+                     uint64_t (*hash)(void *), bool (*eq)(void *, void *));
+bool hash_table_insert(hash_table_t *ht, void *elem);
+void hash_table_remove(hash_table_t *ht, void *iter);
+
+// return a iterator
+void *hash_table_find(hash_table_t *ht, void *elem);
+void *hash_table_begin(hash_table_t *ht);
+void *hash_table_next(hash_table_t *ht, void *iter);
+
+#endif
diff --git a/src/mmhash.c b/src/mmhash.c
new file mode 100644
index 0000000..7897b9e
--- /dev/null
+++ b/src/mmhash.c
@@ -0,0 +1,57 @@
+#include "mmhash.h"
+
+/*-----------------------------------------------------------------------------
+// MurmurHash2, 64-bit versions, by Austin Appleby
+//
+// The same caveats as 32-bit MurmurHash2 apply here - beware of alignment
+// and endian-ness issues if used across multiple platforms.
+//
+// 64-bit hash for 64-bit platforms
+*/
+
+uint64_t mmhash(const void *key, int len, uint64_t seed) {
+    const uint64_t m = 0xc6a4a7935bd1e995LL;
+    const int r = 47;
+
+    uint64_t h = seed ^ (len * m);
+
+    const uint64_t *data = (const uint64_t *)key;
+    const uint64_t *end = data + (len / 8);
+
+    while (data != end) {
+        uint64_t k = *data++;
+
+        k *= m;
+        k ^= k >> r;
+        k *= m;
+
+        h ^= k;
+        h *= m;
+    }
+
+    const unsigned char *data2 = (const unsigned char *)data;
+
+    switch (len & 7) {
+        case 7:
+            h ^= ((uint64_t)data2[6]) << 48;
+        case 6:
+            h ^= ((uint64_t)data2[5]) << 40;
+        case 5:
+            h ^= ((uint64_t)data2[4]) << 32;
+        case 4:
+            h ^= ((uint64_t)data2[3]) << 24;
+        case 3:
+            h ^= ((uint64_t)data2[2]) << 16;
+        case 2:
+            h ^= ((uint64_t)data2[1]) << 8;
+        case 1:
+            h ^= ((uint64_t)data2[0]);
+            h *= m;
+    };
+
+    h ^= h >> r;
+    h *= m;
+    h ^= h >> r;
+
+    return h;
+}
diff --git a/src/mmhash.h b/src/mmhash.h
new file mode 100644
index 0000000..a795cb1
--- /dev/null
+++ b/src/mmhash.h
@@ -0,0 +1,8 @@
+#ifndef ALGDS_HASH_H_
+#define ALGDS_HASH_H_
+
+#include <stdint.h>
+
+uint64_t mmhash(const void *key, int len, uint64_t seed);
+
+#endif
diff --git a/src/priority_queue.c b/src/priority_queue.c
new file mode 100644
index 0000000..59d64df
--- /dev/null
+++ b/src/priority_queue.c
@@ -0,0 +1,73 @@
+#include "priority_queue.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+void init_priority_queue(priority_queue_t *pq, int cap, int elem_sz,
+                         int (*cmp)(void *, void *)) {
+    pq->cap = cap;
+    pq->size = 0;
+    pq->elemsz = elem_sz;
+    pq->cmp = cmp;
+    pq->buf = malloc(cap * elem_sz);
+}
+
+static void swap(priority_queue_t *pq, int a, int b) {
+    char buf[pq->elemsz];
+    void *tmp = buf;
+    int elemsz = pq->elemsz;
+    memcpy(tmp, pq->buf + a * elemsz, elemsz);
+    memcpy(pq->buf + a * elemsz, pq->buf + b * elemsz, elemsz);
+    memcpy(pq->buf + b * elemsz, tmp, elemsz);
+}
+
+static int cmp(priority_queue_t *pq, int a, int b) {
+    return pq->cmp(pq->buf + a * pq->elemsz, pq->buf + b * pq->elemsz);
+}
+
+void priority_queue_push(priority_queue_t *pq, void *elem) {
+    if (pq->size + 1 > pq->cap) {
+        pq->buf = realloc(pq->buf, 2 * pq->cap * pq->elemsz);
+        pq->cap *= 2;
+    }
+    memcpy(pq->buf + pq->size * pq->elemsz, elem, pq->elemsz);
+    pq->size++;
+    if (pq->size == 0) {
+        return;
+    }
+    int i = pq->size - 1;
+    while (i > 0 && cmp(pq, i, i / 2) > 0) {
+        swap(pq, i, i / 2);
+        i /= 2;
+    }
+}
+
+static void heapify(priority_queue_t *pq, int idx) {
+    int left, right, largest;
+    left = 2 * idx + 1;
+    right = 2 * idx + 2;
+    if (left < pq->size && cmp(pq, left, idx) > 0) {
+        largest = left;
+    } else {
+        largest = idx;
+    }
+    if (right < pq->size && cmp(pq, right, largest) > 0) {
+        largest = right;
+    }
+    if (largest != idx) {
+        swap(pq, largest, idx);
+        heapify(pq, largest);
+    }
+}
+
+void priority_queue_pop(priority_queue_t *pq) {
+    if (pq->size == 0) return;
+    memcpy(pq->buf, pq->buf + (pq->size - 1) * pq->elemsz, pq->elemsz);
+    pq->size -= 1;
+    heapify(pq, 0);
+}
+
+void *priority_queue_top(priority_queue_t *pq) {
+    if (pq->size == 0) return NULL;
+    return pq->buf;
+}
diff --git a/src/priority_queue.h b/src/priority_queue.h
new file mode 100644
index 0000000..895bb42
--- /dev/null
+++ b/src/priority_queue.h
@@ -0,0 +1,19 @@
+#ifndef PQUEUE_H_
+#define PQUEUE_H_
+
+struct priority_queue {
+    void *buf;
+    int elemsz;
+    int cap;
+    int size;
+    int (*cmp)(void *, void *);
+};
+typedef struct priority_queue priority_queue_t;
+
+void init_priority_queue(priority_queue_t *pq, int cap, int elemsz,
+                         int (*cmp)(void *, void *));
+void priority_queue_push(priority_queue_t *pq, void *elem);
+void priority_queue_pop(priority_queue_t *pq);
+void *priority_queue_top();
+
+#endif
diff --git a/src/rb_tree.c b/src/rb_tree.c
new file mode 100644
index 0000000..f2bcd0c
--- /dev/null
+++ b/src/rb_tree.c
@@ -0,0 +1,386 @@
+/*
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "rb_tree.h"
+
+#define RED 1
+#define BLACK 0
+
+static rb_node_t *rb_tree_minmax(rb_tree_t *, int);
+void *rb_tree_min(rb_tree_t *head) { return rb_tree_minmax(head, -1); }
+void *rb_tree_max(rb_tree_t *head) { return rb_tree_minmax(head, 1); }
+
+void *rb_tree_left(void *node) {
+    rb_node_t *elm = node;
+    if (node == NULL) return NULL;
+    return elm->entry.rbe_left;
+}
+void *rb_tree_right(void *node) {
+    rb_node_t *elm = node;
+    if (node == NULL) return NULL;
+    return elm->entry.rbe_right;
+}
+void *rb_tree_parent(void *node) {
+    rb_node_t *elm = node;
+    if (node == NULL) return NULL;
+    return elm->entry.rbe_parent;
+}
+
+static void augment(rb_tree_t *head, rb_node_t *elm) {
+    if (head->augment != NULL) head->augment(elm);
+}
+
+static void rb_tree_insert_color(rb_tree_t *head, rb_node_t *elm);
+static void rb_tree_remove_color(rb_tree_t *head, rb_node_t *parent,
+                                 rb_node_t *elm);
+
+static void rotate_left(rb_tree_t *head, rb_node_t *elm) {
+    rb_node_t *tmp = elm->entry.rbe_right;
+    if ((elm->entry.rbe_right = tmp->entry.rbe_left)) {
+        tmp->entry.rbe_left->entry.rbe_parent = elm;
+    }
+    augment(head, elm);
+    if ((tmp->entry.rbe_parent = elm->entry.rbe_parent)) {
+        if (elm == elm->entry.rbe_parent->entry.rbe_left)
+            elm->entry.rbe_parent->entry.rbe_left = tmp;
+        else
+            elm->entry.rbe_parent->entry.rbe_right = tmp;
+    } else {
+        head->rbh_root = tmp;
+    }
+    tmp->entry.rbe_left = elm;
+    elm->entry.rbe_parent = tmp;
+    augment(head, tmp);
+    if (tmp->entry.rbe_parent) {
+        augment(head, tmp->entry.rbe_parent);
+    }
+}
+
+static void rotate_right(rb_tree_t *head, rb_node_t *elm) {
+    rb_node_t *tmp = elm->entry.rbe_left;
+    if ((elm->entry.rbe_left = tmp->entry.rbe_right)) {
+        tmp->entry.rbe_right->entry.rbe_parent = elm;
+    }
+    augment(head, elm);
+    if ((tmp->entry.rbe_parent = elm->entry.rbe_parent)) {
+        if (elm == elm->entry.rbe_parent->entry.rbe_left)
+            elm->entry.rbe_parent->entry.rbe_left = tmp;
+        else
+            elm->entry.rbe_parent->entry.rbe_right = tmp;
+    } else {
+        head->rbh_root = tmp;
+    }
+    tmp->entry.rbe_right = elm;
+    elm->entry.rbe_parent = tmp;
+    augment(head, tmp);
+    if (tmp->entry.rbe_parent) {
+        augment(head, tmp->entry.rbe_parent);
+    }
+}
+
+static void rb_tree_insert_color(rb_tree_t *head, rb_node_t *elm) {
+    rb_node_t *parent, *gparent, *tmp;
+    while ((parent = elm->entry.rbe_parent) && parent->entry.rbe_color == 1) {
+        gparent = parent->entry.rbe_parent;
+        if (parent == gparent->entry.rbe_left) {
+            tmp = gparent->entry.rbe_right;
+            if (tmp && tmp->entry.rbe_color == 1) {
+                tmp->entry.rbe_color = BLACK;
+                parent->entry.rbe_color = BLACK;
+                gparent->entry.rbe_color = RED;
+                elm = gparent;
+                continue;
+            }
+            if (parent->entry.rbe_right == elm) {
+                rotate_left(head, parent);
+                tmp = parent;
+                parent = elm;
+                elm = tmp;
+            }
+            parent->entry.rbe_color = BLACK;
+            gparent->entry.rbe_color = RED;
+            rotate_right(head, gparent);
+        } else {
+            tmp = gparent->entry.rbe_left;
+            if (tmp && tmp->entry.rbe_color == 1) {
+                tmp->entry.rbe_color = BLACK;
+                parent->entry.rbe_color = BLACK;
+                gparent->entry.rbe_color = RED;
+                ;
+                elm = gparent;
+                continue;
+            }
+            if (parent->entry.rbe_left == elm) {
+                rotate_right(head, parent);
+                tmp = parent;
+                parent = elm;
+                elm = tmp;
+            }
+            parent->entry.rbe_color = BLACK;
+            gparent->entry.rbe_color = RED;
+            rotate_left(head, gparent);
+        }
+    }
+    head->rbh_root->entry.rbe_color = BLACK;
+}
+
+static void rb_tree_remove_color(rb_tree_t *head, rb_node_t *parent,
+                                 rb_node_t *elm) {
+    rb_node_t *tmp;
+    while ((elm == NULL || elm->entry.rbe_color == 0) &&
+           elm != head->rbh_root) {
+        if (parent->entry.rbe_left == elm) {
+            tmp = parent->entry.rbe_right;
+            if (tmp->entry.rbe_color == 1) {
+                tmp->entry.rbe_color = BLACK;
+                parent->entry.rbe_color = RED;
+                rotate_left(head, parent);
+                tmp = parent->entry.rbe_right;
+            }
+            if ((tmp->entry.rbe_left == NULL ||
+                 tmp->entry.rbe_left->entry.rbe_color == 0) &&
+                (tmp->entry.rbe_right == NULL ||
+                 tmp->entry.rbe_right->entry.rbe_color == 0)) {
+                tmp->entry.rbe_color = RED;
+                elm = parent;
+                parent = elm->entry.rbe_parent;
+            } else {
+                if (tmp->entry.rbe_right == NULL ||
+                    tmp->entry.rbe_right->entry.rbe_color == 0) {
+                    rb_node_t *oleft;
+                    if ((oleft = tmp->entry.rbe_left))
+                        oleft->entry.rbe_color = BLACK;
+                    tmp->entry.rbe_color = RED;
+                    rotate_right(head, tmp);
+                    tmp = parent->entry.rbe_right;
+                }
+                tmp->entry.rbe_color = parent->entry.rbe_color;
+                parent->entry.rbe_color = BLACK;
+                if (tmp->entry.rbe_right)
+                    tmp->entry.rbe_right->entry.rbe_color = BLACK;
+                rotate_left(head, parent);
+                elm = head->rbh_root;
+                break;
+            }
+        } else {
+            tmp = parent->entry.rbe_left;
+            if (tmp->entry.rbe_color == 1) {
+                tmp->entry.rbe_color = BLACK;
+                parent->entry.rbe_color = RED;
+                rotate_right(head, parent);
+                tmp = parent->entry.rbe_left;
+            }
+            if ((tmp->entry.rbe_left == NULL ||
+                 tmp->entry.rbe_left->entry.rbe_color == 0) &&
+                (tmp->entry.rbe_right == NULL ||
+                 tmp->entry.rbe_right->entry.rbe_color == 0)) {
+                tmp->entry.rbe_color = RED;
+                elm = parent;
+                parent = elm->entry.rbe_parent;
+            } else {
+                if (tmp->entry.rbe_left == NULL ||
+                    tmp->entry.rbe_left->entry.rbe_color == 0) {
+                    rb_node_t *oright;
+                    if ((oright = tmp->entry.rbe_right))
+                        oright->entry.rbe_color = BLACK;
+                    tmp->entry.rbe_color = RED;
+                    rotate_left(head, tmp);
+                    tmp = parent->entry.rbe_left;
+                }
+                tmp->entry.rbe_color = parent->entry.rbe_color;
+                parent->entry.rbe_color = BLACK;
+                if (tmp->entry.rbe_left)
+                    tmp->entry.rbe_left->entry.rbe_color = BLACK;
+                rotate_right(head, parent);
+                elm = head->rbh_root;
+                break;
+            }
+        }
+    }
+    if (elm) elm->entry.rbe_color = BLACK;
+}
+
+void rb_tree_remove(rb_tree_t *head, void *elmv) {
+    rb_node_t *elm = elmv;
+    rb_node_t *child, *parent;
+    int color;
+    if (elm->entry.rbe_left == NULL)
+        child = elm->entry.rbe_right;
+    else if (elm->entry.rbe_right == NULL)
+        child = elm->entry.rbe_left;
+    else {
+        rb_node_t *old = elm, *left;
+        elm = elm->entry.rbe_right;
+        while ((left = elm->entry.rbe_left))
+            elm = left;
+        child = elm->entry.rbe_right;
+        parent = elm->entry.rbe_parent;
+        color = elm->entry.rbe_color;
+        if (child) child->entry.rbe_parent = parent;
+        if (parent) {
+            if (parent->entry.rbe_left == elm)
+                parent->entry.rbe_left = child;
+            else
+                parent->entry.rbe_right = child;
+            augment(head, parent);
+        } else
+            head->rbh_root = child;
+        if (elm->entry.rbe_parent == old) parent = elm;
+        elm->entry = old->entry;
+        if (old->entry.rbe_parent) {
+            if ((old->entry.rbe_parent)->entry.rbe_left == old)
+                (old->entry.rbe_parent)->entry.rbe_left = elm;
+            else
+                (old->entry.rbe_parent)->entry.rbe_right = elm;
+            augment(head, old->entry.rbe_parent);
+        } else
+            head->rbh_root = elm;
+        old->entry.rbe_left->entry.rbe_parent = elm;
+        if (old->entry.rbe_right) old->entry.rbe_right->entry.rbe_parent = elm;
+        if (parent) {
+            left = parent;
+            if (head->augment != NULL) {
+                do {
+                    augment(head, left);
+                } while ((left = left->entry.rbe_parent));
+            }
+        }
+        goto color;
+    }
+    parent = elm->entry.rbe_parent;
+    color = elm->entry.rbe_color;
+    if (child) child->entry.rbe_parent = parent;
+    if (parent) {
+        if (parent->entry.rbe_left == elm)
+            parent->entry.rbe_left = child;
+        else
+            parent->entry.rbe_right = child;
+        rb_node_t *goback = parent;
+        if (head->augment != NULL) {
+            do {
+                augment(head, goback);
+            } while ((goback = goback->entry.rbe_parent));
+        }
+    } else
+        head->rbh_root = child;
+color:
+    if (color == 0) rb_tree_remove_color(head, parent, child);
+}
+
+void *rb_tree_insert(rb_tree_t *head, void *elmv) {
+    rb_node_t *elm = elmv;
+    rb_node_t *tmp;
+    rb_node_t *parent = NULL;
+    int comp = 0;
+    tmp = head->rbh_root;
+    while (tmp) {
+        parent = tmp;
+        comp = head->cmp((void *)elm->content, (void *)parent->content);
+        if (comp < 0)
+            tmp = tmp->entry.rbe_left;
+        else if (comp > 0)
+            tmp = tmp->entry.rbe_right;
+        else
+            return tmp;
+    }
+    elm->entry.rbe_parent = parent;
+    elm->entry.rbe_left = elm->entry.rbe_right = NULL;
+    elm->entry.rbe_color = RED;
+    if (parent != NULL) {
+        if (comp < 0)
+            parent->entry.rbe_left = elm;
+        else
+            parent->entry.rbe_right = elm;
+        rb_node_t *goback = parent;
+        if (head->augment != NULL) {
+            do {
+                augment(head, goback);
+            } while ((goback = goback->entry.rbe_parent));
+        }
+    } else
+        head->rbh_root = elm;
+    rb_tree_insert_color(head, elm);
+    return (NULL);
+}
+
+void *rb_tree_find(rb_tree_t *head, void *key) {
+    rb_node_t *tmp = head->rbh_root;
+    int comp;
+    while (tmp) {
+        comp = head->cmp(key, (void *)tmp->content);
+        if (comp < 0)
+            tmp = tmp->entry.rbe_left;
+        else if (comp > 0)
+            tmp = tmp->entry.rbe_right;
+        else
+            return tmp;
+    }
+    return (NULL);
+}
+
+void *rb_tree_next(rb_tree_t *head, void *elmv) {
+    rb_node_t *elm = elmv;
+    if (elm->entry.rbe_right) {
+        elm = elm->entry.rbe_right;
+        while (elm->entry.rbe_left)
+            elm = elm->entry.rbe_left;
+    } else {
+        if (elm->entry.rbe_parent &&
+            (elm == (elm->entry.rbe_parent)->entry.rbe_left))
+            elm = elm->entry.rbe_parent;
+        else {
+            while (elm->entry.rbe_parent &&
+                   (elm == (elm->entry.rbe_parent)->entry.rbe_right))
+                elm = elm->entry.rbe_parent;
+            elm = elm->entry.rbe_parent;
+        }
+    }
+    return elm;
+}
+
+static rb_node_t *rb_tree_minmax(rb_tree_t *head, int val) {
+    rb_node_t *tmp = head->rbh_root;
+    rb_node_t *parent = NULL;
+    while (tmp) {
+        parent = tmp;
+        if (val < 0)
+            tmp = tmp->entry.rbe_left;
+        else
+            tmp = tmp->entry.rbe_right;
+    }
+    return parent;
+};
+
+static void destroy_rb_tree_impl(rb_node_t *node, void (*free_cb)(void *)) {
+    if (node == NULL) return;
+    if (free_cb != NULL) free_cb(node->content);
+    destroy_rb_tree_impl(node->entry.rbe_left, free_cb);
+    destroy_rb_tree_impl(node->entry.rbe_right, free_cb);
+    free(node);
+}
+
+void destroy_rb_tree(rb_tree_t *head, void (*free_cb)(void *)) {
+    destroy_rb_tree_impl(head->rbh_root, free_cb);
+}
diff --git a/src/rb_tree.h b/src/rb_tree.h
new file mode 100644
index 0000000..936cd34
--- /dev/null
+++ b/src/rb_tree.h
@@ -0,0 +1,64 @@
+/*
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef RB_TREE_H_
+#define RB_TREE_H_
+
+#include <stdlib.h>
+
+struct rb_node {
+    struct {
+        struct rb_node *rbe_left;
+        struct rb_node *rbe_right;
+        struct rb_node *rbe_parent;
+        int rbe_color;
+    } entry;
+    char content[0];
+};
+typedef struct rb_node rb_node_t;
+
+struct rb_tree {
+    rb_node_t *rbh_root;
+    int (*cmp)(void *k1, void *k2);
+    void (*augment)(void *elm);
+};
+typedef struct rb_tree rb_tree_t;
+
+void rb_tree_remove(rb_tree_t *, void *iter);
+
+// return a iterator
+void *rb_tree_insert(rb_tree_t *, void *treenode);
+void *rb_tree_find(rb_tree_t *, void *val);
+void *rb_tree_next(rb_tree_t *, void *iter);
+void *rb_tree_min(rb_tree_t *);
+void *rb_tree_max(rb_tree_t *);
+void *rb_tree_left(void *node);
+void *rb_tree_right(void *node);
+void *rb_tree_parent(void *node);
+
+void destroy_rb_tree(rb_tree_t *, void (*freeCb)(void *));
+
+#endif
+
diff --git a/src/str.c b/src/str.c
new file mode 100644
index 0000000..22aebac
--- /dev/null
+++ b/src/str.c
@@ -0,0 +1,131 @@
+#include "str.h"
+
+#include <ctype.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+char **str_split(char *str, char delim) {
+    char **ret;
+
+    if (str == NULL) return NULL;
+    if (*str == '\n') {
+        ret = malloc(sizeof(char *));
+        *ret = NULL;
+        return ret;
+    }
+    int count = 0;
+    char *begin = str;
+    for (char *p = str; *p != '\0'; p++) {
+        if (*p != delim && !(delim == '\0' && isspace(*p))) {
+            continue;
+        }
+        int size = p - begin;
+        if (size > 0) count++;
+    }
+    count++;
+    ret = malloc((count + 1) * sizeof(char *));
+    memset(ret, 0, (count + 1) * sizeof(char *));
+
+    begin = str;
+    int i = 0;
+    bool finished = false;
+    for (char *p = str; !finished; p++) {
+        if (*p == '\0') finished = true;
+        if (*p != delim && *p != '\0' && !(delim == '\0' && isspace(*p))) {
+            continue;
+        }
+        int size = p - begin;
+        if (size == 0) {
+            begin = p + 1;
+            continue;
+        }
+        char *buf = malloc(sizeof(char) * (size + 1));
+        buf[size] = '\0';
+        memcpy(buf, begin, size * sizeof(char));
+        begin = p + 1;
+        ret[i] = buf;
+        i++;
+    }
+    return ret;
+}
+
+void destroy_str_list(char **list) {
+    char **p = list;
+    while (*p != NULL) {
+        free(*p);
+        p++;
+    }
+    free(list);
+}
+
+char *str_strip(char *str) {
+    if (str == NULL) return NULL;
+    int len = strlen(str);
+    char *begin = str;
+    char *end = str + len - 1;
+    while (isspace(*begin) && begin < end) {
+        begin++;
+    }
+    while (isspace(*end) && end >= begin) {
+        end--;
+    }
+    len = end - begin + 1;
+    char *buf = malloc(sizeof(char) * (len) + 1);
+    buf[len] = '\0';
+    memcpy(buf, begin, len);
+    return buf;
+}
+
+void init_str_builder(str_builder_t *sb) {
+    *sb = (str_builder_t){.size = 0, .cap = 16};
+    sb->buf = malloc(sizeof(char) * 17);
+}
+
+static void sb_reserve(str_builder_t *sb, int extra) {
+    if (sb->size + extra <= sb->cap) {
+        return;
+    }
+    int new_cap = (sb->size + extra) * 2;
+    sb->buf = realloc(sb->buf, new_cap + 1);
+    memset(sb->buf + sb->cap, 0, new_cap - sb->cap + 1);
+    sb->cap = new_cap;
+}
+
+void str_builder_append(str_builder_t *sb, char *format, ...) {
+    va_list va1;
+    va_list va2;
+    va_start(va1, format);
+    va_copy(va2, va1);
+    int size = vsnprintf(NULL, 0, format, va1);
+    sb_reserve(sb, size);
+    vsnprintf(sb->buf + sb->size, sb->cap - sb->size + 1, format, va2);
+}
+
+void str_builder_append_char(str_builder_t *sb, char c) {
+    sb_reserve(sb, 1);
+    sb->buf[sb->size] = c;
+    sb->size++;
+}
+
+char *fgetline(FILE *fp) {
+    str_builder_t sb;
+    init_str_builder(&sb);
+    while (true) {
+        int c = fgetc(fp);
+        if (c == EOF && sb.size == 0) return NULL;
+        if (c != EOF) str_builder_append_char(&sb, c);
+        if (c == EOF || c == '\n') return sb.buf;
+    }
+    return NULL;
+}
+
+int fpeek(FILE *fp) {
+    int c = fgetc(fp);
+    if (c == EOF) return c;
+    ungetc(c, fp);
+    return c;
+}
diff --git a/src/str.h b/src/str.h
new file mode 100644
index 0000000..441451e
--- /dev/null
+++ b/src/str.h
@@ -0,0 +1,24 @@
+#ifndef ALGDS_STR_H_
+#define ALGDS_STR_H_
+
+#include <stdio.h>
+
+char *str_strip(char *str);
+char **str_split(char *str, char delim);
+void destroy_str_list(char **list);
+
+struct str_builder {
+    char *buf;
+    int size;
+    int cap;
+};
+typedef struct str_builder str_builder_t;
+
+void init_str_builder(str_builder_t *sb);
+void str_builder_append(str_builder_t *sb, char *format, ...);
+void str_builder_append_char(str_builder_t *sb, char c);
+
+char *fgetline(FILE *fp);
+int fpeek(FILE *fp);
+
+#endif
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;
+}