new
diff --git a/src/libndb/csgetval.c b/src/libndb/csgetval.c
new file mode 100644
index 0000000..22705ad
--- /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 0000000..76f3d8e
--- /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 0000000..4cf8735
--- /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 0000000..d23d5ee
--- /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 0000000..a49cd5e
--- /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 0000000..94246fc
--- /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 0000000..701d63e
--- /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 0000000..61ef5e4
--- /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 0000000..3725f18
--- /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 0000000..9b2fc0c
--- /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 0000000..647bff0
--- /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 0000000..f076cd9
--- /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 0000000..2c66b20
--- /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 0000000..a6965cd
--- /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 0000000..4505d13
--- /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 0000000..5cdc24b
--- /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 0000000..012bc4b
--- /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 0000000..d504702
--- /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 0000000..86a108d
--- /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 0000000..167d0a0
--- /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 0000000..46f6371
--- /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;
+}
