Adding debian version 1.8.3-2.debian/1.8.3-2

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

20 files changed, 2335 insertions, 0 deletions

diff --git a/debian/vendor-h2o/deps/klib/test/Makefile b/debian/vendor-h2o/deps/klib/test/Makefile
new file mode 100644
index 0000000..a392c8e
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/Makefile
@@ -0,0 +1,60 @@
+CC=gcc
+CXX=g++
+CFLAGS=-g -Wall -O2 -I..
+CXXFLAGS=$(CFLAGS)
+PROGS=kbtree_test khash_keith khash_keith2 khash_test klist_test kseq_test kseq_bench \
+		kseq_bench2 ksort_test ksort_test-stl kvec_test kmin_test kstring_bench kstring_bench2 kstring_test \
+		kthread_test
+
+all:$(PROGS)
+
+clean:
+		rm -fr $(PROGS) *.dSYM a.out
+
+kbtree_test:kbtree_test.c ../kbtree.h
+		$(CC) $(CFLAGS) -o $@ kbtree_test.c
+
+khash_keith:khash_keith.c ../khash.h
+		$(CC) $(CFLAGS) -o $@ khash_keith.c
+
+khash_keith2:khash_keith2.c ../khash.h
+		$(CC) $(CFLAGS) -o $@ khash_keith2.c
+
+khash_test:khash_test.c ../khash.h
+		$(CC) $(CFLAGS) -o $@ khash_test.c
+
+klist_test:klist_test.c ../klist.h
+		$(CC) $(CFLAGS) -o $@ klist_test.c
+
+kseq_test:kseq_test.c ../kseq.h
+		$(CC) $(CFLAGS) -o $@ kseq_test.c -lz
+
+kseq_bench:kseq_bench.c ../kseq.h
+		$(CC) $(CFLAGS) -o $@ kseq_bench.c -lz
+
+kseq_bench2:kseq_bench2.c ../kseq.h
+		$(CC) $(CFLAGS) -o $@ kseq_bench2.c -lz
+
+ksort_test:ksort_test.c ../ksort.h
+		$(CC) $(CFLAGS) -o $@ ksort_test.c
+
+ksort_test-stl:ksort_test.cc ../ksort.h
+		$(CXX) $(CXXFLAGS) -o $@ ksort_test.cc
+
+kvec_test:kvec_test.cc ../kvec.h
+		$(CXX) $(CXXFLAGS) -o $@ kvec_test.cc
+
+kmin_test:kmin_test.c ../kmath.h ../kmath.c
+		$(CC) $(CFLAGS) -o $@ kmin_test.c ../kmath.c
+
+kstring_bench:kstring_bench.c ../kstring.h ../kstring.c
+		$(CC) $(CFLAGS) -o $@ kstring_bench.c ../kstring.c
+
+kstring_bench2:kstring_bench2.c ../kstring.h ../kstring.c
+		$(CC) $(CFLAGS) -o $@ kstring_bench2.c ../kstring.c
+
+kstring_test:kstring_test.c ../kstring.h ../kstring.c
+		$(CC) $(CFLAGS) -o $@ kstring_test.c ../kstring.c
+
+kthread_test:kthread_test.c ../kthread.c
+		$(CC) $(CFLAGS) -fopenmp -o $@ kthread_test.c ../kthread.c
diff --git a/debian/vendor-h2o/deps/klib/test/kbit_test.c b/debian/vendor-h2o/deps/klib/test/kbit_test.c
new file mode 100644
index 0000000..3ae3bd3
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kbit_test.c
@@ -0,0 +1,137 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <time.h>
+#include <emmintrin.h>
+#include "kbit.h"
+
+// from bowtie-0.9.8.1
+inline static int bt1_pop64(uint64_t x) // the kbi_popcount64() equivalence; similar to popcount_2() in wiki
+{
+   x -= ((x >> 1) & 0x5555555555555555llu);
+   x = (x & 0x3333333333333333llu) + ((x >> 2) & 0x3333333333333333llu);
+   x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0Fllu;
+   x = x + (x >> 8);
+   x = x + (x >> 16);
+   x = x + (x >> 32);
+   return x & 0x3F;
+}
+
+inline static int bt1_countInU64(uint64_t dw, int c) // the kbi_DNAcount64() equivalence
+{
+	uint64_t dwA  = dw &  0xAAAAAAAAAAAAAAAAllu;
+	uint64_t dwNA = dw & ~0xAAAAAAAAAAAAAAAAllu;
+	uint64_t tmp;
+	switch (c) {
+	case 0: tmp = (dwA >> 1) | dwNA; break;
+	case 1: tmp = ~(dwA >> 1) & dwNA; break;
+	case 2: tmp = (dwA >> 1) & ~dwNA; break;
+	default: tmp = (dwA >> 1) & dwNA;
+	}
+	tmp = bt1_pop64(tmp);
+	if (c == 0) tmp = 32 - tmp;
+	return (int)tmp;
+}
+
+// from bigmagic
+static uint32_t sse2_bit_count32(const __m128i* block, const __m128i* block_end)
+{
+    const unsigned mu1 = 0x55555555;
+    const unsigned mu2 = 0x33333333;
+    const unsigned mu3 = 0x0F0F0F0F;
+    const unsigned mu4 = 0x0000003F;
+
+	uint32_t tcnt[4];
+
+    // Loading masks
+    __m128i m1 = _mm_set_epi32 (mu1, mu1, mu1, mu1);
+    __m128i m2 = _mm_set_epi32 (mu2, mu2, mu2, mu2);
+    __m128i m3 = _mm_set_epi32 (mu3, mu3, mu3, mu3);
+    __m128i m4 = _mm_set_epi32 (mu4, mu4, mu4, mu4);
+    __m128i mcnt;
+    mcnt = _mm_xor_si128(m1, m1); // cnt = 0
+
+    __m128i tmp1, tmp2;
+    do
+    {        
+        __m128i b = _mm_load_si128(block);
+        ++block;
+
+        // b = (b & 0x55555555) + (b >> 1 & 0x55555555);
+        tmp1 = _mm_srli_epi32(b, 1);                    // tmp1 = (b >> 1 & 0x55555555)
+        tmp1 = _mm_and_si128(tmp1, m1); 
+        tmp2 = _mm_and_si128(b, m1);                    // tmp2 = (b & 0x55555555)
+        b    = _mm_add_epi32(tmp1, tmp2);               //  b = tmp1 + tmp2
+
+        // b = (b & 0x33333333) + (b >> 2 & 0x33333333);
+        tmp1 = _mm_srli_epi32(b, 2);                    // (b >> 2 & 0x33333333)
+        tmp1 = _mm_and_si128(tmp1, m2); 
+        tmp2 = _mm_and_si128(b, m2);                    // (b & 0x33333333)
+        b    = _mm_add_epi32(tmp1, tmp2);               // b = tmp1 + tmp2
+
+        // b = (b + (b >> 4)) & 0x0F0F0F0F;
+        tmp1 = _mm_srli_epi32(b, 4);                    // tmp1 = b >> 4
+        b = _mm_add_epi32(b, tmp1);                     // b = b + (b >> 4)
+        b = _mm_and_si128(b, m3);                       //           & 0x0F0F0F0F
+
+        // b = b + (b >> 8);
+        tmp1 = _mm_srli_epi32 (b, 8);                   // tmp1 = b >> 8
+        b = _mm_add_epi32(b, tmp1);                     // b = b + (b >> 8)
+
+        // b = (b + (b >> 16)) & 0x0000003F;
+        tmp1 = _mm_srli_epi32 (b, 16);                  // b >> 16
+        b = _mm_add_epi32(b, tmp1);                     // b + (b >> 16)
+        b = _mm_and_si128(b, m4);                       // (b >> 16) & 0x0000003F;
+
+        mcnt = _mm_add_epi32(mcnt, b);                  // mcnt += b
+
+    } while (block < block_end);
+
+    _mm_store_si128((__m128i*)tcnt, mcnt);
+
+    return tcnt[0] + tcnt[1] + tcnt[2] + tcnt[3];
+}
+
+int main(void)
+{
+	int i, N = 100000000;
+	uint64_t *x, cnt;
+	clock_t t;
+	int c = 1;
+
+	x = (uint64_t*)calloc(N, 8);
+	srand48(11);
+	for (i = 0; i < N; ++i)
+		x[i] = (uint64_t)lrand48() << 32 ^ lrand48();
+
+	fprintf(stderr, "\n===> Calculate # of 1 in an integer (popcount) <===\n");
+
+	t = clock(); cnt = 0;
+	for (i = 0; i < N; ++i) cnt += kbi_popcount64(x[i]);
+	fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "kbit", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC);
+
+	t = clock(); cnt = 0;
+	for (i = 0; i < N; ++i) cnt += bt1_pop64(x[i]);
+	fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "wiki-popcount_2", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC);
+
+	t = clock(); cnt = 0;
+	for (i = 0; i < N; ++i) cnt += __builtin_popcountl(x[i]);
+	fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "__builtin_popcountl", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC);
+
+	t = clock(); cnt = 0;
+	cnt += sse2_bit_count32((__m128i*)x, (__m128i*)(x+N));
+	fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "SSE2-32bit", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC);
+
+	fprintf(stderr, "\n===> Count '%c' in 2-bit encoded integers <===\n", "ACGT"[c]);
+
+	t = clock(); cnt = 0;
+	for (i = 0; i < N; ++i) cnt += kbi_DNAcount64(x[i], c);
+	fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "kbit", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC);
+
+	t = clock(); cnt = 0;
+	for (i = 0; i < N; ++i) cnt += bt1_countInU64(x[i], c);
+	fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "bowtie1", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC);
+
+	fprintf(stderr, "\n");
+	free(x);
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kbtree_test.c b/debian/vendor-h2o/deps/klib/test/kbtree_test.c
new file mode 100644
index 0000000..8e10687
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kbtree_test.c
@@ -0,0 +1,94 @@
+#include <stdio.h>
+#include <assert.h>
+#include <time.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+
+typedef const char *str_t;
+
+#include "kbtree.h"
+KBTREE_INIT(int, uint32_t, kb_generic_cmp)
+KBTREE_INIT(str, str_t, kb_str_cmp)
+
+static int data_size = 5000000;
+static unsigned *int_data;
+static char **str_data;
+
+void ht_init_data()
+{
+	int i;
+	char buf[256];
+	printf("--- generating data... ");
+	srand48(11);
+	int_data = (unsigned*)calloc(data_size, sizeof(unsigned));
+	str_data = (char**)calloc(data_size, sizeof(char*));
+	for (i = 0; i < data_size; ++i) {
+		int_data[i] = (unsigned)(data_size * drand48() / 4) * 271828183u;
+		sprintf(buf, "%x", int_data[i]);
+		str_data[i] = strdup(buf);
+	}
+	printf("done!\n");
+}
+void ht_destroy_data()
+{
+	int i;
+	for (i = 0; i < data_size; ++i) free(str_data[i]);
+	free(str_data); free(int_data);
+}
+
+void ht_khash_int()
+{
+	int i;
+	unsigned *data = int_data;
+	uint32_t *l, *u;
+	kbtree_t(int) *h;
+
+	h = kb_init(int, KB_DEFAULT_SIZE);
+	for (i = 0; i < data_size; ++i) {
+		if (kb_get(int, h, data[i]) == 0) kb_put(int, h, data[i]);
+		else kb_del(int, h, data[i]);
+	}
+	printf("[ht_khash_int] size: %d\n", kb_size(h));
+	if (1) {
+		int cnt = 0;
+		uint32_t x, y;
+		kb_interval(int, h, 2174625464u, &l, &u);
+		printf("interval for 2174625464: (%u, %u)\n", l? *l : 0, u? *u : 0);
+#define traverse_f(p) { if (cnt == 0) y = *p; ++cnt; }
+		__kb_traverse(uint32_t, h, traverse_f);
+		__kb_get_first(uint32_t, h, x);
+		printf("# of elements from traversal: %d\n", cnt);
+		printf("first element: %d == %d\n", x, y);
+	}
+	__kb_destroy(h);
+}
+void ht_khash_str()
+{
+	int i;
+	char **data = str_data;
+	kbtree_t(str) *h;
+
+	h = kb_init(str, KB_DEFAULT_SIZE);
+	for (i = 0; i < data_size; ++i) {
+		if (kb_get(str, h, data[i]) == 0) kb_put(str, h, data[i]);
+		else kb_del(str, h, data[i]);
+	}
+	printf("[ht_khash_int] size: %d\n", kb_size(h));
+	__kb_destroy(h);
+}
+void ht_timing(void (*f)(void))
+{
+	clock_t t = clock();
+	(*f)();
+	printf("[ht_timing] %.3lf sec\n", (double)(clock() - t) / CLOCKS_PER_SEC);
+}
+int main(int argc, char *argv[])
+{
+	if (argc > 1) data_size = atoi(argv[1]);
+	ht_init_data();
+	ht_timing(ht_khash_int);
+	ht_timing(ht_khash_str);
+	ht_destroy_data();
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kgraph_test.c b/debian/vendor-h2o/deps/klib/test/kgraph_test.c
new file mode 100644
index 0000000..3da1cd7
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kgraph_test.c
@@ -0,0 +1,26 @@
+#include <stdio.h>
+#include "kgraph.h"
+
+KHASH_INIT2(e32, extern, uint32_t, int, 1, kh_int_hash_func, kh_int_hash_equal)
+
+typedef struct {
+	int i;
+	khash_t(e32) *_arc;
+} vertex_t;
+
+KGRAPH_INIT(g, extern, vertex_t, int, e32)
+KGRAPH_PRINT(g, extern)
+
+int main()
+{
+	int *pb, *pe;
+	kgraph_t(g) *g;
+	g = kg_init_g();
+	kg_put_a_g(g, 10, 20, 0, &pb, &pe);
+	kg_put_a_g(g, 20, 30, 0, &pb, &pe);
+	kg_put_a_g(g, 30, 10, 1, &pb, &pe);
+	kg_del_v_g(g, 20);
+	kg_print_g(g);
+	kg_destroy_g(g);
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/khash_keith.c b/debian/vendor-h2o/deps/klib/test/khash_keith.c
new file mode 100644
index 0000000..ddd755a
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/khash_keith.c
@@ -0,0 +1,95 @@
+/*
+ * This is an optimized version of the following C++ program:
+ *
+ *   http://keithlea.com/javabench/src/cpp/hash.cpp
+ *
+ * Keith in his benchmark (http://keithlea.com/javabench/data) showed that the
+ * Java implementation is twice as fast as the C++ version. In fact, this is
+ * only because the C++ implementation is substandard. Most importantly, Keith
+ * is using "sprintf()" to convert an integer to a string, which is known to be
+ * extremely inefficient.
+ */
+#include <stdio.h>
+#include "khash.h"
+KHASH_MAP_INIT_STR(str, int)
+
+inline void int2str(int c, int base, char *ret)
+{
+	const char *tab = "0123456789abcdef";
+	if (c == 0) ret[0] = '0', ret[1] = 0;
+	else {
+		int l, x, y;
+		char buf[16];
+		for (l = 0, x = c < 0? -c : c; x > 0; x /= base) buf[l++] = tab[x%base];
+		if (c < 0) buf[l++] = '-';
+		for (x = l - 1, y = 0; x >= 0; --x) ret[y++] = buf[x];
+		ret[y] = 0;
+	}
+}
+
+#ifndef _USE_STRDUP
+#define BLOCK_SIZE 0x100000
+int main(int argc, char *argv[])
+{
+	char **mem = 0;
+	int i, l, n = 1000000, ret, block_end = 0, curr = 0, c = 0;
+	khash_t(str) *h;
+	h = kh_init(str);
+	if (argc > 1) n = atoi(argv[1]);
+	mem = malloc(sizeof(void*));
+	mem[0] = malloc(BLOCK_SIZE); // memory buffer to avoid memory fragmentation
+	curr = block_end = 0;
+	for (i = 1; i <= n; ++i) {
+		char buf[16];
+		int2str(i, 16, buf);
+		khint_t k = kh_put(str, h, buf, &ret);
+		l = strlen(buf) + 1;
+		if (block_end + l > BLOCK_SIZE) {
+			++curr; block_end = 0;
+			mem = realloc(mem, (curr + 1) * sizeof(void*));
+			mem[curr] = malloc(BLOCK_SIZE);
+		}
+		memcpy(mem[curr] + block_end, buf, l);
+		kh_key(h, k) = mem[curr] + block_end;
+		block_end += l;
+		kh_val(h, k) = i;
+	}
+	for (i = 1; i <= n; ++i) {
+		char buf[16];
+		int2str(i, 10, buf);
+		khint_t k = kh_get(str, h, buf);
+		if (k != kh_end(h)) ++c;
+	}
+	printf("%d\n", c);
+	for (ret = 0; ret <= curr; ++ret) free(mem[ret]);
+	free(mem);
+	kh_destroy(str, h);
+	return 0;
+}
+#else // _USE_STRDUP
+int main(int argc, char *argv[])
+{
+	int i, l, n = 1000000, ret, c = 0;
+	khash_t(str) *h;
+	khint_t k;
+	h = kh_init(str);
+	if (argc > 1) n = atoi(argv[1]);
+	for (i = 1; i <= n; ++i) {
+		char buf[16];
+		int2str(i, 16, buf);
+		k = kh_put(str, h, strdup(buf), &ret);
+		kh_val(h, k) = i;
+	}
+	for (i = 1; i <= n; ++i) {
+		char buf[16];
+		int2str(i, 10, buf);
+		k = kh_get(str, h, buf);
+		if (k != kh_end(h)) ++c;
+	}
+	for (k = kh_begin(h); k != kh_end(h); ++k) // explicitly freeing memory takes 10-20% CPU time.
+		if (kh_exist(h, k)) free((char*)kh_key(h, k));
+	printf("%d\n", c);
+	kh_destroy(str, h);
+	return 0;
+}
+#endif
diff --git a/debian/vendor-h2o/deps/klib/test/khash_keith2.c b/debian/vendor-h2o/deps/klib/test/khash_keith2.c
new file mode 100644
index 0000000..b9df9b7
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/khash_keith2.c
@@ -0,0 +1,67 @@
+/*
+ * This is an optimized version of the following C++ program:
+ *
+ *   http://keithlea.com/javabench/src/cpp/hash.cpp
+ *
+ * Keith in his benchmark (http://keithlea.com/javabench/data) showed that the
+ * Java implementation is twice as fast as the C++ version. In fact, this is
+ * only because the C++ implementation is substandard. Most importantly, Keith
+ * is using "sprintf()" to convert an integer to a string, which is known to be
+ * extremely inefficient.
+ */
+#include <stdio.h>
+#include "khash.h"
+KHASH_MAP_INIT_STR(str, int)
+
+inline void int2str(int c, int base, char *ret)
+{
+	const char *tab = "0123456789abcdef";
+	if (c == 0) ret[0] = '0', ret[1] = 0;
+	else {
+		int l, x, y;
+		char buf[16];
+		for (l = 0, x = c < 0? -c : c; x > 0; x /= base) buf[l++] = tab[x%base];
+		if (c < 0) buf[l++] = '-';
+		for (x = l - 1, y = 0; x >= 0; --x) ret[y++] = buf[x];
+		ret[y] = 0;
+	}
+}
+
+int main(int argc, char *argv[])
+{
+	int i, l, n = 1000, ret;
+	khash_t(str) *h, *h2;
+	khint_t k;
+	h = kh_init(str);
+	h2 = kh_init(str);
+	if (argc > 1) n = atoi(argv[1]);
+	for (i = 0; i < 10000; ++i) {
+		char buf[32];
+		strcpy(buf, "foo_");
+		int2str(i, 10, buf+4);
+		k = kh_put(str, h, strdup(buf), &ret);
+		kh_val(h, k) = i;
+	}
+	for (i = 0; i < n; ++i) {
+		for (k = kh_begin(h); k != kh_end(h); ++k) {
+			if (kh_exist(h, k)) {
+				khint_t k2 = kh_put(str, h2, kh_key(h, k), &ret);
+				if (ret) { // absent
+					kh_key(h2, k2) = strdup(kh_key(h, k));
+					kh_val(h2, k2) = kh_val(h, k);
+				} else kh_val(h2, k2) += kh_val(h, k);
+			}
+		}
+	}
+	k = kh_get(str, h, "foo_1"); printf("%d", kh_val(h, k));
+	k = kh_get(str, h, "foo_9999"); printf(" %d", kh_val(h, k));
+	k = kh_get(str, h2, "foo_1"); printf(" %d", kh_val(h2, k));
+	k = kh_get(str, h2, "foo_9999"); printf(" %d\n", kh_val(h2, k));
+	for (k = kh_begin(h); k != kh_end(h); ++k)
+		if (kh_exist(h, k)) free((char*)kh_key(h, k));
+	for (k = kh_begin(h2); k != kh_end(h2); ++k)
+		if (kh_exist(h2, k)) free((char*)kh_key(h2, k));
+	kh_destroy(str, h);
+	kh_destroy(str, h2);
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/khash_test.c b/debian/vendor-h2o/deps/klib/test/khash_test.c
new file mode 100644
index 0000000..8d6687f
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/khash_test.c
@@ -0,0 +1,141 @@
+#include <stdio.h>
+#include <assert.h>
+#include <time.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "khash.h"
+KHASH_SET_INIT_STR(str)
+KHASH_MAP_INIT_INT(int, unsigned char)
+
+typedef struct {
+	unsigned key;
+	unsigned char val;
+} int_unpack_t;
+
+typedef struct {
+	unsigned key;
+	unsigned char val;
+} __attribute__ ((__packed__)) int_packed_t;
+
+#define hash_eq(a, b) ((a).key == (b).key)
+#define hash_func(a) ((a).key)
+
+KHASH_INIT(iun, int_unpack_t, char, 0, hash_func, hash_eq)
+KHASH_INIT(ipk, int_packed_t, char, 0, hash_func, hash_eq)
+
+static int data_size = 5000000;
+static unsigned *int_data;
+static char **str_data;
+
+void ht_init_data()
+{
+	int i;
+	char buf[256];
+	khint32_t x = 11;
+	printf("--- generating data... ");
+	int_data = (unsigned*)calloc(data_size, sizeof(unsigned));
+	str_data = (char**)calloc(data_size, sizeof(char*));
+	for (i = 0; i < data_size; ++i) {
+		int_data[i] = (unsigned)(data_size * ((double)x / UINT_MAX) / 4) * 271828183u;
+		sprintf(buf, "%x", int_data[i]);
+		str_data[i] = strdup(buf);
+		x = 1664525L * x + 1013904223L;
+	}
+	printf("done!\n");
+}
+
+void ht_destroy_data()
+{
+	int i;
+	for (i = 0; i < data_size; ++i) free(str_data[i]);
+	free(str_data); free(int_data);
+}
+
+void ht_khash_int()
+{
+	int i, ret;
+	unsigned *data = int_data;
+	khash_t(int) *h;
+	unsigned k;
+
+	h = kh_init(int);
+	for (i = 0; i < data_size; ++i) {
+		k = kh_put(int, h, data[i], &ret);
+		kh_val(h, k) = i&0xff;
+		if (!ret) kh_del(int, h, k);
+	}
+	printf("[ht_khash_int] size: %u\n", kh_size(h));
+	kh_destroy(int, h);
+}
+
+void ht_khash_str()
+{
+	int i, ret;
+	char **data = str_data;
+	khash_t(str) *h;
+	unsigned k;
+
+	h = kh_init(str);
+	for (i = 0; i < data_size; ++i) {
+		k = kh_put(str, h, data[i], &ret);
+		if (!ret) kh_del(str, h, k);
+	}
+	printf("[ht_khash_int] size: %u\n", kh_size(h));
+	kh_destroy(str, h);
+}
+
+void ht_khash_unpack()
+{
+	int i, ret;
+	unsigned *data = int_data;
+	khash_t(iun) *h;
+	unsigned k;
+
+	h = kh_init(iun);
+	for (i = 0; i < data_size; ++i) {
+		int_unpack_t x;
+		x.key = data[i]; x.val = i&0xff;
+		k = kh_put(iun, h, x, &ret);
+		if (!ret) kh_del(iun, h, k);
+	}
+	printf("[ht_khash_unpack] size: %u (sizeof=%ld)\n", kh_size(h), sizeof(int_unpack_t));
+	kh_destroy(iun, h);
+}
+
+void ht_khash_packed()
+{
+	int i, ret;
+	unsigned *data = int_data;
+	khash_t(ipk) *h;
+	unsigned k;
+
+	h = kh_init(ipk);
+	for (i = 0; i < data_size; ++i) {
+		int_packed_t x;
+		x.key = data[i]; x.val = i&0xff;
+		k = kh_put(ipk, h, x, &ret);
+		if (!ret) kh_del(ipk, h, k);
+	}
+	printf("[ht_khash_packed] size: %u (sizeof=%ld)\n", kh_size(h), sizeof(int_packed_t));
+	kh_destroy(ipk, h);
+}
+
+void ht_timing(void (*f)(void))
+{
+	clock_t t = clock();
+	(*f)();
+	printf("[ht_timing] %.3lf sec\n", (double)(clock() - t) / CLOCKS_PER_SEC);
+}
+
+int main(int argc, char *argv[])
+{
+	if (argc > 1) data_size = atoi(argv[1]);
+	ht_init_data();
+	ht_timing(ht_khash_int);
+	ht_timing(ht_khash_str);
+	ht_timing(ht_khash_unpack);
+	ht_timing(ht_khash_packed);
+	ht_destroy_data();
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/klist_test.c b/debian/vendor-h2o/deps/klib/test/klist_test.c
new file mode 100644
index 0000000..cd13813
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/klist_test.c
@@ -0,0 +1,19 @@
+#include <stdio.h>
+#include "klist.h"
+
+#define __int_free(x)
+KLIST_INIT(32, int, __int_free)
+
+int main()
+{
+	klist_t(32) *kl;
+	kliter_t(32) *p;
+	kl = kl_init(32);
+	*kl_pushp(32, kl) = 1;
+	*kl_pushp(32, kl) = 10;
+	kl_shift(32, kl, 0);
+	for (p = kl_begin(kl); p != kl_end(kl); p = kl_next(p))
+		printf("%d\n", kl_val(p));
+	kl_destroy(32, kl);
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kmin_test.c b/debian/vendor-h2o/deps/klib/test/kmin_test.c
new file mode 100644
index 0000000..33ccd1c
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kmin_test.c
@@ -0,0 +1,48 @@
+#include <stdio.h>
+#include <math.h>
+#include "kmath.h"
+
+static int n_evals;
+
+double f_Chebyquad(int n, double *x, void *data)
+{
+    int i, j;
+    double y[20][20], f;
+    int np, iw;
+    double sum;
+    for (j = 0; j != n; ++j) {
+		y[0][j] = 1.;
+		y[1][j] = 2. * x[j] - 1.;
+    }
+    for (i = 1; i != n; ++i)
+		for (j = 0; j != n; ++j)
+			y[i+1][j] = 2. * y[1][j] * y[i][j] - y[i-1][j];
+    f = 0.;
+    np = n + 1;
+    iw = 1;
+    for (i = 0; i != np; ++i) {
+		sum = 0.;
+		for (j = 0; j != n; ++j) sum += y[i][j];
+		sum /= n;
+		if (iw > 0) sum += 1. / ((i - 1) * (i + 1));
+		iw = -iw;
+		f += sum * sum;
+    }
+	++n_evals;
+    return f;
+}
+
+int main()
+{
+	double x[20], y;
+	int n, i;
+	printf("\nMinimizer: Hooke-Jeeves\n");
+	for (n = 2; n <= 8; n += 2) {
+		for (i = 0; i != n; ++i) x[i] = (double)(i + 1) / n;
+		n_evals = 0;
+		y = kmin_hj(f_Chebyquad, n, x, 0, KMIN_RADIUS, KMIN_EPS, KMIN_MAXCALL);
+		printf("n=%d,min=%.8lg,n_evals=%d\n", n, y, n_evals);
+	}
+	printf("\n");
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kseq_bench.c b/debian/vendor-h2o/deps/klib/test/kseq_bench.c
new file mode 100644
index 0000000..eeda13f
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kseq_bench.c
@@ -0,0 +1,69 @@
+#include <zlib.h>
+#include <stdio.h>
+#include <time.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include "kseq.h"
+
+#define BUF_SIZE 4096
+KSTREAM_INIT(gzFile, gzread, BUF_SIZE)
+
+int main(int argc, char *argv[])
+{
+	gzFile fp;
+	clock_t t;
+	if (argc == 1) {
+		fprintf(stderr, "Usage: kseq_bench <in.gz>\n");
+		return 1;
+	}
+	{
+		uint8_t *buf = malloc(BUF_SIZE);
+		fp = gzopen(argv[1], "r");
+		t = clock();
+		while (gzread(fp, buf, BUF_SIZE) > 0);
+		fprintf(stderr, "[gzread] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+		gzclose(fp);
+		free(buf);
+	}
+	{
+		kstream_t *ks;
+		fp = gzopen(argv[1], "r");
+		ks = ks_init(fp);
+		t = clock();
+		while (ks_getc(ks) >= 0);
+		fprintf(stderr, "[ks_getc] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+		ks_destroy(ks);
+		gzclose(fp);
+	}
+	{
+		kstream_t *ks;
+		kstring_t *s;
+		int dret;
+		s = calloc(1, sizeof(kstring_t));
+		fp = gzopen(argv[1], "r");
+		ks = ks_init(fp);
+		t = clock();
+		while (ks_getuntil(ks, '\n', s, &dret) >= 0);
+		fprintf(stderr, "[ks_getuntil] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+		ks_destroy(ks);
+		gzclose(fp);
+		free(s->s); free(s);
+	}
+	if (argc == 2) {
+		fp = gzopen(argv[1], "r");
+		t = clock();
+		while (gzgetc(fp) >= 0);
+		fprintf(stderr, "[gzgetc] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+		gzclose(fp);
+	}
+	if (argc == 2) {
+		char *buf = malloc(BUF_SIZE);
+		fp = gzopen(argv[1], "r");
+		t = clock();
+		while (gzgets(fp, buf, BUF_SIZE) > 0);
+		fprintf(stderr, "[gzgets] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+		gzclose(fp);
+		free(buf);
+	}
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kseq_bench2.c b/debian/vendor-h2o/deps/klib/test/kseq_bench2.c
new file mode 100644
index 0000000..b415458
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kseq_bench2.c
@@ -0,0 +1,43 @@
+#include <stdio.h>
+#include <time.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <fcntl.h>
+#include "kseq.h"
+KSTREAM_INIT(int, read, 4096)
+
+#define BUF_SIZE 65536
+
+int main(int argc, char *argv[])
+{
+	clock_t t;
+	if (argc == 1) {
+		fprintf(stderr, "Usage: %s <in.txt>\n", argv[0]);
+		return 1;
+	}
+	{
+		FILE *fp;
+		char *s;
+		t = clock();
+		s = malloc(BUF_SIZE);
+		fp = fopen(argv[1], "r");
+		while (fgets(s, BUF_SIZE, fp));
+		fclose(fp);
+		fprintf(stderr, "[fgets] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+	}
+	{
+		int fd, dret;
+		kstream_t *ks;
+		kstring_t s;
+		t = clock();
+		s.l = s.m = 0; s.s = 0;
+		fd = open(argv[1], O_RDONLY);
+		ks = ks_init(fd);
+		while (ks_getuntil(ks, '\n', &s, &dret) >= 0);
+		free(s.s);
+		ks_destroy(ks);
+		close(fd);
+		fprintf(stderr, "[kstream] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+	}
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kseq_test.c b/debian/vendor-h2o/deps/klib/test/kseq_test.c
new file mode 100644
index 0000000..0304dea
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kseq_test.c
@@ -0,0 +1,27 @@
+#include <zlib.h>
+#include <stdio.h>
+#include "kseq.h"
+KSEQ_INIT(gzFile, gzread)
+
+int main(int argc, char *argv[])
+{
+	gzFile fp;
+	kseq_t *seq;
+	int l;
+	if (argc == 1) {
+		fprintf(stderr, "Usage: %s <in.fasta>\n", argv[0]);
+		return 1;
+	}
+	fp = gzopen(argv[1], "r");
+	seq = kseq_init(fp);
+	while ((l = kseq_read(seq)) >= 0) {
+		printf("name: %s\n", seq->name.s);
+		if (seq->comment.l) printf("comment: %s\n", seq->comment.s);
+		printf("seq: %s\n", seq->seq.s);
+		if (seq->qual.l) printf("qual: %s\n", seq->qual.s);
+	}
+	printf("return value: %d\n", l);
+	kseq_destroy(seq);
+	gzclose(fp);
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kseq_test.dat b/debian/vendor-h2o/deps/klib/test/kseq_test.dat
new file mode 100644
index 0000000..b774ae2
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kseq_test.dat
@@ -0,0 +1,12 @@
+>1
+acgtacgtacgtagc
+>2 test
+acgatcgatc
+@3 test2
+cgctagcatagc
+cgatatgactta
++
+78wo82usd980
+d88fau
+
+238ud8
diff --git a/debian/vendor-h2o/deps/klib/test/ksort_test.c b/debian/vendor-h2o/deps/klib/test/ksort_test.c
new file mode 100644
index 0000000..92c7d3d
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/ksort_test.c
@@ -0,0 +1,104 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <time.h>
+#include "ksort.h"
+
+KSORT_INIT_GENERIC(int)
+
+int main(int argc, char *argv[])
+{
+	int i, N = 10000000;
+	int *array, x;
+	clock_t t1, t2;
+	if (argc > 1) N = atoi(argv[1]);
+	array = (int*)malloc(sizeof(int) * N);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	x = ks_ksmall(int, N, array, 10500);
+	t2 = clock();
+	fprintf(stderr, "ksmall [%d]: %.3lf\n", x, (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	ks_introsort(int, N, array);
+	t2 = clock();
+	fprintf(stderr, "introsort [%d]: %.3lf\n", array[10500], (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in introsort!\n");
+			exit(1);
+		}
+	}
+
+#ifndef _ALIGNED_ONLY
+	{ // test unaligned ksmall
+		srand48(11);
+		unsigned char *a;
+		int *b;
+		a = malloc(N * sizeof(int) + 1);
+		b = (int*)(a + 1);
+		for (i = 0; i < N; ++i) b[i] = (int)lrand48();
+		t1 = clock();
+		ks_introsort(int, N, b);
+		t2 = clock();
+		fprintf(stderr, "introsort [%d]: %.3lf (unaligned: 0x%lx) \n", b[10500], (double)(t2-t1)/CLOCKS_PER_SEC, (size_t)b);
+	}
+#endif
+
+	t1 = clock();
+	ks_introsort(int, N, array);
+	t2 = clock();
+	fprintf(stderr, "introsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	ks_combsort(int, N, array);
+	t2 = clock();
+	fprintf(stderr, "combsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in combsort!\n");
+			exit(1);
+		}
+	}
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	ks_mergesort(int, N, array, 0);
+	t2 = clock();
+	fprintf(stderr, "mergesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in mergesort!\n");
+			exit(1);
+		}
+	}
+
+	t1 = clock();
+	ks_mergesort(int, N, array, 0);
+	t2 = clock();
+	fprintf(stderr, "mergesort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	ks_heapmake(int, N, array);
+	ks_heapsort(int, N, array);
+	t2 = clock();
+	fprintf(stderr, "heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in heapsort!\n");
+			exit(1);
+		}
+	}
+
+	free(array);
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/ksort_test.cc b/debian/vendor-h2o/deps/klib/test/ksort_test.cc
new file mode 100644
index 0000000..8950d80
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/ksort_test.cc
@@ -0,0 +1,997 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <time.h>
+#include <algorithm>
+
+#include "ksort.h"
+KSORT_INIT_GENERIC(int)
+
+using namespace std;
+
+/**********************************
+ * BEGIN OF PAUL'S IMPLEMENTATION *
+ **********************************/
+
+/* Attractive Chaos: I have added inline where necessary. */
+
+/*
+Copyright (c) 2004 Paul Hsieh
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    Redistributions of source code must retain the above copyright notice,
+    this list of conditions and the following disclaimer.
+
+    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.
+
+    Neither the name of sorttest nor the names of its contributors may be
+    used to endorse or promote products derived from this software without
+    specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 COPYRIGHT OWNER OR CONTRIBUTORS 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.
+*/
+
+/*
+
+Recommended flags:
+------------------
+
+Intel C/C++:
+icl /O2 /G6 /Qaxi /Qxi /Qip sorttest.c
+
+WATCOM C/C++:
+wcl386 /otexan /6r sorttest.c
+
+GCC:
+gcc -O3 -mcpu=athlon-xp -march=athlon-xp sorttest.c
+
+MSVC:
+cl /O2 /Ot /Og /G6 sorttest.c
+
+*/
+
+static inline void sort2 (int * numbers) {
+int tmp;
+
+    if (numbers[0] <= numbers[1]) return;
+    tmp = numbers[0];
+    numbers[0] = numbers[1];
+    numbers[1] = tmp;
+}
+
+static inline void sort3 (int * numbers) {
+int tmp;
+
+    if (numbers[0] <= numbers[1]) {
+        if (numbers[1] <= numbers[2]) return;
+        if (numbers[2] <= numbers[0]) {
+            tmp = numbers[0];
+            numbers[0] = numbers[2];
+            numbers[2] = numbers[1];
+            numbers[1] = tmp;
+            return;
+        }
+        tmp = numbers[1];
+    } else {
+        tmp = numbers[0];
+        if (numbers[0] <= numbers[2]) {
+            numbers[0] = numbers[1];
+            numbers[1] = tmp;
+            return;
+        }
+        if (numbers[2] <= numbers[1]) {
+            numbers[0] = numbers[2];
+            numbers[2] = tmp;
+            return;
+        }
+        numbers[0] = numbers[1];
+    }
+    numbers[1] = numbers[2];
+    numbers[2] = tmp;
+}
+
+static inline void sort4 (int * num) {
+int tmp;
+  if (num[0] < num[1]) {
+    if (num[1] < num[2]) {
+      if (num[1] < num[3]) {
+        if (num[2] >= num[3]) {
+          tmp = num[2];
+          num[2] = num[3];
+          num[3] = tmp;
+        }
+      } else {
+        tmp = num[1];
+        if (num[0] < num[3]) {
+          num[1] = num[3];
+        } else {
+          num[1] = num[0];
+          num[0] = num[3];
+        }
+        num[3] = num[2];
+        num[2] = tmp;
+      }
+    } else {
+      if (num[0] < num[2]) {
+        if (num[2] < num[3]) {
+          if (num[1] < num[3]) {
+            tmp = num[1];
+          } else {
+            tmp = num[3];
+            num[3] = num[1];
+          }
+          num[1] = num[2];
+          num[2] = tmp;
+        } else {
+          if (num[0] < num[3]) {
+            tmp = num[3];
+          } else {
+            tmp = num[0];
+            num[0] = num[3];
+          }
+          num[3] = num[1];
+          num[1] = tmp;
+        }
+      } else {
+        if (num[0] < num[3]) {
+          tmp = num[0];
+          num[0] = num[2];
+          if (num[1] < num[3]) {
+            num[2] = num[1];
+          } else {
+            num[2] = num[3];
+            num[3] = num[1];
+          }
+          num[1] = tmp;
+        } else {
+          if (num[2] < num[3]) {
+            tmp = num[0];
+            num[0] = num[2];
+            num[2] = tmp;
+            tmp = num[1];
+            num[1] = num[3];
+          } else {
+            tmp = num[1];
+            num[1] = num[2];
+            num[2] = num[0];
+            num[0] = num[3];
+          }
+          num[3] = tmp;
+        }
+      }
+    }
+  } else {
+    tmp = num[0];
+    if (tmp < num[2]) {
+      if (tmp < num[3]) {
+        num[0] = num[1];
+        num[1] = tmp;
+        if (num[2] >= num[3]) {
+          tmp = num[2];
+          num[2] = num[3];
+          num[3] = tmp;
+        }
+      } else {
+        if (num[1] < num[3]) {
+          num[0] = num[1];
+          num[1] = num[3];
+        } else {
+          num[0] = num[3];
+        }
+        num[3] = num[2];
+        num[2] = tmp;
+      }
+    } else {
+      if (num[1] < num[2]) {
+        if (num[2] < num[3]) {
+          num[0] = num[1];
+          num[1] = num[2];
+          if (tmp < num[3]) {
+            num[2] = tmp;
+          } else {
+            num[2] = num[3];
+            num[3] = tmp;
+          }
+        } else {
+          if (num[1] < num[3]) {
+            num[0] = num[1];
+            num[1] = num[3];
+          } else {
+            num[0] = num[3];
+          }
+          num[3] = tmp;
+        }
+      } else {
+        if (num[1] < num[3]) {
+          num[0] = num[2];
+          if (tmp < num[3]) {
+            num[2] = tmp;
+          } else {
+            num[2] = num[3];
+            num[3] = tmp;
+          }
+        } else {
+          if (num[2] < num[3]) {
+            num[0] = num[2];
+            num[2] = num[1];
+            num[1] = num[3];
+            num[3] = tmp;
+          } else {
+            num[0] = num[3];
+            num[3] = tmp;
+            tmp = num[1];
+            num[1] = num[2];
+            num[2] = tmp;
+          }
+        }
+      }
+    }
+  }
+}
+
+static inline void sortAlt2 (int * numbers, int * altNumbers) {
+    if (numbers[0] <= numbers[1]) {
+        altNumbers[0] = numbers[0];
+        altNumbers[1] = numbers[1];
+    } else {
+        altNumbers[0] = numbers[1];
+        altNumbers[1] = numbers[0];
+    }
+}
+
+static inline void sortAlt3 (int * numbers, int * altNumbers) {
+    if (numbers[0] <= numbers[1]) {
+        if (numbers[1] <= numbers[2]) {
+            altNumbers[0] = numbers[0];
+            altNumbers[1] = numbers[1];
+            altNumbers[2] = numbers[2];
+        } else if (numbers[2] <= numbers[0]) {
+            altNumbers[0] = numbers[2];
+            altNumbers[1] = numbers[0];
+            altNumbers[2] = numbers[1];
+        } else {
+            altNumbers[0] = numbers[0];
+            altNumbers[1] = numbers[2];
+            altNumbers[2] = numbers[1];
+        }
+    } else {
+        if (numbers[0] <= numbers[2]) {
+            altNumbers[0] = numbers[1];
+            altNumbers[1] = numbers[0];
+            altNumbers[2] = numbers[2];
+        } else if (numbers[2] <= numbers[1]) {
+            altNumbers[0] = numbers[2];
+            altNumbers[1] = numbers[1];
+            altNumbers[2] = numbers[0];
+        } else {
+            altNumbers[0] = numbers[1];
+            altNumbers[1] = numbers[2];
+            altNumbers[2] = numbers[0];
+        }
+    }
+}
+
+/*
+ *  Insert Sort
+ */
+
+inline void insertSort (int numbers[], int qty) {
+int i, j, idx, q4;
+int tmp;
+
+    if (qty <= 4) {
+        if (qty == 4) sort4 (numbers);
+        else if (qty == 3) sort3 (numbers);
+        else if (qty == 2) sort2 (numbers);
+        return;
+    }
+
+    q4 = qty - 4;
+
+    for (i=0; i < q4; i++) {
+        idx = i;
+        for (j=i+1; j < qty; j++) {
+            if (numbers[j] < numbers[idx]) idx = j;
+        }
+        if (idx != i) {
+            tmp = numbers[idx];
+            numbers[idx] = numbers[i];
+            numbers[i] = tmp;
+        }
+    }
+
+    sort4 (numbers + q4);
+}
+
+/*
+ *  Heap Sort
+ */
+
+/* Assure the heap property for entries from top to last */
+static void siftDown (int numbers[], int top, int last) {
+int tmp = numbers[top];
+int maxIdx = top;
+
+    while (last >= (maxIdx += maxIdx)) {
+
+        /* This is where the comparison occurrs and where a sufficiently
+           good compiler can use a computed conditional result rather
+           than using control logic. */
+        if (maxIdx != last && numbers[maxIdx] < numbers[maxIdx + 1]) maxIdx++;
+
+        if (tmp >= numbers[maxIdx]) break;
+        numbers[top] = numbers[maxIdx];
+        top = maxIdx;
+    }
+    numbers[top] = tmp;
+}
+
+/* Peel off the top siftDown operation since its parameters are trivial to
+   fill in directly (and this saves us some moves.) */
+static void siftDown0 (int numbers[], int last) {
+int tmp;
+
+    if (numbers[0] < numbers[1]) {
+        tmp = numbers[1];
+        numbers[1] = numbers[0];
+        siftDown (numbers, 1, last);
+    } else {
+        tmp = numbers[0];
+    }
+    numbers[0] = numbers[last];
+    numbers[last] = tmp;
+}
+
+void heapSort (int numbers[], int qty) {
+int i;
+
+    if (qty <= 4) {
+        if (qty == 4) sort4 (numbers);
+        else if (qty == 3) sort3 (numbers);
+        else if (qty == 2) sort2 (numbers);
+        return;
+    }
+
+    i = qty / 2;
+    /* Enforce the heap property for each position in the tree */
+    for (  qty--; i >  0; i--) siftDown  (numbers, i, qty);
+    for (i = qty; i > 0; i--) siftDown0 (numbers, i);
+}
+
+/*
+ *  Quick Sort
+ */
+
+static int medianOf3 (int * numbers, int i, int j) {
+int tmp;
+
+    if (numbers[0] <= numbers[i]) {
+        if (numbers[j] <= numbers[0]) return numbers[0]; /* j 0 i */
+        if (numbers[i] <= numbers[j]) j = i;             /* 0 i j */
+                                                         /* 0 j i */
+    } else {
+        if (numbers[0] <= numbers[j]) return numbers[0]; /* i 0 j */
+        if (numbers[j] <= numbers[i]) j = i;             /* j i 0 */
+                                                         /* i j 0 */
+    }
+    tmp = numbers[j];
+    numbers[j] = numbers[0];
+    numbers[0] = tmp;
+    return tmp;
+}
+
+static void quickSortRecurse (int * numbers, int left, int right) {
+int pivot, lTmp, rTmp;
+
+    qsrStart:;
+
+#if defined(__GNUC__)
+    if (right <= left + 8) {
+        insertSort (numbers + left, right - left + 1);
+        return;
+    }
+#else
+    if (right <= left + 3) {
+        if (right == left + 1) {
+            sort2 (numbers + left);
+        } else if (right == left + 2) {
+            sort3 (numbers + left);
+        } else if (right == left + 3) {
+            sort4 (numbers + left);
+        }
+        return;
+    }
+#endif
+
+    lTmp = left;
+    rTmp = right;
+
+    pivot = medianOf3 (numbers + left, (right-left) >> 1, right-1-left);
+
+    goto QStart;
+    while (1) {
+        do {
+            right--;
+            if (left >= right) goto QEnd;
+            QStart:;
+        } while (numbers[right] > pivot);
+        numbers[left] = numbers[right];
+        do { 
+            left++;
+            if (left >= right) {
+                left = right;
+                goto QEnd;
+            }
+        } while (numbers[ left] < pivot);
+        numbers[right] = numbers[left];
+    }
+    QEnd:;
+    numbers[left] = pivot;
+
+    /* Only recurse the smaller partition */
+
+    if (left-1 - lTmp <= rTmp - left - 1) {
+        if (lTmp < left) quickSortRecurse (numbers,   lTmp, left-1);
+
+        /* Set up for larger partition */
+        left++;
+        right = rTmp;
+    } else {
+        if (rTmp > left) quickSortRecurse (numbers, left+1,   rTmp);
+
+        /* Set up for larger partition */
+        right = left - 1;
+        left = lTmp;
+    }
+
+    /* Rerun with larger partition (recursion not required.) */
+    goto qsrStart;
+}
+
+void quickSort (int numbers[], int qty) {
+    if (qty < 2) return;
+    quickSortRecurse (numbers, 0, qty - 1);
+}
+
+/*
+ *  Merge Sort
+ */
+
+static void mergesortInPlace (int * numbers, int * altNumbers, int qty);
+
+/* Perform mergesort, but store results in altNumbers */
+
+static void mergesortExchange (int * numbers, int * altNumbers, int qty) {
+int half, i0, i1, i;
+
+    if (qty == 2) {
+        sortAlt2 (numbers, altNumbers);
+        return;
+    }
+    if (qty == 3) {
+        sortAlt3 (numbers, altNumbers);
+        return;
+    }
+
+    half = (qty + 1)/2;
+
+    mergesortInPlace (numbers, altNumbers, half);
+    mergesortInPlace (numbers + half, altNumbers, qty - half);
+
+    i0 = 0; i1 = half;
+
+    for (i=0; i < qty; i++) {
+        if (i1 >= qty || (i0 < half && numbers[i0] < numbers[i1])) {
+            altNumbers[i] = numbers[i0];
+            i0++;
+        } else {
+            altNumbers[i] = numbers[i1];
+            i1++;
+        }
+    }
+}
+
+/* Perform mergesort and store results in numbers */
+
+static void mergesortInPlace (int * numbers, int * altNumbers, int qty) {
+int half, i0, i1, i;
+
+#if 0
+    if (qty == 2) {
+        sort2 (numbers);
+        return;
+    }
+    if (qty == 3) {
+        sort3 (numbers);
+        return;
+    }
+    if (qty == 4) {
+        sort4 (numbers);
+        return;
+    }
+#else
+    if (qty <= 12) {
+        insertSort (numbers, qty);
+        return;
+    }
+#endif
+
+    half = (qty + 1)/2;
+
+    mergesortExchange (numbers, altNumbers, half);
+    mergesortExchange (numbers + half, altNumbers + half, qty - half);
+
+    i0 = 0; i1 = half;
+
+    for (i=0; i < qty; i++) {
+        if (i1 >= qty || (i0 < half && altNumbers[i0] < altNumbers[i1])) {
+            numbers[i] = altNumbers[i0];
+            i0++;
+        } else {
+            numbers[i] = altNumbers[i1];
+            i1++;
+        }
+    }
+}
+
+#include <stdlib.h>
+
+void mergeSort (int numbers[], int qty) {
+int * tmpArray;
+
+    if (qty <= 12) {
+        insertSort (numbers, qty);
+        return;
+    }
+
+    tmpArray = (int *) malloc (qty * sizeof (int));
+    mergesortInPlace (numbers, tmpArray, qty);
+    free (tmpArray);
+}
+
+/********************************
+ * END OF PAUL'S IMPLEMENTATION *
+ ********************************/
+
+/*************************************************
+ *** Implementation 1: faster on sorted arrays ***
+ *************************************************/
+
+#define rstype_t unsigned
+#define rskey(x) (x)
+
+#define RS_MIN_SIZE 64
+
+typedef struct {
+	rstype_t *b, *e;
+} rsbucket_t;
+
+void rs_sort(rstype_t *beg, rstype_t *end, int n_bits, int s)
+{
+	rstype_t *i;
+	int size = 1<<n_bits, m = size - 1;
+	rsbucket_t *k, b[size], *be = b + size;
+
+	for (k = b; k != be; ++k) k->b = k->e = beg;
+	for (i = beg; i != end; ++i) ++b[rskey(*i)>>s&m].e;
+	for (k = b + 1; k != be; ++k)
+		k->e += (k-1)->e - beg, k->b = (k-1)->e;
+	for (k = b; k != be;) {
+		if (k->b != k->e) {
+			rsbucket_t *l;
+			if ((l = b + (rskey(*k->b)>>s&m)) != k) {
+				rstype_t tmp = *k->b, swap;
+				do {
+					swap = tmp; tmp = *l->b; *l->b++ = swap;
+					l = b + (rskey(tmp)>>s&m);
+				} while (l != k);
+				*k->b++ = tmp;
+			} else ++k->b;
+		} else ++k;
+	}
+	for (b->b = beg, k = b + 1; k != be; ++k) k->b = (k-1)->e;
+	if (s) {
+		s = s > n_bits? s - n_bits : 0;
+		for (k = b; k != be; ++k)
+			if (k->e - k->b > RS_MIN_SIZE) rs_sort(k->b, k->e, n_bits, s);
+			else if (k->e - k->b > 1)
+				for (i = k->b + 1; i < k->e; ++i)
+					if (rskey(*i) < rskey(*(i - 1))) {
+						rstype_t *j, tmp = *i;
+						for (j = i; j > k->b && rskey(tmp) < rskey(*(j-1)); --j)
+							*j = *(j - 1);
+						*j = tmp;
+					}
+	}
+}
+
+/*************************************************
+ *** Implementation 2: faster on random arrays ***
+ *************************************************/
+
+static inline void rs_insertsort(rstype_t *s, rstype_t *t)
+{
+	rstype_t *i;
+	for (i = s + 1; i < t; ++i) {
+		if (rskey(*i) < rskey(*(i - 1))) {
+			rstype_t *j, tmp = *i;
+			for (j = i; j > s && rskey(tmp) < rskey(*(j-1)); --j)
+				*j = *(j - 1);
+			*j = tmp;
+		}
+	}
+}
+/*
+void rs_sort2(rstype_t *beg, rstype_t *end, int n_bits, int s)
+{
+	int j, size = 1<<n_bits, m = size - 1;
+	unsigned long c[size];
+	rstype_t *i, *b[size], *e[size];
+
+	for (j = 0; j < size; ++j) c[j] = 0;
+	for (i = beg; i != end; ++i) ++c[rskey(*i)>>s&m];
+	b[0] = e[0] = beg;
+	for (j = 1; j != size; ++j) b[j] = e[j] = b[j - 1] + c[j - 1];
+	for (i = beg, j = 0; i != end;) {
+		rstype_t tmp = *i, swap;
+		int x;
+		for (;;) {
+			x = rskey(tmp)>>s&m;
+			if (e[x] == i) break;
+			swap = tmp; tmp = *e[x]; *e[x]++ = swap;
+		}
+		*i++ = tmp;
+		++e[x];
+		while (j != size && i >= b[j]) ++j;
+		while (j != size && e[j-1] == b[j]) ++j;
+		if (i < e[j-1]) i = e[j-1];
+	}
+	if (s) {
+		s = s > n_bits? s - n_bits : 0;
+		for (j = 0; j < size; ++j) {
+			if (c[j] >= RS_MIN_SIZE) rs_sort2(b[j], e[j], n_bits, s);
+			else if (c[j] >= 2) rs_insertsort(b[j], e[j]);
+		}
+	}
+}
+*/
+void radix_sort(unsigned *array, int offset, int end, int shift) {
+    int x, y, value, temp;
+    int last[256] = { 0 }, pointer[256];
+
+    for (x=offset; x<end; ++x) {
+        ++last[(array[x] >> shift) & 0xFF];
+    }
+
+    last[0] += offset;
+    pointer[0] = offset;
+    for (x=1; x<256; ++x) {
+        pointer[x] = last[x-1];
+        last[x] += last[x-1];
+    }
+
+    for (x=0; x<256; ++x) {
+        while (pointer[x] != last[x]) {
+            value = array[pointer[x]];
+            y = (value >> shift) & 0xFF;
+            while (x != y) {
+                temp = array[pointer[y]];
+                array[pointer[y]++] = value;
+                value = temp;
+                y = (value >> shift) & 0xFF;
+            }
+            array[pointer[x]++] = value;
+        }
+    }
+
+    if (shift > 0) {
+        shift -= 8;
+        for (x=0; x<256; ++x) {
+            temp = x > 0 ? pointer[x] - pointer[x-1] : pointer[0] - offset;
+            if (temp > 64) {
+                radix_sort(array, pointer[x] - temp, pointer[x], shift);
+            } else if (temp > 1) rs_insertsort(array + pointer[x] - temp, array + pointer[x]);
+        }
+    }
+}
+/*************************
+ *** END OF RADIX SORT ***
+ *************************/
+
+template< class _Type, unsigned long PowerOfTwoRadix, unsigned long Log2ofPowerOfTwoRadix, long Threshold >
+inline void _RadixSort_Unsigned_PowerOf2Radix_1( _Type* a, long last, _Type bitMask, unsigned long shiftRightAmount )
+{
+	const unsigned long numberOfBins = PowerOfTwoRadix;
+	unsigned long count[ numberOfBins ];
+	for( unsigned long i = 0; i < numberOfBins; i++ )
+		count[ i ] = 0;
+	for ( long _current = 0; _current <= last; _current++ ) // Scan the array and count the number of times each value appears
+	{
+		unsigned long digit = (unsigned long)(( a[ _current ] & bitMask ) >> shiftRightAmount ); // extract the digit we are sorting based on
+		count[ digit ]++;
+	}
+	long startOfBin[ numberOfBins ], endOfBin[ numberOfBins ], nextBin;
+	startOfBin[ 0 ] = endOfBin[ 0 ] = nextBin = 0;
+	for( unsigned long i = 1; i < numberOfBins; i++ )
+		startOfBin[ i ] = endOfBin[ i ] = startOfBin[ i - 1 ] + count[ i - 1 ];
+	for ( long _current = 0; _current <= last; )
+	{
+		unsigned long digit;
+		_Type tmp = a[ _current ];  // get the compiler to recognize that a register can be used for the loop instead of a[_current] memory location
+		while ( true ) {
+			digit = (unsigned long)(( tmp & bitMask ) >> shiftRightAmount );   // extract the digit we are sorting based on
+			if ( endOfBin[ digit ] == _current )
+				break;
+			_Type tmp2;
+			//_swap( tmp, a[ endOfBin[ digit ] ] );
+			tmp2 = a[endOfBin[digit]]; a[endOfBin[digit]] = tmp; tmp = tmp2;
+			endOfBin[ digit ]++;
+		}
+		a[ _current ] = tmp;
+		endOfBin[ digit ]++;   // leave the element at its location and grow the bin
+		_current++;  // advance the current pointer to the next element
+		while( _current >= startOfBin[ nextBin ] && nextBin < numberOfBins )
+			nextBin++;
+		while( endOfBin[ nextBin - 1 ] == startOfBin[ nextBin ] && nextBin < numberOfBins )
+			nextBin++;
+		if ( _current < endOfBin[ nextBin - 1 ] )
+			_current = endOfBin[ nextBin - 1 ];
+	}
+	bitMask >>= Log2ofPowerOfTwoRadix;
+	if ( bitMask != 0 )   // end recursion when all the bits have been processes
+	{
+		if ( shiftRightAmount >= Log2ofPowerOfTwoRadix ) shiftRightAmount -= Log2ofPowerOfTwoRadix;
+		else shiftRightAmount  = 0;
+		for( unsigned long i = 0; i < numberOfBins; i++ )
+		{
+			long numberOfElements = endOfBin[ i ] - startOfBin[ i ];
+			if ( numberOfElements >= Threshold )  // endOfBin actually points to one beyond the bin
+				_RadixSort_Unsigned_PowerOf2Radix_1< _Type, PowerOfTwoRadix, Log2ofPowerOfTwoRadix, Threshold >( &a[ startOfBin[ i ]], numberOfElements - 1, bitMask, shiftRightAmount );
+			else if ( numberOfElements >= 2 )
+				rs_insertsort(&a[ startOfBin[ i ]], &a[ endOfBin[ i ]]);
+		}
+	}
+}
+inline void RadixSortInPlace_HybridUnsigned_Radix256( unsigned* a, unsigned long a_size )
+{
+	if ( a_size < 2 ) return;
+	unsigned long bitMask = 0xFF000000; // bitMask controls how many bits we process at a time
+	unsigned long shiftRightAmount = 24;
+	if ( a_size >= 32 )
+		_RadixSort_Unsigned_PowerOf2Radix_1<unsigned, 256, 8, 32>(a, a_size - 1, bitMask, shiftRightAmount );
+	else
+		rs_insertsort(a, a + a_size);
+}
+
+struct intcmp_t {
+	inline int operator() (int a, int b) const {
+		return a < b? -1 : a > b? 1 : 0;
+	}
+};
+
+int compare_int(int a, int b)
+{
+	return a < b? -1 : a > b? 1 : 0;
+}
+int compare(const void *a, const void *b)
+{
+	return *((int*)a) - *((int*)b);
+}
+
+int main(int argc, char *argv[])
+{
+	int i, N = 50000000;
+	int *array, *temp;
+	clock_t t1, t2;
+	if (argc == 1) fprintf(stderr, "Usage: %s [%d]\n", argv[0], N);
+	if (argc > 1) N = atoi(argv[1]);
+	temp = (int*)malloc(sizeof(int) * N);
+	array = (int*)malloc(sizeof(int) * N);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	rs_sort((unsigned*)array, (unsigned*)array + N, 8, 24);
+	t2 = clock();
+	fprintf(stderr, "radix sort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in radix sort!\n");
+			exit(1);
+		}
+	}
+	t1 = clock();
+	rs_sort((unsigned*)array, (unsigned*)array + N, 8, 24);
+	t2 = clock();
+	fprintf(stderr, "radix sort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	RadixSortInPlace_HybridUnsigned_Radix256((unsigned*)array, N);
+//	radix_sort((unsigned*)array, 0, N, 24);
+	t2 = clock();
+	fprintf(stderr, "vd's radix sort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in radix sort!\n");
+			exit(1);
+		}
+	}
+	t1 = clock();
+	RadixSortInPlace_HybridUnsigned_Radix256((unsigned*)array, N);
+//	radix_sort((unsigned*)array, 0, N, 24);
+	t2 = clock();
+	fprintf(stderr, "vd's radix sort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	sort(array, array+N);
+	t2 = clock();
+	fprintf(stderr, "STL introsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	t1 = clock();
+	sort(array, array+N);
+	t2 = clock();
+	fprintf(stderr, "STL introsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	stable_sort(array, array+N);
+	t2 = clock();
+	fprintf(stderr, "STL stablesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	t1 = clock();
+	stable_sort(array, array+N);
+	t2 = clock();
+	fprintf(stderr, "STL stablesort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	make_heap(array, array+N);
+	sort_heap(array, array+N);
+	t2 = clock();
+	fprintf(stderr, "STL heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in heap_sort!\n");
+			exit(1);
+		}
+	}
+	t1 = clock();
+	make_heap(array, array+N);
+	sort_heap(array, array+N);
+	t2 = clock();
+	fprintf(stderr, "STL heapsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	ks_combsort(int, N, array);
+	t2 = clock();
+	fprintf(stderr, "combsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in combsort!\n");
+			exit(1);
+		}
+	}
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	qsort(array, N, sizeof(int), compare);
+	t2 = clock();
+	fprintf(stderr, "libc qsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	ks_introsort(int, N, array);
+	t2 = clock();
+	fprintf(stderr, "my introsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in intro_sort!\n");
+			exit(1);
+		}
+	}
+	t1 = clock();
+	ks_introsort(int, N, array);
+	t2 = clock();
+	fprintf(stderr, "introsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	ks_mergesort(int, N, array, 0);
+	t2 = clock();
+	fprintf(stderr, "iterative mergesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in merge_sort!\n");
+			exit(1);
+		}
+	}
+	t1 = clock();
+	ks_mergesort(int, N, array, 0);
+	t2 = clock();
+	fprintf(stderr, "iterative mergesort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	ks_heapmake(int, N, array);
+	ks_heapsort(int, N, array);
+	t2 = clock();
+	fprintf(stderr, "my heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in heap_sort!\n");
+			exit(1);
+		}
+	}
+	t1 = clock();
+	ks_heapmake(int, N, array);
+	ks_heapsort(int, N, array);
+	t2 = clock();
+	fprintf(stderr, "heapsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	heapSort(array, N);
+	t2 = clock();
+	fprintf(stderr, "Paul's heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in intro_sort!\n");
+			exit(1);
+		}
+	}
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	quickSort(array, N);
+	t2 = clock();
+	fprintf(stderr, "Paul's quicksort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in intro_sort!\n");
+			exit(1);
+		}
+	}
+
+	srand48(11);
+	for (i = 0; i < N; ++i) array[i] = (int)lrand48();
+	t1 = clock();
+	mergeSort(array, N);
+	t2 = clock();
+	fprintf(stderr, "Paul's mergesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
+	for (i = 0; i < N-1; ++i) {
+		if (array[i] > array[i+1]) {
+			fprintf(stderr, "Bug in intro_sort!\n");
+			exit(1);
+		}
+	}
+
+	free(array); free(temp);
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kstring_bench.c b/debian/vendor-h2o/deps/klib/test/kstring_bench.c
new file mode 100644
index 0000000..82598e8
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kstring_bench.c
@@ -0,0 +1,51 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include "kstring.h"
+
+#define N 10000000
+
+int main()
+{
+	int i;
+	clock_t t;
+	kstring_t s, s2;
+	srand48(11);
+	s.l = s.m = 0; s.s = 0;
+	t = clock();
+	for (i = 0; i < N; ++i) {
+		int x = lrand48();
+		s.l = 0;
+		kputw(x, &s);
+	}
+	fprintf(stderr, "kputw: %lf\n", (double)(clock() - t) / CLOCKS_PER_SEC);
+	srand48(11);
+	t = clock();
+	for (i = 0; i < N; ++i) {
+		int x = lrand48();
+		s.l = 0;
+		ksprintf(&s, "%d", x);
+	}
+	fprintf(stderr, "ksprintf: %lf\n", (double)(clock() - t) / CLOCKS_PER_SEC);
+
+	srand48(11);
+	s2.l = s2.m = 0; s2.s = 0;
+	t = clock();
+	for (i = 0; i < N; ++i) {
+		int x = lrand48();
+		s2.l = s.l = 0;
+		kputw(x, &s2);
+		kputs(s2.s, &s);
+	}
+	fprintf(stderr, "kputw+kputs: %lf\n", (double)(clock() - t) / CLOCKS_PER_SEC);
+	srand48(11);
+	t = clock();
+	for (i = 0; i < N; ++i) {
+		int x = lrand48();
+		s2.l = s.l = 0;
+		kputw(x, &s2);
+		ksprintf(&s, "%s", s2.s);
+	}
+	fprintf(stderr, "kputw+ksprintf: %lf\n", (double)(clock() - t) / CLOCKS_PER_SEC);
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kstring_bench2.c b/debian/vendor-h2o/deps/klib/test/kstring_bench2.c
new file mode 100644
index 0000000..b7707a8
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kstring_bench2.c
@@ -0,0 +1,131 @@
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include "kstring.h"
+
+#ifdef __APPLE__
+#define HAVE_STRNSTR
+#endif
+
+#ifdef __linux__
+#define HAVE_MEMMEM
+#endif
+
+static int str_len = 1024*1024*128;
+static int pat_len = 30;
+static int alphabet = 2;
+static int repeat = 50;
+
+char *gen_data(int len, int a)
+{
+	char *data;
+	int i;
+	long x;
+	srand48(11);
+	data = malloc(len);
+	for (i = 0; i < len; ++i)
+		data[i] = (int)(a * drand48()) + '!';
+	data[str_len - 1] = 0;
+	return data;
+}
+// http://srcvault.scali.eu.org/cgi-bin/Syntax/c/BoyerMoore.c
+char *BoyerMoore( unsigned char *data, unsigned int dataLength, unsigned char *string, unsigned int strLength )
+{
+	unsigned int skipTable[256], i;
+	unsigned char *search;
+	register unsigned char lastChar;
+
+	if (strLength == 0)
+		return NULL;
+
+	for (i = 0; i < 256; i++)
+		skipTable[i] = strLength;
+	search = string;
+	i = --strLength;
+	do {
+		skipTable[*search++] = i;
+	} while (i--);
+	lastChar = *--search;
+	search = data + strLength;
+	dataLength -= strLength+(strLength-1);
+	while ((int)dataLength > 0 ) {
+		unsigned int skip;
+		skip = skipTable[*search];
+		search += skip;
+		dataLength -= skip;
+		skip = skipTable[*search];
+		search += skip;
+		dataLength -= skip;
+		skip = skipTable[*search];
+		if (*search != lastChar) {
+			search += skip;
+			dataLength -= skip;
+			continue;
+		}
+		i = strLength;
+		do {
+			if (i-- == 0) return search;
+		} while (*--search == string[i]);
+		search += (strLength - i + 1);
+		dataLength--;
+	}
+	return NULL;
+}
+
+int main()
+{
+	char *data;
+	int i;
+	clock_t t;
+	t = clock();
+	data = gen_data(str_len, alphabet);
+	fprintf(stderr, "Generate data in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+	{
+		t = clock(); srand48(1331);
+		for (i = 0; i < repeat; ++i) {
+			int y = lrand48() % (str_len - pat_len);
+			char *ret;
+			ret = kmemmem(data, str_len, data + y, pat_len, 0);
+//			printf("%d, %d\n", (int)(ret - data), y);
+		}
+		fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+	}
+	if (1) {
+		t = clock(); srand48(1331);
+		for (i = 0; i < repeat; ++i) {
+			int y = lrand48() % (str_len - pat_len);
+			char *ret;
+			ret = BoyerMoore(data, str_len, data + y, pat_len);
+//			printf("%d, %d\n", (int)(ret - data), y);
+		}
+		fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+	}
+#ifdef HAVE_STRNSTR
+	if (1) {
+		char *tmp;
+		t = clock(); srand48(1331);
+		tmp = calloc(pat_len+1, 1);
+		for (i = 0; i < repeat; ++i) {
+			int y = lrand48() % (str_len - pat_len);
+			char *ret;
+			memcpy(tmp, data + y, pat_len);
+			ret = strnstr(data, tmp, str_len);
+		}
+		fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);		
+	}
+#endif
+#ifdef HAVE_MEMMEM
+	if (1) {
+		t = clock(); srand48(1331);
+		for (i = 0; i < repeat; ++i) {
+			int y = lrand48() % (str_len - pat_len);
+			char *ret;
+			ret = memmem(data, str_len, data + y, pat_len);
+//			printf("%d, %d\n", (int)(ret - data), y);
+		}
+		fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+	}
+#endif
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kstring_test.c b/debian/vendor-h2o/deps/klib/test/kstring_test.c
new file mode 100644
index 0000000..76f9532
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kstring_test.c
@@ -0,0 +1,76 @@
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "kstring.h"
+
+int nfail = 0;
+
+void check(const char *what, const kstring_t *ks, const char *correct)
+{
+	if (ks->l != strlen(correct) || strcmp(ks->s, correct) != 0) {
+		fprintf(stderr, "%s produced \"%.*s\" (\"%s\" is correct)\tFAIL\n", what, (int)(ks->l), ks->s, correct);
+		nfail++;
+	}
+}
+
+void test_kputw(kstring_t *ks, int n)
+{
+	char buf[16];
+
+	ks->l = 0;
+	kputw(n, ks);
+
+	sprintf(buf, "%d", n);
+	check("kputw()", ks, buf);
+}
+
+void test_kputl(kstring_t *ks, long n)
+{
+	char buf[24];
+
+	ks->l = 0;
+	kputl(n, ks);
+
+	sprintf(buf, "%ld", n);
+	check("kputl()", ks, buf);
+}
+
+int main()
+{
+	kstring_t ks;
+
+	ks.l = ks.m = 0;
+	ks.s = NULL;
+
+	test_kputw(&ks, 0);
+	test_kputw(&ks, 1);
+	test_kputw(&ks, 37);
+	test_kputw(&ks, 12345);
+	test_kputw(&ks, -12345);
+	test_kputw(&ks, INT_MAX);
+	test_kputw(&ks, -INT_MAX);
+	test_kputw(&ks, INT_MIN);
+
+	test_kputl(&ks, 0);
+	test_kputl(&ks, 1);
+	test_kputl(&ks, 37);
+	test_kputl(&ks, 12345);
+	test_kputl(&ks, -12345);
+	test_kputl(&ks, INT_MAX);
+	test_kputl(&ks, -INT_MAX);
+	test_kputl(&ks, INT_MIN);
+	test_kputl(&ks, LONG_MAX);
+	test_kputl(&ks, -LONG_MAX);
+	test_kputl(&ks, LONG_MIN);
+
+	free(ks.s);
+
+	if (nfail > 0) {
+		fprintf(stderr, "Total failures: %d\n", nfail);
+		return EXIT_FAILURE;
+	}
+
+	return EXIT_SUCCESS;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kthread_test.c b/debian/vendor-h2o/deps/klib/test/kthread_test.c
new file mode 100644
index 0000000..1b67ed4
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kthread_test.c
@@ -0,0 +1,69 @@
+#include <stdio.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <pthread.h>
+#if HAVE_CILK
+#include <cilk/cilk.h>
+#include <cilk/cilk_api.h>
+#endif
+
+typedef struct {
+	int max_iter, w, h;
+	double xmin, xmax, ymin, ymax;
+	int *k;
+} global_t;
+
+static void compute(void *_g, int i, int tid)
+{
+	global_t *g = (global_t*)_g;
+	double x, x0 = g->xmin + (g->xmax - g->xmin) * (i%g->w) / g->w;
+	double y, y0 = g->ymin + (g->ymax - g->ymin) * (i/g->w) / g->h;
+	int k;
+
+	assert(g->k[i] < 0);
+	x = x0, y = y0;
+	for (k = 0; k < g->max_iter; ++k) {
+		double z = x * y;
+		x *= x; y *= y;
+		if (x + y >= 4) break;
+		x = x - y + x0;
+		y = z + z + y0; 
+	}
+	g->k[i] = k;
+}
+
+void kt_for(int n_threads, int n_items, void (*func)(void*,int,int), void *data);
+
+int main(int argc, char *argv[])
+{
+	int i, tmp, tot, type = 0, n_threads = 2;
+	global_t global = { 10240*100, 800, 600, -2., -1.2, -1.2, 1.2, 0 };
+//	global_t global = { 10240*1, 8, 6, -2., -1.2, -1.2, 1.2, 0 };
+
+	if (argc > 1) {
+		type = argv[1][0] == 'o'? 2 : argv[1][0] == 'c'? 3 : argv[1][0] == 'n'? 1 : 0;
+		if (argv[1][0] >= '0' && argv[1][0] <= '9')
+			n_threads = atoi(argv[1]);
+	} else {
+		fprintf(stderr, "Usage: ./a.out [openmp | cilk | #threads]\n");
+	}
+	tot = global.w * global.h;
+	global.k = calloc(tot, sizeof(int));
+	for (i = 0; i < tot; ++i) global.k[i] = -1;
+	if (type == 0) {
+		kt_for(n_threads, tot, compute, &global);
+	} else if (type == 2) {
+		#pragma omp parallel for
+		for (i = 0; i < tot; ++i)
+			compute(&global, i, 0);
+	} else if (type == 3) {
+		#if HAVE_CILK
+		cilk_for (i = 0; i < tot; ++i)
+			compute(&global, i, 0);
+		#endif
+	}
+	for (i = tmp = 0; i < tot; ++i) tmp += (global.k[i] < 0);
+	free(global.k);
+	assert(tmp == 0);
+	return 0;
+}
diff --git a/debian/vendor-h2o/deps/klib/test/kvec_test.cc b/debian/vendor-h2o/deps/klib/test/kvec_test.cc
new file mode 100644
index 0000000..1015574
--- /dev/null
+++ b/debian/vendor-h2o/deps/klib/test/kvec_test.cc
@@ -0,0 +1,69 @@
+#include <vector>
+#include <time.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include "kvec.h"
+
+int main()
+{
+	int M = 10, N = 20000000, i, j;
+	clock_t t;
+	t = clock();
+	for (i = 0; i < M; ++i) {
+		int *array = (int*)malloc(N * sizeof(int));
+		for (j = 0; j < N; ++j) array[j] = j;
+		free(array);
+	}
+	printf("C array, preallocated: %.3f sec\n",
+		   (float)(clock() - t) / CLOCKS_PER_SEC);
+	t = clock();
+	for (i = 0; i < M; ++i) {
+		int *array = 0, max = 0;
+		for (j = 0; j < N; ++j) {
+			if (j == max) {
+				max = !max? 1 : max << 1;
+				array = (int*)realloc(array, sizeof(int)*max);
+			}
+			array[j] = j;
+		}
+		free(array);
+	}
+	printf("C array, dynamic: %.3f sec\n",
+		   (float)(clock() - t) / CLOCKS_PER_SEC);
+	t = clock();
+	for (i = 0; i < M; ++i) {
+		kvec_t(int) array;
+		kv_init(array);
+		kv_resize(int, array, N);
+		for (j = 0; j < N; ++j) kv_a(int, array, j) = j;
+		kv_destroy(array);
+	}
+	printf("C vector, dynamic(kv_a): %.3f sec\n",
+		   (float)(clock() - t) / CLOCKS_PER_SEC);
+	t = clock();
+	for (i = 0; i < M; ++i) {
+		kvec_t(int) array;
+		kv_init(array);
+		for (j = 0; j < N; ++j)
+			kv_push(int, array, j);
+		kv_destroy(array);
+	}
+	printf("C vector, dynamic(kv_push): %.3f sec\n",
+		   (float)(clock() - t) / CLOCKS_PER_SEC);
+	t = clock();
+	for (i = 0; i < M; ++i) {
+		std::vector<int> array;
+		array.reserve(N);
+		for (j = 0; j < N; ++j) array[j] = j;
+	}
+	printf("C++ vector, preallocated: %.3f sec\n",
+		   (float)(clock() - t) / CLOCKS_PER_SEC);
+	t = clock();
+	for (i = 0; i < M; ++i) {
+		std::vector<int> array;
+		for (j = 0; j < N; ++j) array.push_back(j);
+	}
+	printf("C++ vector, dynamic: %.3f sec\n",
+		   (float)(clock() - t) / CLOCKS_PER_SEC);
+	return 0;
+}