// Debugging printfs in dbnode_query
#ifdef DEBUG_QUERY
#include <stdio.h>
#endif
/*
 * Resource manager.  In addition to what lx.h says:
 *
 * We convert the ComponentName character set to small integers 0-63
 *  for the sake of saving memory in the lookup tree we use for
 *  interning them.
 *
 * A database of resource settings is conceptually a table where the
 *  query side is strings of BQs and the value side is arbitrary octet
 *  strings.  Lookups match the query string of quarks (or,
 *  equivalently, a string of BQs where all BINDINGs are BIND_TIGHT)
 *  against the query side entries and return the value for the most
 *  specific (in the above sense) match, or a no-match indication if
 *  there is no match.
 */

#include <ctype.h>
#include <fcntl.h>
#include <stddef.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdarg.h>
#include <strings.h>

#include "lx.h"

/* Quark stuff */

/*
 * Array mapping ComponentName character to 1-64.  We use 1-64 here
 *  rather than 0-63 because C has no way to specify a value other than
 *  0 for the uninitialized elements; we subtract 1 before using
 *  nonzero values found here.
 */
static unsigned char cnc_to_xp1[]
 = { ['-'] =  1, ['0'] =  2, ['1'] =  3, ['2'] =  4,
     ['3'] =  5, ['4'] =  6, ['5'] =  7, ['6'] =  8,
     ['7'] =  9, ['8'] = 10, ['9'] = 11, ['A'] = 12,
     ['B'] = 13, ['C'] = 14, ['D'] = 15, ['E'] = 16,
     ['F'] = 17, ['G'] = 18, ['H'] = 19, ['I'] = 20,
     ['J'] = 21, ['K'] = 22, ['L'] = 23, ['M'] = 24,
     ['N'] = 25, ['O'] = 26, ['P'] = 27, ['Q'] = 28,
     ['R'] = 29, ['S'] = 30, ['T'] = 31, ['U'] = 32,
     ['V'] = 33, ['W'] = 34, ['X'] = 35, ['Y'] = 36,
     ['Z'] = 37, ['_'] = 38, ['a'] = 39, ['b'] = 40,
     ['c'] = 41, ['d'] = 42, ['e'] = 43, ['f'] = 44,
     ['g'] = 45, ['h'] = 46, ['i'] = 47, ['j'] = 48,
     ['k'] = 49, ['l'] = 50, ['m'] = 51, ['n'] = 52,
     ['o'] = 53, ['p'] = 54, ['q'] = 55, ['r'] = 56,
     ['s'] = 57, ['t'] = 58, ['u'] = 59, ['v'] = 60,
     ['w'] = 61, ['x'] = 62, ['y'] = 63, ['z'] = 64 };
#define CNC_COUNT (sizeof(cnc_to_xp1) / sizeof(cnc_to_xp1[0]))
#define CNC_N 64

/*
 * When interning strings of ComponentName characters into QUARKs, we
 *  keep strings in a 65-way tree.  Conceptually, it's just a tree with
 *  a branching factor of 65 (64 possible characters plus
 *  end-of-string).  But, use patterns typically involve some
 *  relatively long strings with few branches, and we'd rather not
 *  allocate lots of 65-way nodes of which only one way is used.  So,
 *  there is a compact representation for a node with exactly one
 *  child.
 *
 * Looking at the statistics of my own .Xdefaults, I wonder if it might
 *  be worth special-casing 2-way and 3-way branches as well.  The
 *  sort -n | uniq -c output on the number of arms in the NWAYs:
 *	  25 2
 *	  11 3
 *	   3 4
 *	   3 5
 *	   1 7
 *	   1 8
 *	   1 10
 *	   1 36
 *  I'm not sure whether I think the memory win is big enough to be
 *  worth the code complexity.
 *
 * If experience indicates it's worth it, I may include a way of
 *  collapsing a chain of UNIQ nodes into a single node.  They are by
 *  far the most prevalent kind of node.  My .Xdefaults again:
 *	126 LEAF
 *	643 UNIQ
 *	 46 NWAY
 */

typedef enum {
	  QTNT_LEAF = 1, // leaf node
	  QTNT_UNIQ, // exactly one child
	  QTNT_NWAY, // 65-way split
	  } QTNTYPE;

typedef struct qtnode QTNODE;
typedef struct cncstr CNCSTR;

struct cncstr {
  int l; // length
  unsigned char *s; // octets 0..63
  char *t; // text form
  } ;

struct qtnode {
  QTNTYPE type;
  union {
    LX_QUARK leaf; // for QTNT_LEAF
    struct {
      unsigned char val;
      QTNODE *kid;
      } uniq; // for QTNT_UNIQ
    char nway_dummy; // dummy for QTNT_NWAY; see QTNT_NWAY_ARRAY
    } u;
  } ;
// For QTNT_NWAY, array follows:
#define NWAY_OFFSET ROUNDUP(offsetof(QTNODE,u.nway_dummy),__alignof__(QTNODE *))
#define QTNT_NWAY_ARRAY(n) ((QTNODE **)(((char *)(n))+NWAY_OFFSET))

/*
 * This represents an entry within a database.  The representation is a
 *  trace of a walk down the tree.  The walk contains n steps,
 *  represented as v, except that if n<0 the walk has ended.  (a is
 *  just the number of ints v points to; except for the `ended' case,
 *  0<=n<a is an invariant.)
 *
 * Conceptually, we alternate between <which,n> pairs (where `which'
 *  selects `tight' or `loose' and n is an index into v[]) and <val>
 *  booleans (which specify whether we are taking the value or walking
 *  down the kids pointer).  However, <val> is not explicit, because
 *  the last is always true and all others are always false.  We
 *  compact <which,n> into a single int by representing <tight,n> as
 *  simply n and <loose,n> as -(n+1).
 */
struct lx_db_iter {
  LX_DB *db;
  int n;
  int *v;
  int a;
  } ;

/* Database stuff */

/*
 * We represent a database as a tree.  A node in the tree, a DBNODE,
 *  consists of two lists of QUARKs, each with an associated subnode
 *  and/or value.  One list is for tight bindings, the other for loose
 *  bindings.  The lists are kept sorted so they can be searched
 *  (comparatively) fast.  Tree leaves with neither subnode nor value
 *  get pruned.
 */

typedef enum {
	  DBD_KIDS = 1,
	  DBD_VALUE,
	  } DBDTYPE;

typedef struct dbdata DBDATA;
typedef struct dbnode DBNODE;
typedef struct value VALUE;
typedef struct dbdsort_state DBDSORT_STATE;
typedef struct find_thread FIND_THREAD;
typedef struct find_state FIND_STATE;
typedef struct datavec DATAVEC;
typedef struct putq_state PUTQ_STATE;
typedef struct datasource DATASOURCE;
typedef struct ds_ops DS_OPS;
typedef struct ds_priv_string DS_PRIV_STRING;
typedef struct ds_priv_file DS_PRIV_FILE;
typedef struct map_state MAP_STATE;

struct datavec {
  int n;
  int a;
  DBDATA *v;
  } ;
#define EMPTY_DATAVEC ((DATAVEC){.n=0,.a=0,.v=0})

struct find_state {
  int create;
  void (*op)(FIND_THREAD *, void *);
  void *oparg;
  } ;

struct find_thread {
  FIND_THREAD *up;
  DBNODE *n;
  LX_BOUNDQUARK bq;
  DATAVEC *dv;
  int inx;
  } ;

struct lx_db {
  unsigned int flags;
#define DBF_DEFER 0x00000001
  DBNODE *root;
  } ;

struct dbdata {
  LX_QUARK q;
  VALUE *val;
  DBNODE *kids;
  } ;
#define ZDBD ((DBDATA){.q=0,.val=0,.kids=0})

struct dbnode {
  DATAVEC tight;
  DATAVEC loose;
  } ;

struct value {
  unsigned char *b;
  int l;
  } ;

struct dbdsort_state {
  DBDATA *v;
  int *map;
  } ;

struct putq_state {
  int rv;
  const void *val;
  int vallen;
  } ;

struct datasource {
  const DS_OPS *ops;
  void *priv;
  unsigned char *pushb;
  int pusha;
  int pushn;
  } ;

struct ds_ops {
  int (*next)(DATASOURCE *);
  void (*done)(DATASOURCE *);
  } ;
#define DS_OPS_INIT(tag) {\
	&ds_ops_##tag##_next,				\
	&ds_ops_##tag##_done				\
	}

struct ds_priv_string {
  const unsigned char *str;
  int len;
  int inx;
  } ;

struct ds_priv_file {
  int fd;
  unsigned int flags;
#define PRIV_F_EOF 0x00000001
  unsigned char rbuf[512];
  int rfill;
  int rptr;
  } ;

struct map_state {
  int (*cb)(void *, const LX_BOUNDQUARK *, int, const LX_DBVAL *);
  void *cbarg;
  LX_BOUNDQUARK *bqv;
  int bqa;
  int bqn;
  int rv;
  } ;

// Current size of qstr.
// aquarks is allocated size, nquarks live size.
static int aquarks = 0;
static int nquarks = 0;
// Quark-to-string table.
// Stringless quarks (lx_new_quark) have s=0 t=0 l=-1 here.
static CNCSTR *qstr = 0;

static QTNODE *quarkroot = 0;

#define ROUNDUP(a,b) ((((a) + (b) - 1) / (b)) * (b))

#define H_U(x) (((x)-1)/2)
#define H_L(x) (((x)*2)+1)
#define H_R(x) (((x)+1)*2)

#define NODBVAL ((LX_DBVAL){.s = 0,.l = -1})

#ifdef DEBUG_QUERY

typedef struct indent_priv INDENT_PRIV;
struct indent_priv {
  FILE *inner;
  const char *indent;
  int atnl;
  } ;

static int w_indent(void *pv, const char *s, int l)
{
 INDENT_PRIV *p;
 int i;

 p = pv;
 for (i=0;i<l;i++)
  { if (p->atnl)
     { fputs(p->indent,p->inner);
       p->atnl = 0;
     }
    putc(s[i],p->inner);
    p->atnl = (s[i] == '\n');
  }
 return(l);
}

static int c_indent(void *pv)
{
 free(pv);
 return(0);
}

static FILE *open_indent(FILE *inner, const char *pfx)
{
 INDENT_PRIV *p;
 FILE *f;

 p = malloc(sizeof(INDENT_PRIV));
 f = funopen(p,0,&w_indent,0,&c_indent);
 p->inner = inner;
 p->indent = pfx;
 p->atnl = 1;
 return(f);
}

#endif

static QTNODE *qtnode_nway(void)
{
 QTNODE *n;
 int i;
 QTNODE **p;

 n = malloc(NWAY_OFFSET+((CNC_N+1)*sizeof(QTNODE *)));
 n->type = QTNT_NWAY;
 p = QTNT_NWAY_ARRAY(n);
 for (i=CNC_N;i>=0;i--) p[i] = 0;
 return(n);
}

static QTNODE *qtnode_uniq(int x)
{
 QTNODE *n;

 if (! ((x >= 0) && (x <= CNC_N)))
  { lx_abort();
    return(0);
  }
 n = malloc(sizeof(QTNODE));
 n->type = QTNT_UNIQ;
 n->u.uniq.val = x;
 n->u.uniq.kid = 0;
 return(n);
}

static QTNODE *qtnode_leaf(LX_QUARK q)
{
 QTNODE *n;

 n = malloc(sizeof(QTNODE));
 n->type = QTNT_LEAF;
 n->u.leaf = q;
 return(n);
}

static QTNODE *uniq_to_nway(QTNODE *u)
{
 QTNODE *n;

 n = qtnode_nway();
 if (u->u.uniq.val > CNC_N)
  { lx_abort();
    return(0);
  }
 QTNT_NWAY_ARRAY(n)[u->u.uniq.val] = u->u.uniq.kid;
 free(u);
 return(n);
}

static LX_QUARK newquark(void)
{
 if (nquarks >= aquarks)
  { aquarks += (aquarks >> 1) + 8;
    qstr = realloc(qstr,aquarks*sizeof(*qstr));
  }
 qstr[nquarks] = (CNCSTR){.s=0,.t=0,.l=-1};
 return(nquarks++);
}

static LX_QUARK text_to_quark(const char *s, int l)
{
 unsigned char *b;
 int i;
 unsigned char cnc;
 unsigned char xp1;
 QTNODE *n;
 QTNODE **np;
 int x;
 LX_QUARK q;

 b = malloc(l);
 for (i=l-1;i>=0;i--)
  { cnc = ((const unsigned char *)s)[i];
    if (cnc >= CNC_COUNT) return(LX_ERRQUARK);
    xp1 = cnc_to_xp1[cnc];
    if (! xp1) return(LX_ERRQUARK);
    b[i] = xp1 - 1;
  }
 np = &quarkroot;
 for (i=0;i<=l;i++)
  { x = (i < l) ? b[i] : CNC_N;
    if (x > CNC_N)
     { lx_abort();
       return(LX_ERRQUARK);
     }
    n = *np;
    if (! n)
     { n = qtnode_uniq(x);
       *np = n;
     }
    switch (n->type)
     { case QTNT_UNIQ:
	  if (x == n->u.uniq.val)
	   { np = &n->u.uniq.kid;
	   }
	  else
	   { n = uniq_to_nway(n);
	     *np = n;
       case QTNT_NWAY:
	     np = &QTNT_NWAY_ARRAY(n)[x];
	   }
	  break;
       default:
	  lx_abort();
	  return(LX_ERRQUARK);
	  break;
     }
  }
 n = *np;
 if (! n)
  { q = newquark();
    qstr[q].l = l;
    qstr[q].s = b;
    qstr[q].t = malloc(l+1);
    bcopy(s,qstr[q].t,l);
    qstr[q].t[l] = '\0';
    n = qtnode_leaf(q);
    *np = n;
    b = 0;
  }
 if (n->type != QTNT_LEAF)
  { lx_abort();
    return(LX_ERRQUARK);
  }
 q = n->u.leaf;
 free(b);
 return(q);
}

static void free_dbnode(DBNODE *); // forward

static void free_value(VALUE *v)
{
 if (v)
  { free(v->b);
    free(v);
  }
}

static void free_dbdata_sub(DBDATA *d)
{
 free_value(d->val);
 free_dbnode(d->kids);
}

static void free_dbvec(DATAVEC *v)
{
 int i;

 if (! v) return;
 for (i=v->n-1;i>=0;i--) free_dbdata_sub(v->v+i);
 free(v->v);
}

static void free_dbnode(DBNODE *n)
{
 if (! n) return;
 free_dbvec(&n->tight);
 free_dbvec(&n->loose);
 free(n);
}

LX_QUARK lx_new_quark(void)
{
 return(newquark());
}

LX_QUARK lx_quark_for_string(const char *s, int l)
{
 return(text_to_quark(s,(l==-1)?strlen(s):l));
}

const char *lx_string_for_quark(LX_QUARK q)
{
 if (q >= nquarks) return(0);
 return(qstr[q].t);
}

int lx_rm_bq_string(const char *sarg, int slen, LX_BOUNDQUARK *bqv, int bqn)
{
 const unsigned char *s;
 int o;
 int n;
 LX_BOUNDQUARK bq;
 int q0;

 if (slen == -1) slen = strlen(sarg);
 if (slen < 0) return(-1);
 s = (const void *)sarg;
 o = 0;
 n = 0;
 while (o < slen)
  { if ((s[o] != '.') && (s[o] != '*') && (n > 0)) return(-1);
    bq.b = LX_BIND_TIGHT;
    while <"binding"> (1)
     { if (o >= slen) return(-1);
       switch (s[o])
	{ case '.':
	     break;
	  case '*':
	     bq.b = LX_BIND_LOOSE;
	     break;
	  default:
	     break <"binding">;
	}
       o ++;
     }
    if ((s[o] >= CNC_COUNT) || !cnc_to_xp1[s[o]]) return(-1);
    q0 = o;
    while ((o < slen) && (s[o] < CNC_COUNT) && cnc_to_xp1[s[o]]) o ++;
    bq.q = text_to_quark(s+q0,o-q0);
    if (bq.q == LX_ERRQUARK)
     { lx_abort();
       return(-1);
     }
    if (n < bqn) bqv[n] = bq;
    n ++;
  }
 return(n);
}

int lx_rm_q_string(const char *sarg, int slen, LX_QUARK *qv, int qn)
{
 const unsigned char *s;
 int o;
 int n;
 LX_QUARK q;
 int q0;

 if (slen == -1) slen = strlen(sarg);
 if (slen < 0) return(-1);
 s = (const void *)sarg;
 o = 0;
 n = 0;
 while (o < slen)
  { if (s[o] == '.')
     { o ++;
       if (o >= slen) return(-1);
     }
    else
     { if (n > 0) return(-1);
     }
    if ((s[o] >= CNC_COUNT) || !cnc_to_xp1[s[o]]) return(-1);
    q0 = o;
    while ((o < slen) && (s[o] < CNC_COUNT) && cnc_to_xp1[s[o]]) o ++;
    q = text_to_quark(s+q0,o-q0);
    if (q == LX_ERRQUARK)
     { lx_abort();
       return(-1);
     }
    if (n < qn) qv[n] = q;
    n ++;
  }
 return(n);
}

LX_DB *lx_db_new(void)
{
 LX_DB *db;
 DBNODE *n;

 n = malloc(sizeof(DBNODE));
 n->loose = EMPTY_DATAVEC;
 n->tight = EMPTY_DATAVEC;
 db = malloc(sizeof(LX_DB));
 db->flags = 0;
 db->root = n;
 return(db);
}

void lx_db_done(LX_DB *db)
{
 if (! db) return;
 free_dbnode(db->root);
 free(db);
}

static void find_entry_(DBNODE *node, FIND_THREAD *up, const LX_BOUNDQUARK *bqv, int nbq, FIND_STATE *state)
{
 int h;
 int m;
 int l;
 FIND_THREAD thread;
 DBNODE *n;

 if (nbq < 1)
  { lx_abort();
    return;
  }
 thread.up = up;
 thread.n = node;
 thread.bq = bqv[0];
 switch (thread.bq.b)
  { case LX_BIND_TIGHT:
       thread.dv = &node->tight;
       break;
    case LX_BIND_LOOSE:
       thread.dv = &node->loose;
       break;
    default:
       lx_abort();
       return;
       break;
  }
 l = -1;
 h = thread.dv->n;
 while (h-l > 1)
  { m = (h + l) / 2;
    if (thread.dv->v[m].q <= thread.bq.q) l = m;
    if (thread.dv->v[m].q >= thread.bq.q) h = m;
  }
 if (h != l)
  { if (! state->create) return;
    if (thread.dv->n+1 > thread.dv->a)
     { thread.dv->a = thread.dv->n + 8;
       thread.dv->v = realloc(thread.dv->v,thread.dv->a*sizeof(*thread.dv->v));
     }
    if (h < thread.dv->n) bcopy(thread.dv->v+h,thread.dv->v+h+1,(thread.dv->n-h)*sizeof(*thread.dv->v));
    thread.dv->v[h] = (DBDATA){.q=thread.bq.q,.val=0,.kids=0};
    thread.dv->n ++;
  }
 thread.inx = h;
 if (nbq < 2)
  { (*state->op)(&thread,state->oparg);
  }
 else
  { n = thread.dv->v[thread.inx].kids;
    if (! n)
     { if (! state->create) return;
       n = malloc(sizeof(DBNODE));
       n->tight = EMPTY_DATAVEC;
       n->loose = EMPTY_DATAVEC;
       thread.dv->v[thread.inx].kids = n;
     }
    find_entry_(n,&thread,bqv+1,nbq-1,state);
  }
}

static void find_entry(DBNODE *node, const LX_BOUNDQUARK *bqv, int nbq, int create, void (*op)(FIND_THREAD *, void *), void *oparg)
{
 FIND_STATE state;

 state.create = create;
 state.op = op;
 state.oparg = oparg;
 find_entry_(node,0,bqv,nbq,&state);
}

static int emptyleaf(DBDATA *dd)
{
 return(!dd->val&&!dd->kids);
}

static void putq_delete(FIND_THREAD *t, void *sp)
{
 DBDATA *dd;

 dd = t->dv->v + t->inx;
 if (dd->val)
  { ((PUTQ_STATE *)sp)->rv = 1;
    free_value(dd->val);
    dd->val = 0;
    while (emptyleaf(t->dv->v+t->inx))
     { if (t->inx < t->dv->n-1) bcopy(t->dv->v+t->inx+1,t->dv->v+t->inx,(t->dv->n-1-t->inx)*sizeof(DBDATA));
       t->dv->n --;
       if (! t->dv->n)
	{ free(t->dv->v);
	  t->dv->a = 0;
	  t->dv->v = 0;
	}
       if (t->n->tight.n || t->n->loose.n) break;
       if (t->up)
	{ if (t->up->dv->v[t->up->inx].kids != t->n)
	   { lx_abort();
	     return;
	   }
	  free_dbnode(t->n);
	  t = t->up;
	  t->dv->v[t->inx].kids = 0;
	}
       else
	{ break;
	}
     }
  }
}

static void putq_probe(FIND_THREAD *t __attribute__((__unused__)), void *sp)
{
 ((PUTQ_STATE *)sp)->rv = 1;
}

static void putq_set_doit(DBDATA *dd, const void *data, int len)
{
 free_value(dd->val);
 dd->val = malloc(sizeof(VALUE));
 dd->val->b = malloc(len+1);
 bcopy(data,dd->val->b,len);
 dd->val->b[len] = '\0';
 dd->val->l = len;
}

static void putq_set_notifx(FIND_THREAD *t, void *sp)
{
 PUTQ_STATE *s;
 DBDATA *dd;

 dd = t->dv->v + t->inx;
 if (dd->val) return;
 s = sp;
 putq_set_doit(dd,s->val,s->vallen);
}

static void putq_set_notifnx(FIND_THREAD *t, void *sp)
{
 PUTQ_STATE *s;
 DBDATA *dd;

 dd = t->dv->v + t->inx;
 if (! dd->val) return;
 s = sp;
 putq_set_doit(dd,s->val,s->vallen);
}

static void putq_set_always(FIND_THREAD *t, void *sp)
{
 PUTQ_STATE *s;
 DBDATA *dd;

 dd = t->dv->v + t->inx;
 s = sp;
 putq_set_doit(dd,s->val,s->vallen);
}

int lx_db_putq(LX_DB *db, const LX_BOUNDQUARK *bqv, int nbq, const void *val, int vlen, unsigned int flags)
{
 PUTQ_STATE s;

 if ((nbq < 1) || (vlen < 0)) return(-1);
 s.rv = 0;
 if (flags == LX_DB_PUTQ_DELETE)
  { find_entry(db->root,bqv,nbq,0,&putq_delete,&s);
  }
 else if (flags == LX_DB_PUTQ_PROBE)
  { find_entry(db->root,bqv,nbq,0,&putq_probe,&s);
  }
 else if (flags & ~(LX_DB_PUTQ_NOTIFX|LX_DB_PUTQ_NOTIFNX))
  { return(-1);
  }
 else
  { s.val = val;
    s.vallen = vlen;
    switch (flags & (LX_DB_PUTQ_NOTIFX|LX_DB_PUTQ_NOTIFNX))
     { case 0:
	  find_entry(db->root,bqv,nbq,1,&putq_set_always,&s);
	  break;
       case LX_DB_PUTQ_NOTIFX:
	  find_entry(db->root,bqv,nbq,1,&putq_set_notifx,&s);
	  break;
       case LX_DB_PUTQ_NOTIFNX:
	  find_entry(db->root,bqv,nbq,0,&putq_set_notifnx,&s);
	  break;
       case LX_DB_PUTQ_NOTIFX | LX_DB_PUTQ_NOTIFNX:
	  break;
     }
  }
 return(s.rv);
}

static void getq_found(FIND_THREAD *t, void *vp)
{
 DBDATA *dd;

 dd = t->dv->v + t->inx;
 if (dd->val) *((LX_DBVAL *)vp) = (LX_DBVAL){.s=dd->val->b,.l=dd->val->l};
}

LX_DBVAL lx_db_getq(LX_DB *db, const LX_BOUNDQUARK *bqv, int nbq)
{
 LX_DBVAL v;

 v.s = 0;
 v.l = -1;
 find_entry(db->root,bqv,nbq,0,&getq_found,&v);
 return(v);
}

static DATASOURCE *ds_new(const DS_OPS *ops, void *priv)
{
 DATASOURCE *ds;

 ds = malloc(sizeof(DATASOURCE));
 ds->ops = ops;
 ds->priv = priv;
 ds->pushb = 0;
 ds->pusha = 0;
 ds->pushn = 0;
 return(ds);
}

static void ds_done(DATASOURCE *ds)
{
 (*ds->ops->done)(ds);
 free(ds);
}

static int ds_next(DATASOURCE *ds)
{
 if (ds->pushn > 0) return(ds->pushb[--ds->pushn]);
 return((*ds->ops->next)(ds));
}

static void ds_pushback(DATASOURCE *ds, int c)
{
 if (c < 0)
  { lx_abort();
    return;
  }
 if (ds->pushn >= ds->pusha)
  { ds->pusha += 8;
    ds->pushb = realloc(ds->pushb,ds->pusha);
  }
 ds->pushb[ds->pushn++] = c;
}

static LX_DB *ds_load_db(DATASOURCE *ds, unsigned int flags, va_list ap)
{
 int c;
 int ares;
 int nres;
 LX_BOUNDQUARK *res;
 int aval;
 int nval;
 unsigned char *val;
 LX_BOUNDQUARK bq;
 int esc;
 unsigned char v;
 LX_DB *db;
 unsigned char *qbb;
 int qba;
 int qbn;
 int *ecp;
 int ec;
#define NEXT() do { c = ds_next(ds); } while (0)

 if (flags & ~(LX_DB_IGNORE_ERR|LX_DB_ERR_COUNT)) return(0);
 ecp = (flags & LX_DB_ERR_COUNT) ? va_arg(ap,int *) : 0;
 ec = 0;
 db = lx_db_new();
 ares = 0;
 res = 0;
 aval = 0;
 val = 0;
 qbb = 0;
 qba = 0;
 qbn = 0;
 NEXT();
 do <"ret">
  { do <"err">
#define ERR() do { ec ++; if (! (flags & LX_DB_IGNORE_ERR)) break <"err">; } while (0)
     { while <"read"> (1)
	{ do <"flush line">
	   { while ((c >= 0) && isspace(c)) NEXT();
	     if (c == '!') break <"flush line">;
	     nres = 0;
	     if (c < 0) break <"read">;
	     while <"name"> (1)
	      { while ((c >= 0) && isspace(c)) NEXT();
		if (c < 0)
		 { // Partial resource spec at end
		   ERR();
		   break <"read">;
		 }
		if (c == ':') break <"name">;
		if ((c != '.') && (c != '*') && (nres > 0))
		 { // Invalid component delimiter
		   ERR();
		   break <"flush line">;
		 }
		bq.b = LX_BIND_TIGHT;
		while <"binding"> (c >= 0)
		 { switch (c)
		    { case '.':
			 break;
		      case '*':
			 bq.b = LX_BIND_LOOSE;
			 break;
		      default:
			 break <"binding">;
		    }
		   NEXT();
		 }
		if (c < 0)
		 { // Partial resource spec at end
		   ERR();
		   break <"read">;
		 }
		if ((c >= CNC_COUNT) || !cnc_to_xp1[c])
		 { // Invalid component character
		   ERR();
		   break <"flush line">;
		 }
		qbn = 0;
		while ((c >= 0) && (c < CNC_COUNT) && cnc_to_xp1[c])
		 { if (qbn >= qba)
		    { qba = qbn + 8;
		      qbb = realloc(qbb,qba);
		    }
		   qbb[qbn++] = c;
		   NEXT();
		 }
		bq.q = text_to_quark(qbb,qbn);
		if (bq.q == LX_ERRQUARK)
		 { lx_abort();
		   return(0);
		 }
		if (nres >= ares)
		 { ares += 8;
		   res = realloc(res,ares*sizeof(*res));
		 }
		res[nres++] = bq;
	      }
	     if (c != ':')
	      { // including c < 0
		lx_abort();
		return(0);
	      }
	     if (nres < 1)
	      { // No name before colon
		ERR();
		break <"flush line">;
	      }
	     do NEXT(); while ((c >= 0) && (c != '\n') && isspace(c));
	     nval = 0;
	     esc = 0;
	     while <"value"> ((c >= 0) && (c != '\n'))
	      { do <"accum">
		 { switch <"char"> (esc)
		    { case 0:
			 if (c == '\\')
			  { esc = 1;
			  }
			 else
			  { v = c;
			    break <"accum">;
			  }
			 break;
		      case 1:
			 v = c;
			 switch (c)
			  { case 'a': v = '\a'; break <"accum">;
			    case 'b': v = '\b'; break <"accum">;
			    case 'e': v = '\e'; break <"accum">;
			    case 'f': v = '\f'; break <"accum">;
			    case 'n': v = '\n'; break <"accum">;
			    case 'r': v = '\r'; break <"accum">;
			    case 't': v = '\t'; break <"accum">;
			    case 'v': v = '\v'; break <"accum">;
			    case 'x':
			       v = 0;
			       esc = 5;
			       break <"char">;
			    case '0': v = 0;   if (0) {
			    case '1': v = 1; } if (0) {
			    case '2': v = 2; } if (0) {
			    case '3': v = 3; } if (0) {
			    case '4': v = 4; } if (0) {
			    case '5': v = 5; } if (0) {
			    case '6': v = 6; } if (0) {
			    case '7': v = 7; }
			       esc = 2;
			       break <"char">;
			    // Two unusual escapes....
			    case 's': case ' ':
			       esc = 0;
			       v = ' ';
			       break <"accum">;
			    case '/': // \/ is dropped, as an escape sequence terminator
			       esc = 0;
			       break <"char">;
			    case '\n':
			       // \ at end of line
			       ERR();
			       break <"flush line">;
			    default:
			       // Unrecognized escape - ignore the backslash
			       break <"accum">;
			  }
			 break;
		      case 2: case 3: case 4:
			 switch (c)
			  { case '0': c = 0;   if (0) {
			    case '1': c = 1; } if (0) {
			    case '2': c = 2; } if (0) {
			    case '3': c = 3; } if (0) {
			    case '4': c = 4; } if (0) {
			    case '5': c = 5; } if (0) {
			    case '6': c = 6; } if (0) {
			    case '7': c = 7; }
			       esc ++;
			       v = (v << 3) | c;
			       if (esc > 4)
				{ esc = 0;
				  break <"accum">;
				}
			       break;
			    default:
			       esc = 0;
			       ds_pushback(ds,c);
			       break <"accum">;
			  }
			 break;
		      case 5:
			 switch (c)
			  { case '0': c = 0;   if (0) {
			    case '1': c = 1; } if (0) {
			    case '2': c = 2; } if (0) {
			    case '3': c = 3; } if (0) {
			    case '4': c = 4; } if (0) {
			    case '5': c = 5; } if (0) {
			    case '6': c = 6; } if (0) {
			    case '7': c = 7; } if (0) {
			    case '8': c = 8; } if (0) {
			    case '9': c = 9; } if (0) {
			    case 'a': case 'A': c = 10; } if (0) {
			    case 'b': case 'B': c = 11; } if (0) {
			    case 'c': case 'C': c = 12; } if (0) {
			    case 'd': case 'D': c = 13; } if (0) {
			    case 'e': case 'E': c = 14; } if (0) {
			    case 'f': case 'F': c = 15; }
			       v = (v << 4) | c;
			       break;
			    default:
			       esc = 0;
			       ds_pushback(ds,c);
			       break <"accum">;
			  }
			 break;
		    }
		   NEXT();
		   continue <"value">;
		 } while (0);
		NEXT();
		if (nval >= aval)
		 { aval += 8;
		   val = realloc(val,aval);
		 }
		val[nval++] = v;
	      }
	     lx_db_putq(db,res,nres,val,nval,0);
// dump_resource(res,nres,val,nval,stdout);
// db_add(db,res,nres,val,nval);
// printf("DB now:\n");
// dump_db(db);
	     continue <"read">;
	   } while (0);
	  while ((c >= 0) && (c != '\n')) NEXT();
	  if (c >= 0) NEXT();
	}
       break <"ret">;
     } while (0);
    lx_db_done(db);
    db = 0;
  } while (0);
 free(res);
 free(val);
 free(qbb);
 return(db);
#undef NEXT
}

static int ds_ops_string_next(DATASOURCE *ds)
{
 DS_PRIV_STRING *p;

 p = ds->priv;
 if (p->inx < p->len) return(p->str[p->inx++]);
 return(-1);
}

static void ds_ops_string_done(DATASOURCE *ds)
{
 DS_PRIV_STRING *p;

 p = ds->priv;
 free(p);
}

static const DS_OPS ds_ops_string = DS_OPS_INIT(string);

static int ds_ops_file_next(DATASOURCE *ds)
{
 DS_PRIV_FILE *p;

 p = ds->priv;
 if (p->flags & PRIV_F_EOF) return(-1);
 if (p->rptr >= p->rfill)
  { p->rfill = read(p->fd,&p->rbuf[0],sizeof(p->rbuf));
    if (p->rfill <= 0)
     { p->flags |= PRIV_F_EOF;
       return(-1);
     }
    p->rptr = 0;
  }
 return(p->rbuf[p->rptr++]);
}

static void ds_ops_file_done(DATASOURCE *ds)
{
 DS_PRIV_FILE *p;

 p = ds->priv;
 close(p->fd);
 free(p);
}

static const DS_OPS ds_ops_file = DS_OPS_INIT(file);

static DATASOURCE *ds_init_string(const char *str, int len)
{
 DS_PRIV_STRING *ps;

 ps = malloc(sizeof(DS_PRIV_STRING));
 ps->str = (const void *)str;
 ps->len = len;
 ps->inx = 0;
 return(ds_new(&ds_ops_string,ps));
}

static DATASOURCE *ds_init_file(const char *path)
{
 int fd;
 DS_PRIV_FILE *pf;

 fd = open(path,O_RDONLY,0);
 if (fd < 0) return(0);
 pf = malloc(sizeof(DS_PRIV_FILE));
 pf->fd = fd;
 pf->flags = 0;
 pf->rfill = 0;
 pf->rptr = 0;
 return(ds_new(&ds_ops_file,pf));
}

LX_DB *lx_db_from_string(const char *str, int len, unsigned int flags, ...)
{
 DATASOURCE *ds;
 va_list ap;
 LX_DB *rv;

 ds = ds_init_string(str,len);
 if (! ds)
  { /*
     * We can get away with this only because LX_DB_ERR_COUNT is
     *  currently the only flag bit taking another arg.
     */
    if (flags & LX_DB_ERR_COUNT)
     { int *ecp;
       va_start(ap,flags);
       ecp = va_arg(ap,int *);
       va_end(ap);
       *ecp = 1;
     }
    return(0);
  }
 va_start(ap,flags);
 rv = ds_load_db(ds,flags,ap);
 va_end(ap);
 ds_done(ds);
 return(rv);
}

LX_DB *lx_db_from_file(const char *path, unsigned int flags, ...)
{
 DATASOURCE *ds;
 va_list ap;
 LX_DB *rv;

 ds = ds_init_file(path);
 if (! ds)
  { /*
     * We can get away with this only because LX_DB_ERR_COUNT is
     *  currently the only flag bit taking another arg.
     */
    if (flags & LX_DB_ERR_COUNT)
     { int *ecp;
       va_start(ap,flags);
       ecp = va_arg(ap,int *);
       va_end(ap);
       *ecp = 1;
     }
    return(0);
  }
 va_start(ap,flags);
 rv = ds_load_db(ds,flags,ap);
 va_end(ap);
 ds_done(ds);
 return(rv);
}

static void map_walk_dbnode(DBNODE *, MAP_STATE *); // forward

static void map_walk_callback(VALUE *v, MAP_STATE *ms)
{
 LX_DBVAL dbv;
 int r;

 dbv.s = (void *)v->b;
 dbv.l = v->l;
 r = (ms->cb)(ms->cbarg,ms->bqv,ms->bqn,&dbv);
 if (r < 0) ms->rv = r; else ms->rv += r;
}

static void map_walk_datavec(DATAVEC *dv, LX_BINDING b, MAP_STATE *ms)
{
 int i;
 DBDATA *dd;
 LX_BOUNDQUARK *bq;

 if (ms->bqn >= ms->bqa)
  { ms->bqa = ms->bqn + 8;
    ms->bqv = realloc(ms->bqv,ms->bqa*sizeof(*ms->bqv));
  }
 bq = &ms->bqv[ms->bqn++];
 for (i=dv->n-1;i>=0;i--)
  { dd = dv->v + i;
    ms->bqv[ms->bqn-1] = (LX_BOUNDQUARK){.b=b,.q=dd->q};
    if (dd->val) map_walk_callback(dd->val,ms);
    if (ms->rv < 0) return;
    if (dd->kids) map_walk_dbnode(dd->kids,ms);
    if (ms->rv < 0) return;
  }
 ms->bqn --;
}

static void map_walk_dbnode(DBNODE *n, MAP_STATE *ms)
{
 map_walk_datavec(&n->tight,LX_BIND_TIGHT,ms);
 if (ms->rv < 0) return;
 map_walk_datavec(&n->loose,LX_BIND_LOOSE,ms);
}

int lx_db_map(LX_DB *db, int (*cb)(void *, const LX_BOUNDQUARK *, int, const LX_DBVAL *), void *cbarg)
{
 MAP_STATE ms;

 ms.cb = cb;
 ms.cbarg = cbarg;
 ms.bqv = 0;
 ms.bqa = 0;
 ms.bqn = 0;
 ms.rv = 0;
 map_walk_dbnode(db->root,&ms);
 free(ms.bqv);
 return(ms.rv);
}

static void merge_dvs(DATAVEC *into, DATAVEC *from)
{
 int n;
 int fn;
 int in;
 DBDATA *fv;
 DBDATA *iv;
 DBDATA *nv;
 int fi;
 int ii;
 int ni;
 DBDATA *t;

 fn = from->n;
 if (fn < 1) return;
 in = into->n;
 if (in < 1)
  { free(into->v);
    *into = *from;
    *from = EMPTY_DATAVEC;
    return;
  }
 fv = from->v;
 iv = into->v;
 fi = 0;
 ii = 0;
 n = 0;
 while (1)
  { if (ii < in)
     { if (fi < fn)
	{      if (iv[ii].q < fv[fi].q) ii ++;
	  else if (fv[fi].q < iv[ii].q) fi ++;
	  else                          ii++, fi++;
	  n ++;
	}
       else
	{ ii ++;
	  n ++;
	}
     }
    else
     { if (fi < fn)
	{ fi ++;
	  n ++;
	}
       else
	{ break;
	}
     }
  }
 nv = malloc(n*sizeof(DBDATA));
 ni = n - 1;
 ii = in - 1;
 fi = fn - 1;
 while <"copying"> (1)
  { do <"usef">
     { do <"usei">
	{ if (ii >= 0)
	   { if (fi >= 0)
	      { if (iv[ii].q > fv[fi].q) break <"usei">;
		if (fv[fi].q > iv[ii].q) break <"usef">;
		if (ni < 0)
		 { lx_abort();
		   return;
		 }
    		t = &nv[ni--];
		*t = iv[ii];
		if (fv[fi].val) t->val = fv[fi].val;
		merge_dvs(&t->kids->tight,&fv[fi].kids->tight);
		merge_dvs(&t->kids->loose,&fv[fi].kids->loose);
		ii --;
		fi --;
		continue <"copying">;
	      }
	     else
	      { break <"usei">;
	      }
	   }
	  else
	   { if (fi >= 0)
	      { break <"usef">;
	      }
	     else
	      { break <"copying">;
	      }
	   }
	} while (0);
       if (ni < 0)
	{ lx_abort();
	  return;
	}
       nv[ni--] = iv[ii--];
       continue <"copying">;
     } while (0);
    if (ni < 0)
     { lx_abort();
       return;
     }
    nv[ni--] = fv[fi--];
  }
 if ((ni != -1) || (ii != -1) || (fi != -1))
  { lx_abort();
    return;
  }
 free(from->v);
 *from = EMPTY_DATAVEC;
 free(into->v);
 into->n = n;
 into->a = n;
 into->v = nv;
}

void lx_db_merge(LX_DB *t, LX_DB *f)
{
 merge_dvs(&t->root->tight,&f->root->tight);
 merge_dvs(&t->root->loose,&f->root->loose);
}

static int binsearch_datavec(DATAVEC *dv, LX_QUARK q)
{
 int l;
 int m;
 int h;

 l = -1;
 h = dv->n;
 while (h-l > 1)
  { m = (h + l) / 2;
    if (dv->v[m].q <= q) l = m;
    if (dv->v[m].q >= q) h = m;
  }
 return((l==h)?l:-1);
}

#ifdef DEBUG_QUERY
static void print_value(VALUE *v, FILE *to)
{
 int i;
 unsigned char ch;

 fprintf(to,"[%p:%d@%p]\"",(void *)v,v->l,(void *)v->b);
 for (i=0;i<v->l;i++)
  { ch = v->b[i];
    switch (ch)
     { case '\a': fprintf(to,"\\a"); break;
       case '\b': fprintf(to,"\\b"); break;
       case '\e': fprintf(to,"\\e"); break;
       case '\f': fprintf(to,"\\f"); break;
       case '\n': fprintf(to,"\\n"); break;
       case '\r': fprintf(to,"\\r"); break;
       case '\t': fprintf(to,"\\t"); break;
       case '\v': fprintf(to,"\\v"); break;
       case '\\': fprintf(to,"\\\\"); break;
       case '"': fprintf(to,"\\\""); break;
       default:
	  if ((ch < 32) || ((ch > 126) && (ch < 160)))
	   { if ((i+1 < v->l) && isdigit(v->b[i+1]))
	      { fprintf(to,"\\%03o",ch);
	      }
	     else
	      { fprintf(to,"\\%o",ch);
	      }
	   }
	  else
	   { putc(ch,to);
	   }
	  break;
     }
  }
 putc('"',to);
}
#endif

static LX_DBVAL dbnode_query(DBNODE *n, const LX_QUARK *nqv, const LX_QUARK *cqv, int qn, int looseonly
#ifdef DEBUG_QUERY
	, FILE *to
#define RECURSE_F ,f
#else
#define RECURSE_F
#endif
	)
{
#ifdef DEBUG_QUERY
 FILE *f;
#endif
 int x;
 DATAVEC *dv;
 VALUE *v;
 LX_DBVAL rv;
 DBNODE *fn;

#ifdef DEBUG_QUERY
  { int i;
    fprintf(to,"dbnode_query: node %p<%d,%d> name ",(void *)n,n->tight.n,n->loose.n);
    for (i=0;i<qn;i++)
     { fprintf(to,"%s[%u",i?".":"",(unsigned int)nqv[i]);
       if ((nqv[i] > nquarks) || !qstr[nqv[i]].t) fprintf(to,"?]"); else fprintf(to,"]%s",qstr[nqv[i]].t);
     }
    fprintf(to," class ");
    for (i=0;i<qn;i++)
     { fprintf(to,"%s[%u",i?".":"",(unsigned int)cqv[i]);
       if ((cqv[i] > nquarks) || !qstr[cqv[i]].t) fprintf(to,"?]"); else fprintf(to,"]%s",qstr[cqv[i]].t);
     }
    fprintf(to,"\n");
    f = open_indent(to,"  ");
  }
// Using old macro varargs syntax because 1.4T
#define DEBUG_PRINTF(args...) fprintf(f,args)
#define DEBUG_CLOSE() fclose(f)
#else
#define DEBUG_PRINTF(args...) do ; while (0)
#define DEBUG_CLOSE() do ; while (0)
#endif
 if (qn < 1)
  { DEBUG_PRINTF("no quark lists, failing\n");
    DEBUG_CLOSE();
    return(NODBVAL);
  }
 if (! n)
  { DEBUG_PRINTF("no DBNODE, failing\n");
    DEBUG_CLOSE();
    return(NODBVAL);
  }
 do <"leaf">
  { if (! looseonly)
     { dv = &n->tight;
#define BLOCK(qv,bind,kind) do\
	{ x = binsearch_datavec(dv,qv[0]);			\
	  if (x >= 0)						\
	   { DEBUG_PRINTF("found %s %s\n",#bind,#kind);		\
	     if (qn < 2)					\
	      { DEBUG_PRINTF("end of quarks\n");		\
		break <"leaf">;					\
	      }							\
	     fn = dv->v[x].kids;				\
	     if (fn)						\
	      { DEBUG_PRINTF("recursing\n");			\
		rv = dbnode_query(fn,nqv+1,cqv+1,qn-1,0 RECURSE_F);\
		if (rv.l >= 0)					\
		 { DEBUG_PRINTF("recursion returned success\n");\
		   DEBUG_CLOSE();				\
		   return(rv);					\
		 }						\
	      }							\
	     else						\
	      { DEBUG_PRINTF("no kids\n");			\
	      }							\
	   }							\
	  else							\
	   { DEBUG_PRINTF("didn't find %s %s\n",#bind,#kind);	\
	   }							\
	} while (0)
       BLOCK(nqv,tight,name);
       BLOCK(cqv,tight,class);
     }
    else
     { DEBUG_PRINTF("skipping tight, looseonly set\n");
     }
    dv = &n->loose;
    BLOCK(nqv,loose,name);
    BLOCK(cqv,loose,class);
    if (n->loose.n < 1)
     { DEBUG_PRINTF("no loose subtree, failing\n");
       DEBUG_CLOSE();
       return(NODBVAL);
     }
    if (qn < 2)
     { DEBUG_PRINTF("end of quarks, failing\n");
       DEBUG_CLOSE();
       return(NODBVAL);
     }
    DEBUG_PRINTF("skipping head and recursing\n");
    rv = dbnode_query(n,nqv+1,cqv+1,qn-1,1 RECURSE_F);
    DEBUG_CLOSE();
    return(rv);
  } while (0);
 v = dv->v[x].val;
#ifdef DEBUG_QUERY
 if (v)
  { fprintf(f,"found value ");
    print_value(v,f);
    fprintf(f,"\n");
  }
 else
  { fprintf(f,"no value\n");
  }
#endif
 DEBUG_CLOSE();
 return(v?(LX_DBVAL){.s=v->b,.l=v->l}:NODBVAL);
#undef BLOCK
#undef RECURSE_F
#undef DEBUG_PRINTF
#undef DEBUG_CLOSE
}

LX_DBVAL lx_db_query(LX_DB *db, const LX_QUARK *nqv, const LX_QUARK *cqv, int qn)
{
 return(dbnode_query(db->root,nqv,cqv,qn,0
#ifdef DEBUG_QUERY
	,stdout
#endif
				));
}

static void set_i_vx(LX_DB_ITER *i, int x, int v)
{
 if (x >= i->a)
  { i->a = x + 1;
    i->v = realloc(i->v,i->a*sizeof(*i->v));
  }
 i->v[x] = v;
}

LX_DB_ITER *lx_db_iter_start(LX_DB *db)
{
 LX_DB_ITER *i;
 DBNODE *n;
 int x;
 DBDATA *dbd;

 i = malloc(sizeof(LX_DB_ITER));
 i->db = db;
 i->n = 0;
 i->v = 0;
 i->a = 0;
 n = db->root;
 if (!n->tight.n && !n->loose.n)
  { // empty db
    i->n = -1;
    return(i);
  }
 x = 0;
 while (1)
  { if (n->tight.n)
     { dbd = &n->tight.v[0];
       set_i_vx(i,x,0);
     }
    else if (n->loose.n)
     { dbd = &n->loose.v[0];
       set_i_vx(i,x,-1);
     }
    x ++;
    if (dbd->val)
     { i->n = x;
       return(i);
     }
    n = dbd->kids;
    if (! n)
     { // impossible: dbd has neither value nor kids
       lx_abort();
       return(0);
     }
  }
}

static void iter_next(LX_DB_ITER *i, int x, DBDATA *dbd)
{
 if (x == i->n-1)
  { if (dbd->kids)
     {
     }
  }
}

static void iter_advance(LX_DB_ITER *i)
{
 DBDATA fakedbd;

 fakedbd.kids = i->db->root;
 iter_next(i,0,&fakedbd);
}

LX_DB_ITERSTAT lx_db_iter_next(LX_DB_ITER *i, LX_BOUNDQUARK *bqv, int *nbqp, LX_DBVAL *val)
{
 int nbq;
 int j;
 int e;
 DBDATA fakedbd;
 DBDATA *dbd;
 DATAVEC *dv;
 int dvx;

 if (i->n < 0) return(LX_DB_ITER_DONE);
 do <"fakedone">
  { if (i->n == 0) break <"fakedone">;
    nbq = *nbqp;
    if (nbq < 0)
     { iter_advance(i);
       return(LX_DB_ITER_SKIP);
     }
    if (i->n > nbq)
     { *nbqp = i->n;
       return(LX_DB_ITER_OVERFLOW);
     }
    dbd = &fakedbd;
    fakedbd.kids = i->db->root;
    fakedbd.val = 0;
    e = i->n - 1;
    for (j=0;j<e;j++)
     { if (! dbd->kids) break <"fakedone">;
       if (i->v[j] < 0)
	{ dv = &dbd->kids->loose;
	  dvx = - i->v[j] - 1;
	  bqv[j].b = LX_BIND_LOOSE;
	}
       else
	{ dv = &dbd->kids->tight;
	  dvx = i->v[j];
	  bqv[j].b = LX_BIND_TIGHT;
	}
       if ((dvx < 0) || (dvx >= dv->n)) break <"fakedone">;
       dbd = &dv->v[dvx];
       bqv[j].q = dbd->q;
     }
    if (dbd == &fakedbd) break <"fakedone">;
    if (! dbd->val) break <"fakedone">;
    *nbqp = i->n;
    val->s = (void *) dbd->val->b;
    val->l = dbd->val->l;
    iter_advance(i);
    return(LX_DB_ITER_NORMAL);
  } while (0);
 lx_abort();
 i->n = -1;
 return(LX_DB_ITER_DONE);
}

void lx_db_iter_done(LX_DB_ITER *i)
{
 free(i->v);
 free(i);
}

#if 0

#include <stdio.h>
#include <ctype.h>
#include <errno.h>
#include <fcntl.h>
#include <stdlib.h>
#include <unistd.h>
#include <strings.h>
#include <sys/mman.h>
#include <sys/stat.h>

extern const char *__progname;

static void check(const char *s, QUARK v)
{
 QUARK q;

 q = string_to_quark(s,0);
 if (q != v) abort();
}

static void print_cncstr(const CNCSTR *s, FILE *to)
{
 int i;
 unsigned char c;

 for (i=0;i<s->l;i++)
  { c = s->s[i];
    if (c >= CNC_N)
     { fprintf(to,"?<%u>",c);
     }
    else
     { putc(x_to_cnc[c],to);
     }
  }
}

static void dumpqtn(QTNODE *n, FILE *to)
{
 FILE *f;
 int i;
 int j;

 if (n == 0)
  { fprintf(to,"nil\n");
    return;
  }
 switch (n->type)
  { case QTNT_LEAF:
       fprintf(to,"LEAF %u ",n->u.leaf);
       if (n->u.leaf >= nquarks)
	{ fprintf(to,"(invalid)");
	}
       else
	{ print_cncstr(qstr+n->u.leaf,to);
	}
       putc('\n',to);
       break;
    case QTNT_UNIQ:
       fprintf(to,"UNIQ %u [",n->u.uniq.val);
       if (n->u.uniq.val > CNC_N)
	{ fprintf(to,"invalid");
	}
       else if (n->u.uniq.val == CNC_N)
	{ fprintf(to,"EOS");
	}
       else
	{ putc(x_to_cnc[n->u.uniq.val],to);
	}
       fprintf(to,"]\n");
       f = open_indent(to,"  ");
       dumpqtn(n->u.uniq.kid,f);
       fclose(f);
       break;
    case QTNT_NWAY:
       j = 0;
       for (i=CNC_N;i>=0;i--) if (QTNT_NWAY_ARRAY(n)[i]) j ++;
       fprintf(to,"NWAY %d\n",j);
       f = open_indent(to,"  ");
       for (i=0;i<CNC_N;i++)
	{ if (QTNT_NWAY_ARRAY(n)[i])
	   { fprintf(f,"[%c]: ",x_to_cnc[i]);
	     dumpqtn(QTNT_NWAY_ARRAY(n)[i],f);
	   }
	}
       if (QTNT_NWAY_ARRAY(n)[CNC_N])
	{ fprintf(f,"[EOS]: ");
	  dumpqtn(QTNT_NWAY_ARRAY(n)[CNC_N],f);
	}
       fclose(f);
       break;
    default:
       fprintf(to,"?type=%d\n",(int)n->type);
       break;
  }
}

static void dump_quarktable(const char *tag)
{
 printf("---- %s\n",tag);
 dumpqtn(quarkroot,stdout);
}

static void check_quarks(void)
{
 QUARK qd[15];

 qd[0] = string_to_quark("Zero",1);
 qd[1] = string_to_quark("One",1);
 qd[2] = string_to_quark("Two",1);
 qd[3] = string_to_quark("Three",1);
 qd[4] = string_to_quark("Four",1);
 qd[5] = string_to_quark("Five",1);
 qd[6] = string_to_quark("Six",1);
 qd[7] = string_to_quark("Seven",1);
 qd[8] = string_to_quark("Eight",1);
 qd[9] = string_to_quark("Nine",1);
 qd[10] = string_to_quark("PrefixOne",1);
 qd[11] = string_to_quark("PrefixTwo",1);
 qd[12] = string_to_quark("Prefix",1);
 qd[13] = string_to_quark("PrefixThree",1);
 dump_quarktable("Quark tree is");
 check("Zero",qd[0]);
 check("One",qd[1]);
 check("Two",qd[2]);
 check("Three",qd[3]);
 check("Four",qd[4]);
 check("Five",qd[5]);
 check("Six",qd[6]);
 check("Seven",qd[7]);
 check("Eight",qd[8]);
 check("Nine",qd[9]);
 check("-",NOQUARK);
 check("----",NOQUARK);
 check("--------",NOQUARK);
 check("ABCD",NOQUARK);
 check("EFGHIJKL",NOQUARK);
 check("M",NOQUARK);
 check("NOPQR",NOQUARK);
 check("STUVWXYZ",NOQUARK);
 check("Z",NOQUARK);
 check("ZZZ",NOQUARK);
 check("k",NOQUARK);
 check("rrr",NOQUARK);
 check("z",NOQUARK);
 check("Prefi",NOQUARK);
 check("PrefixOne",qd[10]);
 check("PrefixTwo",qd[11]);
 check("Prefix",qd[12]);
 check("PrefixThree",qd[13]);
}

static void dump_resource(const BQ *res, int nres, const unsigned char *val, int nval, FILE *to)
{
 int i;
 unsigned char c;

 for (i=0;i<nres;i++)
  { switch (res[i].b)
     { case BIND_TIGHT: putc('.',to); break;
       case BIND_LOOSE: putc('*',to); break;
       default: abort(); break;
     }
    if (res[i].q >= nquarks) abort();
    print_cncstr(qstr+res[i].q,to);
  }
 fprintf(to,": ");
 for (i=0;i<nval;i++)
  { c = val[i];
    switch (c)
     { case '\a': fprintf(to,"\\a"); break;
       case '\b': fprintf(to,"\\b"); break;
       case '\e': fprintf(to,"\\e"); break;
       case '\f': fprintf(to,"\\f"); break;
       case '\n': fprintf(to,"\\n"); break;
       case '\r': fprintf(to,"\\r"); break;
       case '\t': fprintf(to,"\\t"); break;
       case '\v': fprintf(to,"\\v"); break;
       case ' ':
	  if (i == 0)
	   { fprintf(to,"\\ ");
	     break;
	   }
	  // fall through
       default:
	  if ((c < 32) || ((c > 126) && (c < 160)))
	   { if ((i+1 < nval) && (val[i+1] >= '0') && (val[i+1] <= '9'))
	      { fprintf(to,"\\%03o",c);
	      }
	     else
	      { fprintf(to,"\\%o",c);
	      }
	   }
	  else
	   { putc(c,to);
	   }
	  break;
     }
  }
 putc('\n',to);
}

static void db_defer(DB *db)
{
 db->flags |= DBF_DEFER;
}

static void reheap(DBDSORT_STATE *s, int x, int n)
{
 int t;
 int l;
 int r;
 int c;

 while (1)
  { l = H_L(x);
    if (l >= n) break;
    r = H_R(x);
    if ((r >= n) || (s->v[s->map[r]].q <= s->v[s->map[x]].q))
     { if (s->v[s->map[l]].q <= s->v[s->map[x]].q)
	{ break;
	}
       else
	{ c = l;
	}
     }
    else
     { if (s->v[s->map[l]].q <= s->v[s->map[x]].q)
	{ c = r;
	}
       else
	{ c = (s->v[s->map[l]].q > s->v[s->map[r]].q) ? l : r;
	}
     }
    t = s->map[c];
    s->map[c] = s->map[x];
    s->map[x] = t;
    x = c;
  }
}

static void value_free(VALUE *v)
{
 free(v->b);
 free(v);
}

static void dump_dbnode(DBNODE *, FILE *); // forward

static void dump_dbdata_vec(int n, DBDATA *v, FILE *to)
{
 int i;
 DBDATA *d;
 FILE *f;

 for (i=0;i<n;i++)
  { d = v + i;
    fprintf(to,"[%d] %u ",i,d->q);
    if (d->q >= nquarks)
     { fprintf(to,"(invalid)");
     }
    else
     { fprintf(to,"[");
       print_cncstr(qstr+d->q,to);
       fprintf(to,"]");
     }
    if (d->val)
     { fprintf(to," val=");
       print_value(d->val,to);
     }
    if (d->kids)
     { fprintf(to," kids %p:\n",(void *)d->kids);
       f = open_indent(to,"  ");
       dump_dbnode(d->kids,f);
       fclose(f);
     }
    else
     { putc('\n',to);
     }
  }
}

static void dump_dbnode(DBNODE *n, FILE *to)
{
 FILE *f;

 fprintf(to,"[%p] tight %d %p\n",(void *)n,n->ntight,(void *)n->vtight);
 f = open_indent(to,"  ");
 dump_dbdata_vec(n->ntight,n->vtight,f);
 fclose(f);
 fprintf(to,"[%p] loose %d %p\n",(void *)n,n->nloose,(void *)n->vloose);
 f = open_indent(to,"  ");
 dump_dbdata_vec(n->nloose,n->vloose,f);
 fclose(f);
}

static void sortmerge_dbdata_list(int *np, DBDATA **vp, FILE *to)
{
 FILE *f;
 int n;
 DBDSORT_STATE s;
 int i;
 int t;
 int j;
 DBDATA *newv;
 int newn;
 int newx;
 DBDATA *newd;
 int nt;
 int nl;
 int kx;
 VALUE *v;

 f = open_indent(to,"  ");
 n = *np;
 s.v = *vp;
 s.map = malloc(n*sizeof(int));
 fprintf(to,"sortmerge_dbdata_list: initial list is\n");
 for (i=0;i<n;i++) fprintf(f,"%u\n",s.v[i].q);
 for (i=n-1;i>=0;i--) s.map[i] = i;
 for (i=H_U(n-1);i>=0;i--) reheap(&s,i,n);
 fflush(f);
 fprintf(to,"heap is\n");
 for (i=0;i<n;i++) fprintf(f,"%u\n",s.v[s.map[i]].q);
 for (i=n-1;i>0;i--)
  { t = s.map[i];
    s.map[i] = s.map[0];
    s.map[0] = t;
    reheap(&s,0,i);
  }
 fflush(f);
 fprintf(to,"sorted list is\n");
 for (i=0;i<n;i++) fprintf(f,"%u\n",s.v[s.map[i]].q);
 newn = 0;
 for (i=0;i<n;i=j)
  { for (j=i+1;(j<n)&&(s.v[s.map[j]].q==s.v[s.map[i]].q);j++) ;
    newn ++;
  }
 fflush(f);
 fprintf(to,"newn = %d\n",newn);
 fflush(0);
 fflush(0);
 fflush(0);
 newv = malloc(newn*sizeof(DBDATA));
 newx = 0;
 for (i=0;i<n;i++)
  { for (j=i+1;(j<n)&&(s.v[s.map[j]].q==s.v[s.map[i]].q);j++) ;
    if (j == i+1)
     { // DBNODE *n;
       fprintf(to,"i=%d j=%d, simple copy into [%d]\n",i,j,newx);
       if ((newx < 0) || (newx >= newn)) abort();
       newv[newx++] = s.v[s.map[i]];
       s.v[s.map[i]].kids = 0;
//       if (n) *n = (DBNODE){.ntight=0x111111,.vtight=(void *)0xdeadbeef,.nloose=0x111111,.vloose=(void *)0xdeadbeef};
     }
    else
     { fprintf(to,"i=%d j=%d, merge\n",i,j);
       nt = 0;
       nl = 0;
       v = 0;
       for (kx=i;kx<j;kx++)
	{ DBDATA *d;
	  d = &s.v[s.map[kx]];
	  fprintf(to,"[%d] -> %d -> %p:",kx,s.map[kx],(void *)d);
	  if (d->val)
	   { // do we want anything more in the if(v) case?
	     if (v) value_free(v);
	     v = d->val;
	     d->val = 0;
	     fprintf(to," val=");
	     print_value(v,to);
	   }
	  if (d->kids)
	   { fprintf(to," kids=%p(%d,%d)",(void *)d->kids,d->kids->ntight,d->kids->nloose);
	     nt += d->kids->ntight;
	     nl += d->kids->nloose;
	   }
	  fprintf(to,"\n");
	}
       fprintf(to,"nt=%d nl=%d, loading [%d]\n",nt,nl,newx);
       if ((newx < 0) || (newx >= newn)) abort();
       newd = &newv[newx++];
       newd->q = s.v[s.map[i]].q;
       fprintf(to,"q=%u\n",newd->q);
       newd->val = v;
       fprintf(to,"v=%p",(void *)v);
       if (v)
	{ putc('=',to);
	  print_value(v,to);
	}
       putc('\n',to);
       if (!nt && !nl)
	{ newd->kids = 0;
	  fprintf(to,"new kids = nil");
	}
       else
	{ DBNODE *newdn;
	  newdn = malloc(sizeof(DBNODE));
	  fprintf(to,"new kids = %p",(void *)newdn);
	  newdn->ntight = 0;
	  newdn->vtight = malloc(nt*sizeof(DBDATA));
	  newdn->nloose = 0;
	  newdn->vloose = malloc(nl*sizeof(DBDATA));
	  for (kx=i;kx<j;kx++)
	   { DBDATA *d;
	     d = &s.v[s.map[kx]];
	     if ((d->kids->nloose == 0x111111) || (d->kids->ntight == 0x111111)) abort();
#define COPYLOOP(kind,nv)\
	     do								\
	      { if (d->kids->n##kind)					\
		 { if (newdn->n##kind+d->kids->n##kind > nv) abort();	\
		   bcopy(d->kids->v##kind,&newdn->v##kind[newdn->n##kind],d->kids->n##kind*sizeof(DBDATA));\
		   newdn->n##kind += d->kids->n##kind;			\
		   free(d->kids->v##kind);				\
		   d->kids->n##kind = 0x111111;				\
		   d->kids->v##kind = (void *)0xdeadbeef;		\
		 }							\
	      } while (0)
	     COPYLOOP(tight,nt);
	     COPYLOOP(loose,nl);
#undef COPYLOOP
	   }
	  if ((newdn->ntight != nt) || (newdn->nloose != nl)) abort();
	  fprintf(to," (t=%d@%p l=%d@%p)\n",nt,(void *)newdn->vtight,nl,(void *)newdn->vloose);
	  dump_dbnode(newdn,to);
	  fprintf(to,"recursing tight\n");
	  sortmerge_dbdata_list(&newdn->ntight,&newdn->vtight,f);
	  fprintf(to,"recursing loose\n");
	  sortmerge_dbdata_list(&newdn->nloose,&newdn->vloose,f);
	  fprintf(to,"recursing done\n");
	  fprintf(to,"setting kids to %p\n",(void *)newdn);
	  newd->kids = newdn;
	}
       i = j - 1;
     }
  }
 for (i=n-1;i>=0;i--)
  { DBDATA *d;
    d = s.v + i;
    if (d->kids)
     { if (d->kids->ntight != 0x111111) free(d->kids->vtight);
       if (d->kids->nloose != 0x111111) free(d->kids->vloose);
       free(d->kids);
     }
  }
 free(s.v);
 free(s.map);
 *vp = newv;
 *np = newn;
 fclose(f);
}

static void undefer(DBNODE *n)
{
 FILE *f;
 int dt;
 int dl;

 printf("undefer %p:\n",(void *)n);
 dump_dbnode(n,stdout);
 f = open_indent(stdout,"  ");
 sortmerge_dbdata_list(&n->ntight,&n->vtight,f);
 sortmerge_dbdata_list(&n->nloose,&n->vloose,f);
 fclose(f);
}

static void db_undefer(DB *db)
{
 if (! (db->flags & DBF_DEFER)) return;
 db->flags &= ~DBF_DEFER;
 undefer(db->root);
}

static void append_dbds(int *into_np, DBDATA **into_vp, int *from_np, DBDATA **from_vp)
{
 int n;
 DBDATA *v;

 if (*from_np < 1) return;
 if (*into_np < 1)
  { *into_np = *from_np;
    free(*into_vp);
    *into_vp = *from_vp;
  }
 else
  { n = *into_np + *from_np;
    v = realloc(*into_vp,n*sizeof(DBDATA));
    bcopy(*from_vp,v+*into_np,(*from_np)*sizeof(DBDATA));
    free(*from_vp);
    *into_np = n;
    *into_vp = v;
  }
 *from_np = 0;
 *from_vp = 0;
}

static void merge_db_deferred(DB *from, DB *into)
{
 append_dbds(&into->root->ntight,&into->root->vtight,&from->root->ntight,&from->root->vtight);
 append_dbds(&into->root->nloose,&into->root->vloose,&from->root->nloose,&from->root->vloose);
}

static void merge_db(DB *from, DB *into)
{
 if (into->flags & DBF_DEFER)
  { merge_db_deferred(from,into);
  }
 else
  { merge_db_now(from,into);
  }
}

static void db_add(DB *db, const BQ *res, int nres, const unsigned char *val, int nval)
{
 DB topdb;
 DBNODE *top;
 DBNODE **np;
 VALUE **vp;
 DBNODE *n;
 DBDATA *dd;
 int i;
 VALUE *v;

 if (nres < 1) return;
 for (i=nres-1;i>=0;i--)
  { switch (res[i].b)
     { case BIND_TIGHT:
       case BIND_LOOSE:
	  if (res[i].q >= nquarks) return;
	  break;
       default:
	  return;
	  break;
     }
  }
 np = &top;
 vp = 0;
 for (i=0;i<nres;i++)
  { n = malloc(sizeof(DBNODE));
    dd = malloc(sizeof(DBDATA));
    switch (res[i].b)
     { case BIND_TIGHT:
	  n->ntight = 1;
	  n->vtight = dd;
	  n->nloose = 0;
	  n->vloose = 0;
	  break;
       case BIND_LOOSE:
	  n->ntight = 0;
	  n->vtight = 0;
	  n->nloose = 1;
	  n->vloose = dd;
	  break;
       default:
	  abort();
	  break;
     }
    dd->q = res[i].q;
    dd->val = 0;
    dd->kids = 0;
    *np = n;
    np = &dd->kids;
    vp = &dd->val;
  }
 if (! vp) abort();
 v = malloc(sizeof(VALUE));
 v->b = malloc(nval+1);
 v->l = nval;
 bcopy(val,v->b,nval);
 *vp = v;
 topdb.flags = 0;
 topdb.root = top;
 merge_db(&topdb,db);
 if (topdb.root->nloose || topdb.root->vloose || topdb.root->ntight || topdb.root->vtight) abort();
 free(top);
}

static void dump_db(DB *db)
{
 printf("DB%s:\n",(db->flags&DBF_DEFER)?" (DEFER)":"");
 dump_dbnode(db->root,stdout);
}

static void load_sample_file(void)
{
 char *home;
 char *path;
 int fd;
 struct stat stb;
 void *mmrv;
 int len;
 DB *db;

#if 0
 home = getenv("HOME");
 if (! home)
  { fprintf(stderr,"%s: no $HOME\n",__progname);
    return;
  }
 asprintf(&path,"%s/.Xdefaults",home);
#else
 home = 0;
 (void)home;
 asprintf(&path,"test-defaults");
#endif
 do
  { fd = open(path,O_RDONLY,0);
    if (fd < 0)
     { fprintf(stderr,"%s: open %s: %s\n",__progname,path,strerror(errno));
       break;
     }
    do
     { if (fstat(fd,&stb) < 0)
	{ fprintf(stderr,"%s: fstat %s: %s\n",__progname,path,strerror(errno));
	  break;
	}
       len = stb.st_size;
       if (len != stb.st_size)
	{ fprintf(stderr,"%s: %s: too large\n",__progname,path);
	  break;
	}
       mmrv = mmap(0,len,PROT_READ,MAP_FILE|MAP_SHARED,fd,0);
       if (mmrv == MAP_FAILED)
	{ fprintf(stderr,"%s: mmap %s: %s\n",__progname,path,strerror(errno));
	  break;
	}
       db = parse_resources(mmrv,len);
       printf("--------\n");
       dump_db(db);
       munmap(mmrv,len);
     } while (0);
    close(fd);
  } while (0);
 free(path);
 dump_quarktable("Quark tree now is");
}

int main(void);
int main(void)
{
// check_quarks();
 (void)&check_quarks;
 load_sample_file();
 return(0);
}

#endif