git init

12 files changed, 953 insertions, 0 deletions

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