shithub: mc

Info  •  Files  •  Log  •  Branches

Extract util functions into separate dir from parse/

--- a/6/Makefile

+++ b/6/Makefile

@@ -12,7 +12,7 @@

 	simp.o \

 	typeinfo.o \

-DEPS=../parse/libparse.a ../mi/libmi.a

+DEPS=../parse/libparse.a ../mi/libmi.a ../util/libutil.a

 include ../config.mk

 include ../mk/c.mk

--- a/6/blob.c

+++ b/6/blob.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "asm.h"

--- a/6/gen.c

+++ b/6/gen.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "asm.h"

--- a/6/gengas.c

+++ b/6/gengas.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "asm.h"

--- a/6/genp9.c

+++ b/6/genp9.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "asm.h"

--- a/6/isel.c

+++ b/6/isel.c

@@ -11,6 +11,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "asm.h"

--- a/6/locs.c

+++ b/6/locs.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "asm.h"

--- a/6/main.c

+++ b/6/main.c

@@ -13,6 +13,7 @@

 #include <sys/time.h>

 #include <sys/wait.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "asm.h"

--- a/6/peep.c

+++ b/6/peep.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "asm.h"

--- a/6/ra.c

+++ b/6/ra.c

@@ -7,6 +7,7 @@

 #include <limits.h>

 #include <string.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "asm.h"

--- a/6/simp.c

+++ b/6/simp.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "asm.h"

--- a/6/typeinfo.c

+++ b/6/typeinfo.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "asm.h"

--- a/Makefile

+++ b/Makefile

@@ -3,6 +3,7 @@

       6 \

       muse \

       rt \

+      util \

       doc

 EXTRA=buildmyr

--- a/mi/Makefile

+++ b/mi/Makefile

@@ -7,6 +7,6 @@

 	reaching.o \

-DEPS=../parse/libparse.a

+DEPS=../parse/libparse.a ../util/libutil.a

 include ../mk/c.mk

--- a/mi/cfg.c

+++ b/mi/cfg.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

--- a/mi/dfcheck.c

+++ b/mi/dfcheck.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

--- a/mi/flatten.c

+++ b/mi/flatten.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

 #include "../config.h"

--- a/mi/match.c

+++ b/mi/match.c

@@ -9,6 +9,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

--- a/mi/reaching.c

+++ b/mi/reaching.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "mi.h"

--- a/muse/Makefile

+++ b/muse/Makefile

@@ -2,7 +2,7 @@

 BIN=muse

 OBJ=muse.o

-DEPS=../parse/libparse.a

+DEPS=../parse/libparse.a ../util/libutil.a

 include ../mk/c.mk

 include ../config.mk

--- a/muse/muse.c

+++ b/muse/muse.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "../config.h"

--- a/parse/Makefile

+++ b/parse/Makefile

@@ -1,21 +1,23 @@

 LIB=libparse.a

-OBJ=bitset.o \

-    dump.o \

-    fold.o \

-    gram.o \

-    htab.o \

-    infer.o \

-    names.o \

-    node.o \

-    specialize.o \

-    stab.o \

-    tok.o \

-    type.o \

-    use.o \

-    util.o

+OBJ=\

+	bitset.o \

+	dump.o \

+	err.o \

+	fold.o \

+	gram.o \

+	infer.o \

+	names.o \

+	node.o \

+	specialize.o \

+	stab.o \

+	tok.o \

+	type.o \

+	use.o \

 GENHDR=gram.h

 CLEAN=gram.c gram.h

+

+DEPS=../util/libutil.a

 include ../mk/lexyacc.mk

 include ../mk/c.mk

--- a/parse/bitset.c

+++ b/parse/bitset.c

@@ -6,6 +6,7 @@

 #include <limits.h>

 #include <string.h>

+#include "util.h"

 #include "parse.h"

 #define Sizetbits (CHAR_BIT * sizeof(size_t)) /* used in graph reprs */

--- a/parse/dump.c

+++ b/parse/dump.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 /* outputs a fully qualified name */

--- a/parse/fold.c

+++ b/parse/fold.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 static int getintlit(Node *n, vlong *v)

--- a/parse/gram.y

+++ b/parse/gram.y

@@ -14,6 +14,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

--- a/parse/htab.c

+++ /dev/null

@@ -1,288 +1,0 @@

-#include <stdlib.h>

-#include <stdio.h>

-#include <stdarg.h>

-#include <inttypes.h>

-#include <assert.h>

-#include <limits.h>

-#include <string.h>

-

-#include "parse.h"

-

-#define Initsz 16

-

-/* Creates a new empty hash table, using 'hash' as the

- * hash funciton, and 'cmp' to verify that there are no

- * hash collisions. */

-Htab *mkht(ulong (*hash)(void *key), int (*cmp)(void *k1, void *k2))

-{

-	Htab *ht;

-

-	ht = xalloc(sizeof(Htab));

-	ht->nelt = 0;

-	ht->ndead = 0;

-	ht->sz = Initsz;

-	ht->hash = hash;

-	ht->cmp = cmp;

-	ht->keys = zalloc(Initsz * sizeof(void *));

-	ht->vals = zalloc(Initsz * sizeof(void *));

-	ht->hashes = zalloc(Initsz * sizeof(void *));

-	ht->dead = zalloc(Initsz * sizeof(char));

-

-	return ht;

-}

-

-/* Frees a hash table. Passing this function

- * NULL is a no-op. */

-void htfree(Htab *ht)

-{

-	if (!ht)

-		return;

-	free(ht->keys);

-	free(ht->vals);

-	free(ht->hashes);

-	free(ht->dead);

-	free(ht);

-}

-

-/* Offsets the hash so that '0' can be

- * used as a 'no valid value */

-static ulong hash(Htab *ht, void *k)

-{

-	ulong h;

-	h = ht->hash(k);

-	if (h == 0)

-		return 1;

-	else

-		return h;

-}

-

-/* Resizes the hash table by copying all

- * the old keys into the right slots in a

- * new table. */

-static void grow(Htab *ht, int sz)

-{

-	void **oldk;

-	void **oldv;

-	ulong *oldh;

-	char *oldd;

-	int oldsz;

-	int i;

-

-	oldk = ht->keys;

-	oldv = ht->vals;

-	oldh = ht->hashes;

-	oldd = ht->dead;

-	oldsz = ht->sz;

-

-	ht->nelt = 0;

-	ht->ndead = 0;

-	ht->sz = sz;

-	ht->keys = zalloc(sz * sizeof(void *));

-	ht->vals = zalloc(sz * sizeof(void *));

-	ht->hashes = zalloc(sz * sizeof(void *));

-	ht->dead = zalloc(sz * sizeof(void *));

-

-	for (i = 0; i < oldsz; i++)

-		if (oldh[i] && !oldd[i])

-			htput(ht, oldk[i], oldv[i]);

-

-	free(oldh);

-	free(oldk);

-	free(oldv);

-	free(oldd);

-}

-

-/* Inserts 'k' into the hash table, possibly

- * killing any previous key that compares

- * as equal. */

-int htput(Htab *ht, void *k, void *v)

-{

-	int i;

-	ulong h;

-	int di;

-

-	di = 0;

-	h = hash(ht, k);

-	i = h & (ht->sz - 1);

-	while (ht->hashes[i] && !ht->dead[i]) {

-		/* second insertion overwrites first. nb, we shouldn't touch the

-		 * keys for dead values */

-		if (ht->hashes[i] == h) {

-			if (ht->dead[i])

-				break;

-			else if (ht->cmp(ht->keys[i], k))

-				goto conflicted;

-		}

-		di++;

-		i = (h + di) & (ht->sz - 1);

-	}

-	ht->nelt++;

-conflicted:

-	if (ht->dead[i])

-		ht->ndead--;

-	ht->hashes[i] = h;

-	ht->keys[i] = k;

-	ht->vals[i] = v;

-	ht->dead[i] = 0;

-

-	if (ht->sz < ht->nelt * 2)

-		grow(ht, ht->sz * 2);

-	if (ht->sz < ht->ndead * 4)

-		grow(ht, ht->sz);

-	return 1;

-}

-

-/* Finds the index that we would insert

- * the key into */

-static ssize_t htidx(Htab *ht, void *k)

-{

-	ssize_t i;

-	ulong h;

-	int di;

-

-	di = 0;

-	h = hash(ht, k);

-	i = h & (ht->sz - 1);

-	while (ht->hashes[i] && !ht->dead[i] && ht->hashes[i] != h) {

-searchmore:

-		di++;

-		i = (h + di) & (ht->sz - 1);

-	}

-	if (!ht->hashes[i])

-		return -1;

-	if ((ht->hashes[i] == h && ht->dead[i]) || !ht->cmp(ht->keys[i], k))

-		goto searchmore; /* collision */

-	return i;

-}

-

-/* Looks up a key, returning NULL if

- * the value is not present. Note,

- * if NULL is a valid value, you need

- * to check with hthas() to see if it's

- * not there */

-void *htget(Htab *ht, void *k)

-{

-	ssize_t i;

-

-	i = htidx(ht, k);

-	if (i < 0)

-		return NULL;

-	else

-		return ht->vals[i];

-}

-

-void htdel(Htab *ht, void *k)

-{

-	ssize_t i;

-

-	i = htidx(ht, k);

-	if (i < 0)

-		return;

-	assert(!ht->dead[i]);

-	assert(ht->hashes[i]);

-	ht->dead[i] = 1;

-	ht->nelt--;

-	ht->ndead++;

-}

-

-/* Tests for 'k's presence in 'ht' */

-int hthas(Htab *ht, void *k) { return htidx(ht, k) >= 0; }

-

-/* Returns a list of all keys in the hash

- * table, storing the size of the returned

- * array in 'nkeys'. NB: the value returned

- * is allocated on the heap, and it is the

- * job of the caller to free it */

-void **htkeys(Htab *ht, size_t *nkeys)

-{

-	void **k;

-	size_t i, j;

-

-	j = 0;

-	k = xalloc(sizeof(void *) * ht->nelt);

-	for (i = 0; i < ht->sz; i++)

-		if (ht->hashes[i] && !ht->dead[i])

-			k[j++] = ht->keys[i];

-	*nkeys = ht->nelt;

-	return k;

-}

-

-ulong strhash(void *_s)

-{

-	char *s;

-	ulong h;

-	ulong g;

-

-	s = _s;

-	h = 0;

-	while (s && *s) {

-		h = ((h << 4) + *s++);

-

-		if ((g = (h & 0xF0000000)))

-			h ^= (g >> 24);

-

-		h &= ~g;

-	}

-	return h;

-}

-

-int streq(void *a, void *b)

-{

-	if (a == b)

-		return 1;

-	if (a == NULL || b == NULL)

-		return 0;

-	return !strcmp(a, b);

-}

-

-ulong strlithash(void *_s)

-{

-	Str *s;

-	ulong h, g, i;

-

-	s = _s;

-	h = 0;

-	for (i = 0; i < s->len; i++) {

-		h = ((h << 4) + s->buf[i]);

-

-		if ((g = (h & 0xF0000000)))

-			h ^= (g >> 24);

-

-		h &= ~g;

-	}

-	return h;

-}

-

-int strliteq(void *_a, void *_b)

-{

-	Str *a, *b;

-

-	a = _a;

-	b = _b;

-	if (a == b)

-		return 1;

-	if (a == NULL || b == NULL)

-		return 0;

-	if (a->len != b->len)

-		return 0;

-	return !memcmp(a, b, a->len);

-}

-

-ulong ptrhash(void *key) { return inthash((uintptr_t)key); }

-

-ulong inthash(uint64_t key)

-{

-	uintptr_t h;

-

-	h = (uintptr_t)key;

-	h *= 357913941;

-	h ^= h << 24;

-	h += ~357913941;

-	h ^= h >> 31;

-	h ^= h << 31;

-	return h;

-}

-

-int inteq(uint64_t a, uint64_t b) { return a == b; }

-

-int ptreq(void *a, void *b) { return a == b; }

--- a/parse/infer.c

+++ b/parse/infer.c

@@ -12,6 +12,7 @@

 #include <unistd.h>

 #include <assert.h>

+#include "util.h"

 #include "parse.h"

 typedef struct Inferstate Inferstate;

--- a/parse/names.c

+++ b/parse/names.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 char *opstr[] = {

--- a/parse/node.c

+++ b/parse/node.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 Node **nodes;

--- a/parse/parse.h

+++ b/parse/parse.h

@@ -1,23 +1,6 @@

-#ifdef __GNUC__

-#define FATAL __attribute__((noreturn))

-#else

-#define FATAL

-#endif

-

 #define Abiversion 10

-typedef uint8_t byte;

-typedef unsigned int uint;

-typedef unsigned long ulong;

-typedef long long vlong;

-typedef unsigned long long uvlong;

-

 typedef struct Srcloc Srcloc;

-typedef struct Bitset Bitset;

-typedef struct Optctx Optctx;

-typedef struct Strbuf Strbuf;

-typedef struct Htab Htab;

-typedef struct Str Str;

 typedef struct Tysubst Tysubst;

 typedef struct Tok Tok;

@@ -71,22 +54,11 @@

 #define Zloc ((Srcloc){-1, 0})

-struct Strbuf {

-	char *buf;

-	size_t sz;

-	size_t len;

-};

-

 struct Srcloc {

 	int line;

 	int file;

 };

-struct Str {

-	size_t len;

-	char *buf;

-};

-

 typedef enum {

 	Visintern,

 	Visexport,

@@ -99,23 +71,7 @@

 	Dclextern = 1 << 1,

 } Dclflags;

-struct Bitset {

-	size_t nchunks;

-	size_t *chunks;

-};

-struct Htab {

-	size_t nelt;

-	size_t ndead;

-	size_t sz;

-	ulong (*hash)(void *k);

-	int (*cmp)(void *a, void *b);

-	void **keys;

-	void **vals;

-	ulong *hashes;

-	char *dead;

-};

-

 struct Tok {

 	int type;

 	Srcloc loc;

@@ -381,22 +337,6 @@

 	};

 };

-struct Optctx {

-	/* public exports */

-	char *optarg;

-	char **args;

-	size_t nargs;

-

-	/* internal state */

-	char *optstr;

-	char **optargs;

-	size_t noptargs;

-	size_t argidx;

-	int optdone; /* seen -- */

-	int finished;

-	char *curarg;

-};

-

 /* globals */

 extern Srcloc curloc;

 extern char *filename;

@@ -451,24 +391,9 @@

 		   0;

 }

-Htab *mkht(ulong (*hash)(void *key), int (*cmp)(void *k1, void *k2));

-void htfree(Htab *ht);

-int htput(Htab *ht, void *k, void *v);

-void htdel(Htab *ht, void *k);

-void *htget(Htab *ht, void *k);

-int hthas(Htab *ht, void *k);

-void **htkeys(Htab *ht, size_t *nkeys);

 /* useful key types */

 int liteq(Node *a, Node *b);

 int litvaleq(Node *a, Node *b);

-ulong strhash(void *key);

-int streq(void *a, void *b);

-ulong strlithash(void *key);

-int strliteq(void *a, void *b);

-ulong ptrhash(void *key);

-int ptreq(void *a, void *b);

-ulong inthash(uint64_t key);

-int inteq(uint64_t a, uint64_t b);

 ulong tyhash(void *t);

 int tyeq(void *a, void *b);

 ulong namehash(void *t);

@@ -476,27 +401,18 @@

 ulong nsnamehash(void *t);

 int nsnameeq(void *a, void *b);

-/* util functions */

+/* parsing etc */

+void tokinit(char *file);

+int yylex(void);

+int yyparse(void);

+

+/* locations */

 char *fname(Srcloc l);

 int lnum(Srcloc l);

-void *zalloc(size_t size);

-void *xalloc(size_t size);

-void *zrealloc(void *p, size_t oldsz, size_t size);

-void *xrealloc(void *p, size_t size);

-void die(char *msg, ...) FATAL;

 void fatal(Node *n, char *fmt, ...) FATAL;

 void lfatal(Srcloc l, char *fmt, ...) FATAL;

 void lfatalv(Srcloc l, char *fmt, va_list ap) FATAL;

-char *strdupn(char *s, size_t len);

-char *strjoin(char *u, char *v);

-void *memdup(void *mem, size_t len);

-size_t bprintf(char *buf, size_t len, char *fmt, ...);

-/* parsing etc */

-void tokinit(char *file);

-int yylex(void);

-int yyparse(void);

-

 /* stab creation */

 Stab *mkstab(int isfunc);

@@ -665,47 +581,8 @@

 void ldel(void *l, size_t *len, size_t idx);

 void lfree(void *l, size_t *len);

-/* serializing/unserializing */

-void be64(vlong v, byte buf[8]);

-vlong host64(byte buf[8]);

-void be32(long v, byte buf[4]);

-long host32(byte buf[4]);

-static inline intptr_t ptoi(void *p) { return (intptr_t)p; }

-static inline void *itop(intptr_t i) { return (void *)i; }

-

-void wrbuf(FILE *fd, void *buf, size_t sz);

-void rdbuf(FILE *fd, void *buf, size_t sz);

-char rdbyte(FILE *fd);

-void wrbyte(FILE *fd, char val);

-char rdbyte(FILE *fd);

-void wrint(FILE *fd, long val);

-long rdint(FILE *fd);

-void wrstr(FILE *fd, char *val);

-char *rdstr(FILE *fd);

-void wrlenstr(FILE *fd, Str str);

-void rdlenstr(FILE *fd, Str *str);

-void wrflt(FILE *fd, double val);

-double rdflt(FILE *fd);

-void wrbool(FILE *fd, int val);

-int rdbool(FILE *fd);

-

-size_t max(size_t a, size_t b);

-size_t min(size_t a, size_t b);

-size_t align(size_t sz, size_t a);

-

-/* string buffer */

-Strbuf *mksb();

-char *sbfin(Strbuf *sb);

-void sbputs(Strbuf *sb, char *s);

-void sbputb(Strbuf *sb, char b);

-

 /* suffix replacement */

 char *swapsuffix(char *buf, size_t sz, char *s, char *suf, char *swap);

-

-/* indented printf */

-void indentf(int depth, char *fmt, ...);

-void findentf(FILE *fd, int depth, char *fmt, ...);

-void vfindentf(FILE *fd, int depth, char *fmt, va_list ap);

 /* Options to control the compilation */

 extern char debugopt[128];

--- a/parse/specialize.c

+++ b/parse/specialize.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 static Node *specializenode(Node *g, Tysubst *tsmap);

--- a/parse/stab.c

+++ b/parse/stab.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 /* Allows us to look up types/traits by name nodes */

--- a/parse/tok.c

+++ b/parse/tok.c

@@ -11,6 +11,7 @@

 #include <errno.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 #include "gram.h"

--- a/parse/type.c

+++ b/parse/type.c

@@ -11,6 +11,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 typedef struct Typename Typename;

--- a/parse/use.c

+++ b/parse/use.c

@@ -10,6 +10,7 @@

 #include <fcntl.h>

 #include <unistd.h>

+#include "util.h"

 #include "parse.h"

 static void wrtype(FILE *fd, Type *val);

--- a/parse/util.c

+++ /dev/null

@@ -1,553 +1,0 @@

-#include <stdlib.h>

-#include <stdio.h>

-#include <inttypes.h>

-#include <stdarg.h>

-#include <ctype.h>

-#include <string.h>

-#include <assert.h>

-

-#include <sys/types.h>

-#include <sys/stat.h>

-#include <fcntl.h>

-#include <unistd.h>

-

-#include "parse.h"

-

-/* malloc wrappers */

-void *zalloc(size_t sz)

-{

-	void *mem;

-

-	mem = calloc(1, sz);

-	if (!mem && sz)

-		die("Out of memory");

-	return mem;

-}

-

-void *xalloc(size_t sz)

-{

-	void *mem;

-

-	mem = malloc(sz);

-	if (!mem && sz)

-		die("Out of memory");

-	return mem;

-}

-

-void *zrealloc(void *mem, size_t oldsz, size_t sz)

-{

-	char *p;

-

-	p = xrealloc(mem, sz);

-	if (sz > oldsz)

-		memset(&p[oldsz], 0, sz - oldsz);

-	return p;

-}

-

-void *xrealloc(void *mem, size_t sz)

-{

-	mem = realloc(mem, sz);

-	if (!mem && sz)

-		die("Out of memory");

-	return mem;

-}

-

-/* errors */

-void die(char *msg, ...)

-{

-	va_list ap;

-

-	va_start(ap, msg);

-	vfprintf(stderr, msg, ap);

-	fprintf(stderr, "\n");

-	va_end(ap);

-	abort();

-}

-

-void fatal(Node *n, char *msg, ...)

-{

-	va_list ap;

-

-	va_start(ap, msg);

-	lfatalv(n->loc, msg, ap);

-	va_end(ap);

-}

-

-void lfatal(Srcloc l, char *msg, ...)

-{

-	va_list ap;

-

-	va_start(ap, msg);

-	lfatalv(l, msg, ap);

-	va_end(ap);

-}

-

-void lfatalv(Srcloc l, char *msg, va_list ap)

-{

-	fprintf(stdout, "%s:%d: ", fname(l), lnum(l));

-	vfprintf(stdout, msg, ap);

-	fprintf(stdout, "\n");

-	exit(1);

-}

-

-/* Some systems don't have strndup. */

-char *strdupn(char *s, size_t len)

-{

-	char *ret;

-

-	ret = xalloc(len + 1);

-	memcpy(ret, s, len);

-	ret[len] = '\0';

-	return ret;

-}

-

-char *strjoin(char *u, char *v)

-{

-	size_t n;

-	char *s;

-

-	n = strlen(u) + strlen(v) + 1;

-	s = xalloc(n);

-	bprintf(s, n + 1, "%s%s", u, v);

-	return s;

-}

-

-void *memdup(void *mem, size_t len)

-{

-	void *ret;

-

-        if (!mem)

-            return NULL;

-	ret = xalloc(len);

-	return memcpy(ret, mem, len);

-}

-

-/* lists */

-void lappend(void *l, size_t *len, void *n)

-{

-	void ***pl;

-

-	pl = l;

-	*pl = xrealloc(*pl, (*len + 1) * sizeof(void *));

-	(*pl)[*len] = n;

-	(*len)++;

-}

-

-void *lpop(void *l, size_t *len)

-{

-	void ***pl;

-	void *v;

-

-	pl = l;

-	(*len)--;

-	v = (*pl)[*len];

-	*pl = xrealloc(*pl, *len * sizeof(void *));

-	return v;

-}

-

-void linsert(void *p, size_t *len, size_t idx, void *v)

-{

-	void ***pl, **l;

-

-	pl = p;

-	*pl = xrealloc(*pl, (*len + 1) * sizeof(void *));

-	l = *pl;

-

-	memmove(&l[idx + 1], &l[idx], (*len - idx) * sizeof(void *));

-	l[idx] = v;

-	(*len)++;

-}

-

-void ldel(void *p, size_t *len, size_t idx)

-{

-	void ***pl, **l;

-

-	assert(p != NULL);

-	assert(idx < *len);

-	pl = p;

-	l = *pl;

-	memmove(&l[idx], &l[idx + 1], (*len - idx - 1) * sizeof(void *));

-	(*len)--;

-	*pl = xrealloc(l, *len * sizeof(void *));

-}

-

-void lcat(void *dst, size_t *ndst, void *src, size_t nsrc)

-{

-	size_t i;

-	void ***d, **s;

-

-	d = dst;

-	s = src;

-	for (i = 0; i < nsrc; i++)

-		lappend(d, ndst, s[i]);

-}

-

-void lfree(void *l, size_t *len)

-{

-	void ***pl;

-

-	assert(l != NULL);

-	pl = l;

-	free(*pl);

-	*pl = NULL;

-	*len = 0;

-}

-

-/* endian packing */

-void be64(vlong v, byte buf[8])

-{

-	buf[0] = (v >> 56) & 0xff;

-	buf[1] = (v >> 48) & 0xff;

-	buf[2] = (v >> 40) & 0xff;

-	buf[3] = (v >> 32) & 0xff;

-	buf[4] = (v >> 24) & 0xff;

-	buf[5] = (v >> 16) & 0xff;

-	buf[6] = (v >> 8) & 0xff;

-	buf[7] = (v >> 0) & 0xff;

-}

-

-vlong host64(byte buf[8])

-{

-	vlong v = 0;

-

-	v |= ((vlong)buf[0] << 56LL);

-	v |= ((vlong)buf[1] << 48LL);

-	v |= ((vlong)buf[2] << 40LL);

-	v |= ((vlong)buf[3] << 32LL);

-	v |= ((vlong)buf[4] << 24LL);

-	v |= ((vlong)buf[5] << 16LL);

-	v |= ((vlong)buf[6] << 8LL);

-	v |= ((vlong)buf[7] << 0LL);

-	return v;

-}

-

-void be32(long v, byte buf[4])

-{

-	buf[0] = (v >> 24) & 0xff;

-	buf[1] = (v >> 16) & 0xff;

-	buf[2] = (v >> 8) & 0xff;

-	buf[3] = (v >> 0) & 0xff;

-}

-

-long host32(byte buf[4])

-{

-	int32_t v = 0;

-	v |= ((long)buf[0] << 24);

-	v |= ((long)buf[1] << 16);

-	v |= ((long)buf[2] << 8);

-	v |= ((long)buf[3] << 0);

-	return v;

-}

-

-void wrbuf(FILE *fd, void *p, size_t sz)

-{

-	size_t n;

-	char *buf;

-

-	n = 0;

-	buf = p;

-	while (n < sz) {

-		n += fwrite(buf + n, 1, sz - n, fd);

-		if (feof(fd))

-			die("Unexpected EOF");

-		if (ferror(fd))

-			die("Error writing");

-	}

-}

-

-void rdbuf(FILE *fd, void *buf, size_t sz)

-{

-	size_t n;

-

-	n = sz;

-	while (n > 0) {

-		n -= fread(buf, 1, n, fd);

-		if (feof(fd))

-			die("Unexpected EOF");

-		if (ferror(fd))

-			die("Error writing");

-	}

-}

-

-void wrbyte(FILE *fd, char val)

-{

-	if (fputc(val, fd) == EOF)

-		die("Unexpected EOF");

-}

-

-char rdbyte(FILE *fd)

-{

-	int c;

-	c = fgetc(fd);

-	if (c == EOF)

-		die("Unexpected EOF");

-	return c;

-}

-

-void wrint(FILE *fd, long val)

-{

-	byte buf[4];

-	be32(val, buf);

-	wrbuf(fd, buf, 4);

-}

-

-long rdint(FILE *fd)

-{

-	byte buf[4];

-	rdbuf(fd, buf, 4);

-	return host32(buf);

-}

-

-void wrstr(FILE *fd, char *val)

-{

-	size_t len;

-

-	if (!val) {

-		wrint(fd, -1);

-	} else {

-		wrint(fd, strlen(val));

-		len = strlen(val);

-		wrbuf(fd, val, len);

-	}

-}

-

-char *rdstr(FILE *fd)

-{

-	ssize_t len;

-	char *s;

-

-	len = rdint(fd);

-	if (len == -1) {

-		return NULL;

-	} else {

-		s = xalloc(len + 1);

-		rdbuf(fd, s, len);

-		s[len] = '\0';

-		return s;

-	}

-}

-

-void wrlenstr(FILE *fd, Str str)

-{

-	wrint(fd, str.len);

-	wrbuf(fd, str.buf, str.len);

-}

-

-void rdlenstr(FILE *fd, Str *str)

-{

-	str->len = rdint(fd);

-	str->buf = xalloc(str->len + 1);

-	rdbuf(fd, str->buf, str->len);

-	str->buf[str->len] = '\0';

-}

-

-void wrflt(FILE *fd, double val)

-{

-	byte buf[8];

-	/* Assumption: We have 'val' in 64 bit IEEE format */

-	union {

-		uvlong ival;

-		double fval;

-	} u;

-

-	u.fval = val;

-	be64(u.ival, buf);

-	wrbuf(fd, buf, 8);

-}

-

-double rdflt(FILE *fd)

-{

-	byte buf[8];

-	union {

-		uvlong ival;

-		double fval;

-	} u;

-

-	if (fread(buf, 8, 1, fd) < 8)

-		die("Unexpected EOF");

-	u.ival = host64(buf);

-	return u.fval;

-}

-

-size_t bprintf(char *buf, size_t sz, char *fmt, ...)

-{

-	va_list ap;

-	size_t n;

-

-	va_start(ap, fmt);

-	n = vsnprintf(buf, sz, fmt, ap);

-	if (n >= sz)

-		n = sz;

-	va_end(ap);

-

-	return n;

-}

-

-void wrbool(FILE *fd, int val) { wrbyte(fd, val); }

-

-int rdbool(FILE *fd) { return rdbyte(fd); }

-

-char *swapsuffix(char *buf, size_t sz, char *s, char *suf, char *swap)

-{

-	size_t slen, suflen, swaplen;

-

-	slen = strlen(s);

-	suflen = strlen(suf);

-	swaplen = strlen(swap);

-

-	if (slen < suflen)

-		return NULL;

-	if (slen + swaplen >= sz)

-		die("swapsuffix: buf too small");

-

-	buf[0] = '\0';

-	/* if we have matching suffixes */

-	if (suflen < slen && !strcmp(suf, &s[slen - suflen])) {

-		strncat(buf, s, slen - suflen);

-		strncat(buf, swap, swaplen);

-	} else {

-		bprintf(buf, sz, "%s%s", s, swap);

-	}

-

-	return buf;

-}

-

-size_t max(size_t a, size_t b)

-{

-	if (a > b)

-		return a;

-	else

-		return b;

-}

-

-size_t min(size_t a, size_t b)

-{

-	if (a < b)

-		return a;

-	else

-		return b;

-}

-

-size_t align(size_t sz, size_t a)

-{

-	/* align to 0 just returns sz */

-	if (a == 0)

-		return sz;

-	return (sz + a - 1) & ~(a - 1);

-}

-

-void indentf(int depth, char *fmt, ...)

-{

-	va_list ap;

-	va_start(ap, fmt);

-	vfindentf(stdout, depth, fmt, ap);

-	va_end(ap);

-}

-

-void findentf(FILE *fd, int depth, char *fmt, ...)

-{

-	va_list ap;

-	va_start(ap, fmt);

-	vfindentf(fd, depth, fmt, ap);

-	va_end(ap);

-}

-

-void vfindentf(FILE *fd, int depth, char *fmt, va_list ap)

-{

-	ssize_t i;

-

-	for (i = 0; i < depth; i++)

-		fprintf(fd, "\t");

-	vfprintf(fd, fmt, ap);

-}

-

-static int optinfo(Optctx *ctx, char arg, int *take, int *mand)

-{

-	char *s;

-

-	for (s = ctx->optstr; *s != '\0'; s++) {

-		if (*s == arg) {

-			s++;

-			if (*s == ':') {

-				*take = 1;

-				*mand = 1;

-				return 1;

-			} else if (*s == '?') {

-				*take = 1;

-				*mand = 0;

-				return 1;

-			} else {

-				*take = 0;

-				*mand = 0;

-				return 1;

-			}

-		}

-	}

-	return 0;

-}

-

-static int findnextopt(Optctx *ctx)

-{

-	size_t i;

-

-	for (i = ctx->argidx + 1; i < ctx->noptargs; i++) {

-		if (ctx->optargs[i][0] == '-')

-			goto foundopt;

-		else

-			lappend(&ctx->args, &ctx->nargs, ctx->optargs[i]);

-	}

-	ctx->finished = 1;

-	return 0;

-foundopt:

-	ctx->argidx = i;

-	ctx->curarg = ctx->optargs[i] + 1; /* skip initial '-' */

-	return 1;

-}

-

-void optinit(Optctx *ctx, char *optstr, char **optargs, size_t noptargs)

-{

-	ctx->args = NULL;

-	ctx->nargs = 0;

-

-	ctx->optstr = optstr;

-	ctx->optargs = optargs;

-	ctx->noptargs = noptargs;

-	ctx->optdone = 0;

-	ctx->finished = 0;

-	ctx->argidx = 0;

-	ctx->curarg = "";

-	findnextopt(ctx);

-}

-

-int optnext(Optctx *ctx)

-{

-	int take, mand;

-	int c;

-

-	c = *ctx->curarg;

-	ctx->curarg++;

-	if (!optinfo(ctx, c, &take, &mand)) {

-		printf("Unexpected argument %c\n", *ctx->curarg);

-		exit(1);

-	}

-

-	ctx->optarg = NULL;

-	if (take) {

-		if (*ctx->curarg) {

-			ctx->optarg = ctx->curarg;

-			ctx->curarg += strlen(ctx->optarg);

-		} else if (ctx->argidx < ctx->noptargs - 1) {

-			ctx->optarg = ctx->optargs[ctx->argidx + 1];

-			ctx->argidx++;

-		} else if (mand) {

-			fprintf(stderr, "expected argument for %c\n", *ctx->curarg);

-		}

-		findnextopt(ctx);

-	} else {

-		if (*ctx->curarg == '\0')

-			findnextopt(ctx);

-	}

-	return c;

-}

-

-int optdone(Optctx *ctx) { return *ctx->curarg == '\0' && ctx->finished; }

--- /dev/null

+++ b/util/htab.c

@@ -1,0 +1,288 @@

+#include <stdlib.h>

+#include <stdio.h>

+#include <stdarg.h>

+#include <inttypes.h>

+#include <assert.h>

+#include <limits.h>

+#include <string.h>

+

+#include "util.h"

+

+#define Initsz 16

+

+/* Creates a new empty hash table, using 'hash' as the

+ * hash funciton, and 'cmp' to verify that there are no

+ * hash collisions. */

+Htab *mkht(ulong (*hash)(void *key), int (*cmp)(void *k1, void *k2))

+{

+	Htab *ht;

+

+	ht = xalloc(sizeof(Htab));

+	ht->nelt = 0;

+	ht->ndead = 0;

+	ht->sz = Initsz;

+	ht->hash = hash;

+	ht->cmp = cmp;

+	ht->keys = zalloc(Initsz * sizeof(void *));

+	ht->vals = zalloc(Initsz * sizeof(void *));

+	ht->hashes = zalloc(Initsz * sizeof(void *));

+	ht->dead = zalloc(Initsz * sizeof(char));

+

+	return ht;

+}

+

+/* Frees a hash table. Passing this function

+ * NULL is a no-op. */

+void htfree(Htab *ht)

+{

+	if (!ht)

+		return;

+	free(ht->keys);

+	free(ht->vals);

+	free(ht->hashes);

+	free(ht->dead);

+	free(ht);

+}

+

+/* Offsets the hash so that '0' can be

+ * used as a 'no valid value */

+static ulong hash(Htab *ht, void *k)

+{

+	ulong h;

+	h = ht->hash(k);

+	if (h == 0)

+		return 1;

+	else

+		return h;

+}

+

+/* Resizes the hash table by copying all

+ * the old keys into the right slots in a

+ * new table. */

+static void grow(Htab *ht, int sz)

+{

+	void **oldk;

+	void **oldv;

+	ulong *oldh;

+	char *oldd;

+	int oldsz;

+	int i;

+

+	oldk = ht->keys;

+	oldv = ht->vals;

+	oldh = ht->hashes;

+	oldd = ht->dead;

+	oldsz = ht->sz;

+

+	ht->nelt = 0;

+	ht->ndead = 0;

+	ht->sz = sz;

+	ht->keys = zalloc(sz * sizeof(void *));

+	ht->vals = zalloc(sz * sizeof(void *));

+	ht->hashes = zalloc(sz * sizeof(void *));

+	ht->dead = zalloc(sz * sizeof(void *));

+

+	for (i = 0; i < oldsz; i++)

+		if (oldh[i] && !oldd[i])

+			htput(ht, oldk[i], oldv[i]);

+

+	free(oldh);

+	free(oldk);

+	free(oldv);

+	free(oldd);

+}

+

+/* Inserts 'k' into the hash table, possibly

+ * killing any previous key that compares

+ * as equal. */

+int htput(Htab *ht, void *k, void *v)

+{

+	int i;

+	ulong h;

+	int di;

+

+	di = 0;

+	h = hash(ht, k);

+	i = h & (ht->sz - 1);

+	while (ht->hashes[i] && !ht->dead[i]) {

+		/* second insertion overwrites first. nb, we shouldn't touch the

+		 * keys for dead values */

+		if (ht->hashes[i] == h) {

+			if (ht->dead[i])

+				break;

+			else if (ht->cmp(ht->keys[i], k))

+				goto conflicted;

+		}

+		di++;

+		i = (h + di) & (ht->sz - 1);

+	}

+	ht->nelt++;

+conflicted:

+	if (ht->dead[i])

+		ht->ndead--;

+	ht->hashes[i] = h;

+	ht->keys[i] = k;

+	ht->vals[i] = v;

+	ht->dead[i] = 0;

+

+	if (ht->sz < ht->nelt * 2)

+		grow(ht, ht->sz * 2);

+	if (ht->sz < ht->ndead * 4)

+		grow(ht, ht->sz);

+	return 1;

+}

+

+/* Finds the index that we would insert

+ * the key into */

+static ssize_t htidx(Htab *ht, void *k)

+{

+	ssize_t i;

+	ulong h;

+	int di;

+

+	di = 0;

+	h = hash(ht, k);

+	i = h & (ht->sz - 1);

+	while (ht->hashes[i] && !ht->dead[i] && ht->hashes[i] != h) {

+searchmore:

+		di++;

+		i = (h + di) & (ht->sz - 1);

+	}

+	if (!ht->hashes[i])

+		return -1;

+	if ((ht->hashes[i] == h && ht->dead[i]) || !ht->cmp(ht->keys[i], k))

+		goto searchmore; /* collision */

+	return i;

+}

+

+/* Looks up a key, returning NULL if

+ * the value is not present. Note,

+ * if NULL is a valid value, you need

+ * to check with hthas() to see if it's

+ * not there */

+void *htget(Htab *ht, void *k)

+{

+	ssize_t i;

+

+	i = htidx(ht, k);

+	if (i < 0)

+		return NULL;

+	else

+		return ht->vals[i];

+}

+

+void htdel(Htab *ht, void *k)

+{

+	ssize_t i;

+

+	i = htidx(ht, k);

+	if (i < 0)

+		return;

+	assert(!ht->dead[i]);

+	assert(ht->hashes[i]);

+	ht->dead[i] = 1;

+	ht->nelt--;

+	ht->ndead++;

+}

+

+/* Tests for 'k's presence in 'ht' */

+int hthas(Htab *ht, void *k) { return htidx(ht, k) >= 0; }

+

+/* Returns a list of all keys in the hash

+ * table, storing the size of the returned

+ * array in 'nkeys'. NB: the value returned

+ * is allocated on the heap, and it is the

+ * job of the caller to free it */

+void **htkeys(Htab *ht, size_t *nkeys)

+{

+	void **k;

+	size_t i, j;

+

+	j = 0;

+	k = xalloc(sizeof(void *) * ht->nelt);

+	for (i = 0; i < ht->sz; i++)

+		if (ht->hashes[i] && !ht->dead[i])

+			k[j++] = ht->keys[i];

+	*nkeys = ht->nelt;

+	return k;

+}

+

+ulong strhash(void *_s)

+{

+	char *s;

+	ulong h;

+	ulong g;

+

+	s = _s;

+	h = 0;

+	while (s && *s) {

+		h = ((h << 4) + *s++);

+

+		if ((g = (h & 0xF0000000)))

+			h ^= (g >> 24);

+

+		h &= ~g;

+	}

+	return h;

+}

+

+int streq(void *a, void *b)

+{

+	if (a == b)

+		return 1;

+	if (a == NULL || b == NULL)

+		return 0;

+	return !strcmp(a, b);

+}

+

+ulong strlithash(void *_s)

+{

+	Str *s;

+	ulong h, g, i;

+

+	s = _s;

+	h = 0;

+	for (i = 0; i < s->len; i++) {

+		h = ((h << 4) + s->buf[i]);

+

+		if ((g = (h & 0xF0000000)))

+			h ^= (g >> 24);

+

+		h &= ~g;

+	}

+	return h;

+}

+

+int strliteq(void *_a, void *_b)

+{

+	Str *a, *b;

+

+	a = _a;

+	b = _b;

+	if (a == b)

+		return 1;

+	if (a == NULL || b == NULL)

+		return 0;

+	if (a->len != b->len)

+		return 0;

+	return !memcmp(a, b, a->len);

+}

+

+ulong ptrhash(void *key) { return inthash((uintptr_t)key); }

+

+ulong inthash(uint64_t key)

+{

+	uintptr_t h;

+

+	h = (uintptr_t)key;

+	h *= 357913941;

+	h ^= h << 24;

+	h += ~357913941;

+	h ^= h >> 31;

+	h ^= h << 31;

+	return h;

+}

+

+int inteq(uint64_t a, uint64_t b) { return a == b; }

+

+int ptreq(void *a, void *b) { return a == b; }

--- /dev/null

+++ b/util/util.c

@@ -1,0 +1,516 @@

+#include <stdlib.h>

+#include <stdio.h>

+#include <inttypes.h>

+#include <stdarg.h>

+#include <ctype.h>

+#include <string.h>

+#include <assert.h>

+

+#include <sys/types.h>

+#include <sys/stat.h>

+#include <fcntl.h>

+#include <unistd.h>

+

+#include "util.h"

+

+/* malloc wrappers */

+void *zalloc(size_t sz)

+{

+	void *mem;

+

+	mem = calloc(1, sz);

+	if (!mem && sz)

+		die("Out of memory");

+	return mem;

+}

+

+void *xalloc(size_t sz)

+{

+	void *mem;

+

+	mem = malloc(sz);

+	if (!mem && sz)

+		die("Out of memory");

+	return mem;

+}

+

+void *zrealloc(void *mem, size_t oldsz, size_t sz)

+{

+	char *p;

+

+	p = xrealloc(mem, sz);

+	if (sz > oldsz)

+		memset(&p[oldsz], 0, sz - oldsz);

+	return p;

+}

+

+void *xrealloc(void *mem, size_t sz)

+{

+	mem = realloc(mem, sz);

+	if (!mem && sz)

+		die("Out of memory");

+	return mem;

+}

+

+

+/* Some systems don't have strndup. */

+char *strdupn(char *s, size_t len)

+{

+	char *ret;

+

+	ret = xalloc(len + 1);

+	memcpy(ret, s, len);

+	ret[len] = '\0';

+	return ret;

+}

+

+char *strjoin(char *u, char *v)

+{

+	size_t n;

+	char *s;

+

+	n = strlen(u) + strlen(v) + 1;

+	s = xalloc(n);

+	bprintf(s, n + 1, "%s%s", u, v);

+	return s;

+}

+

+void *memdup(void *mem, size_t len)

+{

+	void *ret;

+

+        if (!mem)

+            return NULL;

+	ret = xalloc(len);

+	return memcpy(ret, mem, len);

+}

+

+/* lists */

+void lappend(void *l, size_t *len, void *n)

+{

+	void ***pl;

+

+	pl = l;

+	*pl = xrealloc(*pl, (*len + 1) * sizeof(void *));

+	(*pl)[*len] = n;

+	(*len)++;

+}

+

+void *lpop(void *l, size_t *len)

+{

+	void ***pl;

+	void *v;

+

+	pl = l;

+	(*len)--;

+	v = (*pl)[*len];

+	*pl = xrealloc(*pl, *len * sizeof(void *));

+	return v;

+}

+

+void linsert(void *p, size_t *len, size_t idx, void *v)

+{

+	void ***pl, **l;

+

+	pl = p;

+	*pl = xrealloc(*pl, (*len + 1) * sizeof(void *));

+	l = *pl;

+

+	memmove(&l[idx + 1], &l[idx], (*len - idx) * sizeof(void *));

+	l[idx] = v;

+	(*len)++;

+}

+

+void ldel(void *p, size_t *len, size_t idx)

+{

+	void ***pl, **l;

+

+	assert(p != NULL);

+	assert(idx < *len);

+	pl = p;

+	l = *pl;

+	memmove(&l[idx], &l[idx + 1], (*len - idx - 1) * sizeof(void *));

+	(*len)--;

+	*pl = xrealloc(l, *len * sizeof(void *));

+}

+

+void lcat(void *dst, size_t *ndst, void *src, size_t nsrc)

+{

+	size_t i;

+	void ***d, **s;

+

+	d = dst;

+	s = src;

+	for (i = 0; i < nsrc; i++)

+		lappend(d, ndst, s[i]);

+}

+

+void lfree(void *l, size_t *len)

+{

+	void ***pl;

+

+	assert(l != NULL);

+	pl = l;

+	free(*pl);

+	*pl = NULL;

+	*len = 0;

+}

+

+/* endian packing */

+void be64(vlong v, byte buf[8])

+{

+	buf[0] = (v >> 56) & 0xff;

+	buf[1] = (v >> 48) & 0xff;

+	buf[2] = (v >> 40) & 0xff;

+	buf[3] = (v >> 32) & 0xff;

+	buf[4] = (v >> 24) & 0xff;

+	buf[5] = (v >> 16) & 0xff;

+	buf[6] = (v >> 8) & 0xff;

+	buf[7] = (v >> 0) & 0xff;

+}

+

+vlong host64(byte buf[8])

+{

+	vlong v = 0;

+

+	v |= ((vlong)buf[0] << 56LL);

+	v |= ((vlong)buf[1] << 48LL);

+	v |= ((vlong)buf[2] << 40LL);

+	v |= ((vlong)buf[3] << 32LL);

+	v |= ((vlong)buf[4] << 24LL);

+	v |= ((vlong)buf[5] << 16LL);

+	v |= ((vlong)buf[6] << 8LL);

+	v |= ((vlong)buf[7] << 0LL);

+	return v;

+}

+

+void be32(long v, byte buf[4])

+{

+	buf[0] = (v >> 24) & 0xff;

+	buf[1] = (v >> 16) & 0xff;

+	buf[2] = (v >> 8) & 0xff;

+	buf[3] = (v >> 0) & 0xff;

+}

+

+long host32(byte buf[4])

+{

+	int32_t v = 0;

+	v |= ((long)buf[0] << 24);

+	v |= ((long)buf[1] << 16);

+	v |= ((long)buf[2] << 8);

+	v |= ((long)buf[3] << 0);

+	return v;

+}

+

+void wrbuf(FILE *fd, void *p, size_t sz)

+{

+	size_t n;

+	char *buf;

+

+	n = 0;

+	buf = p;

+	while (n < sz) {

+		n += fwrite(buf + n, 1, sz - n, fd);

+		if (feof(fd))

+			die("Unexpected EOF");

+		if (ferror(fd))

+			die("Error writing");

+	}

+}

+

+void rdbuf(FILE *fd, void *buf, size_t sz)

+{

+	size_t n;

+

+	n = sz;

+	while (n > 0) {

+		n -= fread(buf, 1, n, fd);

+		if (feof(fd))

+			die("Unexpected EOF");

+		if (ferror(fd))

+			die("Error writing");

+	}

+}

+

+void wrbyte(FILE *fd, char val)

+{

+	if (fputc(val, fd) == EOF)

+		die("Unexpected EOF");

+}

+

+char rdbyte(FILE *fd)

+{

+	int c;

+	c = fgetc(fd);

+	if (c == EOF)

+		die("Unexpected EOF");

+	return c;

+}

+

+void wrint(FILE *fd, long val)

+{

+	byte buf[4];

+	be32(val, buf);

+	wrbuf(fd, buf, 4);

+}

+

+long rdint(FILE *fd)

+{

+	byte buf[4];

+	rdbuf(fd, buf, 4);

+	return host32(buf);

+}

+

+void wrstr(FILE *fd, char *val)

+{

+	size_t len;

+

+	if (!val) {

+		wrint(fd, -1);

+	} else {

+		wrint(fd, strlen(val));

+		len = strlen(val);

+		wrbuf(fd, val, len);

+	}

+}

+

+char *rdstr(FILE *fd)

+{

+	ssize_t len;

+	char *s;

+

+	len = rdint(fd);

+	if (len == -1) {

+		return NULL;

+	} else {

+		s = xalloc(len + 1);

+		rdbuf(fd, s, len);

+		s[len] = '\0';

+		return s;

+	}

+}

+

+void wrlenstr(FILE *fd, Str str)

+{

+	wrint(fd, str.len);

+	wrbuf(fd, str.buf, str.len);

+}

+

+void rdlenstr(FILE *fd, Str *str)

+{

+	str->len = rdint(fd);

+	str->buf = xalloc(str->len + 1);

+	rdbuf(fd, str->buf, str->len);

+	str->buf[str->len] = '\0';

+}

+

+void wrflt(FILE *fd, double val)

+{

+	byte buf[8];

+	/* Assumption: We have 'val' in 64 bit IEEE format */

+	union {

+		uvlong ival;

+		double fval;

+	} u;

+

+	u.fval = val;

+	be64(u.ival, buf);

+	wrbuf(fd, buf, 8);

+}

+

+double rdflt(FILE *fd)

+{

+	byte buf[8];

+	union {

+		uvlong ival;

+		double fval;

+	} u;

+

+	if (fread(buf, 8, 1, fd) < 8)

+		die("Unexpected EOF");

+	u.ival = host64(buf);

+	return u.fval;

+}

+

+size_t bprintf(char *buf, size_t sz, char *fmt, ...)

+{

+	va_list ap;

+	size_t n;

+

+	va_start(ap, fmt);

+	n = vsnprintf(buf, sz, fmt, ap);

+	if (n >= sz)

+		n = sz;

+	va_end(ap);

+

+	return n;

+}

+

+void wrbool(FILE *fd, int val) { wrbyte(fd, val); }

+

+int rdbool(FILE *fd) { return rdbyte(fd); }

+

+char *swapsuffix(char *buf, size_t sz, char *s, char *suf, char *swap)

+{

+	size_t slen, suflen, swaplen;

+

+	slen = strlen(s);

+	suflen = strlen(suf);

+	swaplen = strlen(swap);

+

+	if (slen < suflen)

+		return NULL;

+	if (slen + swaplen >= sz)

+		die("swapsuffix: buf too small");

+

+	buf[0] = '\0';

+	/* if we have matching suffixes */

+	if (suflen < slen && !strcmp(suf, &s[slen - suflen])) {

+		strncat(buf, s, slen - suflen);

+		strncat(buf, swap, swaplen);

+	} else {

+		bprintf(buf, sz, "%s%s", s, swap);

+	}

+

+	return buf;

+}

+

+size_t max(size_t a, size_t b)

+{

+	if (a > b)

+		return a;

+	else

+		return b;

+}

+

+size_t min(size_t a, size_t b)

+{

+	if (a < b)

+		return a;

+	else

+		return b;

+}

+

+size_t align(size_t sz, size_t a)

+{

+	/* align to 0 just returns sz */

+	if (a == 0)

+		return sz;

+	return (sz + a - 1) & ~(a - 1);

+}

+

+void indentf(int depth, char *fmt, ...)

+{

+	va_list ap;

+	va_start(ap, fmt);

+	vfindentf(stdout, depth, fmt, ap);

+	va_end(ap);

+}

+

+void findentf(FILE *fd, int depth, char *fmt, ...)

+{

+	va_list ap;

+	va_start(ap, fmt);

+	vfindentf(fd, depth, fmt, ap);

+	va_end(ap);

+}

+

+void vfindentf(FILE *fd, int depth, char *fmt, va_list ap)

+{

+	ssize_t i;

+

+	for (i = 0; i < depth; i++)

+		fprintf(fd, "\t");

+	vfprintf(fd, fmt, ap);

+}

+

+static int optinfo(Optctx *ctx, char arg, int *take, int *mand)

+{

+	char *s;

+

+	for (s = ctx->optstr; *s != '\0'; s++) {

+		if (*s == arg) {

+			s++;

+			if (*s == ':') {

+				*take = 1;

+				*mand = 1;

+				return 1;

+			} else if (*s == '?') {

+				*take = 1;

+				*mand = 0;

+				return 1;

+			} else {

+				*take = 0;

+				*mand = 0;

+				return 1;

+			}

+		}

+	}

+	return 0;

+}

+

+static int findnextopt(Optctx *ctx)

+{

+	size_t i;

+

+	for (i = ctx->argidx + 1; i < ctx->noptargs; i++) {

+		if (ctx->optargs[i][0] == '-')

+			goto foundopt;

+		else

+			lappend(&ctx->args, &ctx->nargs, ctx->optargs[i]);

+	}

+	ctx->finished = 1;

+	return 0;

+foundopt:

+	ctx->argidx = i;

+	ctx->curarg = ctx->optargs[i] + 1; /* skip initial '-' */

+	return 1;

+}

+

+void optinit(Optctx *ctx, char *optstr, char **optargs, size_t noptargs)

+{

+	ctx->args = NULL;

+	ctx->nargs = 0;

+

+	ctx->optstr = optstr;

+	ctx->optargs = optargs;

+	ctx->noptargs = noptargs;

+	ctx->optdone = 0;

+	ctx->finished = 0;

+	ctx->argidx = 0;

+	ctx->curarg = "";

+	findnextopt(ctx);

+}

+

+int optnext(Optctx *ctx)

+{

+	int take, mand;

+	int c;

+

+	c = *ctx->curarg;

+	ctx->curarg++;

+	if (!optinfo(ctx, c, &take, &mand)) {

+		printf("Unexpected argument %c\n", *ctx->curarg);

+		exit(1);

+	}

+

+	ctx->optarg = NULL;

+	if (take) {

+		if (*ctx->curarg) {

+			ctx->optarg = ctx->curarg;

+			ctx->curarg += strlen(ctx->optarg);

+		} else if (ctx->argidx < ctx->noptargs - 1) {

+			ctx->optarg = ctx->optargs[ctx->argidx + 1];

+			ctx->argidx++;

+		} else if (mand) {

+			fprintf(stderr, "expected argument for %c\n", *ctx->curarg);

+		}

+		findnextopt(ctx);

+	} else {

+		if (*ctx->curarg == '\0')

+			findnextopt(ctx);

+	}

+	return c;

+}

+

+int optdone(Optctx *ctx) { return *ctx->curarg == '\0' && ctx->finished; }

--- /dev/null

+++ b/util/util.h

@@ -1,0 +1,129 @@

+#ifdef __GNUC__

+#define FATAL __attribute__((noreturn))

+#else

+#define FATAL

+#endif

+

+typedef uint8_t byte;

+typedef unsigned int uint;

+typedef unsigned long ulong;

+typedef long long vlong;

+typedef unsigned long long uvlong;

+

+typedef struct Htab Htab;

+typedef struct Bitset Bitset;

+typedef struct Optctx Optctx;

+typedef struct Str Str;

+typedef struct Strbuf Strbuf;

+

+struct Htab {

+	size_t nelt;

+	size_t ndead;

+	size_t sz;

+	ulong (*hash)(void *k);

+	int (*cmp)(void *a, void *b);

+	void **keys;

+	void **vals;

+	ulong *hashes;

+	char *dead;

+};

+

+struct Bitset {

+	size_t nchunks;

+	size_t *chunks;

+};

+

+struct Optctx {

+	/* public exports */

+	char *optarg;

+	char **args;

+	size_t nargs;

+

+	/* internal state */

+	char *optstr;

+	char **optargs;

+	size_t noptargs;

+	size_t argidx;

+	int optdone; /* seen -- */

+	int finished;

+	char *curarg;

+};

+

+struct Str {

+	size_t len;

+	char *buf;

+};

+

+struct Strbuf {

+	char *buf;

+	size_t sz;

+	size_t len;

+};

+

+/* string buffer */

+Strbuf *mksb();

+char *sbfin(Strbuf *sb);

+void sbputs(Strbuf *sb, char *s);

+void sbputb(Strbuf *sb, char b);

+

+/* hash tables */

+Htab *mkht(ulong (*hash)(void *key), int (*cmp)(void *k1, void *k2));

+void htfree(Htab *ht);

+int htput(Htab *ht, void *k, void *v);

+void htdel(Htab *ht, void *k);

+void *htget(Htab *ht, void *k);

+int hthas(Htab *ht, void *k);

+void **htkeys(Htab *ht, size_t *nkeys);

+ulong strhash(void *key);

+int streq(void *a, void *b);

+ulong strlithash(void *key);

+int strliteq(void *a, void *b);

+ulong ptrhash(void *key);

+int ptreq(void *a, void *b);

+ulong inthash(uint64_t key);

+int inteq(uint64_t a, uint64_t b);

+

+/* util functions */

+void *zalloc(size_t size);

+void *xalloc(size_t size);

+void *zrealloc(void *p, size_t oldsz, size_t size);

+void *xrealloc(void *p, size_t size);

+void die(char *msg, ...) FATAL;

+char *strdupn(char *s, size_t len);

+char *strjoin(char *u, char *v);

+void *memdup(void *mem, size_t len);

+size_t bprintf(char *buf, size_t len, char *fmt, ...);

+

+/* indented printf */

+void indentf(int depth, char *fmt, ...);

+void findentf(FILE *fd, int depth, char *fmt, ...);

+void vfindentf(FILE *fd, int depth, char *fmt, va_list ap);

+

+/* serializing/unserializing */

+void be64(vlong v, byte buf[8]);

+vlong host64(byte buf[8]);

+void be32(long v, byte buf[4]);

+long host32(byte buf[4]);

+static inline intptr_t ptoi(void *p) { return (intptr_t)p; }

+static inline void *itop(intptr_t i) { return (void *)i; }

+

+void wrbuf(FILE *fd, void *buf, size_t sz);

+void rdbuf(FILE *fd, void *buf, size_t sz);

+char rdbyte(FILE *fd);

+void wrbyte(FILE *fd, char val);

+char rdbyte(FILE *fd);

+void wrint(FILE *fd, long val);

+long rdint(FILE *fd);

+void wrstr(FILE *fd, char *val);

+char *rdstr(FILE *fd);

+void wrlenstr(FILE *fd, Str str);

+void rdlenstr(FILE *fd, Str *str);

+void wrflt(FILE *fd, double val);

+double rdflt(FILE *fd);

+void wrbool(FILE *fd, int val);

+int rdbool(FILE *fd);

+

+size_t max(size_t a, size_t b);

+size_t min(size_t a, size_t b);

+size_t align(size_t sz, size_t a);

+