removed buggy qsort header and implemented myself

8 files changed, 460 insertions, 61 deletions

diff --git a/sys/libbio/align.c b/sys/libbio/align.c
index 8d1c119..0f00fce 100644
--- a/sys/libbio/align.c
+++ b/sys/libbio/align.c
@@ -87,16 +87,24 @@ sortpos(uintptr len, uint64 vals[], int locs[])
 #undef SWAP
 }
 
+/*
+ * sketch
+ * @param seq:  '0' terminated string
+ * @param len:  number of sequential sketches to keep
+ * @param vals: buffer to store hashes of sketch.
+ * @param locs: buffer to store location of sketch hashes
+ */
 error
-aln·sketch(byte *seq, int L, uint64 *vals[aln·N], int *locs[aln·N])
+aln·sketch(byte *seq, int len, uint64 *vals[aln·N], int *locs[aln·N])
 {
     int    i, n, l, *loc;
-    uint64 kmer, tmp[4], h[3], *val;
+    uint64 kmer, h[3], *val;
+    int    tmpi[2];
+    uint64 tmpu[2];
 
     for (n = 0; n < aln·N; n++) {
-        val = vals[n];
-        for (l = 0; l < L; l++) {
-            val[l] = UINT64_MAX;
+        for (l = 0; l < len; l++) {
+            vals[n][l] = UINT64_MAX;
         }
     }
 
@@ -112,26 +120,21 @@ aln·sketch(byte *seq, int L, uint64 *vals[aln·N], int *locs[aln·N])
             loc = locs[n];
 
             h[2] = (h[0] + n * h[1]) & aln·mask;
-            for (i = 0; i < L && h[2] < val[i]; i++) {
+            for (i = 0; i < len && h[2] < val[i]; i++) {
                 ;
             }
 
-            tmp[1] = h[2];
-            tmp[3] = l;
+            tmpu[1] = h[2];
+            tmpi[1] = l;
             for (i -= 1; i >= 0; i--) {
-                tmp[0] = tmp[1];
-                tmp[1] = val[i];
-                val[i] = tmp[0];
-
-                tmp[2] = tmp[3];
-                tmp[3] = loc[i];
-                loc[i] = tmp[2];
+                tmpu[0] = tmpu[1], tmpu[1] = val[i], val[i] = tmpu[0];
+                tmpi[0] = tmpi[1], tmpi[1] = loc[i], loc[i] = tmpi[0];
             }
         }
     }
 
     for (n = 0; n < aln·N; n++) {
-        sortpos(L, vals[n], locs[n]);
+        sortpos(len, vals[n], locs[n]);
     }
     
     return 0;
@@ -139,30 +142,37 @@ aln·sketch(byte *seq, int L, uint64 *vals[aln·N], int *locs[aln·N])
 
 static
 int
-cmparrs(int L, uint64 a[], uint64 b[])
+lessarrs(int len, uint64 a[], uint64 b[])
 {
     int l;
 
-    for (l = 0; l < L; l++) {
-        if (a[l] < b[l]) return -1;
+    for (l = 0; l < len; l++) {
+        if (a[l] < b[l]) return 1;
+        if (a[l] > b[l]) return 0;
     }
 
-    return +1;
+    return 0;
+}
+
+static
+void
+swaparrs(int len, uint64 a[], uint64 b[])
+{
+    int l;
+    uint64 tmp;
+
+    for (l = 0; l < len; l++) {
+        tmp = a[l], a[l] = b[l], b[l] = tmp;
+    }
 }
 
-// TODO: replace with inlined version
 error
-aln·sort(uintptr len, int L, uint64 *vals)
+aln·sort(uintptr n, int len, uint64 *vals)
 {
-    uint64 tmp[128];
-#define LESS(i, j) (cmparrs((L), (vals+(i)*L), (vals+(j)*L)))
-#define SWAP(i, j) (memcpy(tmp, (vals+(i)*L), (sizeof(uint64)*L)),     \
-                    memcpy((vals+(i)*L), (vals+(j)*L), (sizeof(uint64)*L)), \
-                    memcpy((vals+(j)*L), tmp,  (sizeof(uint64)*L)))
-       
-    QSORT(len, LESS, SWAP);
+#define LESS(i, j) (lessarrs(len, vals+((i)*len), vals+((j)*len)))
+#define SWAP(i, j) (swaparrs(len, vals+((i)*len), vals+((j)*len)))
+    QSORT(n, LESS, SWAP);
 #undef LESS
 #undef SWAP
-    // qsort(vals, len, l*sizeof(uint64), &compare);
     return 0;
 }
diff --git a/sys/libbio/phylo.c b/sys/libbio/phylo.c
index 1cc5b5d..1bb5bc7 100644
--- a/sys/libbio/phylo.c
+++ b/sys/libbio/phylo.c
@@ -1,5 +1,6 @@
 #include <u.h>
 #include <libn.h>
+#include <libn/macro/qsort.h>
 #include <libbio.h>
 
 // -----------------------------------------------------------------------
@@ -50,6 +51,8 @@ FOUND:
     } else {
         prev->sibling = child->sibling;
     }
+
+    parent->nchild--;
     return error·nil;
 }
 
@@ -97,6 +100,55 @@ phylo·countleafs(bio·Node *node, int *n)
 }
 
 // -----------------------------------------------------------------------
+// generic operations on tree
+
+void*
+phylo·postorder(bio·Node *clade, void *(*op)(bio·Node*, void*), void *ctx)
+{
+    bio·Node *it;
+
+    for (it = clade->child; it != nil; it = it->sibling) {
+        ctx = phylo·postorder(it, op, ctx);
+    }
+
+    return op(clade, ctx);
+}
+
+void*
+phylo·preorder(bio·Node *clade, void *(*op)(bio·Node*, void*), void *ctx)
+{
+    bio·Node *it;
+
+    ctx = op(clade, ctx);
+    for (it = clade->child; it != nil; it = it->sibling) {
+        ctx = phylo·preorder(it, op, ctx);
+    }
+
+    return ctx;
+}
+
+static
+inline
+void*
+appendleaf(bio·Node *node, void* list)
+{
+    bio·Node **leafs;
+
+    leafs = list;
+    if (!node->nchild) {
+        *leafs++ = node;
+    }
+
+    return leafs;
+}
+
+void
+phylo·getleafs(bio·Tree tree, bio·Node **leafs)
+{
+    phylo·postorder(tree.root, &appendleaf, leafs);
+}
+
+// -----------------------------------------------------------------------
 // tree editing
 
 static
@@ -147,64 +199,219 @@ phylo·ladderize(bio·Node *root)
     return 0;
 }
 
+/*
+ * compute all distances from a given node
+ * must provide a working buffer
+ */
+
+struct Tuple 
+{
+    double   *d;
+    bio·Node **n;
+};
+
+static
+struct Tuple
+getdistsfrom(bio·Node *node, bio·Node *prev, double curr, double *dist, bio·Node **list)
+{
+    bio·Node     *it;
+    struct Tuple ret;
+
+    *dist++ = curr;
+    *list++ = node;
+
+    ret.d = dist;
+    ret.n = list;
+
+    if (node->parent && node->parent != prev) {
+        ret = getdistsfrom(node->parent, node, curr + node->dist, dist, list);
+
+        dist = ret.d;
+        list = ret.n;
+    }
+
+    for (it = node->child; it != nil; it = it->sibling) {
+        if (it != prev) {
+            ret = getdistsfrom(it, node, curr + it->dist, dist, list);
+
+            dist = ret.d;
+            list = ret.n;
+        }
+    }
+
+    return ret;
+}
+
+int
+phylo·getdistsfrom(bio·Node *node, int len, double *dist, bio·Node **list)
+{
+    struct Tuple ret;
+    // TODO: Better bounds checking.
+
+    ret = getdistsfrom(node, nil, 0.0, dist, list);
+
+    assert(ret.n - list == len);
+    assert(ret.d - dist == len);
+
+    return len;
+}
+
+/*
+static
+void
+disttoroot(bio·Node *clade, double anc, double *dists)
+{
+    double    d;
+    bio·Node *it;
+
+    *dists++ = anc + clade->dist; 
+    d = dists[-1];
+    for (it = clade->child; it != nil; it = it->sibling) {
+        disttoroot(it, d, ++dists);
+    }
+}
+
+void
+phylo·disttoroot(bio·Tree tree, double *dists)
+{
+    disttoroot(tree.root, 0.0, dists);
+}
+*/
+
+/*
+ * compute the path constituting the tree diameter
+ * returns the number of edges in the path
+ */
+
+static
+void
+sort·nodedists(uintptr len, double fs[], bio·Node* ns[])
+{
+    double    f;
+    bio·Node *n;
+#define LESS(i, j) (fs[i] < fs[j])
+#define SWAP(i, j) (n     = ns[i], f     = fs[i], \
+                    fs[i] = fs[j], ns[i] = ns[j], \
+                    fs[j] = f,     ns[j] = n)
+        QSORT(len, LESS, SWAP);
+#undef LESS
+#undef SWAP
+}
+
+#define BUFLEN 4096
+double
+phylo·diameter(bio·Tree tree, int *len, bio·Node **path)
+{
+    // TODO: deal with large tree > BUFLEN gracefully
+    int       n;
+    double    fbuf[BUFLEN];
+    bio·Node *nbuf[BUFLEN];
+
+    n = tree.root->nnode;
+
+    assert(n < BUFLEN);
+
+    n = phylo·getdistsfrom(tree.root, tree.root->nnode, fbuf, nbuf);
+    sort·nodedists(n, fbuf, nbuf);
+
+    path[0] = nbuf[n-1];
+    printf("first end '%s'\n", path[0]->name);
+
+    n = phylo·getdistsfrom(path[0], n, fbuf, nbuf);
+    sort·nodedists(n, fbuf, nbuf);
+    printf("second end '%s'\n", nbuf[n-1]->name);
+
+    *len = 0;
+
+    // TODO: Traverse up the tree from each node
+    //       Find MRCA by intersection of nodes hit
+
+    return 0.0;
+}
+#undef BUFLEN
+
+/*
+ * reroot a tree on a new node
+ */
 static
 error
 rotateparent(bio·Node *node, bio·Node *to)
 {
     error err;
-    bio·Node *it, *prev;
 
+    // NOTE: will this ever be taken?
     if (node->parent == to) {
         return 0;
     }
 
-    prev = nil;
-    for (it = node->child; it != nil; it = it->sibling) {
-        if (it == to) goto FOUND;
-        prev = it;
+    if (!node->parent) {
+        goto RMCHILD;
     }
-    errorf("inconsistent topology: attempting to rotate to non-child");
-    return 1;
 
-FOUND:
-    if (err = rotateparent(node->parent, node), err) {
+    err = rotateparent(node->parent, node);
+    if (err) {
         errorf("failure: broken tree");
         return err;
     }
 
-    if (!prev) {
-        node->child   = node->parent;
-    } else {
-        prev->sibling = node->parent;
+    err = phylo·addchild(node, node->parent);
+    if (err) {
+        errorf("inconsistent topology: could not add parent '%s' as child of '%s'", node->parent->name, node->name);
+        return err;
     }
-    node->parent->sibling = it->sibling;
-    node->parent          = to;
 
+RMCHILD:
+    err = phylo·rmchild(node, to);
+    if (err) {
+        errorf("inconsistent topology: could not remove child '%s' from '%s'", to->name, node->name);
+        return err;
+    }
+    
+    node->parent = to;
     return 0;
 }
 
-#define FLOAT_PREC .00000001
+#define PREC .00000001
 error
 phylo·reroot(bio·Tree *tree, bio·Node *node, double d)
 {
-    bio·Node *old;
     bio·Node *new;
 
     // TODO: should check that node is part of this tree?
+    // TODO: should we check if node->parent != nil?
     
-    old = tree->root;
-    if (fabs(d) < FLOAT_PREC)            new = node;
-    if (fabs(d-node->dist) < FLOAT_PREC) new = node->parent;
-    else {
+    if (fabs(d) < PREC) {
+        new = node;
+        rotateparent(node->parent, node);
+    } else if (fabs(d-node->dist) < PREC) {
+        new = node->parent;
+        if (new->parent->parent) {
+            rotateparent(new->parent->parent, new->parent);
+        }
+    } else {
         new = tree->heap.alloc(tree->h, 1, sizeof(*new));
         memset(new, 0, sizeof(*new));
+
+        phylo·addchild(new, node);
+        node->parent = new;
+
+        phylo·addchild(new, node->parent);
+        if (node->parent->parent) {
+            rotateparent(node->parent->parent, node->parent);
+        }
+        node->parent->parent = new;
     }
 
-    // TODO: Use rotateparent() to perform necessary flips
+    printf("number of children on old root: %d\n", tree->root->nchild);
+    tree->root  = new;
+    tree->nleaf = 0;
+
+    phylo·countleafs(new, &tree->nleaf);
+    phylo·countnodes(new, &new->nnode);
 
-    tree->root = new;
     return 0;
 }
+#undef PREC
 
 // -----------------------------------------------------------------------
 // ancestral inference
@@ -216,7 +423,7 @@ struct phylo·InferOpts
 };
 
 error
-phylo·ancestralinfer(bio·Tree *tree, struct phylo·InferOpts opts)
+phylo·inferancestral(bio·Tree *tree, struct phylo·InferOpts opts)
 {
     return 0;
 }
diff --git a/sys/libbio/rules.mk b/sys/libbio/rules.mk
index fd3e066..0e3d482 100644
--- a/sys/libbio/rules.mk
+++ b/sys/libbio/rules.mk
@@ -21,7 +21,7 @@ LIBS_$(d) := $(d)/libbio.a
 LIBS_$(d) := $(patsubst $(SRC_DIR)/%, $(OBJ_DIR)/%, $(LIBS_$(d)))
 LIBS 	  := $(LIBS) $(LIBS_$(d))
 
-BINS_$(d) := $(d)/test
+BINS_$(d) := $(d)/test $(d)/simulate
 BINS_$(d) := $(patsubst $(SRC_DIR)/%, $(OBJ_DIR)/%, $(BINS_$(d)))
 BINS 	  := $(BINS) $(BINS_$(d))
 
diff --git a/sys/libbio/simulate.c b/sys/libbio/simulate.c
new file mode 100644
index 0000000..a4567d5
--- /dev/null
+++ b/sys/libbio/simulate.c
@@ -0,0 +1,117 @@
+#include <u.h>
+#include <libn.h>
+#include <libbio.h>
+
+#define SEQLEN 2560
+static byte *SEQ =
+"GGCGGCTTCGGTGCGCTGTGTGCATTGCCGCAAAAATATCGTGAACCCGTGCTGGTTTCCGGCACTGACGGCGTAGGTAC"
+"CAAGCTGCGTCTGGCAATGGACTTAAAACGTCACGACACCATTGGTATTGATCTGGTCGCCATGTGCGTTAATGACCTGG"
+"TGGTGCAAGGTGCGGAACCGCTGTTTTTCCTCGACTATTACGCAACCGGAAAACTGGATGTTGATACCGCTTCAGCGGTG"
+"ATCAGCGGCATTGCGGAAGGTTGTCTGCAATCGGGCTGTTCTCTGGTGGGTGGCGAAACGGCAGAAATGCCGGGGATGTA"
+"TCACGGTGAAGATTACGATGTCGCGGGTTTCTGCGTGGGCGTGGTAGAAAAATCAGAAATCATCGACGGCTCTAAAGTCA"
+"GCGACGGCGATGTGCTGATTGCACTCGGTTCCAGCGGTCCGCACTCGAACGGTTATTCGCTGGTGCGCAAAATTCTTGAA"
+"GTCAGCGGTTGTGATCCGCAAACCACCGAACTTGATGGTAAGCCATTAGCCGATCATCTGCTGGCACCGACCCGCATTTA"
+"CGTGAAGTCAGTGCTGGAGTTGATTGAAAAGGTCGATGTGCATGCCATTGCGCACCTGACCGGCGGCGGCTTCTGGGAAA"
+"ACATTCCGCGCGTATTGCCAGATAATACCCAGGCAGTGATTGATGAATCTTCCTGGCAGTGGCCGGAAGTGTTCAACTGG"
+"CTGCAAACGGCAGGTAACGTTGAGCGCCATGAAATGTATCGCACCTTCAACTGCGGCGTCGGGATGATTATCGCCCTGCC"
+"TGCTCCGGAAGTGGACAAAGCCCTCGCCCTGCTCAATGCCAACGGTGAAAACGCGTGGAAAATCGGTATCATCAAAGCCT"
+"CTGATTCCGAACAACGCGTGGTTATCGAATAATGAATATTGTGGTGCTTATTTCCGGCAACGGAAGTAATTTACAGGCAA"
+"TTATTGACGCCTGTAAAACCAACAAAATTAAAGGCACCGTACGGGCAGTTTTCAGCAATAAGGCCGACGCGTTCGGCCTT"
+"GAACGCGCCCGCCAGGCGGGTATTGCAACGCATACGCTCATCGCCAGCGCGTTTGACAGTCGTGAAGCCTATGACCGGGA"
+"GTTGATTCATGAAATCGACATGTACGCACCCGATGTGGTCGTGCTGGCTGGTTTTATGCGCATTCTCAGCCCGGCGTTTG"
+"TCTCCCACTATGCCGGGCGTTTGCTGAACATTCACCCTTCTCTGCTGCCGAAATATCCCGGATTACACACCCATCGTCAA"
+"GCGCTGGAAAATGGCGATGAAGAGCACGGTACATCGGTGCATTTCGTCACCGATGAACTGGACGGTGGCCCGGTTATTTT"
+"ACAGGCGAAAGTCCCGGTATTTGCTGGTGATACGGAAGATGACGTCACCGCCCGCGTGCAAACCCAGGAACACGCCATTT"
+"ATCCACTGGTGATTAGCTGGTTTGCCGATGGTCGTCTGAAAATGCACGAAAACGCCGCGTGGCTGGATGGTCAACGTCTG"
+"CCGCCGCAGGGCTACGCTGCCGACGAGTAATGCCCCCGTAGTTAAAGCGCCAGCTCTGCCGCTGGCGTTTTTCAATTCAC"
+"CTGTAAATCGCAAGCTCCAGCAGTTTTTTTCCCCCTTTTCTGGCATAGTTGGACATCTGCCAATATTGCTCGCCATAATA"
+"TCCAGGCAGTGTCCCGTGAATAAAACGGAGTAAAAGTGGTAATGGGTCAGGAAAAGCTATACATCGAAAAAGAGCTCAGT"
+"TGGTTATCGTTCAATGAACGCGTGCTTCAGGAAGCGGCGGACAAATCTAACCCGCTGATTGAAAGGATGCGTTTCCTGGG"
+"GATCTATTCCAATAACCTTGATGAGTTCTATAAAGTCCGCTTCGCTGAACTGAAGCGACGCATCATTATTAGCGAAGAAC"
+"AAGGCTCCAACTCTCATTCCCGCCATTTACTGGGCAAAATTCAGTCCCGGGTGCTGAAAGCCGATCAGGAATTCGACGGC"
+"CTCTACAACGAGCTATTGCTGGAGATGGCGCGCAACCAGATCTTCCTGATTAATGAACGCCAGCTCTCCGTCAATCAACA"
+"AAACTGGCTGCGTCATTATTTTAAGCAGTATCTGCGTCAGCACATTACGCCGATTTTAATCAATCCTGACACTGACTTAG"
+"TGCAGTTCCTGAAAGATGATTACACCTATCTGGCGGTGGAAATTATCCGTGGCGATACCATCCGTTACGCGCTTCTGGAG"
+"ATCCCATCAGATAAAGTGCCGCGCTTTGTGAATTTACCGCCAGAAGCGCCGCGTCGACGCAAGCCGATGATTCTTCTGGA"
+"TAACATTCTGCGTTACTGCCTTGATGATATTTTCAAAGGCTTCTTTGATTATGACGCGCTGAATGCCTATTCAATGAAGA"
+"TGACCCGCGATGCCGAATACGATTTAGTGCATGAGATGGAAGCCAGCCTGATGGAGTTGATGTCTTCCAGTCTCAAGCAG"
+"CGTTTAACTGCTGAGCCGGTGCGTTTTGTTTATCAGCGCGATATGCCCAATGCGCTGGTTGAAGTTTTACGCGAAAAACT";
+
+byte*
+modify(byte *seq, int *len, double p)
+{
+    byte *head, *new;
+
+    head = calloc(SEQLEN+1, sizeof(byte));
+    new  = head;
+    for (; *seq != '\0'; seq++) {
+        if (rng·bernoulli(p)) {
+            switch (rng·randi(5)) {
+            case 0: *new++ = 'A'; break;
+            case 1: *new++ = 'C'; break;
+            case 2: *new++ = 'G'; break;
+            case 3: *new++ = 'T'; break;
+            case 4: continue;
+            }
+        } else {
+            *new++ = *seq;
+        }
+    }
+    *new = '\0';
+    *len = new - head;
+    return head;
+}
+
+#define NSEQS 20
+int
+main()
+{
+    int n, i, l, lens[NSEQS];
+    byte     *seqs[NSEQS];
+
+    int    locs[aln·N][NSEQS][aln·L];
+    int    *loc[aln·N];
+    uint64 vals[aln·N][NSEQS][aln·L];
+    uint64 *val[aln·N];
+    rng·init(0);
+
+    seqs[0] = SEQ;
+    lens[0] = SEQLEN;
+
+    for (n = 0; n < aln·N; n++) {
+        for (i = 0; i < NSEQS; i++) {
+            for (l = 0; l < aln·L; l++) {
+                vals[n][i][l] = 0;
+            }
+        }
+    }
+
+    for (i = 1; i < NSEQS; i++) {
+        seqs[i] = modify(SEQ, lens + i, .01*i);
+    }
+
+    for (i = 0; i < NSEQS; i++) {
+        for (n = 0; n < aln·N; n++) {
+            val[n] = vals[n][i];
+            loc[n] = locs[n][i];
+        }
+        aln·sketch(seqs[i], aln·L, val, loc);
+    }
+
+    // for (n = 0; n < aln·N; n++) {
+    //     printf("iteration %d\n", n);
+    //     printf("[\n");
+    //     for (i = 0; i < NSEQS; i++) {
+    //         printf("  [");
+    //         for (l = 0; l < aln·L; l++) {
+    //             printf("%lu,", vals[n][i][l]);
+    //         }
+    //         printf("],\n");
+    //     }
+    //     printf("]\n");
+    // }
+
+    for (n = 0; n < aln·N; n++) {
+        aln·sort(NSEQS, aln·L, (uint64*)vals[n]);
+    }
+}
diff --git a/sys/libbio/test.c b/sys/libbio/test.c
index 8054864..da29c84 100644
--- a/sys/libbio/test.c
+++ b/sys/libbio/test.c
@@ -99,6 +99,8 @@ test·newick()
     io·Peeker     rdr;
     io·Putter     wtr;
 
+    bio·Node **end, **it, **list;
+
     heap = mem·makearena(mem·sys, nil);
     rdr  = (io·Peeker){.get = &io·getbyte, .unget  = &io·ungetbyte};
     wtr  = (io·Putter){.put = &io·putbyte, .putstr = &io·putstring};
@@ -109,8 +111,22 @@ test·newick()
     t.h    = heap;
     t.heap = (mem·Allocator){ .alloc = &mem·arenaalloc, .free = nil, };
 
-    err = bio·readnewick(rdr, fd[0], &t);
+    if (err = bio·readnewick(rdr, fd[0], &t), err) {
+        errorf("failed to read newick");
+        return 1;
+    }
+    printf("number of children: %d\n", t.root->nchild);
+
     phylo·ladderize(t.root);
+    
+    list = mem·arenaalloc(heap, t.nleaf, sizeof(**list));
+    phylo·getleafs(t, list);
+    for (it = list, end = list + t.nleaf; it != end; ++it) {
+        printf("Leaf '%s'\n", (*it)->name);
+    }
+
+    bio·Node *path[100];
+    // phylo·diameter(t, path);
 
     printf("Loaded tree with %d leafs and %d nodes\n", t.nleaf, t.root->nnode);
     err = bio·writenewick(t, wtr, fd[1]);
diff --git a/sys/libmath/blas.c b/sys/libmath/blas.c
index c2f7e6c..bbbe1c8 100644
--- a/sys/libmath/blas.c
+++ b/sys/libmath/blas.c
@@ -3,7 +3,6 @@
 #include <vendor/blas/cblas.h>
 
 #include <x86intrin.h>
-
 #include <time.h>
 
 // -----------------------------------------------------------------------
@@ -382,7 +381,6 @@ void
 blas·gemm(int n1, int n2, int n3, double a, double *m1, double *m2, double b, double *m3)
 {
     int i, j, k, len;
-    double prod;
 
     // TODO: Is there anyway this computation can be integrated into the one below?
     for (i = 0; i < n1; i++) {
diff --git a/sys/libn/rules.mk b/sys/libn/rules.mk
index 4731558..ffb41e4 100644
--- a/sys/libn/rules.mk
+++ b/sys/libn/rules.mk
@@ -24,7 +24,7 @@ LIBS_$(d) := $(d)/libn.a
 LIBS_$(d) := $(patsubst $(SRC_DIR)/%, $(OBJ_DIR)/%, $(LIBS_$(d)))
 LIBS 	  := $(LIBS) $(LIBS_$(d))
 
-BINS_$(d) := $(d)/test
+BINS_$(d) := $(d)/test $(d)/scratch
 BINS_$(d) := $(patsubst $(SRC_DIR)/%, $(OBJ_DIR)/%, $(BINS_$(d)))
 BINS 	  := $(BINS) $(BINS_$(d))
 
@@ -37,7 +37,7 @@ $(LIBS_$(d)): $(OBJS_$(d))
 	$(ARCHIVE)
 
 $(BINS_$(d)): TCLIBS := $(LIBS_$(d)) $(LIB_DIR)/vendor/libz.a
-$(BINS_$(d)): $(OBJS_$(d)) $(OBJ_DIR)/libn/test.o
+$(BINS_$(d)): $(OBJ_DIR)/libn/scratch.o
 	$(LINK)
 
 # ---- Pop off stack ----
diff --git a/sys/libn/test.c b/sys/libn/test.c
index 3a21a71..973245f 100644
--- a/sys/libn/test.c
+++ b/sys/libn/test.c
@@ -1,5 +1,6 @@
 #include <u.h>
 #include <libn.h>
+#include <libn/macro/map.h>
 
 #include <time.h>
 
@@ -122,7 +123,7 @@ error
 test·sort()
 {
     clock_t t;
-    int i, test[1000000];
+    int i, test[10000];
     for (i = 0; i < arrlen(test); i++) {
         test[i] = rand();
     }
@@ -154,6 +155,56 @@ test·sort()
     return 0;
 }
 
+#define HASH(str) hash_string(str)
+#define EQUAL(str, str2) (str == str2)
+
+typedef struct Map
+{
+    MAP_STRUCT_BODY(byte*, float)
+} Map;
+
+Map*
+makemap(mem·Allocator heap, void* h)
+{
+    MAP_MAKE(Map);
+}
+
+void
+mapfree(Map *map)
+{
+    MAP_FREE(map);
+}
+
+void
+mapreset(Map *map)
+{
+    MAP_RESET(map);
+}
+
+double
+mapget(Map *map, byte *key)
+{
+    MAP_GET(map, key, HASH, EQUAL);
+}
+
+static
+error
+mapresize(Map *map, int n)
+{
+    MAP_GROW(map, byte*, float, n, HASH);
+}
+
+static
+int
+mapput(Map *map, byte *key, float val, error *err)
+{
+    MAP_PUT(map, key, val, HASH, EQUAL, mapresize, err);
+}
+
+
+#undef HASH
+#undef EQUAL
+
 error
 main()
 {