--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/ploki/mars.c	Fri Dec 20 22:18:50 2013 +0000
@@ -0,0 +1,85 @@
+#include "Str.h"
+#include "mars.h"
+#include "op.h"
+#include "xmalloc.h"
+
+enum {MAGIC = 128};
+
+static void null(struct mars **p, size_t n) {
+	for (; n; --n) {
+		p[n - 1] = NULL;
+	}
+}
+
+void ma_init(struct mars *m) {
+	m->data = NULL;
+	m->table = xmalloc(m->size = MAGIC, sizeof *m->table);
+	null(m->table, m->size);
+}
+
+void ma_end(struct mars *m) {
+	for (; m->size; --m->size) {
+		if (m->table[m->size - 1]) {
+			ma_end(m->table[m->size - 1]);
+			xfree(m->table[m->size - 1]);
+		}
+	}
+	xfree(m->table);
+}
+
+int ma_enter(struct mars *m, const String *key, struct op *value) {
+	size_t p;
+
+	for (p = 0; p < St_len(key); ++p) {
+		size_t tmp = ST_INDEX(key, p);
+		if (m->size <= tmp) {
+			m->table = xrealloc(m->table, m->size * 2);
+			null(m->table + m->size, m->size);
+			m->size *= 2;
+		}
+		if (!m->table[tmp]) {
+			m->table[tmp] = xmalloc(1, sizeof *m->table[tmp]);
+			ma_init(m->table[tmp]);
+		}
+		m = m->table[tmp];
+	}
+
+	if (m->data) {
+		return -1;
+	}
+	m->data = value;
+	return 0;
+}
+
+int ma_exists(const struct mars *m, const String *key) {
+	size_t p;
+	const struct op *ret = NULL;
+
+	for (p = 0; p < St_len(key); ++p) {
+		size_t tmp = ST_INDEX(key, p);
+		ret = m->data;
+		if (tmp >= m->size || !m->table[tmp]) {
+			return 0;
+		}
+		m = m->table[tmp];
+	}
+	return ret != NULL;
+}
+
+struct op *ma_find(const struct mars *m, String *key) {
+	size_t p;
+	struct op *ret = NULL;
+
+	for (p = 0; p < St_len(key); ++p) {
+		size_t tmp = ST_INDEX(key, p);
+		ret = m->data;
+		if (tmp >= m->size || !m->table[tmp]) {
+			break;
+		}
+		m = m->table[tmp];
+	}
+	if (ret) {
+		St_del(key, 0, p);
+	}
+	return ret;
+}