--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/ploki/list.c	Fri Dec 20 22:18:50 2013 +0000
@@ -0,0 +1,219 @@
+#include "list.h"
+#include "val.h"
+#include "xmalloc.h"
+
+#include <string.h>
+#include <assert.h>
+
+typedef struct li_whale whale;
+
+static whale *incr(whale *wp) {
+	assert(wp->refs > 0);
+	++wp->refs;
+	return wp;
+}
+
+static void decr(whale *wp) {
+	assert(wp->refs > 0);
+	if (!--wp->refs) {
+		while (wp->length) {
+			--wp->length;
+			v_delete(wp->field[wp->length]);
+		}
+		xfree(wp->field);
+		xfree(wp);
+	}
+}
+
+enum {MAGIC = 7};
+
+struct list *li_new(void) {
+	struct list *l = xmalloc(1, sizeof *l);
+	l->lwp = xmalloc(1, sizeof *l->lwp);
+	l->lwp->field = xmalloc(l->lwp->size = MAGIC, sizeof *l->lwp->field);
+	l->lwp->length = 0;
+	l->lwp->refs = 1;
+	l->offset = 0;
+	l->length = 0;
+	return l;
+}
+
+struct list *li_dup(const struct list *k) {
+	struct list *l = xmalloc(1, sizeof *l);
+	l->lwp = incr(k->lwp);
+	l->offset = k->offset;
+	l->length = k->length;
+	return l;
+}
+
+static void decouple(struct list *l, size_t slack) {
+	size_t i, n;
+	whale *const wp = l->lwp;
+	struct val **const field = wp->field + l->offset, **nfield;
+	assert(wp->refs > 0);
+	if (wp->refs == 1) {
+		return;
+	}
+	l->lwp = xmalloc(1, sizeof *l->lwp);
+	n = l->length;
+	l->lwp->field = nfield = xmalloc(l->lwp->size = n + slack > MAGIC ? n + slack : MAGIC, sizeof *l->lwp->field);
+	for (i = 0; i < n; ++i) {
+		v_set(nfield[i] = v_undef(), field[i]);
+	}
+	l->lwp->length = n;
+	l->lwp->refs = 1;
+	l->offset = 0;
+	decr(wp);
+}
+
+void li_decouple(struct list *l) {
+	decouple(l, 1);
+}
+
+void li_delete(struct list *l) {
+	decr(l->lwp);
+	xfree(l);
+}
+
+size_t (li_length)(const struct list *l) {
+	return li_length(l);
+}
+
+struct val *li_at(const struct list *l, size_t i) {
+	return i < l->length ? l->lwp->field[l->offset + i] : NULL;
+}
+
+int li_cmp(const struct list *k, const struct list *l) {
+	const size_t len_k = li_length(k), len_l = li_length(l);
+	struct val **const field_k = k->lwp->field + k->offset, **const field_l = l->lwp->field + l->offset;
+	size_t i;
+
+	for (i = 0; i < len_k && i < len_l; ++i) {
+		const int tmp = v_cmp_ls(field_k[i], field_l[i]);
+		if (tmp) {
+			return tmp;
+		}
+	}
+	if (i < len_k) {
+		return 1;
+	}
+	if (i < len_l) {
+		return -1;
+	}
+	return 0;
+}
+
+void (li_zero)(struct list *l) {
+	li_zero(l);
+}
+
+static void vpswap(struct val **p, struct val **q) {
+	struct val *tmp = *p;
+	*p = *q;
+	*q = tmp;
+}
+
+void li_push(struct list *l, struct val *v) {
+	struct li_whale *wp = l->lwp;
+	const size_t off = l->offset, len = l->length, wlen = wp->length, wsiz = wp->size;
+	struct val **field = wp->field;
+	assert(wp->refs > 0);
+	if (wp->refs > 1) {
+		decouple(l, 1);
+		wp = l->lwp;
+		field = wp->field;
+	} else if (off + len < wlen) {
+		v_delete(field[off + len]);
+	} else if (wlen < wsiz) {
+		/* */
+	} else if (off) {
+		size_t i;
+		for (i = 0; i < len; ++i) {
+			vpswap(&field[i], &field[off + i]);
+		}
+		l->offset = 0;
+		v_delete(field[len]);
+	} else {
+		wp->field = field = xrealloc(field, wp->size *= 2);
+	}
+	field[l->offset + l->length++] = v;
+	if (l->offset + l->length > wlen) {
+		wp->length = l->offset + l->length;
+	}
+}
+
+void li_push_cpy(struct list *l, const struct val *v) {
+	struct li_whale *wp = l->lwp;
+	const size_t off = l->offset, len = l->length, wlen = wp->length, wsiz = wp->size;
+	struct val **field = wp->field;
+	assert(wp->refs > 0);
+	if (wp->refs > 1) {
+		decouple(l, 1);
+		wp = l->lwp;
+		field = wp->field;
+		field[l->offset + len] = v_undef();
+	} else if (off + len < wlen) {
+		/* */
+	} else if (wlen < wsiz) {
+		field[off + len] = v_undef();
+	} else if (off) {
+		size_t i;
+		for (i = 0; i < len; ++i) {
+			vpswap(&field[i], &field[off + i]);
+		}
+		l->offset = 0;
+	} else {
+		wp->field = field = xrealloc(field, wp->size *= 2);
+		field[len] = v_undef();
+	}
+	v_set(field[l->offset + l->length++], v);
+	if (l->offset + l->length > wlen) {
+		wp->length = l->offset + l->length;
+	}
+}
+
+void li_append(struct list *k, const struct list *l) {
+	struct val **const field = l->lwp->field + l->offset;
+	const size_t len = li_length(l);
+	size_t i;
+
+	for (i = 0; i < len; ++i) {
+		li_push_cpy(k, field[i]);
+	}
+}
+
+void li_reverse(struct list *l) {
+	struct val **field;
+	size_t i, len;
+
+	len = li_length(l);
+	if (len < 2) {
+		return;
+	}
+
+	li_decouple(l);
+
+	field = l->lwp->field + l->offset;
+
+	for (i = 0; i < len / 2; ++i) {
+		vpswap(&field[i], &field[len - i - 1]);
+	}
+}
+
+void li_trunc(struct list *l, size_t n) {
+	if (l->length > n) {
+		if (!(l->length = n)) {
+			l->offset = 0;
+		}
+	}
+}
+
+void li_shift(struct list *l, size_t n) {
+	if (n >= li_length(l)) {
+		li_zero(l);
+		return;
+	}
+
+	l->offset += n;
+	l->length -= n;
+}