new

21 files changed, 1782 insertions, 0 deletions

diff --git a/src/libndb/csgetval.c b/src/libndb/csgetval.c
new file mode 100644
index 00000000..22705ade
--- /dev/null
+++ b/src/libndb/csgetval.c
@@ -0,0 +1,107 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ndb.h>
+#include <ndbhf.h>
+
+/*
+ *  search for a tuple that has the given 'attr=val' and also 'rattr=x'.
+ *  copy 'x' into 'buf' and return the whole tuple.
+ *
+ *  return 0 if not found.
+ */
+char*
+csgetvalue(char *netroot, char *attr, char *val, char *rattr, Ndbtuple **pp)
+{
+	Ndbtuple *t, *first, *last;
+	int n, linefound;
+	char line[1024];
+	int fd;
+	int oops = 0;
+	char *rv;
+
+	if(pp)
+		*pp = nil;
+	rv = nil;
+
+	if(netroot)
+		snprint(line, sizeof(line), "%s/cs", netroot);
+	else
+		strcpy(line, "/net/cs");
+	fd = open(line, ORDWR);
+	if(fd < 0)
+		return 0;
+	seek(fd, 0, 0);
+	snprint(line, sizeof(line), "!%s=%s %s=*", attr, val, rattr);
+	if(write(fd, line, strlen(line)) < 0){
+		close(fd);
+		return 0;
+	}
+	seek(fd, 0, 0);
+
+	first = last = 0;
+	linefound = 0;
+	for(;;){
+		n = read(fd, line, sizeof(line)-2);
+		if(n <= 0)
+			break;
+		line[n] = '\n';
+		line[n+1] = 0;
+
+		t = _ndbparseline(line);
+		if(t == 0)
+			continue;
+		if(first)
+			last->entry = t;
+		else
+			first = t;
+		last = t;
+
+		while(last->entry)
+			last = last->entry;
+
+		for(; t; t = t->entry){
+			if(linefound == 0){
+				if(strcmp(rattr, t->attr) == 0){
+					linefound = 1;
+					rv = strdup(t->val);
+				}
+			}
+		}
+	}
+	close(fd);
+
+	if(oops){
+		werrstr("buffer too short");
+		ndbfree(first);
+		return nil;
+	}
+
+	if(pp){
+		setmalloctag(first, getcallerpc(&netroot));
+		*pp = first;
+	} else
+		ndbfree(first);
+
+	return rv;
+}
+
+Ndbtuple*
+csgetval(char *netroot, char *attr, char *val, char *rattr, char *buf)
+{
+	Ndbtuple *t;
+	char *p;
+
+	p = csgetvalue(netroot, attr, val, rattr, &t);
+	if(p == nil){
+		if(buf != nil)
+			*buf = 0;
+	} else {
+		if(buf != nil){
+			strncpy(buf, p, Ndbvlen-1);
+			buf[Ndbvlen-1] = 0;
+		}
+		free(p);
+	}
+	return t;
+}
diff --git a/src/libndb/csipinfo.c b/src/libndb/csipinfo.c
new file mode 100644
index 00000000..76f3d8e0
--- /dev/null
+++ b/src/libndb/csipinfo.c
@@ -0,0 +1,68 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ndb.h>
+#include <ndbhf.h>
+
+/*
+ *  look up the ip attributes 'list' for an entry that has the
+ *  given 'attr=val' and a 'ip=' tuples.
+ *
+ *  return nil if not found.
+ */
+Ndbtuple*
+csipinfo(char *netroot, char *attr, char *val, char **list, int n)
+{
+	Ndbtuple *t, *first, *last;
+	int i;
+	char line[1024];
+	int fd;
+	char *p, *e;
+
+	if(netroot)
+		snprint(line, sizeof(line), "%s/cs", netroot);
+	else
+		strcpy(line, "/net/cs");
+	fd = open(line, ORDWR);
+	if(fd < 0)
+		return 0;
+	seek(fd, 0, 0);
+	e = line + sizeof(line);
+	p = seprint(line, e, "!ipinfo %s=%s", attr, val);
+	for(i = 0; i < n; i++){
+		if(*list == nil)
+			break;
+		p = seprint(p, e, " %s", *list++);
+	}
+	
+	if(write(fd, line, strlen(line)) < 0){
+		close(fd);
+		return 0;
+	}
+	seek(fd, 0, 0);
+
+	first = last = 0;
+	for(;;){
+		n = read(fd, line, sizeof(line)-2);
+		if(n <= 0)
+			break;
+		line[n] = '\n';
+		line[n+1] = 0;
+
+		t = _ndbparseline(line);
+		if(t == 0)
+			continue;
+		if(first)
+			last->entry = t;
+		else
+			first = t;
+		last = t;
+
+		while(last->entry)
+			last = last->entry;
+	}
+	close(fd);
+
+	setmalloctag(first, getcallerpc(&netroot));
+	return first;
+}
diff --git a/src/libndb/dnsquery.c b/src/libndb/dnsquery.c
new file mode 100644
index 00000000..4cf8735a
--- /dev/null
+++ b/src/libndb/dnsquery.c
@@ -0,0 +1,156 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ndb.h>
+#include <ndbhf.h>
+
+static void nstrcpy(char*, char*, int);
+static void mkptrname(char*, char*, int);
+static Ndbtuple *doquery(int, char *dn, char *type);
+
+/*
+ *  search for a tuple that has the given 'attr=val' and also 'rattr=x'.
+ *  copy 'x' into 'buf' and return the whole tuple.
+ *
+ *  return 0 if not found.
+ */
+Ndbtuple*
+dnsquery(char *net, char *val, char *type)
+{
+	char rip[128];
+	char *p;
+	Ndbtuple *t;
+	int fd;
+
+	/* if the address is V4 or V6 null address, give up early vwhoi*/
+	if(strcmp(val, "::") == 0 || strcmp(val, "0.0.0.0") == 0)
+		return nil;
+
+	if(net == nil)
+		net = "/net";
+	snprint(rip, sizeof(rip), "%s/dns", net);
+	fd = open(rip, ORDWR);
+	if(fd < 0){
+		if(strcmp(net, "/net") == 0)
+			snprint(rip, sizeof(rip), "/srv/dns");
+		else {
+			snprint(rip, sizeof(rip), "/srv/dns%s", net);
+			p = strrchr(rip, '/');
+			*p = '_';
+		}
+		fd = open(rip, ORDWR);
+		if(fd < 0)
+			return nil;
+		if(mount(fd, -1, net, MBEFORE, "") < 0){
+			close(fd);
+			return nil;
+		}
+		/* fd is now closed */
+		snprint(rip, sizeof(rip), "%s/dns", net);
+		fd = open(rip, ORDWR);
+		if(fd < 0)
+			return nil;
+	}
+
+	/* zero out the error string */
+	werrstr("");
+
+	/* if this is a reverse lookup, first lookup the domain name */
+	if(strcmp(type, "ptr") == 0){
+		mkptrname(val, rip, sizeof rip);
+		t = doquery(fd, rip, "ptr");
+	} else
+		t = doquery(fd, val, type);
+
+	close(fd);
+	return t;
+}
+
+/*
+ *  convert address into a reverse lookup address
+ */
+static void
+mkptrname(char *ip, char *rip, int rlen)
+{
+	char buf[128];
+	char *p, *np;
+	int len;
+
+	if(strstr(ip, "in-addr.arpa") || strstr(ip, "IN-ADDR.ARPA")){
+		nstrcpy(rip, ip, rlen);
+		return;
+	}
+
+	nstrcpy(buf, ip, sizeof buf);
+	for(p = buf; *p; p++)
+		;
+	*p = '.';
+	np = rip;
+	len = 0;
+	while(p >= buf){
+		len++;
+		p--;
+		if(*p == '.'){
+			memmove(np, p+1, len);
+			np += len;
+			len = 0;
+		}
+	}
+	memmove(np, p+1, len);
+	np += len;
+	strcpy(np, "in-addr.arpa");
+}
+
+static void
+nstrcpy(char *to, char *from, int len)
+{
+	strncpy(to, from, len);
+	to[len-1] = 0;
+}
+
+static Ndbtuple*
+doquery(int fd, char *dn, char *type)
+{
+	char buf[1024];
+	int n;
+	Ndbtuple *t, *first, *last;
+
+	seek(fd, 0, 0);
+	snprint(buf, sizeof(buf), "!%s %s", dn, type);
+	if(write(fd, buf, strlen(buf)) < 0)
+		return nil;
+		
+	seek(fd, 0, 0);
+
+	first = last = nil;
+	
+	for(;;){
+		n = read(fd, buf, sizeof(buf)-2);
+		if(n <= 0)
+			break;
+		if(buf[n-1] != '\n')
+			buf[n++] = '\n';	/* ndbparsline needs a trailing new line */
+		buf[n] = 0;
+
+		/* check for the error condition */
+		if(buf[0] == '!'){
+			werrstr("%s", buf+1);
+			return nil;
+		}
+
+		t = _ndbparseline(buf);
+		if(t != nil){
+			if(first)
+				last->entry = t;
+			else
+				first = t;
+			last = t;
+
+			while(last->entry)
+				last = last->entry;
+		}
+	}
+
+	setmalloctag(first, getcallerpc(&fd));
+	return first;
+}
diff --git a/src/libndb/ipattr.c b/src/libndb/ipattr.c
new file mode 100644
index 00000000..d23d5ee0
--- /dev/null
+++ b/src/libndb/ipattr.c
@@ -0,0 +1,46 @@
+#include <u.h>
+#include <ctype.h>
+
+/*
+ *  return ndb attribute type of an ip name
+ */
+char*
+ipattr(char *name)
+{
+	char *p, c;
+	int dot = 0;
+	int alpha = 0;
+	int colon = 0;
+	int hex = 0;
+
+	for(p = name; *p; p++){
+		c = *p;
+		if(isdigit(c))
+			continue;
+		if(isxdigit(c))
+			hex = 1;
+		else if(isalpha(c) || c == '-')
+			alpha = 1;
+		else if(c == '.')
+			dot = 1;
+		else if(c == ':')
+			colon = 1;
+		else
+			return "sys";
+	}
+
+	if(alpha){
+		if(dot)
+			return "dom";
+		else
+			return "sys";
+	}
+
+	if(colon)
+		return "ip";	/* ip v6 */
+
+	if(dot && !hex)
+		return "ip";
+	else
+		return "sys";
+}
diff --git a/src/libndb/mkfile b/src/libndb/mkfile
new file mode 100644
index 00000000..a49cd5e0
--- /dev/null
+++ b/src/libndb/mkfile
@@ -0,0 +1,32 @@
+<$PLAN9/src/mkhdr
+
+LIB=libndb.a
+OFILES=\
+#	csgetval.$O\
+#	csipinfo.$O\
+#	dnsquery.$O\
+	ipattr.$O\
+	ndbaux.$O\
+	ndbcache.$O\
+	ndbcat.$O\
+	ndbconcatenate.$O\
+	ndbdiscard.$O\
+	ndbfree.$O\
+	ndbgetipaddr.$O\
+	ndbgetval.$O\
+	ndbhash.$O\
+	ndbipinfo.$O\
+	ndblookval.$O\
+	ndbopen.$O\
+	ndbparse.$O\
+	ndbreorder.$O\
+	ndbsubstitute.$O\
+
+HFILES=\
+	$PLAN9/include/ndb.h\
+	ndbhf.h
+
+<$PLAN9/src/mksyslib
+
+$O.out: testipinfo.$O
+	$LD $prereq
diff --git a/src/libndb/ndbaux.c b/src/libndb/ndbaux.c
new file mode 100644
index 00000000..94246fc6
--- /dev/null
+++ b/src/libndb/ndbaux.c
@@ -0,0 +1,94 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ctype.h>
+#include <ndb.h>
+#include "ndbhf.h"
+
+
+/*
+ *  parse a single tuple
+ */
+char*
+_ndbparsetuple(char *cp, Ndbtuple **tp)
+{
+	char *p;
+	int len;
+	Ndbtuple *t;
+
+	/* a '#' starts a comment lasting till new line */
+	EATWHITE(cp);
+	if(*cp == '#' || *cp == '\n')
+		return 0;
+
+	t = ndbnew(nil, nil);
+	setmalloctag(t, getcallerpc(&cp));
+	*tp = t;
+
+	/* parse attribute */
+	p = cp;
+	while(*cp != '=' && !ISWHITE(*cp) && *cp != '\n')
+		cp++;
+	len = cp - p;
+	if(len >= Ndbalen)
+		len = Ndbalen-1;
+	strncpy(t->attr, p, len);
+
+	/* parse value */
+	EATWHITE(cp);
+	if(*cp == '='){
+		cp++;
+		if(*cp == '"'){
+			p = ++cp;
+			while(*cp != '\n' && *cp != '"')
+				cp++;
+			len = cp - p;
+			if(*cp == '"')
+				cp++;
+		} else if(*cp == '#'){
+			len = 0;
+		} else {
+			p = cp;
+			while(!ISWHITE(*cp) && *cp != '\n')
+				cp++;
+			len = cp - p;
+		}
+		ndbsetval(t, p, len);
+	}
+
+	return cp;
+}
+
+/*
+ *  parse all tuples in a line.  we assume that the 
+ *  line ends in a '\n'.
+ *
+ *  the tuples are linked as a list using ->entry and
+ *  as a ring using ->line.
+ */
+Ndbtuple*
+_ndbparseline(char *cp)
+{
+	Ndbtuple *t;
+	Ndbtuple *first, *last;
+
+	first = last = 0;
+	while(*cp != '#' && *cp != '\n'){
+		t = 0;
+		cp = _ndbparsetuple(cp, &t);
+		if(cp == 0)
+			break;
+		if(first){
+			last->line = t;
+			last->entry = t;
+		} else
+			first = t;
+		last = t;
+		t->line = 0;
+		t->entry = 0;
+	}
+	if(first)
+		last->line = first;
+	setmalloctag(first, getcallerpc(&cp));
+	return first;
+}
diff --git a/src/libndb/ndbcache.c b/src/libndb/ndbcache.c
new file mode 100644
index 00000000..701d63eb
--- /dev/null
+++ b/src/libndb/ndbcache.c
@@ -0,0 +1,144 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ndb.h>
+
+struct Ndbcache
+{
+	Ndbcache	*next;
+	char		*attr;
+	char		*val;
+	Ndbs		s;
+	Ndbtuple	*t;	
+};
+
+enum
+{
+	Maxcached=	128,
+};
+
+static void
+ndbcachefree(Ndbcache *c)
+{
+	free(c->val);
+	free(c->attr);
+	if(c->t)
+		ndbfree(c->t);
+	free(c);
+}
+
+static Ndbtuple*
+ndbcopy(Ndb *db, Ndbtuple *from_t, Ndbs *from_s, Ndbs *to_s)
+{
+	Ndbtuple *first, *to_t, *last, *line;
+	int newline;
+
+	*to_s = *from_s;
+	to_s->t = nil;
+	to_s->db = db;
+
+	newline = 1;
+	last = nil;
+	first = nil;
+	line = nil;
+	for(; from_t != nil; from_t = from_t->entry){
+		to_t = ndbnew(from_t->attr, from_t->val);
+
+		/* have s point to matching tuple */
+		if(from_s->t == from_t)
+			to_s->t = to_t;
+
+		if(newline)
+			line = to_t;
+		else
+			last->line = to_t;
+
+		if(last != nil)
+			last->entry = to_t;
+		else {
+			first = to_t;
+			line = to_t;
+		}
+		to_t->entry = nil;
+		to_t->line = line;
+		last = to_t;
+		newline = from_t->line != from_t->entry;
+	}
+	return first;
+}
+
+/*
+ *  if found, move to front
+ */
+int
+_ndbcachesearch(Ndb *db, Ndbs *s, char *attr, char *val, Ndbtuple **t)
+{
+	Ndbcache *c, **l;
+
+	*t = nil;
+	c = nil;
+	for(l = &db->cache; *l != nil; l = &(*l)->next){
+		c = *l;
+		if(strcmp(c->attr, attr) == 0 && strcmp(c->val, val) == 0)
+			break;
+	}
+	if(*l == nil)
+		return -1;
+
+	/* move to front */
+	*l = c->next;
+	c->next = db->cache;
+	db->cache = c;
+
+	*t = ndbcopy(db, c->t, &c->s, s);
+	return 0;
+}
+
+Ndbtuple*
+_ndbcacheadd(Ndb *db, Ndbs *s, char *attr, char *val, Ndbtuple *t)
+{
+	Ndbcache *c, **l;
+
+	c = mallocz(sizeof *c, 1);
+	if(c == nil)
+		return nil;
+	c->attr = strdup(attr);
+	if(c->attr == nil)
+		goto err;
+	c->val = strdup(val);
+	if(c->val == nil)
+		goto err;
+	c->t = ndbcopy(db, t, s, &c->s);
+	if(c->t == nil && t != nil)
+		goto err;
+
+	/* add to front */
+	c->next = db->cache;
+	db->cache = c;
+
+	/* trim list */
+	if(db->ncache < Maxcached){
+		db->ncache++;
+		return t;
+	}
+	for(l = &db->cache; (*l)->next; l = &(*l)->next)
+		;
+	c = *l;
+	*l = nil;
+err:
+	ndbcachefree(c);
+	return t;
+}
+
+void
+_ndbcacheflush(Ndb *db)
+{
+	Ndbcache *c;
+
+	while(db->cache != nil){
+		c = db->cache;
+		db->cache = c->next;
+		ndbcachefree(c);
+	}
+	db->ncache = 0;
+}
diff --git a/src/libndb/ndbcat.c b/src/libndb/ndbcat.c
new file mode 100644
index 00000000..61ef5e47
--- /dev/null
+++ b/src/libndb/ndbcat.c
@@ -0,0 +1,18 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ctype.h>
+#include <ndb.h>
+
+Ndb*
+ndbcat(Ndb *a, Ndb *b)
+{
+	Ndb *db = a;
+
+	if(a == nil)
+		return b;
+	while(a->next != nil)
+		a = a->next;
+	a->next = b;
+	return db;
+}
diff --git a/src/libndb/ndbconcatenate.c b/src/libndb/ndbconcatenate.c
new file mode 100644
index 00000000..3725f181
--- /dev/null
+++ b/src/libndb/ndbconcatenate.c
@@ -0,0 +1,18 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ndb.h>
+
+/* concatenate two tuples */
+Ndbtuple*
+ndbconcatenate(Ndbtuple *a, Ndbtuple *b)
+{
+	Ndbtuple *t;
+
+	if(a == nil)
+		return b;
+	for(t = a; t->entry; t = t->entry)
+		;
+	t->entry = b;
+	return a;
+}
diff --git a/src/libndb/ndbdiscard.c b/src/libndb/ndbdiscard.c
new file mode 100644
index 00000000..9b2fc0c9
--- /dev/null
+++ b/src/libndb/ndbdiscard.c
@@ -0,0 +1,29 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ndb.h>
+
+/* remove a from t and free it */
+Ndbtuple*
+ndbdiscard(Ndbtuple *t, Ndbtuple *a)
+{
+	Ndbtuple *nt;
+
+	/* unchain a */
+	for(nt = t; nt != nil; nt = nt->entry){
+		if(nt->line == a)
+			nt->line = a->line;
+		if(nt->entry == a)
+			nt->entry = a->entry;
+	}
+
+	/* a may be start of chain */
+	if(t == a)
+		t = a->entry;
+
+	/* free a */
+	a->entry = nil;
+	ndbfree(a);
+
+	return t;
+}
diff --git a/src/libndb/ndbfree.c b/src/libndb/ndbfree.c
new file mode 100644
index 00000000..647bff03
--- /dev/null
+++ b/src/libndb/ndbfree.c
@@ -0,0 +1,65 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ctype.h>
+#include <ndb.h>
+#include "ndbhf.h"
+
+/*
+ *  free a parsed entry
+ */
+void
+ndbfree(Ndbtuple *t)
+{
+	Ndbtuple *tn;
+
+	for(; t; t = tn){
+		tn = t->entry;
+		if(t->val != t->valbuf){
+			free(t->val);
+		}
+		free(t);
+	}
+}
+
+/*
+ *  set a value in a tuple
+ */
+void
+ndbsetval(Ndbtuple *t, char *val, int n)
+{
+	if(n < Ndbvlen){
+		if(t->val != t->valbuf){
+			free(t->val);
+			t->val = t->valbuf;
+		}
+	} else {
+		if(t->val != t->valbuf)
+			t->val = realloc(t->val, n+1);
+		else
+			t->val = malloc(n+1);
+		if(t->val == nil)
+			sysfatal("ndbsetval %r");
+	}
+	strncpy(t->val, val, n);
+	t->val[n] = 0;
+}
+
+/*
+ *  allocate a tuple
+ */
+Ndbtuple*
+ndbnew(char *attr, char *val)
+{
+	Ndbtuple *t;
+
+	t = mallocz(sizeof(*t), 1);
+	if(t == nil)
+		sysfatal("ndbnew %r");
+	if(attr != nil)
+		strncpy(t->attr, attr, sizeof(t->attr)-1);
+	t->val = t->valbuf;
+	if(val != nil)
+		ndbsetval(t, val, strlen(val));
+	return t;	
+}
diff --git a/src/libndb/ndbgetipaddr.c b/src/libndb/ndbgetipaddr.c
new file mode 100644
index 00000000..f076cd9c
--- /dev/null
+++ b/src/libndb/ndbgetipaddr.c
@@ -0,0 +1,47 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ndb.h>
+#include <ip.h>
+
+/* return list of ip addresses for a name */
+Ndbtuple*
+ndbgetipaddr(Ndb *db, char *val)
+{
+	char *attr, *p;
+	Ndbtuple *it, *first, *last, *next;
+	Ndbs s;
+
+	/* already an IP address? */
+	attr = ipattr(val);
+	if(strcmp(attr, "ip") == 0){
+		it = ndbnew("ip", val);
+		return it;
+	}
+
+	/* look it up */
+	p = ndbgetvalue(db, &s, attr, val, "ip", &it);
+	if(p == nil)
+		return nil;
+	free(p);
+
+	/* remove the non-ip entries */
+	first = last = nil;
+	for(; it; it = next){
+		next = it->entry;
+		if(strcmp(it->attr, "ip") == 0){
+			if(first == nil)
+				first = it;
+			else
+				last->entry = it;
+			it->entry = nil;
+			it->line = first;
+			last = it;
+		} else {
+			it->entry = nil;
+			ndbfree(it);
+		}
+	}
+
+	return first;
+}
diff --git a/src/libndb/ndbgetval.c b/src/libndb/ndbgetval.c
new file mode 100644
index 00000000..2c66b206
--- /dev/null
+++ b/src/libndb/ndbgetval.c
@@ -0,0 +1,75 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include "ndb.h"
+
+/*
+ *  search for a tuple that has the given 'attr=val' and also 'rattr=x'.
+ *  copy 'x' into 'buf' and return the whole tuple.
+ *
+ *  return 0 if not found.
+ */
+char*
+ndbgetvalue(Ndb *db, Ndbs *s, char *attr, char *val, char *rattr, Ndbtuple **pp)
+{
+	Ndbtuple *t, *nt;
+	char *rv;
+	Ndbs temps;
+
+	if(s == nil)
+		s = &temps;
+	if(pp)
+		*pp = nil;
+	t = ndbsearch(db, s, attr, val);
+	while(t){
+		/* first look on same line (closer binding) */
+		nt = s->t;
+		for(;;){
+			if(strcmp(rattr, nt->attr) == 0){
+				rv = strdup(nt->val);
+				if(pp != nil)
+					*pp = t;
+				else
+					ndbfree(t);
+				return rv;
+			}
+			nt = nt->line;
+			if(nt == s->t)
+				break;
+		}
+		/* search whole tuple */
+		for(nt = t; nt; nt = nt->entry){
+			if(strcmp(rattr, nt->attr) == 0){
+				rv = strdup(nt->val);
+				if(pp != nil)
+					*pp = t;
+				else
+					ndbfree(t);
+				return rv;
+			}
+		}
+		ndbfree(t);
+		t = ndbsnext(s, attr, val);
+	}
+	return nil;
+}
+
+Ndbtuple*
+ndbgetval(Ndb *db, Ndbs *s, char *attr, char *val, char *rattr, char *buf)
+{
+	Ndbtuple *t;
+	char *p;
+
+	p = ndbgetvalue(db, s, attr, val, rattr, &t);
+	if(p == nil){
+		if(buf != nil)
+			*buf = 0;
+	} else {
+		if(buf != nil){
+			strncpy(buf, p, Ndbvlen-1);
+			buf[Ndbvlen-1] = 0;
+		}
+		free(p);
+	}
+	return t;
+}
diff --git a/src/libndb/ndbhash.c b/src/libndb/ndbhash.c
new file mode 100644
index 00000000..a6965cdb
--- /dev/null
+++ b/src/libndb/ndbhash.c
@@ -0,0 +1,247 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include "ndb.h"
+#include "ndbhf.h"
+
+enum {
+	Dptr,	/* pointer to database file */
+	Cptr,	/* pointer to first chain entry */
+	Cptr1,	/* pointer to second chain entry */
+};
+
+/*
+ *  generate a hash value for an ascii string (val) given
+ *  a hash table length (hlen)
+ */
+ulong
+ndbhash(char *vp, int hlen)
+{
+	ulong hash;
+	uchar *val = (uchar*)vp;
+
+	for(hash = 0; *val; val++)
+		hash = (hash*13) + *val-'a';
+	return hash % hlen;
+}
+
+/*
+ *  read a hash file with buffering
+ */
+static uchar*
+hfread(Ndbhf *hf, long off, int len)
+{
+	if(off < hf->off || off + len > hf->off + hf->len){
+		if(seek(hf->fd, off, 0) < 0
+		|| (hf->len = read(hf->fd, hf->buf, sizeof(hf->buf))) < len){
+			hf->off = -1;
+			return 0;
+		}
+		hf->off = off;
+	}
+	return &hf->buf[off-hf->off];
+}
+
+/*
+ *  return an opened hash file if one exists for the
+ *  attribute and if it is current vis-a-vis the data
+ *  base file
+ */
+static Ndbhf*
+hfopen(Ndb *db, char *attr)
+{
+	Ndbhf *hf;
+	char buf[sizeof(hf->attr)+sizeof(db->file)+2];
+	uchar *p;
+	Dir *d;
+
+	/* try opening the data base if it's closed */
+	if(db->mtime==0 && ndbreopen(db) < 0)
+		return 0;
+
+	/* if the database has changed, throw out hash files and reopen db */
+	if((d = dirfstat(Bfildes(&db->b))) == nil || db->qid.path != d->qid.path
+	|| db->qid.vers != d->qid.vers){
+		if(ndbreopen(db) < 0){
+			free(d);
+			return 0;
+		}
+	}
+	free(d);
+
+	if(db->nohash)
+		return 0;
+
+	/* see if a hash file exists for this attribute */
+	for(hf = db->hf; hf; hf= hf->next){
+		if(strcmp(hf->attr, attr) == 0)
+			return hf;
+	}
+
+	/* create a new one */
+	hf = (Ndbhf*)malloc(sizeof(Ndbhf));
+	if(hf == 0)
+		return 0;
+	memset(hf, 0, sizeof(Ndbhf));
+
+	/* compare it to the database file */
+	strncpy(hf->attr, attr, sizeof(hf->attr)-1);
+	sprint(buf, "%s.%s", db->file, hf->attr);
+	hf->fd = open(buf, OREAD);
+	if(hf->fd >= 0){
+		hf->len = 0;
+		hf->off = 0;
+		p = hfread(hf, 0, 2*NDBULLEN);
+		if(p){
+			hf->dbmtime = NDBGETUL(p);
+			hf->hlen = NDBGETUL(p+NDBULLEN);
+			if(hf->dbmtime == db->mtime){
+				hf->next = db->hf;
+				db->hf = hf;
+				return hf;
+			}
+		}
+		close(hf->fd);
+	}
+
+	free(hf);
+	return 0;
+}
+
+/*
+ *  return the first matching entry
+ */
+Ndbtuple*
+ndbsearch(Ndb *db, Ndbs *s, char *attr, char *val)
+{
+	uchar *p;
+	Ndbtuple *t;
+	Ndbhf *hf;
+
+	hf = hfopen(db, attr);
+
+	memset(s, 0, sizeof(*s));
+	if(_ndbcachesearch(db, s, attr, val, &t) == 0){
+		/* found in cache */
+		if(t != nil)
+			return t;	/* answer from this file */
+		if(db->next == nil)
+			return nil;
+		return ndbsearch(db->next, s, attr, val);
+	}
+
+	s->db = db;
+	s->hf = hf;
+	if(s->hf){
+		s->ptr = ndbhash(val, s->hf->hlen)*NDBPLEN;
+		p = hfread(s->hf, s->ptr+NDBHLEN, NDBPLEN);
+		if(p == 0)
+			return _ndbcacheadd(db, s, attr, val, nil);
+		s->ptr = NDBGETP(p);
+		s->type = Cptr1;
+	} else if(db->length > 128*1024){
+		print("Missing or out of date hash file %s.%s.\n", db->file, attr);
+	/*	syslog(0, "ndb", "Missing or out of date hash file %s.%s.", db->file, attr); */
+
+		/* advance search to next db file */
+		s->ptr = NDBNAP;
+		_ndbcacheadd(db, s, attr, val, nil);
+		if(db->next == 0)
+			return nil;
+		return ndbsearch(db->next, s, attr, val);
+	} else {
+		s->ptr = 0;
+		s->type = Dptr;
+	}
+	t = ndbsnext(s, attr, val);
+	_ndbcacheadd(db, s, attr, val, (t != nil && s->db == db)?t:nil);
+	setmalloctag(t, getcallerpc(&db));
+	return t;
+}
+
+static Ndbtuple*
+match(Ndbtuple *t, char *attr, char *val)
+{
+	Ndbtuple *nt;
+
+	for(nt = t; nt; nt = nt->entry)
+		if(strcmp(attr, nt->attr) == 0
+		&& strcmp(val, nt->val) == 0)
+			return nt;
+	return 0;
+}
+
+/*
+ *  return the next matching entry in the hash chain
+ */
+Ndbtuple*
+ndbsnext(Ndbs *s, char *attr, char *val)
+{
+	Ndbtuple *t;
+	Ndb *db;
+	uchar *p;
+
+	db = s->db;
+	if(s->ptr == NDBNAP)
+		goto nextfile;
+
+	for(;;){
+		if(s->type == Dptr){
+			if(Bseek(&db->b, s->ptr, 0) < 0)
+				break;
+			t = ndbparse(db);
+			s->ptr = Boffset(&db->b);
+			if(t == 0)
+				break;
+			if(s->t = match(t, attr, val))
+				return t;
+			ndbfree(t);
+		} else if(s->type == Cptr){
+			if(Bseek(&db->b, s->ptr, 0) < 0)
+				break; 
+			s->ptr = s->ptr1;
+			s->type = Cptr1;
+			t = ndbparse(db);
+			if(t == 0)
+				break;
+			if(s->t = match(t, attr, val))
+				return t;
+			ndbfree(t);
+		} else if(s->type == Cptr1){
+			if(s->ptr & NDBCHAIN){	/* hash chain continuation */
+				s->ptr &= ~NDBCHAIN;
+				p = hfread(s->hf, s->ptr+NDBHLEN, 2*NDBPLEN);
+				if(p == 0)
+					break;
+				s->ptr = NDBGETP(p);
+				s->ptr1 = NDBGETP(p+NDBPLEN);
+				s->type = Cptr;
+			} else {		/* end of hash chain */
+				if(Bseek(&db->b, s->ptr, 0) < 0)
+					break; 
+				s->ptr = NDBNAP;
+				t = ndbparse(db);
+				if(t == 0)
+					break;
+				if(s->t = match(t, attr, val)){
+					setmalloctag(t, getcallerpc(&s));
+					return t;
+				}
+				ndbfree(t);
+				break;
+			}
+		}
+	}
+
+nextfile:
+
+	/* nothing left to search? */
+	s->ptr = NDBNAP;
+	if(db->next == 0)
+		return 0;
+
+	/* advance search to next db file */
+	t = ndbsearch(db->next, s, attr, val);
+	setmalloctag(t, getcallerpc(&s));
+	return t;
+}
diff --git a/src/libndb/ndbhf.h b/src/libndb/ndbhf.h
new file mode 100644
index 00000000..4505d13b
--- /dev/null
+++ b/src/libndb/ndbhf.h
@@ -0,0 +1,27 @@
+/* a hash file */
+struct Ndbhf
+{
+	Ndbhf	*next;
+
+	int	fd;
+	ulong	dbmtime;	/* mtime of data base */
+	int	hlen;		/* length (in entries) of hash table */
+	char	attr[Ndbalen];	/* attribute hashed */
+
+	uchar	buf[256];	/* hash file buffer */
+	long	off;		/* offset of first byte of buffer */
+	int	len;		/* length of valid data in buffer */
+};
+
+char*		_ndbparsetuple(char*, Ndbtuple**);
+Ndbtuple*	_ndbparseline(char*);
+
+#define ISWHITE(x) ((x) == ' ' || (x) == '\t' || (x) == '\r')
+#define EATWHITE(x) while(ISWHITE(*(x)))(x)++
+
+extern Ndbtuple *_ndbtfree;
+
+/* caches */
+void	_ndbcacheflush(Ndb *db);
+int	_ndbcachesearch(Ndb *db, Ndbs *s, char *attr, char *val, Ndbtuple **t);
+Ndbtuple* _ndbcacheadd(Ndb *db, Ndbs *s, char *attr, char *val, Ndbtuple *t);
diff --git a/src/libndb/ndbipinfo.c b/src/libndb/ndbipinfo.c
new file mode 100644
index 00000000..5cdc24b5
--- /dev/null
+++ b/src/libndb/ndbipinfo.c
@@ -0,0 +1,242 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ndb.h>
+#include <ip.h>
+
+enum
+{
+	Ffound=	1<<0,
+	Fignore=1<<1,
+	Faddr=	1<<2,
+};
+
+static Ndbtuple*	filter(Ndb *db, Ndbtuple *t, Ndbtuple *f);
+static Ndbtuple*	mkfilter(int argc, char **argv);
+static int		filtercomplete(Ndbtuple *f);
+static Ndbtuple*	toipaddr(Ndb *db, Ndbtuple *t);
+static int		prefixlen(uchar *ip);
+static Ndbtuple*	subnet(Ndb *db, uchar *net, Ndbtuple *f, int prefix);
+
+/* make a filter to be used in filter */
+static Ndbtuple*
+mkfilter(int argc, char **argv)
+{
+	Ndbtuple *t, *first, *last;
+	char *p;
+
+	last = first = nil;
+	while(argc-- > 0){
+		t = ndbnew(0, 0);
+		if(first)
+			last->entry = t;
+		else
+			first = t;
+		last = t;
+		p = *argv++;
+		if(*p == '@'){
+			t->ptr |= Faddr;
+			p++;
+		}
+		strncpy(t->attr, p, sizeof(t->attr)-1);
+	}
+	return first;
+}
+
+/* return true if every pair of filter has been used */
+static int
+filtercomplete(Ndbtuple *f)
+{
+	for(; f; f = f->entry)
+		if((f->ptr & Fignore) == 0)
+			return 0;
+	return 1;
+}
+
+/* set the attribute of all entries in a tuple */
+static Ndbtuple*
+setattr(Ndbtuple *t, char *attr)
+{
+	Ndbtuple *nt;
+
+	for(nt = t; nt; nt = nt->entry)
+		strcpy(nt->attr, attr);
+	return t;
+}
+
+/*
+ *  return only the attr/value pairs in t maching the filter, f.
+ *  others are freed.  line structure is preserved.
+ */
+static Ndbtuple*
+filter(Ndb *db, Ndbtuple *t, Ndbtuple *f)
+{
+	Ndbtuple *nt, *nf, *next;
+
+	/* filter out what we don't want */
+	for(nt = t; nt; nt = next){
+		next = nt->entry;
+
+		/* look through filter */
+		for(nf = f; nf != nil; nf = nf->entry){
+			if(!(nf->ptr&Fignore) && strcmp(nt->attr, nf->attr) == 0)
+				break;
+		}
+		if(nf == nil){
+			/* remove nt from t */
+			t = ndbdiscard(t, nt);
+		} else {
+			if(nf->ptr & Faddr)
+				t = ndbsubstitute(t, nt, setattr(ndbgetipaddr(db, nt->val), nt->attr));
+			nf->ptr |= Ffound;
+		}
+	}
+
+	/* remember filter etnries that matched */
+	for(nf = f; nf != nil; nf = nf->entry)
+		if(nf->ptr & Ffound)
+			nf->ptr = (nf->ptr & ~Ffound) | Fignore;
+
+	return t;
+}
+
+static int
+prefixlen(uchar *ip)
+{
+	int y, i;
+
+	for(y = IPaddrlen-1; y >= 0; y--)
+		for(i = 8; i > 0; i--)
+			if(ip[y] & (1<<(8-i)))
+				return y*8 + i;
+	return 0;
+}
+
+/*
+ *  look through a containing subset
+ */
+static Ndbtuple*
+subnet(Ndb *db, uchar *net, Ndbtuple *f, int prefix)
+{
+	Ndbs s;
+	Ndbtuple *t, *nt, *xt;
+	char netstr[128];
+	uchar mask[IPaddrlen];
+	int masklen;
+
+	t = nil;
+	sprint(netstr, "%I", net);
+	nt = ndbsearch(db, &s, "ip", netstr);
+	while(nt != nil){
+		xt = ndbfindattr(nt, nt, "ipnet");
+		if(xt){
+			xt = ndbfindattr(nt, nt, "ipmask");
+			if(xt)
+				parseipmask(mask, xt->val);
+			else
+				ipmove(mask, defmask(net));
+			masklen = prefixlen(mask);
+			if(masklen <= prefix)
+				t = ndbconcatenate(t, filter(db, nt, f));
+		} else
+			ndbfree(nt);
+		nt = ndbsnext(&s, "ip", netstr);
+	}
+	return t;
+}
+
+/*
+ *  fill in all the requested attributes for a system.
+ *  if the system's entry doesn't have all required,
+ *  walk through successively more inclusive networks
+ *  for inherited attributes.
+ */
+Ndbtuple*
+ndbipinfo(Ndb *db, char *attr, char *val, char **alist, int n)
+{
+	Ndbtuple *t, *nt, *f;
+	Ndbs s;
+	char *ipstr;
+	uchar net[IPaddrlen];
+	uchar ip[IPaddrlen];
+	int prefix, smallestprefix;
+	int force;
+
+	/* just in case */
+	fmtinstall('I', eipfmt);
+	fmtinstall('M', eipfmt);
+
+	/* get needed attributes */
+	f = mkfilter(n, alist);
+
+	/*
+	 *  first look for a matching entry with an ip address
+	 */
+	t = nil;
+	ipstr = ndbgetvalue(db, &s, attr, val, "ip", &nt);
+	if(ipstr == nil){
+		/* none found, make one up */
+		if(strcmp(attr, "ip") != 0)
+			return nil;
+		t = ndbnew("ip", val);
+		t->line = t;
+		t->entry = nil;
+		parseip(net, val);
+	} else {
+		/* found one */
+		while(nt != nil){
+			nt = ndbreorder(nt, s.t);
+			t = ndbconcatenate(t, nt);
+			nt = ndbsnext(&s, attr, val);
+		}
+		parseip(net, ipstr);
+		free(ipstr);
+	}
+	ipmove(ip, net);
+	t = filter(db, t, f);
+
+	/*
+	 *  now go through subnets to fill in any missing attributes
+	 */
+	if(isv4(net)){
+		prefix = 127;
+		smallestprefix = 100;
+		force = 0;
+	} else {
+		/* in v6, the last 8 bytes have no structure (we hope) */
+		prefix = 64;
+		smallestprefix = 2;
+		memset(net+8, 0, 8);
+		force = 1;
+	}
+
+	/*
+	 *  to find a containing network, keep turning off
+	 *  the lower bit and look for a network with
+	 *  that address and a shorter mask.  tedius but
+	 *  complete, we may need to find a trick to speed this up.
+	 */
+	for(; prefix >= smallestprefix; prefix--){
+		if(filtercomplete(f))
+			break;
+		if(!force && (net[prefix/8] & (1<<(7-(prefix%8)))) == 0)
+			continue;
+		force = 0;
+		net[prefix/8] &= ~(1<<(7-(prefix%8)));
+		t = ndbconcatenate(t, subnet(db, net, f, prefix));
+	}
+
+	/*
+	 *  if there's an unfulfilled ipmask, make one up
+	 */
+	nt = ndbfindattr(f, f, "ipmask");
+	if(nt && !(nt->ptr & Fignore)){
+		char x[64];
+
+		snprint(x, sizeof(x), "%M", defmask(ip));
+		t = ndbconcatenate(t, ndbnew("ipmask", x));
+	}
+
+	ndbfree(f);
+	return t;
+}
diff --git a/src/libndb/ndblookval.c b/src/libndb/ndblookval.c
new file mode 100644
index 00000000..012bc4b2
--- /dev/null
+++ b/src/libndb/ndblookval.c
@@ -0,0 +1,44 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ip.h>
+#include <ndb.h>
+
+/*
+ *  Look for a pair with the given attribute.  look first on the same line,
+ *  then in the whole entry.
+ */
+Ndbtuple*
+ndbfindattr(Ndbtuple *entry, Ndbtuple *line, char *attr)
+{
+	Ndbtuple *nt;
+
+	/* first look on same line (closer binding) */
+	for(nt = line; nt;){
+		if(strcmp(attr, nt->attr) == 0)
+			return nt;
+		nt = nt->line;
+		if(nt == line)
+			break;
+	}
+
+	/* search whole tuple */
+	for(nt = entry; nt; nt = nt->entry)
+		if(strcmp(attr, nt->attr) == 0)
+			return nt;
+
+	return nil;
+}
+
+Ndbtuple*
+ndblookval(Ndbtuple *entry, Ndbtuple *line, char *attr, char *to)
+{
+	Ndbtuple *t;
+
+	t = ndbfindattr(entry, line, attr);
+	if(t != nil){
+		strncpy(to, t->val, Ndbvlen-1);
+		to[Ndbvlen-1] = 0;
+	}
+	return t;
+}
diff --git a/src/libndb/ndbopen.c b/src/libndb/ndbopen.c
new file mode 100644
index 00000000..d504702e
--- /dev/null
+++ b/src/libndb/ndbopen.c
@@ -0,0 +1,174 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ctype.h>
+#include <ndb.h>
+#include "ndbhf.h"
+
+static Ndb*	doopen(char*);
+static void	hffree(Ndb*);
+
+static char *deffile = "/lib/ndb/local";
+
+/*
+ *  the database entry in 'file' indicates the list of files
+ *  that makeup the database.  Open each one and search in
+ *  the same order.
+ */
+Ndb*
+ndbopen(char *file)
+{
+	Ndb *db, *first, *last;
+	Ndbs s;
+	Ndbtuple *t, *nt;
+
+	if(file == 0)
+		file = deffile;
+	db = doopen(file);
+	if(db == 0)
+		return 0;
+	first = last = db;
+	t = ndbsearch(db, &s, "database", "");
+	Bseek(&db->b, 0, 0);
+	if(t == 0)
+		return db;
+	for(nt = t; nt; nt = nt->entry){
+		if(strcmp(nt->attr, "file") != 0)
+			continue;
+		if(strcmp(nt->val, file) == 0){
+			/* default file can be reordered in the list */
+			if(first->next == 0)
+				continue;
+			if(strcmp(first->file, file) == 0){
+				db = first;
+				first = first->next;
+				last->next = db;
+				db->next = 0;
+				last = db;
+			}
+			continue;
+		}
+		db = doopen(nt->val);
+		if(db == 0)
+			continue;
+		last->next = db;
+		last = db;
+	}
+	ndbfree(t);
+	return first;
+}
+
+/*
+ *  open a single file
+ */
+static Ndb*
+doopen(char *file)
+{
+	Ndb *db;
+
+	db = (Ndb*)malloc(sizeof(Ndb));
+	if(db == 0)
+		return 0;
+	memset(db, 0, sizeof(Ndb));
+	strncpy(db->file, file, sizeof(db->file)-1);
+
+	if(ndbreopen(db) < 0){
+		free(db);
+		return 0;
+	}
+
+	return db;
+}
+
+/*
+ *  dump any cached information, forget the hash tables, and reopen a single file
+ */
+int
+ndbreopen(Ndb *db)
+{
+	int fd;
+	Dir *d;
+
+	/* forget what we know about the open files */
+	if(db->mtime){
+		_ndbcacheflush(db);
+		hffree(db);
+		close(Bfildes(&db->b));
+		Bterm(&db->b);
+		db->mtime = 0;
+	}
+
+	/* try the open again */
+	fd = open(db->file, OREAD);
+	if(fd < 0)
+		return -1;
+	d = dirfstat(fd);
+	if(d == nil){
+		close(fd);
+		return -1;
+	}
+
+	db->qid = d->qid;
+	db->mtime = d->mtime;
+	db->length = d->length;
+	Binit(&db->b, fd, OREAD);
+	free(d);
+	return 0;
+}
+
+/*
+ *  close the database files
+ */
+void
+ndbclose(Ndb *db)
+{
+	Ndb *nextdb;
+
+	for(; db; db = nextdb){
+		nextdb = db->next;
+		_ndbcacheflush(db);
+		hffree(db);
+		close(Bfildes(&db->b));
+		Bterm(&db->b);
+		free(db);
+	}
+}
+
+/*
+ *  free the hash files belonging to a db
+ */
+static void
+hffree(Ndb *db)
+{
+	Ndbhf *hf, *next;
+
+	for(hf = db->hf; hf; hf = next){
+		next = hf->next;
+		close(hf->fd);
+		free(hf);
+	}
+	db->hf = 0;
+}
+
+/*
+ *  return true if any part of the database has changed
+ */
+int
+ndbchanged(Ndb *db)
+{
+	Ndb *ndb;
+	Dir *d;
+
+	for(ndb = db; ndb != nil; ndb = ndb->next){
+		d = dirfstat(Bfildes(&db->b));
+		if(d == nil)
+			continue;
+		if(ndb->qid.path != d->qid.path
+		|| ndb->qid.vers != d->qid.vers){
+			free(d);
+			return 1;
+		}
+		free(d);
+	}
+	return 0;
+}
diff --git a/src/libndb/ndbparse.c b/src/libndb/ndbparse.c
new file mode 100644
index 00000000..86a108dc
--- /dev/null
+++ b/src/libndb/ndbparse.c
@@ -0,0 +1,57 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ctype.h>
+#include <ndb.h>
+#include "ndbhf.h"
+
+/*
+ *  Parse a data base entry.  Entries may span multiple
+ *  lines.  An entry starts on a left margin.  All subsequent
+ *  lines must be indented by white space.  An entry consists
+ *  of tuples of the forms:
+ *	attribute-name
+ *	attribute-name=value
+ *	attribute-name="value with white space"
+ *
+ *  The parsing returns a 2-dimensional structure.  The first
+ *  dimension joins all tuples. All tuples on the same line
+ *  form a ring along the second dimension.
+ */
+
+/*
+ *  parse the next entry in the file
+ */
+Ndbtuple*
+ndbparse(Ndb *db)
+{
+	char *line;
+	Ndbtuple *t;
+	Ndbtuple *first, *last;
+	int len;
+
+	first = last = 0;
+	for(;;){
+		if((line = Brdline(&db->b, '\n')) == 0)
+			break;
+		len = Blinelen(&db->b);
+		if(line[len-1] != '\n')
+			break;
+		if(first && !ISWHITE(*line) && *line != '#'){
+			Bseek(&db->b, -len, 1);
+			break;
+		}
+		t = _ndbparseline(line);
+		if(t == 0)
+			continue;
+		if(first)
+			last->entry = t;
+		else
+			first = t;
+		last = t;
+		while(last->entry)
+			last = last->entry;
+	}
+	setmalloctag(first, getcallerpc(&db));
+	return first;
+}
diff --git a/src/libndb/ndbreorder.c b/src/libndb/ndbreorder.c
new file mode 100644
index 00000000..167d0a0a
--- /dev/null
+++ b/src/libndb/ndbreorder.c
@@ -0,0 +1,53 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ndb.h>
+
+/*
+ *  reorder the tuple to put x's line first in the entry and x fitst in its line
+ */
+Ndbtuple*
+ndbreorder(Ndbtuple *t, Ndbtuple *x)
+{
+	Ndbtuple *nt;
+	Ndbtuple *last, *prev;
+
+	/* if x is first, we're done */
+	if(x == t)
+		return t;
+
+	/* find end of x's line */
+	for(last = x; last->line == last->entry; last = last->line)
+		;
+
+	/* rotate to make this line first */
+	if(last->line != t){
+
+		/* detach this line and everything after it from the entry */
+		for(nt = t; nt->entry != last->line; nt = nt->entry)
+			;
+		nt->entry = nil;
+	
+		/* switch */
+		for(nt = last; nt->entry != nil; nt = nt->entry)
+			;
+		nt->entry = t;
+	}
+
+	/* rotate line to make x first */
+	if(x != last->line){
+
+		/* find entry before x */
+		for(prev = last; prev->line != x; prev = prev->line);
+			;
+
+		/* detach line */
+		nt = last->entry;
+		last->entry = last->line;
+
+		/* reattach */
+		prev->entry = nt;
+	}
+
+	return x;
+}
diff --git a/src/libndb/ndbsubstitute.c b/src/libndb/ndbsubstitute.c
new file mode 100644
index 00000000..46f63712
--- /dev/null
+++ b/src/libndb/ndbsubstitute.c
@@ -0,0 +1,39 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ndb.h>
+
+/* replace a in t with b, the line structure in b is lost, c'est la vie */
+Ndbtuple*
+ndbsubstitute(Ndbtuple *t, Ndbtuple *a, Ndbtuple *b)
+{
+	Ndbtuple *nt;
+
+	if(a == b)
+		return t;
+	if(b == nil)
+		return ndbdiscard(t, a);
+
+	/* all pointers to a become pointers to b */
+	for(nt = t; nt != nil; nt = nt->entry){
+		if(nt->line == a)
+			nt->line = b;
+		if(nt->entry == a)
+			nt->entry = b;
+	}
+
+	/* end of b chain points to a's successors */
+	for(nt = b; nt->entry; nt = nt->entry){
+		nt->line = nt->entry;
+	}
+	nt->line = a->line;
+	nt->entry = a->entry;
+
+	a->entry = nil;
+	ndbfree(a);
+
+	if(a == t)
+		return b;
+	else
+		return t;
+}