static int __cdbb_copy(struct cdbb *a, size_t ks, size_t vs)
{
	unsigned char k[ks];
	unsigned char v[vs];
	uint32 kp, dp;
	int found, filter;

	found = 0;

	kp = cdb_keypos(a->r);
	cdb_read(a->r, k, ks, kp);

	dp = cdb_datapos(a->r);
	/* in some cases we do not need to read e.g. when deleting
	 * or filtering but for simplicity we just do it anyways */
	cdb_read(a->r, v, vs, dp);

	found = cdbb_check_ops(a, k, ks, v, vs);
	filter = cdbb_check_filter(a, k, ks, v, vs);

	/* if an operation applied or a filter, don't copy */
	if (!found && !filter && kp) {
		cdb_make_add(a->w, k, ks, v, vs);
		return 1;
	}
	return 0;
}

// This is going to be slow since it is a search by value. I.e. it
// walks through the entire CDB sequentially trying to map a value
// back to its key. Therefore it should only be used in debug or
// error scenarios.
static CCS
_shop_find_cmdline(shopping_state_s *ssp, CCS cmdix)
{
    unsigned loc = 0;

    cdb_seqinit(&loc, ssp->cdbp);
    while (cdb_seqnext(&loc, ssp->cdbp) > 0) {
	unsigned len;

	CS cmdstate, ix;

	len = cdb_datalen(ssp->cdbp);
	cmdstate = (CS)alloca(len + 1);
	cdb_read(ssp->cdbp, cmdstate, len, cdb_datapos(ssp->cdbp));
	cmdstate[len] = '\0';

	if ((ix = util_strsep(&cmdstate, FS1)) && !strcmp(cmdix, ix)) {
	    CS line;

	    len = cdb_keylen(ssp->cdbp);
	    line = (CS)putil_malloc(len + 1);
	    cdb_read(ssp->cdbp, line, len, cdb_keypos(ssp->cdbp));
	    line[len] = '\0';
	    return line;
	}
    }

    return NULL;
}

static int __cdbb_findnext(struct cdbb *a, const char *needle, struct nentry *n,
	int ignorecase)
{
	uint32 kp, dp, ks, vs;
	unsigned char *k, *v;

	if (cdb_nextkey(a->r, &a->kfindpos) != 1)
		return -1;

	kp = cdb_keypos(a->r);
	ks = cdb_keylen(a->r);
	k = alloca(ks);
	cdb_read(a->r, k, ks, kp);

	dp = cdb_datapos(a->r);
	vs = cdb_datalen(a->r);
	/* in some cases we do not need to read e.g. when deleting
	 * or filtering but for simplicity we just do it anyways */
	v = alloca(vs);
	cdb_read(a->r, v, vs, dp);

	/* search value */
	if (ignorecase) {
		if (strcasestr((char *)v, needle) == NULL)
			return 0;
	} else {
		if (strstr((char *)v, needle) == NULL)
			return 0;
	}

	array_catb(&n->k, (char *)k, ks);
	array_catb(&n->e, (char *)v, vs);

	return 1;
}

static int doit(char *q,char qtype[2],char ip[4])
{
    int r;
    uint32 dlen;
    unsigned int qlen;

    qlen = dns_domain_length(q);
    if (qlen > 255) return 0; /* impossible */

    if (byte_diff(qtype,2,DNS_T_A) && byte_diff(qtype,2,DNS_T_ANY)) goto REFUSE;

    key[0] = '%';
    byte_copy(key + 1,4,ip);

    r = cdb_find(&c,key,5);
    if (!r) r = cdb_find(&c,key,4);
    if (!r) r = cdb_find(&c,key,3);
    if (!r) r = cdb_find(&c,key,2);
    if (r == -1) return 0;

    key[0] = '+';
    byte_zero(key + 1,2);
    if (r && (cdb_datalen(&c) == 2))
        if (cdb_read(&c,key + 1,2,cdb_datapos(&c)) == -1) return 0;

    byte_copy(key + 3,qlen,q);
    case_lowerb(key + 3,qlen + 3);

    r = cdb_find(&c,key,qlen + 3);
    if (!r) {
        byte_zero(key + 1,2);
        r = cdb_find(&c,key,qlen + 3);
    }
    if (!r) goto REFUSE;
    if (r == -1) return 0;
    dlen = cdb_datalen(&c);

    if (dlen > 512) dlen = 512;
    if (cdb_read(&c,data,dlen,cdb_datapos(&c)) == -1) return 0;

    dns_sortip(data,dlen);

    if (dlen > 12) dlen = 12;
    while (dlen >= 4) {
        dlen -= 4;
        if (!response_rstart(q,DNS_T_A,"\0\0\0\5")) return 0;
        if (!response_addbytes(data + dlen,4)) return 0;
        response_rfinish(RESPONSE_ANSWER);
    }

    return 1;


REFUSE:
    response[2] &= ~4;
    response[3] &= ~15;
    response[3] |= 5;
    return 1;
}

int cdb_findnext(struct cdb *c, ut32 u, const char *key, unsigned int len) {
	char buf[8];
	ut32 pos;
	int m;

	if (!c->loop) {
		if (!cdb_read (c, buf, 8, (u << 3) & 2047))
			return -1;
		ut32_unpack (buf + 4, &c->hslots);
		if (!c->hslots) {
			return 0;
		}
		ut32_unpack (buf, &c->hpos);
		c->khash = u;
		u >>= 8;
		u %= c->hslots;
		u <<= 3;
		c->kpos = c->hpos + u;
	}

	while (c->loop < c->hslots) {
		if (!cdb_read (c, buf, 8, c->kpos))
			return 0;
		ut32_unpack (buf + 4, &pos);
		if (!pos) return 0;
		c->loop++;
		c->kpos += 8;
		if (c->kpos == c->hpos + (c->hslots << 3))
			c->kpos = c->hpos;
		ut32_unpack (buf, &u);
		if (u == c->khash) {
			if (!seek_set (c->fd, pos))
				return -1;
			if (!getkvlen (c->fd, &u, &c->dlen))
				return -1;
			if (u == 0)
				return -1;
			if (u == len) {
				if ((m = match (c, key, len, pos + KVLSZ))==-1)
					return 0;
				if (m == 1) {
					c->dpos = pos + KVLSZ + len;
					return 1;
				}
			}
		}
	}
	return 0;
}

int
cdb_find(struct cdb *C, const uchar_t *key, uint32_t klen)
{
  uint32_t  fp;
  uchar_t   nbuf[8];
  uint32_t  hash, tslots, target;
  
  /* search initialization: */
  C->key = (uchar_t *)key;
  C->klen = klen;
  C->h = hash = cdb_hash(key, klen);

  /* lookup subtable for this hash value: */
  fp = cdb_NTAB(hash) * 8;
  if(cdb_read(C, nbuf, 8, fp) == -1){
      return -1;
  }
  /* subtable offet: */
  C->tbase = upak32_unpack(nbuf);
  /* slots in subtable: */
  C->tslots = tslots = upak32_unpack(nbuf + 4);

  if(tslots == 0){
      /* no slots in this table; key not found: */
      return 0;
  }

  /* target slot for this key: */
  target = cdb_SLOT(hash, tslots);
  C->s0 = target;

  /* probe: */
  return cdb_hash_probe(C, target);
}

int
main(int argc, char* argv[]) {
  int fd;
  static struct cdb c;
  errmsg_iam("cdbget");
  if(argc < 3)
    die(1, "usage: cdbget data.cdb key");
  fd = open(argv[1], O_RDONLY | O_BINARY);
  if(fd == -1)
    diesys(1, "open");
  cdb_init(&c, fd);
  if(cdb_find(&c, argv[2], str_len(argv[2])) > 0) {
    do {
      char* x = malloc(cdb_datalen(&c));
      if(!x)
        die(1, "out of memory");
      if(cdb_read(&c, x, cdb_datalen(&c), cdb_datapos(&c)) == -1)
        diesys(1, "cdb_read");
      buffer_put(buffer_1, x, cdb_datalen(&c));
      buffer_put(buffer_1, "\n", 1);
      free(x);
    } while(cdb_findnext(&c, argv[2], str_len(argv[2])) > 0);
  }
  buffer_flush(buffer_1);
}

int main(int argc, char **argv, char **envp) {
  uint8_t buf[1024];
  cdb_t cdb;
  char *key;
  uint32_t len;
  uint32_t r;
  uint32_t pos;
  uint32_t skip = 0;
  char *skip_str;
  
  if (!*argv || !*++argv)
    usage();
  key = *argv;
  
  skip_str = *++argv;
  if (skip_str) {
    if (sscanf(skip_str, "%" PRIu32, &skip) != strlen(skip_str))
      usage();
  }
  
  /* Initialize the cdb struct using stdin as it's file descriptor. */
  if (cdb_init(&cdb, 0) == -1)
    strerr_die2x(111, FATAL, "failed to initialize cdb");
    
  for (;;) {
    r = cdb_find_next(&cdb, key, strlen(key));
    if (r == -1)
      strerr_die2sys(111, FATAL, "unable to read input: ");
    if (!r)
      _exit(100);
      
    if (!skip)
      break;
    skip--;
  }
  
  /* If there's a record in the cdb file, then the cdb structs dlen property
   * will be set to a non-zero value and it's position will be set to the
   * offset in the file containing the data.  Read the data in chunks and send
   * it to stdout. */
  len = cdb.dlen;
  pos = cdb.dpos;
  while (len > 0) {
    r = sizeof(buf);
    if (r > len)
      r = len;
    if (cdb_read(buf, r, &cdb, pos) == -1)
      strerr_die2sys(111, FATAL, "unable to read input: ");
    if (bio_put(bio_1, buf, r) == -1)
      strerr_die2sys(111, FATAL, "unable to write output: ");
    pos += r;
    len -= r;
  }
  if (bio_flush(bio_1) == -1)
    strerr_die2sys(111, FATAL, "unable to write output: ");
    
  cdb_free(&cdb);
  
  return 0;
}

int respond(char *q,char qtype[2],char ip[4])
{
  int fd;
  int r;
  char key[6];

  tai_now(&now);
  fd = open_read("data.cdb");
  if (fd == -1) return 0;
  cdb_init(&c,fd);

  byte_zero(clientloc,2);
  key[0] = 0;
  key[1] = '%';
  byte_copy(key + 2,4,ip);
  r = cdb_find(&c,key,6);
  if (!r) r = cdb_find(&c,key,5);
  if (!r) r = cdb_find(&c,key,4);
  if (!r) r = cdb_find(&c,key,3);
  if (!r) r = cdb_find(&c,key,2);
  if (r == -1) return 0;
  if (r && (cdb_datalen(&c) == 2))
    if (cdb_read(&c,clientloc,2,cdb_datapos(&c)) == -1) return 0;

  r = doit(q,qtype);

  cdb_free(&c);
  close(fd);
  return r;
}

int
cdb_init(struct cdb *C, int fd)
{
  struct stat  sb;
  uchar_t     *map;
  uchar_t      buf[INITBUF_SIZE];

  buf_zero(C, sizeof (struct cdb));

  /* try to mmap() fd: */
  if((fstat(fd, &sb) == 0) && (sb.st_size <= (off_t)0xffffffff)){
         map = mmap(0, sb.st_size, PROT_READ, MAP_SHARED, fd, 0);
         if(map != MAP_FAILED){
             C->map = map;
             C->map_size = sb.st_size;
         }
  }
  C->fd = fd;

  /* suck in file header: */
  if(cdb_read(C, buf, sizeof buf, 0) == -1){
      return -1;
  }

  /* C->hbase: offset to base of hash table (also eod): */
  C->hbase = upak32_unpack(buf);

  return 0;
}

/* cdb_key_match()
**   compare record key of klen at kpos
**   to search key initialized in cdb_find()
*/   
static
int
cdb_key_match(struct cdb *C, const uchar_t *key, uint32_t klen, uint32_t kpos)
{
  uchar_t   kbuf[80];  /* compare upto 80 bytes of key at a time */
  uint32_t  n;

  while(klen > 0){
      n = sizeof kbuf;
      if(n > klen) n = klen;
      if(cdb_read(C, kbuf, n, kpos) == -1){
          /* io error: */
          return -1;
      }
      if(buf_cmp(key, kbuf, n) != 0){
          /* no match: */
          return 0;
      }
      kpos += n;
      klen -= n;
  }

  /* match! */
  return 1;
}

int cdb_findnext(struct cdb *c,char *key,unsigned int len)
{
  char buf[8];
  uint32 pos;
  uint32 u;

	U_INTERNAL_TRACE("cdb_findnext(%p,%.*s,%u)",c,len,key,len)

  if (!c->loop) {
	 u = cdb_hash(key,len);
	 if (cdb_read(c,buf,8,(u % CDB_NUM_HASH_TABLE_POINTER) * 8) == -1) return -1;
	 uint32_unpack(buf + 4,&c->hslots);
	 if (!c->hslots) return 0;
	 uint32_unpack(buf,&c->hpos);
	 c->khash = u;
	 u /= CDB_NUM_HASH_TABLE_POINTER;
	 u %= c->hslots;
	 u <<= 3;
	 c->kpos = c->hpos + u;
  }

  while (c->loop < c->hslots) {
	 if (cdb_read(c,buf,8,c->kpos) == -1) return -1;
	 uint32_unpack(buf + 4,&pos);
	 if (!pos) return 0;
	 c->loop += 1;
	 c->kpos += 8;
	 if (c->kpos == c->hpos + (c->hslots << 3)) c->kpos = c->hpos;
	 uint32_unpack(buf,&u);
	 if (u == c->khash) {
		if (cdb_read(c,buf,8,pos) == -1) return -1;
		uint32_unpack(buf,&u);
		if (u == len)
	switch(match(c,key,len,pos + 8)) {
	  case -1:
		 return -1;
	  case 1:
		 uint32_unpack(buf + 4,&c->dlen);
		 c->dpos = pos + 8 + len;
		 return 1;
	}
	 }
  }

  U_INTERNAL_TRACE("not found",0)
  return 0;
}

static int do_regex_checks(struct _info *info, char *rr_type, char *key, char *rr_rdata)
{
        char *pattern;
	unsigned keylen = strlen(key), patlen, vpos;
	int nchecks = 0;

	if (cdb_findinit(&info->cdbf, &info->cdb, key, keylen) <= 0) {
		return (-1);
	}

	while (cdb_findnext(&info->cdbf) > 0) {
		int m;

		vpos = cdb_datapos(&info->cdb);
		patlen = cdb_datalen(&info->cdb);
		pattern = malloc(patlen + 1);
		cdb_read(&info->cdb, pattern, patlen, vpos);
		pattern[patlen] = '\0';

		if (*pattern == '@') {
			/*
			 * Handle special function for data check
			 */

			if (!strcmp(pattern, "@IP")) {
				m = func_ip(info, rr_type, rr_rdata);
				if (m) {
					++nchecks;
				} else {
					return (0);
				}
			} else if (!strcmp(pattern, "@SOA")) {
				m = func_soa(info, rr_type, rr_rdata);
				if (m) {
					++nchecks;
				} else {
					return (0);
				}
			}
		} else {

			m = match(pattern, rr_rdata);
//			fprintf(stderr, "*** match %s  ", m ? "TRUE " : "false");
//				fprintf(stderr, "%s\n", pattern);

			if (m) {
				++nchecks;
				// FIXME: can return now
			} else {
				sprintf(info->reason, "%s [%s] fails regexp [%s]",
					rr_type, rr_rdata, pattern);
			}
		}

		free(pattern);
	}

	return (nchecks);
}

static int doit(struct cdb *c,uint32 *kpos) {
  char buf[8];
  uint32 eod,klen;
  if (cdb_read(c,buf,4,0)) return -1;
  uint32_unpack(buf,&eod);
  if (eod<8 || eod-8<*kpos) return 0;
  c->kpos=*kpos+8;
  if (c->kpos<*kpos) return -1; /* wraparound */
  cdb_findstart(c);
  c->hslots=1;
  if (cdb_read(c,buf,8,*kpos) == -1) return -1;
  uint32_unpack(buf,&klen);
  uint32_unpack(buf+4,&c->dlen);
  c->dpos=c->kpos+klen;
  *kpos+=8+klen+c->dlen;
  return 1;
}

int OS_DBSearchKeyAddressValue(ListRule *lrule, char *key)
{
    int result=-1;
    char *val;
    unsigned vlen, vpos;
    if (lrule->db!= NULL)
    {
        if(_OS_CDBOpen(lrule->db) == -1) return 0;

        // First lookup for a single IP address
        if(cdb_find(&lrule->db->cdb, key, strlen(key)) > 0 ) {
            vpos = cdb_datapos(&lrule->db->cdb);
            vlen = cdb_datalen(&lrule->db->cdb);
            val = malloc(vlen);
            cdb_read(&lrule->db->cdb, val, vlen, vpos);
            result = OSMatch_Execute(val, vlen, lrule->matcher);
            free(val);
            return result;
        } else {
            // IP address not found, look for matching subnets
            char *tmpkey;
            os_strdup(key, tmpkey);
            while(strlen(tmpkey) > 0)
            {
                if(tmpkey[strlen(tmpkey) - 1] == '.')
                {
                    if( cdb_find(&lrule->db->cdb, tmpkey, strlen(tmpkey)) > 0 ) {
                        vpos = cdb_datapos(&lrule->db->cdb);
                        vlen = cdb_datalen(&lrule->db->cdb);
                        val = malloc(vlen);
                        cdb_read(&lrule->db->cdb, val, vlen, vpos);
                        result = OSMatch_Execute(val, vlen, lrule->matcher);
                        free(val);
                        free(tmpkey);
                        return result;
                    }
                }
                tmpkey[strlen(tmpkey) - 1] = '\0';
            }
            free(tmpkey);
            return 0;
        }
    }
    return 0;
}

int cdb_findnext(struct cdb *c,char *key,off_t len)
{
  char buf[entry_size];
  ref_t pos;
  ref_t u;

  if (!c->loop) {
    u = cdb_hash(key,len);
    if (cdb_read(c,buf,entry_size,(u * entry_size) & (256*entry_size - 1)) == -1) return -1;
    ref_unpack(buf + ref_size,&c->hslots);
    if (!c->hslots) return 0;
    ref_unpack(buf,&c->hpos);
    c->khash = u;
    u /= ref_size;
    u %= c->hslots;
    u *= entry_size;
    c->kpos = c->hpos + u;
  }

  while (c->loop < c->hslots) {
    if (cdb_read(c,buf,entry_size,c->kpos) == -1) return -1;
    ref_unpack(buf + ref_size,&pos);
    if (!pos) return 0;
    c->loop += 1;
    c->kpos += 8;
    if (c->kpos == c->hpos + (c->hslots * entry_size)) c->kpos = c->hpos;
    ref_unpack(buf,&u);
    if (u == c->khash) {
      if (cdb_read(c,buf,entry_size,pos) == -1) return -1;
      ref_unpack(buf,&u);
      if (u == len)
	switch(match(c,key,len,pos + entry_size)) {
	  case -1:
	    return -1;
	  case 1:
	    ref_unpack(buf + ref_size,&c->dlen);
	    c->dpos = pos + entry_size + len;
	    return 1;
	}
    }
  }

  return 0;
}

int cdb_getnext(struct cdb* cdb, const str* key, str* data)
{
  if (cdb == 0 || key == 0 || data == 0) return -1;
  if (!cdb_findnext(cdb, key->s, key->len)) return 0;
  if (!str_ready(data, cdb->dlen)) return -1;
  if (cdb_read(cdb, (unsigned char*)data->s, cdb->dlen, cdb->dpos) == -1)
    return -1;
  data->len = cdb->dlen;
  data->s[data->len] = 0;
  return 1;
}

int find_client_loc(char loc[2],const char ip[16])
{
  int r, fd;
  char key[32+3];
  static struct cdb c;

  fd = open_read("data.cdb");
  if (fd == -1) return 0;
  cdb_init(&c,fd);

  byte_zero(loc,2);
  key[0] = 0;
  key[1] = '%';
  if (byte_equal(ip,12,V4mappedprefix)) {
    key[2] = 'f';
    byte_copy(key + 3,4,ip+12);
    r = cdb_find(&c,key,7);
    if (!r) r = cdb_find(&c,key,6);
    if (!r) r = cdb_find(&c,key,5);
    if (!r) r = cdb_find(&c,key,4);
    if (!r) r = cdb_find(&c,key,3);
    if (r == -1) return 0;
    if (r && (cdb_datalen(&c) == 2))
      if (cdb_read(&c,loc,2,cdb_datapos(&c)) == -1) return 0;
  } else {
    unsigned int n;
    key[2] = 's';
    ip6_fmt_flat(key+3,ip);
    for (n=19; n>3; --n) {
      r = cdb_find(&c,key,n);
      if (r) break;
    }
    if (r == -1) return 0;
    if (r && (cdb_datalen(&c) == 2))
      if (cdb_read(&c,loc,2,cdb_datapos(&c)) == -1) return 0;
  }

  cdb_free(&c);
  close(fd);
  return r;
}

static PyObject *
_cdbo_keyiter(CdbObject *self) {

  PyObject *key;
  char buf[8];
  uint32 klen, dlen;

  if (! self->eod)
    _cdbo_init_eod(self);

  while (self->iter_pos < self->eod) {
    if (cdb_read(&self->c, buf, 8, self->iter_pos) == -1)
      return CDBerr;

    uint32_unpack(buf, &klen);
    uint32_unpack(buf+4, &dlen);

    key = cdb_pyread(self, klen, self->iter_pos + 8);

    if (key == NULL)
      return NULL;

    switch(cdb_find(&self->c,PyString_AsString(key),PyString_Size(key))) {
      case -1:
        Py_DECREF(key);
        key = NULL;
        return CDBerr;
      case 0:
        /* bizarre, impossible? PyExc_RuntimeError? */
        PyErr_SetString(PyExc_KeyError, 
                        PyString_AS_STRING((PyStringObject *) key));
        Py_DECREF(key);
        key = NULL;
      default:
        if (key == NULL)  /* already raised error */
          return NULL;

        if (cdb_datapos(&self->c) == self->iter_pos + klen + 8) {
          /** first occurrence of key in the cdb **/
          self->iter_pos += 8 + klen + dlen;
          return key;
        }
        Py_DECREF(key);   /* better luck next time around */
        self->iter_pos += 8 + klen + dlen;
    }
  }

  return Py_BuildValue("");  /* iter_pos >= eod; we're done */

}

static int match(struct cdb *c, const char *key, ut32 len, ut32 pos) {
	char buf[32];
	const size_t szb = sizeof buf;
	while (len > 0) {
		int n = (szb>len)? len: szb;
		if (!cdb_read (c, buf, n, pos))
			return -1;
		if (byte_diff (buf, n, key))
			return 0;
		pos += n;
		key += n;
		len -= n;
	}
	return 1;
}