libq/tree: merge vdb and cache

since cache was basically a shadow of vdb, and vdb grew too many
non-vdb-like behaviour, renamed to tree such that further features only
have to be implemented once

Signed-off-by: Fabian Groffen <grobian@gentoo.org>

22 files changed, 1419 insertions, 1554 deletions

diff --git a/TODO.md b/TODO.md
index 3333fd62..ec5f843e 100644
--- a/TODO.md
+++ b/TODO.md
@@ -23,10 +23,11 @@
   we end up getting just:<br>
   `ACCEPT_LICENSE=" bar"`
 
-- vdb\_foreach\_pkg should have variant that takes an atom (or just
-  cat?) to reduce search space, same for cache\_foreach\_pkg
+- tree\_foreach\_pkg should have variant that takes an atom (or just
+  cat?) to reduce search space
 
-- vdb repo/slot think about when it is freed (see cache\_pkg\_close)
+- tree\_get\_atoms should return atoms iso string set, needs a rewrite
+  to use foreach\_pkg and get\_atom
 
 # Atoms
 
diff --git a/libq/Makefile.am b/libq/Makefile.am
index 765347f2..62ffb83a 100644
--- a/libq/Makefile.am
+++ b/libq/Makefile.am
@@ -3,7 +3,6 @@ QFILES = \
 	atom.c atom.h \
 	basename.c basename.h \
 	busybox.h \
-	cache.c cache.h \
 	colors.c colors.h \
 	contents.c contents.h \
 	copy_file.c copy_file.h \
@@ -19,7 +18,7 @@ QFILES = \
 	safe_io.c safe_io.h \
 	scandirat.c scandirat.h \
 	set.c set.h \
-	vdb.c vdb.h \
+	tree.c tree.h \
 	xarray.c xarray.h \
 	xasprintf.h \
 	xchdir.c xchdir.h \
diff --git a/libq/Makefile.in b/libq/Makefile.in
index 5f118fca..c359f4be 100644
--- a/libq/Makefile.in
+++ b/libq/Makefile.in
@@ -241,13 +241,13 @@ CONFIG_CLEAN_FILES =
 CONFIG_CLEAN_VPATH_FILES =
 LTLIBRARIES = $(noinst_LTLIBRARIES)
 libq_la_LIBADD =
-am__objects_1 = libq_la-atom.lo libq_la-basename.lo libq_la-cache.lo \
-	libq_la-colors.lo libq_la-contents.lo libq_la-copy_file.lo \
-	libq_la-dep.lo libq_la-eat_file.lo libq_la-hash_fd.lo \
+am__objects_1 = libq_la-atom.lo libq_la-basename.lo libq_la-colors.lo \
+	libq_la-contents.lo libq_la-copy_file.lo libq_la-dep.lo \
+	libq_la-eat_file.lo libq_la-hash_fd.lo \
 	libq_la-human_readable.lo libq_la-md5_sha1_sum.lo \
 	libq_la-prelink.lo libq_la-profile.lo libq_la-rmspace.lo \
 	libq_la-safe_io.lo libq_la-scandirat.lo libq_la-set.lo \
-	libq_la-vdb.lo libq_la-xarray.lo libq_la-xchdir.lo \
+	libq_la-tree.lo libq_la-xarray.lo libq_la-xchdir.lo \
 	libq_la-xmkdir.lo libq_la-xpak.lo libq_la-xregex.lo \
 	libq_la-xsystem.lo
 am_libq_la_OBJECTS = $(am__objects_1)
@@ -1447,7 +1447,6 @@ QFILES = \
 	atom.c atom.h \
 	basename.c basename.h \
 	busybox.h \
-	cache.c cache.h \
 	colors.c colors.h \
 	contents.c contents.h \
 	copy_file.c copy_file.h \
@@ -1463,7 +1462,7 @@ QFILES = \
 	safe_io.c safe_io.h \
 	scandirat.c scandirat.h \
 	set.c set.h \
-	vdb.c vdb.h \
+	tree.c tree.h \
 	xarray.c xarray.h \
 	xasprintf.h \
 	xchdir.c xchdir.h \
@@ -1535,7 +1534,6 @@ distclean-compile:
 
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-atom.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-basename.Plo@am__quote@
-@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-cache.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-colors.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-contents.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-copy_file.Plo@am__quote@
@@ -1550,7 +1548,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-safe_io.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-scandirat.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-set.Plo@am__quote@
-@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-vdb.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-tree.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-xarray.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-xchdir.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-xmkdir.Plo@am__quote@
@@ -1593,13 +1591,6 @@ libq_la-basename.lo: basename.c
 @AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
 @am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o libq_la-basename.lo `test -f 'basename.c' || echo '$(srcdir)/'`basename.c
 
-libq_la-cache.lo: cache.c
-@am__fastdepCC_TRUE@	$(AM_V_CC)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT libq_la-cache.lo -MD -MP -MF $(DEPDIR)/libq_la-cache.Tpo -c -o libq_la-cache.lo `test -f 'cache.c' || echo '$(srcdir)/'`cache.c
-@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/libq_la-cache.Tpo $(DEPDIR)/libq_la-cache.Plo
-@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='cache.c' object='libq_la-cache.lo' libtool=yes @AMDEPBACKSLASH@
-@AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
-@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o libq_la-cache.lo `test -f 'cache.c' || echo '$(srcdir)/'`cache.c
-
 libq_la-colors.lo: colors.c
 @am__fastdepCC_TRUE@	$(AM_V_CC)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT libq_la-colors.lo -MD -MP -MF $(DEPDIR)/libq_la-colors.Tpo -c -o libq_la-colors.lo `test -f 'colors.c' || echo '$(srcdir)/'`colors.c
 @am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/libq_la-colors.Tpo $(DEPDIR)/libq_la-colors.Plo
@@ -1698,12 +1689,12 @@ libq_la-set.lo: set.c
 @AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
 @am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o libq_la-set.lo `test -f 'set.c' || echo '$(srcdir)/'`set.c
 
-libq_la-vdb.lo: vdb.c
-@am__fastdepCC_TRUE@	$(AM_V_CC)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT libq_la-vdb.lo -MD -MP -MF $(DEPDIR)/libq_la-vdb.Tpo -c -o libq_la-vdb.lo `test -f 'vdb.c' || echo '$(srcdir)/'`vdb.c
-@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/libq_la-vdb.Tpo $(DEPDIR)/libq_la-vdb.Plo
-@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='vdb.c' object='libq_la-vdb.lo' libtool=yes @AMDEPBACKSLASH@
+libq_la-tree.lo: tree.c
+@am__fastdepCC_TRUE@	$(AM_V_CC)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT libq_la-tree.lo -MD -MP -MF $(DEPDIR)/libq_la-tree.Tpo -c -o libq_la-tree.lo `test -f 'tree.c' || echo '$(srcdir)/'`tree.c
+@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/libq_la-tree.Tpo $(DEPDIR)/libq_la-tree.Plo
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='tree.c' object='libq_la-tree.lo' libtool=yes @AMDEPBACKSLASH@
 @AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
-@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o libq_la-vdb.lo `test -f 'vdb.c' || echo '$(srcdir)/'`vdb.c
+@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o libq_la-tree.lo `test -f 'tree.c' || echo '$(srcdir)/'`tree.c
 
 libq_la-xarray.lo: xarray.c
 @am__fastdepCC_TRUE@	$(AM_V_CC)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT libq_la-xarray.lo -MD -MP -MF $(DEPDIR)/libq_la-xarray.Tpo -c -o libq_la-xarray.lo `test -f 'xarray.c' || echo '$(srcdir)/'`xarray.c
diff --git a/libq/cache.c b/libq/cache.c
deleted file mode 100644
index 304cd342..00000000
--- a/libq/cache.c
+++ /dev/null
@@ -1,687 +0,0 @@
-/*
- * Copyright 2005-2019 Gentoo Foundation
- * Distributed under the terms of the GNU General Public License v2
- *
- * Copyright 2005-2008 Ned Ludd        - <solar@gentoo.org>
- * Copyright 2005-2014 Mike Frysinger  - <vapier@gentoo.org>
- * Copyright 2018-     Fabian Groffen  - <grobian@gentoo.org>
- */
-
-#include "main.h"
-
-#include <fcntl.h>
-#include <sys/types.h>
-#include <sys/stat.h>
-#include <ctype.h>
-#include <xalloc.h>
-
-#include "cache.h"
-#include "eat_file.h"
-#include "rmspace.h"
-#include "scandirat.h"
-#include "vdb.h"
-
-#ifdef EBUG
-static void
-cache_dump(cache_pkg_meta *cache)
-{
-	if (!cache)
-		errf("Cache is empty !");
-
-	printf("DEPEND     : %s\n", cache->DEPEND);
-	printf("RDEPEND    : %s\n", cache->RDEPEND);
-	printf("SLOT       : %s\n", cache->SLOT);
-	printf("SRC_URI    : %s\n", cache->SRC_URI);
-	printf("RESTRICT   : %s\n", cache->RESTRICT);
-	printf("HOMEPAGE   : %s\n", cache->HOMEPAGE);
-	printf("LICENSE    : %s\n", cache->LICENSE);
-	printf("DESCRIPTION: %s\n", cache->DESCRIPTION);
-	printf("KEYWORDS   : %s\n", cache->KEYWORDS);
-	printf("INHERITED  : %s\n", cache->INHERITED);
-	printf("IUSE       : %s\n", cache->IUSE);
-	printf("CDEPEND    : %s\n", cache->CDEPEND);
-	printf("PDEPEND    : %s\n", cache->PDEPEND);
-	printf("PROVIDE    : %s\n", cache->PROVIDE);
-	printf("EAPI       : %s\n", cache->EAPI);
-	printf("PROPERTIES : %s\n", cache->PROPERTIES);
-}
-#endif
-
-static const char portcachedir_pms[] = "metadata/cache";
-static const char portcachedir_md5[] = "metadata/md5-cache";
-static const char portrepo_name[]    = "profiles/repo_name";
-cache_ctx *
-cache_open(const char *sroot, const char *portdir)
-{
-	cache_ctx *ret;
-	char buf[_Q_PATH_MAX];
-	char *repo = NULL;
-	size_t repolen = 0;
-
-	snprintf(buf, sizeof(buf), "%s%s/%s", sroot, portdir, portrepo_name);
-	if (eat_file(buf, &repo, &repolen)) {
-		(void)rmspace(repo);
-	} else {
-		repo = NULL;  /* ignore missing repo file */
-	}
-
-	snprintf(buf, sizeof(buf), "%s/%s", portdir, portcachedir_md5);
-	ret = vdb_open2(sroot, buf, true);
-	if (ret != NULL) {
-		ret->cachetype = CACHE_METADATA_MD5;
-		ret->repo = repo;
-		return ret;
-	}
-
-	snprintf(buf, sizeof(buf), "%s/%s", portdir, portcachedir_pms);
-	ret = vdb_open2(sroot, buf, true);
-	if (ret != NULL) {
-		ret->cachetype = CACHE_METADATA_PMS;
-		ret->repo = repo;
-		return ret;
-	}
-
-	ret = vdb_open2(sroot, portdir, true);
-	if (ret != NULL) {
-		ret->cachetype = CACHE_EBUILD;
-		ret->repo = repo;
-		return ret;
-	}
-
-	cache_close(ret);
-	warnf("could not open repository at %s (under root %s)", portdir, sroot);
-
-	return NULL;
-}
-
-void
-cache_close(cache_ctx *ctx)
-{
-	if (ctx->repo != NULL)
-		free(ctx->repo);
-	if (ctx->ebuilddir_ctx != NULL)
-		free(ctx->ebuilddir_ctx);
-	vdb_close(ctx);
-}
-
-cache_cat_ctx *
-cache_open_cat(cache_ctx *ctx, const char *name)
-{
-	return vdb_open_cat(ctx, name);
-}
-
-cache_cat_ctx *
-cache_next_cat(cache_ctx *ctx)
-{
-	return vdb_next_cat(ctx);
-}
-
-void
-cache_close_cat(cache_cat_ctx *cat_ctx)
-{
-	return vdb_close_cat(cat_ctx);
-}
-
-cache_pkg_ctx *
-cache_open_pkg(cache_cat_ctx *cat_ctx, const char *name)
-{
-	return vdb_open_pkg(cat_ctx, name);
-}
-
-cache_pkg_ctx *
-cache_next_pkg(cache_cat_ctx *cat_ctx)
-{
-	cache_ctx *ctx = (cache_ctx *)cat_ctx->ctx;
-	cache_pkg_ctx *ret = NULL;
-
-	if (ctx->cachetype == CACHE_EBUILD) {
-		char *p;
-
-		/* serve *.ebuild files each as separate pkg_ctx with name set
-		 * to CAT/P like in VDB and metadata */
-		do {
-			if (ctx->ebuilddir_pkg_ctx == NULL) {
-				vdb_ctx *pkgdir = ctx->ebuilddir_ctx;
-
-				if (pkgdir == NULL)
-					pkgdir = ctx->ebuilddir_ctx = xmalloc(sizeof(vdb_ctx));
-				memset(ctx->ebuilddir_ctx, '\0', sizeof(*ctx->ebuilddir_ctx));
-
-				if ((ctx->ebuilddir_pkg_ctx = vdb_next_pkg(cat_ctx)) == NULL)
-					return NULL;
-
-				pkgdir->portroot_fd = -1;
-				pkgdir->vdb_fd = cat_ctx->fd;
-				pkgdir->do_sort = ctx->do_sort;
-				pkgdir->catsortfunc = ctx->catsortfunc;
-				pkgdir->pkgsortfunc = ctx->pkgsortfunc;
-				pkgdir->repo = ctx->repo;
-				pkgdir->cachetype = ctx->cachetype;
-
-				ctx->ebuilddir_cat_ctx =
-					vdb_open_cat(pkgdir, ctx->ebuilddir_pkg_ctx->name);
-
-				/* opening might fail if what we found wasn't a
-				 * directory or something */
-				if (ctx->ebuilddir_cat_ctx == NULL) {
-					ctx->ebuilddir_pkg_ctx = NULL;
-					return NULL;
-				}
-
-				/* "zap" the pkg such that it looks like CAT/P */
-				ctx->ebuilddir_cat_ctx->name = cat_ctx->name;
-			}
-
-			ret = vdb_next_pkg(ctx->ebuilddir_cat_ctx);
-			if (ret == NULL) {
-				vdb_close_cat(ctx->ebuilddir_cat_ctx);
-				ctx->ebuilddir_pkg_ctx = NULL;
-			} else {
-				if ((p = strstr(ret->name, ".ebuild")) == NULL) {
-					cache_close_pkg(ret);
-					ret = NULL;
-				} else {
-					*p = '\0';
-				}
-			}
-		} while (ret == NULL);
-	} else {
-		ret = vdb_next_pkg(cat_ctx);
-	}
-
-	return ret;
-}
-
-static cache_pkg_meta *
-cache_read_file_pms(cache_pkg_ctx *pkg_ctx)
-{
-	struct stat s;
-	char *ptr;
-	FILE *f;
-	cache_pkg_meta *ret = NULL;
-	size_t len;
-	char buf[_Q_PATH_MAX];
-
-	if ((f = fdopen(pkg_ctx->fd, "r")) == NULL)
-		goto err;
-
-	if (fstat(pkg_ctx->fd, &s) != 0)
-		goto err;
-
-	len = sizeof(*ret) + s.st_size + 1;
-	ret = xzalloc(len);
-	ptr = (char*)ret;
-	ret->_data = ptr + sizeof(*ret);
-	if ((off_t)fread(ret->_data, 1, s.st_size, f) != s.st_size)
-		goto err;
-
-	ret->DEPEND = ret->_data;
-#define next_line(curr, next) \
-	if ((ptr = strchr(ret->curr, '\n')) == NULL) { \
-		warn("Invalid cache file for '%s'", buf); \
-		goto err; \
-	} \
-	ret->next = ptr+1; \
-	*ptr = '\0';
-	next_line(DEPEND, RDEPEND)
-	next_line(RDEPEND, SLOT)
-	next_line(SLOT, SRC_URI)
-	next_line(SRC_URI, RESTRICT)
-	next_line(RESTRICT, HOMEPAGE)
-	next_line(HOMEPAGE, LICENSE)
-	next_line(LICENSE, DESCRIPTION)
-	next_line(DESCRIPTION, KEYWORDS)
-	next_line(KEYWORDS, INHERITED)
-	next_line(INHERITED, IUSE)
-	next_line(IUSE, CDEPEND)
-	next_line(CDEPEND, PDEPEND)
-	next_line(PDEPEND, PROVIDE)
-	next_line(PROVIDE, EAPI)
-	next_line(EAPI, PROPERTIES)
-#undef next_line
-	ptr = strchr(ptr+1, '\n');
-	if (ptr == NULL) {
-		warn("Invalid cache file for '%s' - could not find end of cache data",
-				buf);
-		goto err;
-	}
-	*ptr = '\0';
-
-	fclose(f);
-	pkg_ctx->fd = -1;
-
-	return ret;
-
-err:
-	if (f)
-		fclose(f);
-	pkg_ctx->fd = -1;
-	if (ret)
-		cache_close_meta(ret);
-	return NULL;
-}
-
-static cache_pkg_meta *
-cache_read_file_md5(cache_pkg_ctx *pkg_ctx)
-{
-	struct stat s;
-	char *ptr, *endptr;
-	FILE *f;
-	cache_pkg_meta *ret = NULL;
-	size_t len;
-
-	if ((f = fdopen(pkg_ctx->fd, "r")) == NULL)
-		goto err;
-
-	if (fstat(pkg_ctx->fd, &s) != 0)
-		goto err;
-
-	len = sizeof(*ret) + s.st_size + 1;
-	ret = xzalloc(len);
-	ptr = (char*)ret;
-	ret->_data = ptr + sizeof(*ret);
-	if ((off_t)fread(ret->_data, 1, s.st_size, f) != s.st_size)
-		goto err;
-
-	/* We have a block of key=value\n data.
-	 * KEY=VALUE\n
-	 * Where KEY does NOT contain:
-	 * \0 \n =
-	 * And VALUE does NOT contain:
-	 * \0 \n
-	 * */
-#define assign_var_cmp(keyname, cmpkey) \
-	if (strncmp(keyptr, cmpkey, strlen(cmpkey)) == 0) { \
-		ret->keyname = valptr; \
-		continue; \
-	}
-#define assign_var(keyname) \
-	assign_var_cmp(keyname, #keyname);
-
-	ptr = ret->_data;
-	endptr = strchr(ptr, '\0');
-	if (endptr == NULL) {
-			warn("Invalid cache file for '%s/%s': "
-					"could not find end of cache data",
-					pkg_ctx->cat_ctx->name, pkg_ctx->name);
-			goto err;
-	}
-
-	while (ptr != NULL && ptr != endptr) {
-		char *keyptr;
-		char *valptr;
-		keyptr = ptr;
-		valptr = strchr(ptr, '=');
-		if (valptr == NULL) {
-			warn("Invalid cache file for '%s/%s': missing val",
-					pkg_ctx->cat_ctx->name, pkg_ctx->name);
-			goto err;
-		}
-		*valptr = '\0';
-		valptr++;
-		ptr = strchr(valptr, '\n');
-		if (ptr == NULL) {
-			warn("Invalid cache file for '%s/%s': missing key",
-					pkg_ctx->cat_ctx->name, pkg_ctx->name);
-			goto err;
-		}
-		*ptr = '\0';
-		ptr++;
-
-		assign_var(CDEPEND);
-		assign_var(DEPEND);
-		assign_var(DESCRIPTION);
-		assign_var(EAPI);
-		assign_var(HOMEPAGE);
-		assign_var(INHERITED);
-		assign_var(IUSE);
-		assign_var(KEYWORDS);
-		assign_var(LICENSE);
-		assign_var(PDEPEND);
-		assign_var(PROPERTIES);
-		assign_var(PROVIDE);
-		assign_var(RDEPEND);
-		assign_var(RESTRICT);
-		assign_var(SLOT);
-		assign_var(SRC_URI);
-		assign_var(DEFINED_PHASES);
-		assign_var(REQUIRED_USE);
-		assign_var(BDEPEND);
-		assign_var(_eclasses_);
-		assign_var(_md5_);
-		warn("Cache file for '%s/%s' has unknown key %s",
-				pkg_ctx->cat_ctx->name, pkg_ctx->name, keyptr);
-	}
-#undef assign_var
-#undef assign_var_cmp
-
-	fclose(f);
-	pkg_ctx->fd = -1;
-
-	return ret;
-
-err:
-	if (f)
-		fclose(f);
-	pkg_ctx->fd = -1;
-	if (ret)
-		cache_close_meta(ret);
-	return NULL;
-}
-
-static cache_pkg_meta *
-cache_read_file_ebuild(cache_pkg_ctx *pkg_ctx)
-{
-	FILE *f;
-	struct stat s;
-	cache_pkg_meta *ret = NULL;
-	size_t len;
-	char *p;
-	char *q;
-	char *w;
-	char **key;
-	bool esc;
-	bool findnl;
-
-	if ((f = fdopen(pkg_ctx->fd, "r")) == NULL)
-		goto err;
-
-	if (fstat(pkg_ctx->fd, &s) != 0)
-		goto err;
-
-	len = sizeof(*ret) + s.st_size + 1;
-	ret = xzalloc(len);
-	p = (char *)ret;
-	ret->_data = p + sizeof(*ret);
-	if ((off_t)fread(ret->_data, 1, s.st_size, f) != s.st_size)
-		goto err;
-
-	p = ret->_data;
-	do {
-		q = p;
-		while (*p >= 'A' && *p <= 'Z')
-			p++;
-
-		key = NULL;
-		if (q < p && *p == '=') {
-			*p++ = '\0';
-			/* match variable against which ones we look for */
-#define match_key(X) else if (strcmp(q, #X) == 0) key = &ret->X
-			if (1 == 0); /* dummy for syntax */
-			match_key(DEPEND);
-			match_key(RDEPEND);
-			match_key(SLOT);
-			match_key(SRC_URI);
-			match_key(RESTRICT);
-			match_key(HOMEPAGE);
-			match_key(LICENSE);
-			match_key(DESCRIPTION);
-			match_key(KEYWORDS);
-			match_key(IUSE);
-			match_key(CDEPEND);
-			match_key(PDEPEND);
-			match_key(EAPI);
-			match_key(REQUIRED_USE);
-#undef match_key
-		}
-
-		findnl = true;
-		if (key != NULL) {
-			q = p;
-			if (*q == '"' || *q == '\'') {
-				/* find matching quote */
-				p++;
-				w = p;
-				esc = false;
-				do {
-					while (*p != '\0' && *p != *q) {
-						if (*p == '\\') {
-							esc = !esc;
-							if (esc) {
-								p++;
-								continue;
-							}
-						} else {
-							/* implement line continuation (\ before newline) */
-							if (esc && (*p == '\n' || *p == '\r'))
-								*p = ' ';
-							esc = false;
-						}
-
-						*w++ = *p++;
-					}
-					if (*p == *q && esc) {
-						/* escaped, move along */
-						esc = false;
-						*w++ = *p++;
-						continue;
-					}
-					break;
-				} while (1);
-				q++;
-				*w = '\0';
-			} else {
-				/* find first whitespace */
-				while (!isspace((int)*p))
-					p++;
-				if (*p == '\n')
-					findnl = false;
-			}
-			*p++ = '\0';
-			*key = q;
-		}
-
-		if (findnl && (p = strchr(p, '\n')) != NULL)
-			p++;
-	} while (p != NULL);
-
-	fclose(f);
-	pkg_ctx->fd = -1;
-
-	return ret;
-
-err:
-	if (f)
-		fclose(f);
-	pkg_ctx->fd = -1;
-	if (ret)
-		cache_close_meta(ret);
-	return NULL;
-}
-
-cache_pkg_meta *
-cache_pkg_read(cache_pkg_ctx *pkg_ctx)
-{
-	cache_ctx *ctx = (cache_ctx *)(pkg_ctx->cat_ctx->ctx);
-
-	if (pkg_ctx->fd == -1) {
-		if (ctx->cachetype != CACHE_EBUILD) {
-			pkg_ctx->fd = openat(pkg_ctx->cat_ctx->fd, pkg_ctx->name,
-					O_RDONLY|O_CLOEXEC);
-		} else {
-			char *p = (char *)pkg_ctx->name;
-			p += strlen(p);
-			*p = '.';
-			pkg_ctx->fd = openat(pkg_ctx->cat_ctx->fd, pkg_ctx->name,
-					O_RDONLY|O_CLOEXEC);
-			*p = '\0';
-		}
-		if (pkg_ctx->fd == -1)
-			return NULL;
-	}
-
-	if (ctx->cachetype == CACHE_METADATA_MD5) {
-		return cache_read_file_md5(pkg_ctx);
-	} else if (ctx->cachetype == CACHE_METADATA_PMS) {
-		return cache_read_file_pms(pkg_ctx);
-	} else if (ctx->cachetype == CACHE_EBUILD) {
-		return cache_read_file_ebuild(pkg_ctx);
-	}
-
-	warn("Unknown metadata cache type!");
-	return NULL;
-}
-
-void
-cache_close_meta(cache_pkg_meta *cache)
-{
-	if (!cache)
-		errf("Cache is empty !");
-	free(cache);
-}
-
-cache_metadata_xml *
-cache_read_metadata(cache_pkg_ctx *pkg_ctx)
-{
-	cache_ctx *ctx = (cache_ctx *)(pkg_ctx->cat_ctx->ctx);
-	int fd;
-	FILE *f;
-	struct stat s;
-	char *xbuf;
-	char *p;
-	char *q;
-	size_t len;
-	cache_metadata_xml *ret = NULL;
-	struct elist *emailw = NULL;
-	char buf[_Q_PATH_MAX];
-
-	/* lame @$$ XML parsing, I don't want to pull in a real parser
-	 * library because we only retrieve one element for now: email
-	 * technically speaking, email may occur only once in a maintainer
-	 * tag, but practically speaking we don't care at all, so we can
-	 * just extract everything between <email> and </email> */
-
-	if (ctx->cachetype == CACHE_EBUILD) {
-		fd = openat(pkg_ctx->cat_ctx->fd, "metadata", O_RDONLY | O_CLOEXEC);
-	} else {
-		depend_atom *atom;
-		snprintf(buf, sizeof(buf), "%s/%s",
-				pkg_ctx->cat_ctx->name, pkg_ctx->name);
-		atom = atom_explode(buf);
-		snprintf(buf, sizeof(buf), "../../%s/%s/metadata.xml",
-				atom->CATEGORY, atom->PN);
-		atom_implode(atom);
-		fd = openat(ctx->vdb_fd, buf, O_RDONLY | O_CLOEXEC);
-	}
-
-	if (fd == -1)
-		return NULL;
-
-	if ((f = fdopen(fd, "r")) == NULL) {
-		close(fd);
-		return NULL;
-	}
-
-	if (fstat(fd, &s) != 0) {
-		fclose(f);
-		return NULL;
-	}
-
-	len = sizeof(*ret) + s.st_size + 1;
-	p = xbuf = xzalloc(len);
-	if ((off_t)fread(p, 1, s.st_size, f) != s.st_size) {
-		free(p);
-		fclose(f);
-		pkg_ctx->fd = -1;
-		return NULL;
-	}
-
-	ret = xmalloc(sizeof(*ret));
-	ret->email = NULL;
-
-	while ((q = strstr(p, "<email>")) != NULL) {
-		p = q + sizeof("<email>") - 1;
-		if ((q = strstr(p, "</email>")) == NULL)
-			break;
-		*q = '\0';
-		rmspace(p);
-		if (emailw == NULL) {
-			emailw = ret->email = xmalloc(sizeof(*emailw));
-		} else {
-			emailw = emailw->next = xmalloc(sizeof(*emailw));
-		}
-		emailw->next = NULL;
-		emailw->addr = xstrdup(p);
-		p = q + 1;
-	}
-
-	free(xbuf);
-	fclose(f);
-	return ret;
-}
-
-void
-cache_close_metadata(cache_metadata_xml *meta_ctx)
-{
-	struct elist *e;
-	while (meta_ctx->email != NULL) {
-		e = meta_ctx->email;
-		free(e->addr);
-		e = e->next;
-		free(meta_ctx->email);
-		meta_ctx->email = e;
-	}
-	free(meta_ctx);
-}
-
-void
-cache_close_pkg(cache_pkg_ctx *pkg_ctx)
-{
-	/* avoid free of cache_ctx' repo by vdb_close_pkg */
-	if (pkg_ctx->cat_ctx->ctx->repo == pkg_ctx->repo)
-		pkg_ctx->repo = NULL;
-
-	vdb_close_pkg(pkg_ctx);
-}
-
-static int
-cache_foreach_pkg_int(const char *sroot, const char *portdir,
-		vdb_pkg_cb callback, void *priv, vdb_cat_filter filter,
-		bool sort, void *catsortfunc, void *pkgsortfunc)
-{
-	cache_ctx *ctx;
-	cache_cat_ctx *cat_ctx;
-	cache_pkg_ctx *pkg_ctx;
-	int ret;
-
-	ctx = cache_open(sroot, portdir);
-	if (!ctx)
-		return EXIT_FAILURE;
-
-	ctx->do_sort = sort;
-	if (catsortfunc != NULL)
-		ctx->catsortfunc = catsortfunc;
-	if (pkgsortfunc != NULL)
-		ctx->pkgsortfunc = pkgsortfunc;
-
-	ret = 0;
-	while ((cat_ctx = cache_next_cat(ctx))) {
-		if (filter && !filter(cat_ctx, priv))
-			continue;
-		while ((pkg_ctx = cache_next_pkg(cat_ctx))) {
-			ret |= callback(pkg_ctx, priv);
-			cache_close_pkg(pkg_ctx);
-		}
-		cache_close_cat(cat_ctx);
-	}
-	cache_close(ctx);
-
-	return ret;
-}
-
-int
-cache_foreach_pkg(const char *sroot, const char *portdir,
-		vdb_pkg_cb callback, void *priv, vdb_cat_filter filter)
-{
-	return cache_foreach_pkg_int(sroot, portdir, callback, priv,
-			filter, false, NULL, NULL);
-}
-
-int
-cache_foreach_pkg_sorted(const char *sroot, const char *portdir,
-		vdb_pkg_cb callback, void *priv,
-		void *catsortfunc, void *pkgsortfunc)
-{
-	return cache_foreach_pkg_int(sroot, portdir, callback, priv,
-			NULL, true, catsortfunc, pkgsortfunc);
-}
diff --git a/libq/cache.h b/libq/cache.h
deleted file mode 100644
index e863daf6..00000000
--- a/libq/cache.h
+++ /dev/null
@@ -1,74 +0,0 @@
-/*
- * Copyright 2005-2019 Gentoo Foundation
- * Distributed under the terms of the GNU General Public License v2
- *
- * Copyright 2005-2010 Ned Ludd        - <solar@gentoo.org>
- * Copyright 2005-2014 Mike Frysinger  - <vapier@gentoo.org>
- * Copyright 2019-     Fabian Groffen  - <grobian@gentoo.org>
- */
-
-#ifndef _CACHE_H
-#define _CACHE_H 1
-
-#include "atom.h"
-#include "vdb.h"
-
-#define cache_ctx     vdb_ctx
-#define cache_cat_ctx vdb_cat_ctx
-#define cache_pkg_ctx vdb_pkg_ctx
-
-typedef struct {
-	char *_data;
-	char *DEPEND;        /* line 1 */
-	char *RDEPEND;
-	char *SLOT;
-	char *SRC_URI;
-	char *RESTRICT;      /* line 5 */
-	char *HOMEPAGE;
-	char *LICENSE;
-	char *DESCRIPTION;
-	char *KEYWORDS;
-	char *INHERITED;     /* line 10 */
-	char *IUSE;
-	char *CDEPEND;
-	char *PDEPEND;
-	char *PROVIDE;       /* line 14 */
-	char *EAPI;
-	char *PROPERTIES;
-	/* These are MD5-Cache only */
-	char *DEFINED_PHASES;
-	char *REQUIRED_USE;
-	char *BDEPEND;
-	char *_eclasses_;
-	char *_md5_;
-} cache_pkg_meta;
-
-typedef struct {
-	struct elist {
-		char *addr;
-		struct elist *next;
-	} *email;
-} cache_metadata_xml;
-
-typedef int (cache_pkg_cb)(cache_pkg_ctx *, void *priv);
-typedef int (cache_cat_filter)(cache_cat_ctx *, void *priv);
-
-cache_ctx *cache_open(const char *sroot, const char *portdir);
-void cache_close(cache_ctx *ctx);
-cache_cat_ctx *cache_open_cat(cache_ctx *ctx, const char *name);
-cache_cat_ctx *cache_next_cat(cache_ctx *ctx);
-void cache_close_cat(cache_cat_ctx *cat_ctx);
-cache_pkg_ctx *cache_open_pkg(cache_cat_ctx *cat_ctx, const char *name);
-cache_pkg_ctx *cache_next_pkg(cache_cat_ctx *cat_ctx);
-cache_pkg_meta *cache_pkg_read(cache_pkg_ctx *pkg_ctx);
-void cache_close_meta(cache_pkg_meta *cache);
-cache_metadata_xml *cache_read_metadata(cache_pkg_ctx *pkg_ctx);
-void cache_close_metadata(cache_metadata_xml *meta_ctx);
-void cache_close_pkg(cache_pkg_ctx *pkg_ctx);
-int cache_foreach_pkg(const char *sroot, const char *portdir,
-		cache_pkg_cb callback, void *priv, cache_cat_filter filter);
-int cache_foreach_pkg_sorted(const char *sroot, const char *portdir,
-		cache_pkg_cb callback, void *priv,
-		void *catsortfunc, void *pkgsortfunc);
-
-#endif
diff --git a/libq/tree.c b/libq/tree.c
new file mode 100644
index 00000000..bb7eefae
--- /dev/null
+++ b/libq/tree.c
@@ -0,0 +1,1066 @@
+/*
+ * Copyright 2005-2019 Gentoo Foundation
+ * Distributed under the terms of the GNU General Public License v2
+ *
+ * Copyright 2005-2008 Ned Ludd        - <solar@gentoo.org>
+ * Copyright 2005-2014 Mike Frysinger  - <vapier@gentoo.org>
+ * Copyright 2018-     Fabian Groffen  - <grobian@gentoo.org>
+ */
+
+#include "main.h"
+
+#include <fcntl.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <ctype.h>
+#include <xalloc.h>
+
+#include "atom.h"
+#include "eat_file.h"
+#include "rmspace.h"
+#include "scandirat.h"
+#include "set.h"
+#include "tree.h"
+
+#include <ctype.h>
+#include <xalloc.h>
+
+static tree_ctx *
+tree_open_int(const char *sroot, const char *tdir, bool quiet)
+{
+	tree_ctx *ctx = xmalloc(sizeof(*ctx));
+
+	ctx->portroot_fd = open(sroot, O_RDONLY | O_CLOEXEC | O_PATH);
+	if (ctx->portroot_fd == -1) {
+		if (!quiet)
+			warnp("could not open root: %s", sroot);
+		goto f_error;
+	}
+
+	/* Skip the leading slash */
+	tdir++;
+	if (*tdir == '\0')
+		tdir = ".";
+	/* Cannot use O_PATH as we want to use fdopendir() */
+	ctx->tree_fd = openat(ctx->portroot_fd, tdir, O_RDONLY | O_CLOEXEC);
+	if (ctx->tree_fd == -1) {
+		if (!quiet)
+			warnp("could not open tree: %s (in root %s)", tdir, sroot);
+		goto cp_error;
+	}
+
+	ctx->dir = fdopendir(ctx->tree_fd);
+	if (ctx->dir == NULL)
+		goto cv_error;
+
+	ctx->do_sort = false;
+	ctx->cat_de = NULL;
+	ctx->catsortfunc = alphasort;
+	ctx->pkgsortfunc = alphasort;
+	ctx->repo = NULL;
+	ctx->ebuilddir_ctx = NULL;
+	ctx->ebuilddir_pkg_ctx = NULL;
+	return ctx;
+
+ cv_error:
+	close(ctx->tree_fd);
+ cp_error:
+	close(ctx->portroot_fd);
+ f_error:
+	free(ctx);
+	return NULL;
+}
+
+static const char portcachedir_pms[] = "metadata/cache";
+static const char portcachedir_md5[] = "metadata/md5-cache";
+static const char portrepo_name[]    = "profiles/repo_name";
+tree_ctx *
+tree_open(const char *sroot, const char *portdir)
+{
+	tree_ctx *ret;
+	char buf[_Q_PATH_MAX];
+	char *repo = NULL;
+	size_t repolen = 0;
+
+	snprintf(buf, sizeof(buf), "%s%s/%s", sroot, portdir, portrepo_name);
+	if (eat_file(buf, &repo, &repolen)) {
+		(void)rmspace(repo);
+	} else {
+		repo = NULL;  /* ignore missing repo file */
+	}
+
+	snprintf(buf, sizeof(buf), "%s/%s", portdir, portcachedir_md5);
+	ret = tree_open_int(sroot, buf, true);
+	if (ret != NULL) {
+		ret->cachetype = CACHE_METADATA_MD5;
+		ret->repo = repo;
+		return ret;
+	}
+
+	snprintf(buf, sizeof(buf), "%s/%s", portdir, portcachedir_pms);
+	ret = tree_open_int(sroot, buf, true);
+	if (ret != NULL) {
+		ret->cachetype = CACHE_METADATA_PMS;
+		ret->repo = repo;
+		return ret;
+	}
+
+	ret = tree_open_int(sroot, portdir, true);
+	if (ret != NULL) {
+		ret->cachetype = CACHE_EBUILD;
+		ret->repo = repo;
+		return ret;
+	}
+
+	tree_close(ret);
+	warnf("could not open repository at %s (under root %s)", portdir, sroot);
+
+	return NULL;
+}
+
+tree_ctx *
+tree_open_vdb(const char *sroot, const char *svdb)
+{
+	tree_ctx *ret = tree_open_int(sroot, svdb, false);
+	if (ret != NULL)
+		ret->cachetype = CACHE_VDB;
+	return ret;
+}
+
+void
+tree_close(tree_ctx *ctx)
+{
+	closedir(ctx->dir);
+	/* closedir() above does this for us: */
+	/* close(ctx->tree_fd); */
+	close(ctx->portroot_fd);
+	if (ctx->do_sort)
+		scandir_free(ctx->cat_de, ctx->cat_cnt);
+	if (ctx->repo != NULL)
+		free(ctx->repo);
+	if (ctx->ebuilddir_ctx != NULL)
+		free(ctx->ebuilddir_ctx);
+	free(ctx);
+}
+
+int
+tree_filter_cat(const struct dirent *de)
+{
+	int i;
+	bool founddash;
+
+#ifdef DT_UNKNOWN
+	/* cat must be a dir */
+	if (de->d_type != DT_UNKNOWN &&
+	    de->d_type != DT_DIR &&
+	    de->d_type != DT_LNK)
+		return 0;
+#endif
+
+	/* PMS 3.1.1 */
+	founddash = false;
+	for (i = 0; de->d_name[i] != '\0'; i++) {
+		switch (de->d_name[i]) {
+			case '_':
+				break;
+			case '-':
+				founddash = true;
+				/* fall through */
+			case '+':
+			case '.':
+				if (i)
+					break;
+				return 0;
+			default:
+				if ((de->d_name[i] >= 'A' && de->d_name[i] <= 'Z') ||
+						(de->d_name[i] >= 'a' && de->d_name[i] <= 'z') ||
+						(de->d_name[i] >= '0' && de->d_name[i] <= '9'))
+					break;
+				return 0;
+		}
+	}
+	if (!founddash && strcmp(de->d_name, "virtual") != 0)
+		return 0;
+
+	return i;
+}
+
+tree_cat_ctx *
+tree_open_cat(tree_ctx *ctx, const char *name)
+{
+	tree_cat_ctx *cat_ctx;
+	int fd;
+	DIR *dir;
+
+	/* Cannot use O_PATH as we want to use fdopendir() */
+	fd = openat(ctx->tree_fd, name, O_RDONLY | O_CLOEXEC);
+	if (fd == -1)
+		return NULL;
+
+	dir = fdopendir(fd);
+	if (!dir) {
+		close(fd);
+		return NULL;
+	}
+
+	cat_ctx = xmalloc(sizeof(*cat_ctx));
+	cat_ctx->name = name;
+	cat_ctx->fd = fd;
+	cat_ctx->dir = dir;
+	cat_ctx->ctx = ctx;
+	cat_ctx->pkg_de = NULL;
+	return cat_ctx;
+}
+
+tree_cat_ctx *
+tree_next_cat(tree_ctx *ctx)
+{
+	/* search for a category directory */
+	tree_cat_ctx *cat_ctx = NULL;
+
+	if (ctx->do_sort) {
+		if (ctx->cat_de == NULL) {
+			ctx->cat_cnt = scandirat(ctx->tree_fd,
+					".", &ctx->cat_de, tree_filter_cat, ctx->catsortfunc);
+			ctx->cat_cur = 0;
+		}
+
+		while (ctx->cat_cur < ctx->cat_cnt) {
+			cat_ctx = tree_open_cat(ctx, ctx->cat_de[ctx->cat_cur++]->d_name);
+			if (!cat_ctx)
+				continue;
+			break;
+		}
+	} else {
+		/* cheaper "streaming" variant */
+		const struct dirent *de;
+		do {
+			de = readdir(ctx->dir);
+			if (!de)
+				break;
+
+			if (tree_filter_cat(de) == 0)
+				continue;
+
+			cat_ctx = tree_open_cat(ctx, de->d_name);
+			if (!cat_ctx)
+				continue;
+
+			break;
+		} while (1);
+	}
+
+	return cat_ctx;
+}
+
+void
+tree_close_cat(tree_cat_ctx *cat_ctx)
+{
+	closedir(cat_ctx->dir);
+	/* closedir() above does this for us: */
+	/* close(ctx->fd); */
+	if (cat_ctx->ctx->do_sort)
+		scandir_free(cat_ctx->pkg_de, cat_ctx->pkg_cnt);
+	free(cat_ctx);
+}
+
+int
+tree_filter_pkg(const struct dirent *de)
+{
+	int i;
+	bool founddash = false;
+
+	/* PMS 3.1.2 */
+	for (i = 0; de->d_name[i] != '\0'; i++) {
+		switch (de->d_name[i]) {
+			case '_':
+				break;
+			case '-':
+				founddash = true;
+				/* fall through */
+			case '+':
+				if (i)
+					break;
+				return 0;
+			default:
+				if ((de->d_name[i] >= 'A' && de->d_name[i] <= 'Z') ||
+						(de->d_name[i] >= 'a' && de->d_name[i] <= 'z') ||
+						(de->d_name[i] >= '0' && de->d_name[i] <= '9'))
+					break;
+				if (founddash)
+					return 1;
+				return 0;
+		}
+	}
+
+	return i;
+}
+
+tree_pkg_ctx *
+tree_open_pkg(tree_cat_ctx *cat_ctx, const char *name)
+{
+	tree_pkg_ctx *pkg_ctx = xmalloc(sizeof(*pkg_ctx));
+	pkg_ctx->name = name;
+	pkg_ctx->slot = NULL;
+	pkg_ctx->repo = cat_ctx->ctx->repo;
+	pkg_ctx->fd = -1;
+	pkg_ctx->cat_ctx = cat_ctx;
+	pkg_ctx->atom = NULL;
+	return pkg_ctx;
+}
+
+static tree_pkg_ctx *
+tree_next_pkg_int(tree_cat_ctx *cat_ctx);
+static tree_pkg_ctx *
+tree_next_pkg_int(tree_cat_ctx *cat_ctx)
+{
+	tree_pkg_ctx *pkg_ctx = NULL;
+
+	if (cat_ctx->ctx->do_sort) {
+		if (cat_ctx->pkg_de == NULL) {
+			cat_ctx->pkg_cnt = scandirat(cat_ctx->fd, ".", &cat_ctx->pkg_de,
+					tree_filter_pkg, cat_ctx->ctx->pkgsortfunc);
+			cat_ctx->pkg_cur = 0;
+		}
+
+		while (cat_ctx->pkg_cur < cat_ctx->pkg_cnt) {
+			pkg_ctx =
+				tree_open_pkg(cat_ctx,
+						cat_ctx->pkg_de[cat_ctx->pkg_cur++]->d_name);
+			if (!pkg_ctx)
+				continue;
+			break;
+		}
+	} else {
+		const struct dirent *de;
+		do {
+			de = readdir(cat_ctx->dir);
+			if (!de)
+				break;
+
+			if (tree_filter_pkg(de) == 0)
+				continue;
+
+			pkg_ctx = tree_open_pkg(cat_ctx, de->d_name);
+			if (!pkg_ctx)
+				continue;
+
+			break;
+		} while (1);
+	}
+
+	return pkg_ctx;
+}
+
+tree_pkg_ctx *
+tree_next_pkg(tree_cat_ctx *cat_ctx)
+{
+	tree_ctx *ctx = cat_ctx->ctx;
+	tree_pkg_ctx *ret = NULL;
+
+	if (ctx->cachetype == CACHE_EBUILD) {
+		char *p;
+
+		/* serve *.ebuild files each as separate pkg_ctx with name set
+		 * to CAT/P like in VDB and metadata */
+		do {
+			if (ctx->ebuilddir_pkg_ctx == NULL) {
+				tree_ctx *pkgdir = ctx->ebuilddir_ctx;
+
+				if (pkgdir == NULL)
+					pkgdir = ctx->ebuilddir_ctx = xmalloc(sizeof(tree_ctx));
+				memset(ctx->ebuilddir_ctx, '\0', sizeof(*ctx->ebuilddir_ctx));
+
+				ctx->ebuilddir_pkg_ctx = tree_next_pkg_int(cat_ctx);
+				if (ctx->ebuilddir_pkg_ctx == NULL)
+					return NULL;
+
+				pkgdir->portroot_fd = -1;
+				pkgdir->tree_fd = cat_ctx->fd;
+				pkgdir->do_sort = ctx->do_sort;
+				pkgdir->catsortfunc = ctx->catsortfunc;
+				pkgdir->pkgsortfunc = ctx->pkgsortfunc;
+				pkgdir->repo = ctx->repo;
+				pkgdir->cachetype = ctx->cachetype;
+
+				ctx->ebuilddir_cat_ctx =
+					tree_open_cat(pkgdir, ctx->ebuilddir_pkg_ctx->name);
+
+				/* opening might fail if what we found wasn't a
+				 * directory or something */
+				if (ctx->ebuilddir_cat_ctx == NULL) {
+					ctx->ebuilddir_pkg_ctx = NULL;
+					return NULL;
+				}
+
+				/* "zap" the pkg such that it looks like CAT/P */
+				ctx->ebuilddir_cat_ctx->name = cat_ctx->name;
+			}
+
+			ret = tree_next_pkg_int(ctx->ebuilddir_cat_ctx);
+			if (ret == NULL) {
+				tree_close_cat(ctx->ebuilddir_cat_ctx);
+				ctx->ebuilddir_pkg_ctx = NULL;
+			} else {
+				if ((p = strstr(ret->name, ".ebuild")) == NULL) {
+					tree_close_pkg(ret);
+					ret = NULL;
+				} else {
+					*p = '\0';
+				}
+			}
+		} while (ret == NULL);
+	} else {
+		ret = tree_next_pkg_int(cat_ctx);
+	}
+
+	return ret;
+}
+
+int
+tree_pkg_vdb_openat(
+		tree_pkg_ctx *pkg_ctx,
+		const char *file,
+		int flags, mode_t mode)
+{
+	if (pkg_ctx->fd == -1) {
+		pkg_ctx->fd = openat(pkg_ctx->cat_ctx->fd, pkg_ctx->name,
+				O_RDONLY | O_CLOEXEC | O_PATH);
+		if (pkg_ctx->fd == -1)
+			return -1;
+	}
+
+	return openat(pkg_ctx->fd, file, flags | O_CLOEXEC, mode);
+}
+
+FILE *
+tree_pkg_vdb_fopenat(
+		tree_pkg_ctx *pkg_ctx,
+		const char *file,
+		int flags,
+		mode_t mode,
+		const char *fmode)
+{
+	FILE *fp;
+	int fd;
+
+	fd = tree_pkg_vdb_openat(pkg_ctx, file, flags, mode);
+	if (fd == -1)
+		return NULL;
+
+	fp = fdopen(fd, fmode);
+	if (!fp)
+		close(fd);
+
+	return fp;
+}
+
+bool
+tree_pkg_vdb_eat(
+		tree_pkg_ctx *pkg_ctx,
+		const char *file,
+		char **bufptr,
+		size_t *buflen)
+{
+	int fd = tree_pkg_vdb_openat(pkg_ctx, file, O_RDONLY, 0);
+	bool ret = eat_file_fd(fd, bufptr, buflen);
+	rmspace(*bufptr);
+	if (fd != -1)
+		close(fd);
+	return ret;
+}
+
+static tree_pkg_meta *
+tree_read_file_pms(tree_pkg_ctx *pkg_ctx)
+{
+	struct stat s;
+	char *ptr;
+	FILE *f;
+	tree_pkg_meta *ret = NULL;
+	size_t len;
+	char buf[_Q_PATH_MAX];
+
+	if ((f = fdopen(pkg_ctx->fd, "r")) == NULL)
+		goto err;
+
+	if (fstat(pkg_ctx->fd, &s) != 0)
+		goto err;
+
+	len = sizeof(*ret) + s.st_size + 1;
+	ret = xzalloc(len);
+	ptr = (char*)ret;
+	ret->_data = ptr + sizeof(*ret);
+	if ((off_t)fread(ret->_data, 1, s.st_size, f) != s.st_size)
+		goto err;
+
+	ret->DEPEND = ret->_data;
+#define next_line(curr, next) \
+	if ((ptr = strchr(ret->curr, '\n')) == NULL) { \
+		warn("Invalid cache file for '%s'", buf); \
+		goto err; \
+	} \
+	ret->next = ptr+1; \
+	*ptr = '\0';
+	next_line(DEPEND, RDEPEND)
+	next_line(RDEPEND, SLOT)
+	next_line(SLOT, SRC_URI)
+	next_line(SRC_URI, RESTRICT)
+	next_line(RESTRICT, HOMEPAGE)
+	next_line(HOMEPAGE, LICENSE)
+	next_line(LICENSE, DESCRIPTION)
+	next_line(DESCRIPTION, KEYWORDS)
+	next_line(KEYWORDS, INHERITED)
+	next_line(INHERITED, IUSE)
+	next_line(IUSE, CDEPEND)
+	next_line(CDEPEND, PDEPEND)
+	next_line(PDEPEND, PROVIDE)
+	next_line(PROVIDE, EAPI)
+	next_line(EAPI, PROPERTIES)
+#undef next_line
+	ptr = strchr(ptr+1, '\n');
+	if (ptr == NULL) {
+		warn("Invalid cache file for '%s' - could not find end of cache data",
+				buf);
+		goto err;
+	}
+	*ptr = '\0';
+
+	fclose(f);
+	pkg_ctx->fd = -1;
+
+	return ret;
+
+err:
+	if (f)
+		fclose(f);
+	pkg_ctx->fd = -1;
+	if (ret)
+		tree_close_meta(ret);
+	return NULL;
+}
+
+static tree_pkg_meta *
+tree_read_file_md5(tree_pkg_ctx *pkg_ctx)
+{
+	struct stat s;
+	char *ptr, *endptr;
+	FILE *f;
+	tree_pkg_meta *ret = NULL;
+	size_t len;
+
+	if ((f = fdopen(pkg_ctx->fd, "r")) == NULL)
+		goto err;
+
+	if (fstat(pkg_ctx->fd, &s) != 0)
+		goto err;
+
+	len = sizeof(*ret) + s.st_size + 1;
+	ret = xzalloc(len);
+	ptr = (char*)ret;
+	ret->_data = ptr + sizeof(*ret);
+	if ((off_t)fread(ret->_data, 1, s.st_size, f) != s.st_size)
+		goto err;
+
+	/* We have a block of key=value\n data.
+	 * KEY=VALUE\n
+	 * Where KEY does NOT contain:
+	 * \0 \n =
+	 * And VALUE does NOT contain:
+	 * \0 \n
+	 * */
+#define assign_var_cmp(keyname, cmpkey) \
+	if (strncmp(keyptr, cmpkey, strlen(cmpkey)) == 0) { \
+		ret->keyname = valptr; \
+		continue; \
+	}
+#define assign_var(keyname) \
+	assign_var_cmp(keyname, #keyname);
+
+	ptr = ret->_data;
+	endptr = strchr(ptr, '\0');
+	if (endptr == NULL) {
+			warn("Invalid cache file for '%s/%s': "
+					"could not find end of cache data",
+					pkg_ctx->cat_ctx->name, pkg_ctx->name);
+			goto err;
+	}
+
+	while (ptr != NULL && ptr != endptr) {
+		char *keyptr;
+		char *valptr;
+		keyptr = ptr;
+		valptr = strchr(ptr, '=');
+		if (valptr == NULL) {
+			warn("Invalid cache file for '%s/%s': missing val",
+					pkg_ctx->cat_ctx->name, pkg_ctx->name);
+			goto err;
+		}
+		*valptr = '\0';
+		valptr++;
+		ptr = strchr(valptr, '\n');
+		if (ptr == NULL) {
+			warn("Invalid cache file for '%s/%s': missing key",
+					pkg_ctx->cat_ctx->name, pkg_ctx->name);
+			goto err;
+		}
+		*ptr = '\0';
+		ptr++;
+
+		assign_var(CDEPEND);
+		assign_var(DEPEND);
+		assign_var(DESCRIPTION);
+		assign_var(EAPI);
+		assign_var(HOMEPAGE);
+		assign_var(INHERITED);
+		assign_var(IUSE);
+		assign_var(KEYWORDS);
+		assign_var(LICENSE);
+		assign_var(PDEPEND);
+		assign_var(PROPERTIES);
+		assign_var(PROVIDE);
+		assign_var(RDEPEND);
+		assign_var(RESTRICT);
+		assign_var(SLOT);
+		assign_var(SRC_URI);
+		assign_var(DEFINED_PHASES);
+		assign_var(REQUIRED_USE);
+		assign_var(BDEPEND);
+		assign_var(_eclasses_);
+		assign_var(_md5_);
+		warn("Cache file for '%s/%s' has unknown key %s",
+				pkg_ctx->cat_ctx->name, pkg_ctx->name, keyptr);
+	}
+#undef assign_var
+#undef assign_var_cmp
+
+	fclose(f);
+	pkg_ctx->fd = -1;
+
+	return ret;
+
+err:
+	if (f)
+		fclose(f);
+	pkg_ctx->fd = -1;
+	if (ret)
+		tree_close_meta(ret);
+	return NULL;
+}
+
+static tree_pkg_meta *
+tree_read_file_ebuild(tree_pkg_ctx *pkg_ctx)
+{
+	FILE *f;
+	struct stat s;
+	tree_pkg_meta *ret = NULL;
+	size_t len;
+	char *p;
+	char *q;
+	char *w;
+	char **key;
+	bool esc;
+	bool findnl;
+
+	if ((f = fdopen(pkg_ctx->fd, "r")) == NULL)
+		goto err;
+
+	if (fstat(pkg_ctx->fd, &s) != 0)
+		goto err;
+
+	len = sizeof(*ret) + s.st_size + 1;
+	ret = xzalloc(len);
+	p = (char *)ret;
+	ret->_data = p + sizeof(*ret);
+	if ((off_t)fread(ret->_data, 1, s.st_size, f) != s.st_size)
+		goto err;
+
+	p = ret->_data;
+	do {
+		q = p;
+		while (*p >= 'A' && *p <= 'Z')
+			p++;
+
+		key = NULL;
+		if (q < p && *p == '=') {
+			*p++ = '\0';
+			/* match variable against which ones we look for */
+#define match_key(X) else if (strcmp(q, #X) == 0) key = &ret->X
+			if (1 == 0); /* dummy for syntax */
+			match_key(DEPEND);
+			match_key(RDEPEND);
+			match_key(SLOT);
+			match_key(SRC_URI);
+			match_key(RESTRICT);
+			match_key(HOMEPAGE);
+			match_key(LICENSE);
+			match_key(DESCRIPTION);
+			match_key(KEYWORDS);
+			match_key(IUSE);
+			match_key(CDEPEND);
+			match_key(PDEPEND);
+			match_key(EAPI);
+			match_key(REQUIRED_USE);
+#undef match_key
+		}
+
+		findnl = true;
+		if (key != NULL) {
+			q = p;
+			if (*q == '"' || *q == '\'') {
+				/* find matching quote */
+				p++;
+				w = p;
+				esc = false;
+				do {
+					while (*p != '\0' && *p != *q) {
+						if (*p == '\\') {
+							esc = !esc;
+							if (esc) {
+								p++;
+								continue;
+							}
+						} else {
+							/* implement line continuation (\ before newline) */
+							if (esc && (*p == '\n' || *p == '\r'))
+								*p = ' ';
+							esc = false;
+						}
+
+						*w++ = *p++;
+					}
+					if (*p == *q && esc) {
+						/* escaped, move along */
+						esc = false;
+						*w++ = *p++;
+						continue;
+					}
+					break;
+				} while (1);
+				q++;
+				*w = '\0';
+			} else {
+				/* find first whitespace */
+				while (!isspace((int)*p))
+					p++;
+				if (*p == '\n')
+					findnl = false;
+			}
+			*p++ = '\0';
+			*key = q;
+		}
+
+		if (findnl && (p = strchr(p, '\n')) != NULL)
+			p++;
+	} while (p != NULL);
+
+	fclose(f);
+	pkg_ctx->fd = -1;
+
+	return ret;
+
+err:
+	if (f)
+		fclose(f);
+	pkg_ctx->fd = -1;
+	if (ret)
+		tree_close_meta(ret);
+	return NULL;
+}
+
+tree_pkg_meta *
+tree_pkg_read(tree_pkg_ctx *pkg_ctx)
+{
+	tree_ctx *ctx = pkg_ctx->cat_ctx->ctx;
+
+	if (pkg_ctx->fd == -1) {
+		if (ctx->cachetype != CACHE_EBUILD) {
+			pkg_ctx->fd = openat(pkg_ctx->cat_ctx->fd, pkg_ctx->name,
+					O_RDONLY | O_CLOEXEC);
+		} else {
+			char *p = (char *)pkg_ctx->name;
+			p += strlen(p);
+			*p = '.';
+			pkg_ctx->fd = openat(pkg_ctx->cat_ctx->fd, pkg_ctx->name,
+					O_RDONLY | O_CLOEXEC);
+			*p = '\0';
+		}
+		if (pkg_ctx->fd == -1)
+			return NULL;
+	}
+
+	if (ctx->cachetype == CACHE_METADATA_MD5) {
+		return tree_read_file_md5(pkg_ctx);
+	} else if (ctx->cachetype == CACHE_METADATA_PMS) {
+		return tree_read_file_pms(pkg_ctx);
+	} else if (ctx->cachetype == CACHE_EBUILD) {
+		return tree_read_file_ebuild(pkg_ctx);
+	}
+
+	warn("Unknown metadata cache type!");
+	return NULL;
+}
+
+void
+tree_close_meta(tree_pkg_meta *cache)
+{
+	if (!cache)
+		errf("Cache is empty !");
+	free(cache);
+}
+
+tree_metadata_xml *
+tree_pkg_metadata(tree_pkg_ctx *pkg_ctx)
+{
+	tree_ctx *ctx = pkg_ctx->cat_ctx->ctx;
+	int fd;
+	FILE *f;
+	struct stat s;
+	char *xbuf;
+	char *p;
+	char *q;
+	size_t len;
+	tree_metadata_xml *ret = NULL;
+	struct elist *emailw = NULL;
+	char buf[_Q_PATH_MAX];
+
+	/* lame @$$ XML parsing, I don't want to pull in a real parser
+	 * library because we only retrieve one element for now: email
+	 * technically speaking, email may occur only once in a maintainer
+	 * tag, but practically speaking we don't care at all, so we can
+	 * just extract everything between <email> and </email> */
+
+	if (ctx->cachetype == CACHE_EBUILD) {
+		fd = openat(pkg_ctx->cat_ctx->fd, "metadata", O_RDONLY | O_CLOEXEC);
+	} else {
+		depend_atom *atom;
+		snprintf(buf, sizeof(buf), "%s/%s",
+				pkg_ctx->cat_ctx->name, pkg_ctx->name);
+		atom = atom_explode(buf);
+		snprintf(buf, sizeof(buf), "../../%s/%s/metadata.xml",
+				atom->CATEGORY, atom->PN);
+		atom_implode(atom);
+		fd = openat(ctx->tree_fd, buf, O_RDONLY | O_CLOEXEC);
+	}
+
+	if (fd == -1)
+		return NULL;
+
+	if ((f = fdopen(fd, "r")) == NULL) {
+		close(fd);
+		return NULL;
+	}
+
+	if (fstat(fd, &s) != 0) {
+		fclose(f);
+		return NULL;
+	}
+
+	len = sizeof(*ret) + s.st_size + 1;
+	p = xbuf = xzalloc(len);
+	if ((off_t)fread(p, 1, s.st_size, f) != s.st_size) {
+		free(p);
+		fclose(f);
+		pkg_ctx->fd = -1;
+		return NULL;
+	}
+
+	ret = xmalloc(sizeof(*ret));
+	ret->email = NULL;
+
+	while ((q = strstr(p, "<email>")) != NULL) {
+		p = q + sizeof("<email>") - 1;
+		if ((q = strstr(p, "</email>")) == NULL)
+			break;
+		*q = '\0';
+		rmspace(p);
+		if (emailw == NULL) {
+			emailw = ret->email = xmalloc(sizeof(*emailw));
+		} else {
+			emailw = emailw->next = xmalloc(sizeof(*emailw));
+		}
+		emailw->next = NULL;
+		emailw->addr = xstrdup(p);
+		p = q + 1;
+	}
+
+	free(xbuf);
+	fclose(f);
+	return ret;
+}
+
+void
+tree_close_metadata(tree_metadata_xml *meta_ctx)
+{
+	struct elist *e;
+	while (meta_ctx->email != NULL) {
+		e = meta_ctx->email;
+		free(e->addr);
+		e = e->next;
+		free(meta_ctx->email);
+		meta_ctx->email = e;
+	}
+	free(meta_ctx);
+}
+
+void
+tree_close_pkg(tree_pkg_ctx *pkg_ctx)
+{
+	if (pkg_ctx->fd != -1)
+		close(pkg_ctx->fd);
+	if (pkg_ctx->atom != NULL)
+		atom_implode(pkg_ctx->atom);
+	/* avoid freeing tree_ctx' repo */
+	if (pkg_ctx->cat_ctx->ctx->repo != pkg_ctx->repo)
+		free(pkg_ctx->repo);
+	free(pkg_ctx->slot);
+	free(pkg_ctx);
+}
+
+int
+tree_foreach_pkg(tree_ctx *ctx,
+		tree_pkg_cb callback, void *priv, tree_cat_filter filter,
+		bool sort, void *catsortfunc, void *pkgsortfunc)
+{
+	tree_cat_ctx *cat_ctx;
+	tree_pkg_ctx *pkg_ctx;
+	int ret;
+
+	if (ctx == NULL)
+		return EXIT_FAILURE;
+
+	ctx->do_sort = sort;
+	if (catsortfunc != NULL)
+		ctx->catsortfunc = catsortfunc;
+	if (pkgsortfunc != NULL)
+		ctx->pkgsortfunc = pkgsortfunc;
+
+	ret = 0;
+	while ((cat_ctx = tree_next_cat(ctx))) {
+		if (filter && !filter(cat_ctx, priv))
+			continue;
+		while ((pkg_ctx = tree_next_pkg(cat_ctx))) {
+			ret |= callback(pkg_ctx, priv);
+			tree_close_pkg(pkg_ctx);
+		}
+		tree_close_cat(cat_ctx);
+	}
+
+	return ret;
+}
+
+depend_atom *
+tree_get_atom(tree_pkg_ctx *pkg_ctx, bool complete)
+{
+	if (pkg_ctx->atom == NULL) {
+		pkg_ctx->atom = atom_explode(pkg_ctx->name);
+		if (pkg_ctx->atom == NULL)
+			return NULL;
+		pkg_ctx->atom->CATEGORY = (char *)pkg_ctx->cat_ctx->name;
+	}
+
+	if (complete) {
+		tree_ctx *ctx = pkg_ctx->cat_ctx->ctx;
+		if (ctx->cachetype == CACHE_VDB) {
+			if (pkg_ctx->atom->SLOT == NULL) {
+				tree_pkg_vdb_eat(pkg_ctx, "SLOT",
+						&pkg_ctx->slot, &pkg_ctx->slot_len);
+				pkg_ctx->atom->SLOT = pkg_ctx->slot;
+			}
+			if (pkg_ctx->atom->REPO == NULL) {
+				tree_pkg_vdb_eat(pkg_ctx, "repository",
+						&pkg_ctx->repo, &pkg_ctx->repo_len);
+				pkg_ctx->atom->REPO = pkg_ctx->repo;
+			}
+		} else { /* metadata or ebuild */
+			if (pkg_ctx->atom->SLOT == NULL) {
+				tree_pkg_meta *meta = tree_pkg_read(pkg_ctx);
+				if (meta != NULL) {
+					pkg_ctx->slot = xstrdup(meta->SLOT);
+					pkg_ctx->slot_len = strlen(pkg_ctx->slot);
+					pkg_ctx->atom->SLOT = pkg_ctx->slot;
+					tree_close_meta(meta);
+				}
+			}
+			/* repo is set from the tree, when found */
+			if (pkg_ctx->atom->REPO == NULL)
+				pkg_ctx->atom->REPO = pkg_ctx->repo;
+		}
+	}
+
+	return pkg_ctx->atom;
+}
+
+set *
+tree_get_vdb_atoms(const char *sroot, const char *svdb, int fullcpv)
+{
+	tree_ctx *ctx;
+
+	int cfd, j;
+	int dfd, i;
+
+	char buf[_Q_PATH_MAX];
+	char slot[_Q_PATH_MAX];
+	char *slotp = slot;
+	size_t slot_len;
+
+	struct dirent **cat;
+	struct dirent **pf;
+
+	depend_atom *atom = NULL;
+	set *cpf = NULL;
+
+	ctx = tree_open_vdb(sroot, svdb);
+	if (!ctx)
+		return NULL;
+
+	/* scan the cat first */
+	cfd = scandirat(ctx->tree_fd, ".", &cat, tree_filter_cat, alphasort);
+	if (cfd < 0)
+		goto fuckit;
+
+	for (j = 0; j < cfd; j++) {
+		dfd = scandirat(ctx->tree_fd, cat[j]->d_name,
+				&pf, tree_filter_pkg, alphasort);
+		if (dfd < 0)
+			continue;
+		for (i = 0; i < dfd; i++) {
+			int blen = snprintf(buf, sizeof(buf), "%s/%s/SLOT",
+					cat[j]->d_name, pf[i]->d_name);
+			if (blen < 0 || (size_t)blen >= sizeof(buf)) {
+				warnf("unable to parse long package: %s/%s",
+						cat[j]->d_name, pf[i]->d_name);
+				continue;
+			}
+
+			/* Chop the SLOT for the atom parsing. */
+			buf[blen - 5] = '\0';
+			if ((atom = atom_explode(buf)) == NULL)
+				continue;
+			/* Restore the SLOT. */
+			buf[blen - 5] = '/';
+
+			slot_len = sizeof(slot);
+			eat_file_at(ctx->tree_fd, buf, &slotp, &slot_len);
+			rmspace(slot);
+
+			if (fullcpv) {
+				if (atom->PR_int)
+					snprintf(buf, sizeof(buf), "%s/%s-%s-r%i",
+							atom->CATEGORY, atom->PN, atom->PV, atom->PR_int);
+				else
+					snprintf(buf, sizeof(buf), "%s/%s-%s",
+							atom->CATEGORY, atom->PN, atom->PV);
+			} else {
+				snprintf(buf, sizeof(buf), "%s/%s", atom->CATEGORY, atom->PN);
+			}
+			atom_implode(atom);
+			cpf = add_set(buf, cpf);
+		}
+		scandir_free(pf, dfd);
+	}
+	scandir_free(cat, cfd);
+
+ fuckit:
+	tree_close(ctx);
+	return cpf;
+}
diff --git a/libq/tree.h b/libq/tree.h
new file mode 100644
index 00000000..7f05819f
--- /dev/null
+++ b/libq/tree.h
@@ -0,0 +1,141 @@
+/*
+ * Copyright 2005-2019 Gentoo Foundation
+ * Distributed under the terms of the GNU General Public License v2
+ */
+
+#ifndef _TREE_H
+#define _TREE_H 1
+
+#include <dirent.h>
+#include <stdbool.h>
+
+#include "atom.h"
+#include "set.h"
+
+typedef struct tree_ctx          tree_ctx;
+typedef struct tree_cat_ctx      tree_cat_ctx;
+typedef struct tree_pkg_ctx      tree_pkg_ctx;
+typedef struct tree_pkg_meta     tree_pkg_meta;
+typedef struct tree_metadata_xml tree_metadata_xml;
+
+/* VDB context */
+struct tree_ctx {
+	int portroot_fd;
+	int tree_fd;
+	DIR *dir;
+	struct dirent **cat_de;
+	size_t cat_cnt;
+	size_t cat_cur;
+	void *catsortfunc;
+	void *pkgsortfunc;
+	bool do_sort:1;
+	enum {
+		CACHE_UNSET = 0,
+		CACHE_METADATA_MD5,
+		CACHE_METADATA_PMS,
+		CACHE_EBUILD,
+		CACHE_VDB,
+	} cachetype:3;
+	tree_pkg_ctx *ebuilddir_pkg_ctx;
+	tree_cat_ctx *ebuilddir_cat_ctx;
+	tree_ctx *ebuilddir_ctx;
+	char *repo;
+};
+
+/* Category context */
+struct tree_cat_ctx {
+	const char *name;
+	int fd;
+	DIR *dir;
+	tree_ctx *ctx;
+	struct dirent **pkg_de;
+	size_t pkg_cnt;
+	size_t pkg_cur;
+};
+
+/* Package context */
+struct tree_pkg_ctx {
+	const char *name;
+	char *slot;
+	char *repo;
+	size_t slot_len;
+	size_t repo_len;
+	int fd;
+	tree_cat_ctx *cat_ctx;
+	depend_atom *atom;
+};
+
+/* Ebuild data */
+struct tree_pkg_meta {
+	char *_data;
+	char *DEPEND;        /* line 1 */
+	char *RDEPEND;
+	char *SLOT;
+	char *SRC_URI;
+	char *RESTRICT;      /* line 5 */
+	char *HOMEPAGE;
+	char *LICENSE;
+	char *DESCRIPTION;
+	char *KEYWORDS;
+	char *INHERITED;     /* line 10 */
+	char *IUSE;
+	char *CDEPEND;
+	char *PDEPEND;
+	char *PROVIDE;       /* line 14 */
+	char *EAPI;
+	char *PROPERTIES;
+	/* These are MD5-Cache only */
+	char *DEFINED_PHASES;
+	char *REQUIRED_USE;
+	char *BDEPEND;
+	char *_eclasses_;
+	char *_md5_;
+};
+
+/* Metadata.xml */
+struct tree_metadata_xml {
+	struct elist {
+		char *addr;
+		struct elist *next;
+	} *email;
+};
+
+/* Global helpers */
+typedef int (tree_pkg_cb)(tree_pkg_ctx *, void *priv);
+typedef int (tree_cat_filter)(tree_cat_ctx *, void *priv);
+
+tree_ctx *tree_open_vdb(const char *sroot, const char *svdb);
+tree_ctx *tree_open(const char *sroot, const char *portdir);
+void tree_close(tree_ctx *ctx);
+int tree_filter_cat(const struct dirent *de);
+tree_cat_ctx *tree_open_cat(tree_ctx *ctx, const char *name);
+tree_cat_ctx *tree_next_cat(tree_ctx *ctx);
+void tree_close_cat(tree_cat_ctx *cat_ctx);
+int tree_filter_pkg(const struct dirent *de);
+tree_pkg_ctx *tree_open_pkg(tree_cat_ctx *cat_ctx, const char *name);
+tree_pkg_ctx *tree_next_pkg(tree_cat_ctx *cat_ctx);
+int tree_pkg_vdb_openat(tree_pkg_ctx *pkg_ctx, const char *file, int flags, mode_t mode);
+FILE *tree_pkg_vdb_fopenat(tree_pkg_ctx *pkg_ctx, const char *file,
+	int flags, mode_t mode, const char *fmode);
+#define tree_pkg_vdb_fopenat_ro(pkg_ctx, file) \
+	tree_pkg_vdb_fopenat(pkg_ctx, file, O_RDONLY, 0, "r")
+#define tree_pkg_vdb_fopenat_rw(pkg_ctx, file) \
+	tree_pkg_vdb_fopenat(pkg_ctx, file, O_RDWR | O_CREAT | O_TRUNC, 0644, "w")
+bool tree_pkg_vdb_eat(tree_pkg_ctx *pkg_ctx, const char *file, char **bufptr, size_t *buflen);
+tree_pkg_meta *tree_pkg_read(tree_pkg_ctx *pkg_ctx);
+void tree_close_meta(tree_pkg_meta *cache);
+tree_metadata_xml *tree_pkg_metadata(tree_pkg_ctx *pkg_ctx);
+void tree_close_metadata(tree_metadata_xml *meta_ctx);
+void tree_close_pkg(tree_pkg_ctx *pkg_ctx);
+int tree_foreach_pkg(tree_ctx *ctx,
+		tree_pkg_cb callback, void *priv, tree_cat_filter filter,
+		bool sort, void *catsortfunc, void *pkgsortfunc);
+#define tree_foreach_pkg_fast(ctx, cb, priv, filter) \
+	tree_foreach_pkg(ctx, cb, priv, filter, false, NULL, NULL);
+#define tree_foreach_pkg_sorted(ctx, cb, priv) \
+	tree_foreach_pkg(ctx, cb, priv, NULL, true, NULL, NULL);
+struct dirent *tree_get_next_dir(DIR *dir);
+set *tree_get_vdb_atoms(const char *sroot, const char *svdb, int fullcpv);
+depend_atom *tree_get_atom(tree_pkg_ctx *pkg_ctx, bool complete);
+
+#endif
diff --git a/libq/vdb.c b/libq/vdb.c
deleted file mode 100644
index 810a84c2..00000000
--- a/libq/vdb.c
+++ /dev/null
@@ -1,515 +0,0 @@
-/*
- * Copyright 2005-2019 Gentoo Foundation
- * Distributed under the terms of the GNU General Public License v2
- *
- * Copyright 2005-2010 Ned Ludd        - <solar@gentoo.org>
- * Copyright 2005-2014 Mike Frysinger  - <vapier@gentoo.org>
- * Copyright 2019-     Fabian Groffen  - <grobian@gentoo.org>
- */
-
-#include "main.h"
-#include "rmspace.h"
-#include "scandirat.h"
-#include "eat_file.h"
-#include "set.h"
-#include "atom.h"
-#include "vdb.h"
-
-#include <ctype.h>
-#include <xalloc.h>
-
-vdb_ctx *
-vdb_open2(const char *sroot, const char *svdb, bool quiet)
-{
-	vdb_ctx *ctx = xmalloc(sizeof(*ctx));
-
-	ctx->portroot_fd = open(sroot, O_RDONLY|O_CLOEXEC|O_PATH);
-	if (ctx->portroot_fd == -1) {
-		if (!quiet)
-			warnp("could not open root: %s", sroot);
-		goto f_error;
-	}
-
-	/* Skip the leading slash */
-	svdb++;
-	if (*svdb == '\0')
-		svdb = ".";
-	/* Cannot use O_PATH as we want to use fdopendir() */
-	ctx->vdb_fd = openat(ctx->portroot_fd, svdb, O_RDONLY|O_CLOEXEC);
-	if (ctx->vdb_fd == -1) {
-		if (!quiet)
-			warnp("could not open vdb: %s (in root %s)", svdb, sroot);
-		goto cp_error;
-	}
-
-	ctx->dir = fdopendir(ctx->vdb_fd);
-	if (ctx->dir == NULL)
-		goto cv_error;
-
-	ctx->do_sort = false;
-	ctx->cat_de = NULL;
-	ctx->catsortfunc = alphasort;
-	ctx->pkgsortfunc = alphasort;
-	ctx->repo = NULL;
-	ctx->ebuilddir_ctx = NULL;
-	ctx->ebuilddir_pkg_ctx = NULL;
-	return ctx;
-
- cv_error:
-	close(ctx->vdb_fd);
- cp_error:
-	close(ctx->portroot_fd);
- f_error:
-	free(ctx);
-	return NULL;
-}
-
-vdb_ctx *
-vdb_open(const char *sroot, const char *svdb)
-{
-	return vdb_open2(sroot, svdb, false);
-}
-
-void
-vdb_close(vdb_ctx *ctx)
-{
-	closedir(ctx->dir);
-	/* closedir() above does this for us: */
-	/* close(ctx->vdb_fd); */
-	close(ctx->portroot_fd);
-	if (ctx->do_sort)
-		scandir_free(ctx->cat_de, ctx->cat_cnt);
-	free(ctx);
-}
-
-int
-vdb_filter_cat(const struct dirent *de)
-{
-	int i;
-	bool founddash;
-
-#ifdef DT_UNKNOWN
-	/* cat must be a dir */
-	if (de->d_type != DT_UNKNOWN &&
-	    de->d_type != DT_DIR &&
-	    de->d_type != DT_LNK)
-		return 0;
-#endif
-
-	/* PMS 3.1.1 */
-	founddash = false;
-	for (i = 0; de->d_name[i] != '\0'; i++) {
-		switch (de->d_name[i]) {
-			case '_':
-				break;
-			case '-':
-				founddash = true;
-				/* fall through */
-			case '+':
-			case '.':
-				if (i)
-					break;
-				return 0;
-			default:
-				if ((de->d_name[i] >= 'A' && de->d_name[i] <= 'Z') ||
-						(de->d_name[i] >= 'a' && de->d_name[i] <= 'z') ||
-						(de->d_name[i] >= '0' && de->d_name[i] <= '9'))
-					break;
-				return 0;
-		}
-	}
-	if (!founddash && strcmp(de->d_name, "virtual") != 0)
-		return 0;
-
-	return i;
-}
-
-vdb_cat_ctx *
-vdb_open_cat(vdb_ctx *ctx, const char *name)
-{
-	vdb_cat_ctx *cat_ctx;
-	int fd;
-	DIR *dir;
-
-	/* Cannot use O_PATH as we want to use fdopendir() */
-	fd = openat(ctx->vdb_fd, name, O_RDONLY|O_CLOEXEC);
-	if (fd == -1)
-		return NULL;
-
-	dir = fdopendir(fd);
-	if (!dir) {
-		close(fd);
-		return NULL;
-	}
-
-	cat_ctx = xmalloc(sizeof(*cat_ctx));
-	cat_ctx->name = name;
-	cat_ctx->fd = fd;
-	cat_ctx->dir = dir;
-	cat_ctx->ctx = ctx;
-	cat_ctx->pkg_de = NULL;
-	return cat_ctx;
-}
-
-vdb_cat_ctx *
-vdb_next_cat(vdb_ctx *ctx)
-{
-	/* search for a category directory */
-	vdb_cat_ctx *cat_ctx = NULL;
-
-	if (ctx->do_sort) {
-		if (ctx->cat_de == NULL) {
-			ctx->cat_cnt = scandirat(ctx->vdb_fd,
-					".", &ctx->cat_de, vdb_filter_cat, ctx->catsortfunc);
-			ctx->cat_cur = 0;
-		}
-
-		while (ctx->cat_cur < ctx->cat_cnt) {
-			cat_ctx = vdb_open_cat(ctx, ctx->cat_de[ctx->cat_cur++]->d_name);
-			if (!cat_ctx)
-				continue;
-			break;
-		}
-	} else {
-		/* cheaper "streaming" variant */
-		const struct dirent *de;
-		do {
-			de = readdir(ctx->dir);
-			if (!de)
-				break;
-
-			if (vdb_filter_cat(de) == 0)
-				continue;
-
-			cat_ctx = vdb_open_cat(ctx, de->d_name);
-			if (!cat_ctx)
-				continue;
-
-			break;
-		} while (1);
-	}
-
-	return cat_ctx;
-}
-
-void
-vdb_close_cat(vdb_cat_ctx *cat_ctx)
-{
-	closedir(cat_ctx->dir);
-	/* closedir() above does this for us: */
-	/* close(ctx->fd); */
-	if (cat_ctx->ctx->do_sort)
-		scandir_free(cat_ctx->pkg_de, cat_ctx->pkg_cnt);
-	free(cat_ctx);
-}
-
-int
-vdb_filter_pkg(const struct dirent *de)
-{
-	int i;
-	bool founddash = false;
-
-	/* PMS 3.1.2 */
-	for (i = 0; de->d_name[i] != '\0'; i++) {
-		switch (de->d_name[i]) {
-			case '_':
-				break;
-			case '-':
-				founddash = true;
-				/* fall through */
-			case '+':
-				if (i)
-					break;
-				return 0;
-			default:
-				if ((de->d_name[i] >= 'A' && de->d_name[i] <= 'Z') ||
-						(de->d_name[i] >= 'a' && de->d_name[i] <= 'z') ||
-						(de->d_name[i] >= '0' && de->d_name[i] <= '9'))
-					break;
-				if (founddash)
-					return 1;
-				return 0;
-		}
-	}
-
-	return i;
-}
-
-vdb_pkg_ctx *
-vdb_open_pkg(vdb_cat_ctx *cat_ctx, const char *name)
-{
-	vdb_pkg_ctx *pkg_ctx = xmalloc(sizeof(*pkg_ctx));
-	pkg_ctx->name = name;
-	pkg_ctx->slot = NULL;
-	pkg_ctx->repo = cat_ctx->ctx->repo;
-	pkg_ctx->fd = -1;
-	pkg_ctx->cat_ctx = cat_ctx;
-	pkg_ctx->atom = NULL;
-	return pkg_ctx;
-}
-
-vdb_pkg_ctx *
-vdb_next_pkg(vdb_cat_ctx *cat_ctx)
-{
-	vdb_pkg_ctx *pkg_ctx = NULL;
-
-	if (cat_ctx->ctx->do_sort) {
-		if (cat_ctx->pkg_de == NULL) {
-			cat_ctx->pkg_cnt = scandirat(cat_ctx->fd, ".", &cat_ctx->pkg_de,
-					vdb_filter_pkg, cat_ctx->ctx->pkgsortfunc);
-			cat_ctx->pkg_cur = 0;
-		}
-
-		while (cat_ctx->pkg_cur < cat_ctx->pkg_cnt) {
-			pkg_ctx =
-				vdb_open_pkg(cat_ctx,
-						cat_ctx->pkg_de[cat_ctx->pkg_cur++]->d_name);
-			if (!pkg_ctx)
-				continue;
-			break;
-		}
-	} else {
-		const struct dirent *de;
-		do {
-			de = readdir(cat_ctx->dir);
-			if (!de)
-				break;
-
-			if (vdb_filter_pkg(de) == 0)
-				continue;
-
-			pkg_ctx = vdb_open_pkg(cat_ctx, de->d_name);
-			if (!pkg_ctx)
-				continue;
-
-			break;
-		} while (1);
-	}
-
-	return pkg_ctx;
-}
-
-int
-vdb_pkg_openat(vdb_pkg_ctx *pkg_ctx, const char *file, int flags, mode_t mode)
-{
-	if (pkg_ctx->fd == -1) {
-		pkg_ctx->fd = openat(pkg_ctx->cat_ctx->fd, pkg_ctx->name,
-				O_RDONLY|O_CLOEXEC|O_PATH);
-		if (pkg_ctx->fd == -1)
-			return -1;
-	}
-
-	return openat(pkg_ctx->fd, file, flags|O_CLOEXEC, mode);
-}
-
-FILE *
-vdb_pkg_fopenat(vdb_pkg_ctx *pkg_ctx, const char *file,
-	int flags, mode_t mode, const char *fmode)
-{
-	FILE *fp;
-	int fd;
-
-	fd = vdb_pkg_openat(pkg_ctx, file, flags, mode);
-	if (fd == -1)
-		return NULL;
-
-	fp = fdopen(fd, fmode);
-	if (!fp)
-		close(fd);
-
-	return fp;
-}
-
-bool
-vdb_pkg_eat(vdb_pkg_ctx *pkg_ctx, const char *file, char **bufptr, size_t *buflen)
-{
-	int fd = vdb_pkg_openat(pkg_ctx, file, O_RDONLY, 0);
-	bool ret = eat_file_fd(fd, bufptr, buflen);
-	rmspace(*bufptr);
-	if (fd != -1)
-		close(fd);
-	return ret;
-}
-
-void
-vdb_close_pkg(vdb_pkg_ctx *pkg_ctx)
-{
-	if (pkg_ctx->fd != -1)
-		close(pkg_ctx->fd);
-	if (pkg_ctx->atom != NULL)
-		atom_implode(pkg_ctx->atom);
-	free(pkg_ctx->slot);
-	free(pkg_ctx->repo);
-	free(pkg_ctx);
-}
-
-static int
-vdb_foreach_pkg_int(const char *sroot, const char *svdb,
-		vdb_pkg_cb callback, void *priv, vdb_cat_filter filter,
-		bool sort, void *catsortfunc, void *pkgsortfunc)
-{
-	vdb_ctx *ctx;
-	vdb_cat_ctx *cat_ctx;
-	vdb_pkg_ctx *pkg_ctx;
-	int ret;
-
-	ctx = vdb_open(sroot, svdb);
-	if (!ctx)
-		return EXIT_FAILURE;
-
-	ctx->do_sort = sort;
-	if (catsortfunc != NULL)
-		ctx->catsortfunc = catsortfunc;
-	if (pkgsortfunc != NULL)
-		ctx->pkgsortfunc = pkgsortfunc;
-
-	ret = 0;
-	while ((cat_ctx = vdb_next_cat(ctx))) {
-		if (filter && !filter(cat_ctx, priv))
-			continue;
-		while ((pkg_ctx = vdb_next_pkg(cat_ctx))) {
-			ret |= callback(pkg_ctx, priv);
-			vdb_close_pkg(pkg_ctx);
-		}
-		vdb_close_cat(cat_ctx);
-	}
-	vdb_close(ctx);
-
-	return ret;
-}
-
-int
-vdb_foreach_pkg(const char *sroot, const char *svdb,
-		vdb_pkg_cb callback, void *priv, vdb_cat_filter filter)
-{
-	return vdb_foreach_pkg_int(sroot, svdb, callback, priv,
-			filter, false, NULL, NULL);
-}
-
-int
-vdb_foreach_pkg_sorted(const char *sroot, const char *svdb,
-		vdb_pkg_cb callback, void *priv)
-{
-	return vdb_foreach_pkg_int(sroot, svdb, callback, priv,
-			NULL, true, NULL, NULL);
-}
-
-struct dirent *
-vdb_get_next_dir(DIR *dir)
-{
-	/* search for a category directory */
-	struct dirent *ret;
-
-next_entry:
-	ret = readdir(dir);
-	if (ret == NULL) {
-		closedir(dir);
-		return NULL;
-	}
-
-	if (vdb_filter_cat(ret) == 0)
-		goto next_entry;
-
-	return ret;
-}
-
-depend_atom *
-vdb_get_atom(vdb_pkg_ctx *pkg_ctx, bool complete)
-{
-	if (pkg_ctx->atom == NULL) {
-		pkg_ctx->atom = atom_explode(pkg_ctx->name);
-		if (pkg_ctx->atom == NULL)
-			return NULL;
-		pkg_ctx->atom->CATEGORY = (char *)pkg_ctx->cat_ctx->name;
-	}
-
-	if (complete) {
-		if (pkg_ctx->atom->SLOT == NULL) {
-			vdb_pkg_eat(pkg_ctx, "SLOT",
-					&pkg_ctx->slot, &pkg_ctx->slot_len);
-			pkg_ctx->atom->SLOT = pkg_ctx->slot;
-		}
-		if (pkg_ctx->atom->REPO == NULL) {
-			vdb_pkg_eat(pkg_ctx, "repository",
-					&pkg_ctx->repo, &pkg_ctx->repo_len);
-			pkg_ctx->atom->REPO = pkg_ctx->repo;
-		}
-	}
-
-	return pkg_ctx->atom;
-}
-
-set *
-get_vdb_atoms(const char *sroot, const char *svdb, int fullcpv)
-{
-	vdb_ctx *ctx;
-
-	int cfd, j;
-	int dfd, i;
-
-	char buf[_Q_PATH_MAX];
-	char slot[_Q_PATH_MAX];
-	char *slotp = slot;
-	size_t slot_len;
-
-	struct dirent **cat;
-	struct dirent **pf;
-
-	depend_atom *atom = NULL;
-	set *cpf = NULL;
-
-	ctx = vdb_open(sroot, svdb);
-	if (!ctx)
-		return NULL;
-
-	/* scan the cat first */
-	cfd = scandirat(ctx->vdb_fd, ".", &cat, vdb_filter_cat, alphasort);
-	if (cfd < 0)
-		goto fuckit;
-
-	for (j = 0; j < cfd; j++) {
-		dfd = scandirat(ctx->vdb_fd, cat[j]->d_name,
-				&pf, vdb_filter_pkg, alphasort);
-		if (dfd < 0)
-			continue;
-		for (i = 0; i < dfd; i++) {
-			int blen = snprintf(buf, sizeof(buf), "%s/%s/SLOT",
-					cat[j]->d_name, pf[i]->d_name);
-			if (blen < 0 || (size_t)blen >= sizeof(buf)) {
-				warnf("unable to parse long package: %s/%s",
-						cat[j]->d_name, pf[i]->d_name);
-				continue;
-			}
-
-			/* Chop the SLOT for the atom parsing. */
-			buf[blen - 5] = '\0';
-			if ((atom = atom_explode(buf)) == NULL)
-				continue;
-			/* Restore the SLOT. */
-			buf[blen - 5] = '/';
-
-			slot_len = sizeof(slot);
-			eat_file_at(ctx->vdb_fd, buf, &slotp, &slot_len);
-			rmspace(slot);
-
-			if (fullcpv) {
-				if (atom->PR_int)
-					snprintf(buf, sizeof(buf), "%s/%s-%s-r%i",
-							atom->CATEGORY, atom->PN, atom->PV, atom->PR_int);
-				else
-					snprintf(buf, sizeof(buf), "%s/%s-%s",
-							atom->CATEGORY, atom->PN, atom->PV);
-			} else {
-				snprintf(buf, sizeof(buf), "%s/%s", atom->CATEGORY, atom->PN);
-			}
-			atom_implode(atom);
-			cpf = add_set(buf, cpf);
-		}
-		scandir_free(pf, dfd);
-	}
-	scandir_free(cat, cfd);
-
- fuckit:
-	vdb_close(ctx);
-	return cpf;
-}
diff --git a/libq/vdb.h b/libq/vdb.h
deleted file mode 100644
index 28ca0408..00000000
--- a/libq/vdb.h
+++ /dev/null
@@ -1,96 +0,0 @@
-/*
- * Copyright 2005-2019 Gentoo Foundation
- * Distributed under the terms of the GNU General Public License v2
- */
-
-#ifndef _VDB_H
-#define _VDB_H 1
-
-#include <dirent.h>
-#include <stdbool.h>
-
-#include "set.h"
-
-typedef struct vdb_ctx vdb_ctx;
-typedef struct vdb_cat_ctx vdb_cat_ctx;
-typedef struct vdb_pkg_ctx vdb_pkg_ctx;
-
-/* VDB context */
-struct vdb_ctx {
-	int portroot_fd;
-	int vdb_fd;
-	DIR *dir;
-	struct dirent **cat_de;
-	size_t cat_cnt;
-	size_t cat_cur;
-	void *catsortfunc;
-	void *pkgsortfunc;
-	bool do_sort:1;
-	enum {
-		CACHE_UNSET = 0,
-		CACHE_METADATA_MD5,
-		CACHE_METADATA_PMS,
-		CACHE_EBUILD,
-		CACHE_VDB,
-	} cachetype:3;
-	vdb_pkg_ctx *ebuilddir_pkg_ctx;
-	vdb_cat_ctx *ebuilddir_cat_ctx;
-	vdb_ctx *ebuilddir_ctx;
-	char *repo;
-};
-
-/* Category context */
-struct vdb_cat_ctx {
-	const char *name;
-	int fd;
-	DIR *dir;
-	const vdb_ctx *ctx;
-	struct dirent **pkg_de;
-	size_t pkg_cnt;
-	size_t pkg_cur;
-};
-
-/* Package context */
-struct vdb_pkg_ctx {
-	const char *name;
-	char *slot;
-	char *repo;
-	size_t slot_len;
-	size_t repo_len;
-	int fd;
-	vdb_cat_ctx *cat_ctx;
-	depend_atom *atom;
-};
-
-/* Global helpers */
-typedef int (vdb_pkg_cb)(vdb_pkg_ctx *, void *priv);
-typedef int (vdb_cat_filter)(vdb_cat_ctx *, void *priv);
-
-vdb_ctx *vdb_open(const char *sroot, const char *svdb);
-vdb_ctx *vdb_open2(const char *sroot, const char *svdb, bool quiet);
-void vdb_close(vdb_ctx *ctx);
-int vdb_filter_cat(const struct dirent *de);
-vdb_cat_ctx *vdb_open_cat(vdb_ctx *ctx, const char *name);
-vdb_cat_ctx *vdb_next_cat(vdb_ctx *ctx);
-void vdb_close_cat(vdb_cat_ctx *cat_ctx);
-int vdb_filter_pkg(const struct dirent *de);
-vdb_pkg_ctx *vdb_open_pkg(vdb_cat_ctx *cat_ctx, const char *name);
-vdb_pkg_ctx *vdb_next_pkg(vdb_cat_ctx *cat_ctx);
-int vdb_pkg_openat(vdb_pkg_ctx *pkg_ctx, const char *file, int flags, mode_t mode);
-FILE *vdb_pkg_fopenat(vdb_pkg_ctx *pkg_ctx, const char *file,
-	int flags, mode_t mode, const char *fmode);
-#define vdb_pkg_fopenat_ro(pkg_ctx, file) \
-	vdb_pkg_fopenat(pkg_ctx, file, O_RDONLY, 0, "r")
-#define vdb_pkg_fopenat_rw(pkg_ctx, file) \
-	vdb_pkg_fopenat(pkg_ctx, file, O_RDWR|O_CREAT|O_TRUNC, 0644, "w")
-bool vdb_pkg_eat(vdb_pkg_ctx *pkg_ctx, const char *file, char **bufptr, size_t *buflen);
-void vdb_close_pkg(vdb_pkg_ctx *pkg_ctx);
-int vdb_foreach_pkg(const char *sroot, const char *svdb,
-		vdb_pkg_cb callback, void *priv, vdb_cat_filter filter);
-int vdb_foreach_pkg_sorted(const char *sroot, const char *svdb,
-		vdb_pkg_cb callback, void *priv);
-struct dirent *vdb_get_next_dir(DIR *dir);
-set *get_vdb_atoms(const char *sroot, const char *svdb, int fullcpv);
-depend_atom *vdb_get_atom(vdb_pkg_ctx *pkg_ctx, bool complete);
-
-#endif
diff --git a/main.c b/main.c
index 159b262f..944950e9 100644
--- a/main.c
+++ b/main.c
@@ -17,30 +17,10 @@
 #include <sys/time.h>
 #include <limits.h>
 
-#include "atom.h"
-#include "basename.h"
-#include "busybox.h"
-#include "cache.h"
-#include "colors.h"
-#include "copy_file.h"
 #include "eat_file.h"
-#include "hash_fd.h"
-#include "human_readable.h"
-#include "i18n.h"
-#include "md5_sha1_sum.h"
-#include "prelink.h"
-#include "profile.h"
 #include "rmspace.h"
-#include "safe_io.h"
 #include "scandirat.h"
-#include "set.h"
-#include "vdb.h"
-#include "xarray.h"
 #include "xasprintf.h"
-#include "xchdir.h"
-#include "xmkdir.h"
-#include "xregex.h"
-#include "xsystem.h"
 
 /* variables to control runtime behavior */
 char *module_name = NULL;
diff --git a/q.c b/q.c
index a18c7912..b6486ee0 100644
--- a/q.c
+++ b/q.c
@@ -19,9 +19,7 @@
 #include <libproc.h>
 #endif
 
-#include "atom.h"
 #include "basename.h"
-#include "cache.h"
 
 #define Q_FLAGS "iM:" COMMON_FLAGS
 static struct option const q_long_opts[] = {
diff --git a/qcheck.c b/qcheck.c
index 68cdb30c..a26b25db 100644
--- a/qcheck.c
+++ b/qcheck.c
@@ -20,7 +20,7 @@
 #include "md5_sha1_sum.h"
 #include "prelink.h"
 #include "set.h"
-#include "vdb.h"
+#include "tree.h"
 #include "xarray.h"
 #include "xasprintf.h"
 #include "xregex.h"
@@ -65,7 +65,7 @@ struct qcheck_opt_state {
 };
 
 static int
-qcheck_process_contents(vdb_pkg_ctx *pkg_ctx, struct qcheck_opt_state *state)
+qcheck_process_contents(tree_pkg_ctx *pkg_ctx, struct qcheck_opt_state *state)
 {
 	int fd_contents;
 	FILE *fp_contents, *fp_contents_update;
@@ -80,7 +80,8 @@ qcheck_process_contents(vdb_pkg_ctx *pkg_ctx, struct qcheck_opt_state *state)
 	fp_contents_update = NULL;
 
 	/* Open contents */
-	fd_contents = vdb_pkg_openat(pkg_ctx, "CONTENTS", O_RDONLY|O_CLOEXEC, 0);
+	fd_contents = tree_pkg_vdb_openat(pkg_ctx, "CONTENTS",
+			O_RDONLY | O_CLOEXEC, 0);
 	if (fd_contents == -1)
 		return EXIT_SUCCESS;
 	if (fstat(fd_contents, &cst)) {
@@ -93,13 +94,13 @@ qcheck_process_contents(vdb_pkg_ctx *pkg_ctx, struct qcheck_opt_state *state)
 	}
 
 	/* Open contents_update, if needed */
-	atom = vdb_get_atom(pkg_ctx, false);
+	atom = tree_get_atom(pkg_ctx, false);
 	num_files = num_files_ok = num_files_unknown = num_files_ignored = 0;
 	qcprintf("%sing %s ...\n",
 		(state->qc_update ? "Updat" : "Check"),
 		atom_format("%[CATEGORY]%[PF]", atom, 0));
 	if (state->qc_update) {
-		fp_contents_update = vdb_pkg_fopenat_rw(pkg_ctx, "CONTENTS~");
+		fp_contents_update = tree_pkg_vdb_fopenat_rw(pkg_ctx, "CONTENTS~");
 		if (fp_contents_update == NULL) {
 			fclose(fp_contents);
 			warnp("unable to fopen(%s/%s, w)", atom->P, "CONTENTS~");
@@ -355,7 +356,7 @@ qcheck_process_contents(vdb_pkg_ctx *pkg_ctx, struct qcheck_opt_state *state)
 }
 
 static int
-qcheck_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
+qcheck_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	struct qcheck_opt_state *state = priv;
 	bool showit = false;
@@ -366,7 +367,7 @@ qcheck_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 		depend_atom *qatom;
 		depend_atom *atom;
 
-		qatom = vdb_get_atom(pkg_ctx, false);
+		qatom = tree_get_atom(pkg_ctx, false);
 		array_for_each(state->atoms, i, atom) {
 			if (atom_compare(atom, qatom) == EQUAL) {
 				showit = true;
@@ -384,6 +385,7 @@ int qcheck_main(int argc, char **argv)
 {
 	size_t i;
 	int ret;
+	tree_ctx *vdb;
 	DECLARE_ARRAY(regex_arr);
 	depend_atom *atom;
 	DECLARE_ARRAY(atoms);
@@ -403,9 +405,9 @@ int qcheck_main(int argc, char **argv)
 		switch (ret) {
 		COMMON_GETOPTS_CASES(qcheck)
 		case 's': {
-			regex_t regex;
-			xregcomp(&regex, optarg, REG_EXTENDED|REG_NOSUB);
-			xarraypush(regex_arr, &regex, sizeof(regex));
+			regex_t preg;
+			xregcomp(&preg, optarg, REG_EXTENDED | REG_NOSUB);
+			xarraypush(regex_arr, &preg, sizeof(preg));
 			break;
 		}
 		case 'u': state.qc_update = true; break;
@@ -428,11 +430,16 @@ int qcheck_main(int argc, char **argv)
 			xarraypush_ptr(atoms, atom);
 	}
 
-	ret = vdb_foreach_pkg_sorted(portroot, portvdb, qcheck_cb, &state);
-	{
-		void *regex;
-		array_for_each(regex_arr, i, regex)
-			regfree(regex);
+	vdb = tree_open_vdb(portroot, portvdb);
+	ret = -1;
+	if (vdb != NULL) {
+		ret = tree_foreach_pkg_sorted(vdb, qcheck_cb, &state);
+		tree_close(vdb);
+	}
+	if (array_cnt(regex_arr) > 0) {
+		void *preg;
+		array_for_each(regex_arr, i, preg)
+			regfree(preg);
 	}
 	xarrayfree(regex_arr);
 	array_for_each(atoms, i, atom)
diff --git a/qdepends.c b/qdepends.c
index 64bf9918..15d52536 100644
--- a/qdepends.c
+++ b/qdepends.c
@@ -17,7 +17,7 @@
 #include "atom.h"
 #include "dep.h"
 #include "set.h"
-#include "vdb.h"
+#include "tree.h"
 #include "xarray.h"
 #include "xasprintf.h"
 #include "xregex.h"
@@ -92,7 +92,7 @@ qdepends_print_depend(FILE *fp, const char *depend)
 }
 
 static int
-qdepends_results_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
+qdepends_results_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	struct qdepends_opt_state *state = priv;
 	depend_atom *atom;
@@ -116,7 +116,7 @@ qdepends_results_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 	 * *DEPEND alters the search somewhat and affects results printing.
 	 */
 
-	datom = vdb_get_atom(pkg_ctx, false);
+	datom = tree_get_atom(pkg_ctx, false);
 	if (datom == NULL)
 		return ret;
 
@@ -135,7 +135,7 @@ qdepends_results_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 
 		ret = 1;
 
-		datom = vdb_get_atom(pkg_ctx, true);
+		datom = tree_get_atom(pkg_ctx, true);
 		printf("%s:", atom_format(state->format, datom, 0));
 	}
 
@@ -146,7 +146,7 @@ qdepends_results_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 	for (i = QMODE_DEPEND; i <= QMODE_BDEPEND; i <<= 1, dfile++) {
 		if (!(state->qmode & i))
 			continue;
-		if (!vdb_pkg_eat(pkg_ctx, *dfile,
+		if (!tree_pkg_vdb_eat(pkg_ctx, *dfile,
 					&state->depend, &state->depend_len))
 			continue;
 
@@ -174,7 +174,7 @@ qdepends_results_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 					ret = 1;
 
 					if (!firstmatch) {
-						datom = vdb_get_atom(pkg_ctx, true);
+						datom = tree_get_atom(pkg_ctx, true);
 						printf("%s:", atom_format(state->format, datom, 0));
 					}
 					firstmatch = true;
@@ -203,7 +203,7 @@ qdepends_results_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 						ret = 1;
 
 						if (!firstmatch) {
-							datom = vdb_get_atom(pkg_ctx, true);
+							datom = tree_get_atom(pkg_ctx, true);
 							printf("%s:", atom_format(state->format, datom, 0));
 						}
 						firstmatch = true;
@@ -243,6 +243,7 @@ qdepends_results_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 int qdepends_main(int argc, char **argv)
 {
 	depend_atom *atom;
+	tree_ctx *vdb;
 	DECLARE_ARRAY(atoms);
 	DECLARE_ARRAY(deps);
 	struct qdepends_opt_state state = {
@@ -307,8 +308,11 @@ int qdepends_main(int argc, char **argv)
 			xarraypush_ptr(atoms, atom);
 	}
 
-	ret = vdb_foreach_pkg(portroot, portvdb,
-			qdepends_results_cb, &state, NULL);
+	vdb = tree_open_vdb(portroot, portvdb);
+	if (vdb != NULL) {
+		ret = tree_foreach_pkg_fast(vdb, qdepends_results_cb, &state, NULL);
+		tree_close(vdb);
+	}
 
 	if (state.depend != NULL)
 		free(state.depend);
diff --git a/qfile.c b/qfile.c
index 3d1543e8..c451ae46 100644
--- a/qfile.c
+++ b/qfile.c
@@ -18,7 +18,7 @@
 #include "basename.h"
 #include "contents.h"
 #include "rmspace.h"
-#include "vdb.h"
+#include "tree.h"
 
 #define QFILE_FLAGS "boRx:S" COMMON_FLAGS
 static struct option const qfile_long_opts[] = {
@@ -74,7 +74,7 @@ struct qfile_opt_state {
  * We assume the people calling us have chdir(/var/db/pkg) and so
  * we use relative paths throughout here.
  */
-static int qfile_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
+static int qfile_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	struct qfile_opt_state *state = priv;
 	const char *catname = pkg_ctx->cat_ctx->name;
@@ -115,14 +115,14 @@ static int qfile_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 		}
 		if (state->exclude_slot == NULL)
 			goto qlist_done; /* "(CAT/)?(PN|PF)" matches, and no SLOT specified */
-		vdb_pkg_eat(pkg_ctx, "SLOT", &state->buf, &state->buflen);
+		tree_pkg_vdb_eat(pkg_ctx, "SLOT", &state->buf, &state->buflen);
 		rmspace(state->buf);
 		if (strcmp(state->exclude_slot, state->buf) == 0)
 			goto qlist_done; /* "(CAT/)?(PN|PF):SLOT" matches */
 	}
  dont_skip_pkg: /* End of the package exclusion tests. */
 
-	fp = vdb_pkg_fopenat_ro(pkg_ctx, "CONTENTS");
+	fp = tree_pkg_vdb_fopenat_ro(pkg_ctx, "CONTENTS");
 	if (fp == NULL)
 		goto qlist_done;
 
@@ -227,7 +227,7 @@ static int qfile_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 					/* XXX: This assumes the buf is big enough. */
 					char *slot_hack = slot + 1;
 					size_t slot_len = sizeof(slot) - 1;
-					vdb_pkg_eat(pkg_ctx, "SLOT", &slot_hack, &slot_len);
+					tree_pkg_vdb_eat(pkg_ctx, "SLOT", &slot_hack, &slot_len);
 					rmspace(slot_hack);
 					slot[0] = ':';
 				} else
@@ -478,8 +478,13 @@ int qfile_main(int argc, char **argv)
 	/* Prepare the qfile(...) arguments structure */
 	nb_of_queries = prepare_qfile_args(argc, (const char **) argv, &state);
 	/* Now do the actual `qfile` checking */
-	if (nb_of_queries > 0)
-		found += vdb_foreach_pkg_sorted(portroot, portvdb, qfile_cb, &state);
+	if (nb_of_queries > 0) {
+		tree_ctx *vdb = tree_open_vdb(portroot, portvdb);
+		if (vdb != NULL) {
+			found += tree_foreach_pkg_sorted(vdb, qfile_cb, &state);
+			tree_close(vdb);
+		}
+	}
 
 	if (state.args.non_orphans) {
 		/* display orphan files */
diff --git a/qgrep.c b/qgrep.c
index f38f461b..8e240f3e 100644
--- a/qgrep.c
+++ b/qgrep.c
@@ -19,8 +19,7 @@
 #include <fcntl.h>
 
 #include "atom.h"
-#include "cache.h"
-#include "vdb.h"
+#include "tree.h"
 #include "xarray.h"
 #include "xchdir.h"
 #include "xregex.h"
@@ -381,14 +380,14 @@ print_after_context:
 }
 
 static int
-qgrep_cache_cb(cache_pkg_ctx *pkg_ctx, void *priv)
+qgrep_cache_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	struct qgrep_grepargs *data = (struct qgrep_grepargs *)priv;
 	char buf[_Q_PATH_MAX];
 	char name[_Q_PATH_MAX];
 	char *label;
 	depend_atom *patom = NULL;
-	cache_ctx *cctx;
+	tree_ctx *cctx;
 	int ret;
 	int pfd;
 
@@ -411,11 +410,11 @@ qgrep_cache_cb(cache_pkg_ctx *pkg_ctx, void *priv)
 	}
 
 	/* need to construct path in portdir to ebuild, pass it to grep */
-	cctx = (cache_ctx *)(pkg_ctx->cat_ctx->ctx);
+	cctx = (tree_ctx *)(pkg_ctx->cat_ctx->ctx);
 	if (cctx->cachetype == CACHE_EBUILD) {
-		pfd = cctx->vdb_fd;
+		pfd = cctx->tree_fd;
 	} else {
-		pfd = openat(cctx->vdb_fd, "../..", O_RDONLY|O_CLOEXEC);
+		pfd = openat(cctx->tree_fd, "../..", O_RDONLY|O_CLOEXEC);
 	}
 
 	/* cat/pkg/pkg-ver.ebuild */
@@ -441,7 +440,7 @@ qgrep_cache_cb(cache_pkg_ctx *pkg_ctx, void *priv)
 }
 
 static int
-qgrep_vdb_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
+qgrep_vdb_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	struct qgrep_grepargs *data = (struct qgrep_grepargs *)priv;
 	char buf[_Q_PATH_MAX];
@@ -687,11 +686,17 @@ int qgrep_main(int argc, char **argv)
 			}
 			closedir(eclass_dir);
 		} else if (do_installed) {
-			status = vdb_foreach_pkg(portroot, portvdb,
-					qgrep_vdb_cb, &args, NULL);
+			tree_ctx *t = tree_open_vdb(portroot, portvdb);
+			if (t != NULL) {
+				status = tree_foreach_pkg_fast(t, qgrep_vdb_cb, &args, NULL);
+				tree_close(t);
+			}
 		} else { /* do_ebuild */
-			status = cache_foreach_pkg(portroot, overlay,
-					qgrep_cache_cb, &args, NULL);
+			tree_ctx *t = tree_open(portroot, overlay);
+			if (t != NULL) {
+				status = tree_foreach_pkg_fast(t, qgrep_cache_cb, &args, NULL);
+				tree_close(t);
+			}
 		}
 	}
 
diff --git a/qkeyword.c b/qkeyword.c
index ef61fba9..b9792af5 100644
--- a/qkeyword.c
+++ b/qkeyword.c
@@ -18,10 +18,10 @@
 #include <sys/stat.h>
 
 #include "atom.h"
-#include "cache.h"
-#include "scandirat.h"
 #include "rmspace.h"
+#include "scandirat.h"
 #include "set.h"
+#include "tree.h"
 #include "xasprintf.h"
 
 /********************************************************************/
@@ -62,7 +62,7 @@ typedef struct {
 	int *keywordsbuf;
 	size_t keywordsbuflen;
 	const char *arch;
-	cache_pkg_cb *runfunc;
+	tree_pkg_cb *runfunc;
 } qkeyword_data;
 
 static set *archs = NULL;
@@ -214,7 +214,7 @@ qkeyword_vercmp(const struct dirent **x, const struct dirent **y)
 }
 
 static int
-qkeyword_imlate(cache_pkg_ctx *pkg_ctx, void *priv)
+qkeyword_imlate(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	size_t a;
 	qkeyword_data *data = (qkeyword_data *)priv;
@@ -241,7 +241,7 @@ qkeyword_imlate(cache_pkg_ctx *pkg_ctx, void *priv)
 }
 
 static int
-qkeyword_not(cache_pkg_ctx *pkg_ctx, void *priv)
+qkeyword_not(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	size_t a;
 	qkeyword_data *data = (qkeyword_data *)priv;
@@ -266,7 +266,7 @@ qkeyword_not(cache_pkg_ctx *pkg_ctx, void *priv)
 }
 
 static int
-qkeyword_all(cache_pkg_ctx *pkg_ctx, void *priv)
+qkeyword_all(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	qkeyword_data *data = (qkeyword_data *)priv;
 
@@ -282,7 +282,7 @@ qkeyword_all(cache_pkg_ctx *pkg_ctx, void *priv)
 }
 
 static int
-qkeyword_dropped(cache_pkg_ctx *pkg_ctx, void *priv)
+qkeyword_dropped(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	static bool candidate = false;
 	static char pkg1[_Q_PATH_MAX];
@@ -393,7 +393,7 @@ print_seconds_for_earthlings(const unsigned long t)
 }
 
 static int
-qkeyword_stats(cache_pkg_ctx *pkg_ctx, void *priv)
+qkeyword_stats(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	static time_t runtime;
 	static int numpkg  = 0;
@@ -536,7 +536,7 @@ qkeyword_stats(cache_pkg_ctx *pkg_ctx, void *priv)
 }
 
 static int
-qkeyword_testing_only(cache_pkg_ctx *pkg_ctx, void *priv)
+qkeyword_testing_only(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	static bool candidate = false;
 	static char pkg1[_Q_PATH_MAX];
@@ -606,14 +606,14 @@ qkeyword_testing_only(cache_pkg_ctx *pkg_ctx, void *priv)
 }
 
 static int
-qkeyword_results_cb(cache_pkg_ctx *pkg_ctx, void *priv)
+qkeyword_results_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	int *keywords;
 	qkeyword_data *data = (qkeyword_data *)priv;
 	char buf[_Q_PATH_MAX];
 	depend_atom *patom = NULL;
-	cache_pkg_meta *meta;
-	cache_metadata_xml *metadata;
+	tree_pkg_meta *meta;
+	tree_metadata_xml *metadata;
 	struct elist *emailw;
 	int ret;
 
@@ -638,7 +638,7 @@ qkeyword_results_cb(cache_pkg_ctx *pkg_ctx, void *priv)
 	}
 
 	if (data->qmaint != NULL) {
-		metadata = cache_read_metadata(pkg_ctx);
+		metadata = tree_pkg_metadata(pkg_ctx);
 		if (metadata == NULL)
 			return EXIT_SUCCESS;
 
@@ -650,13 +650,13 @@ qkeyword_results_cb(cache_pkg_ctx *pkg_ctx, void *priv)
 			/* arbitrary pointer to trigger exit below */
 			emailw = (struct elist *)buf;
 
-		cache_close_metadata(metadata);
+		tree_close_metadata(metadata);
 		if (emailw != NULL)
 			return EXIT_SUCCESS;
 	}
 
 	keywords = data->keywordsbuf;
-	meta = cache_pkg_read(pkg_ctx);
+	meta = tree_pkg_read(pkg_ctx);
 	if (meta == NULL) {
 		atom_implode(patom);
 		return EXIT_FAILURE;
@@ -731,7 +731,7 @@ qkeyword_load_arches(const char *overlay)
 }
 
 static int
-qkeyword_traverse(cache_pkg_cb func, void *priv)
+qkeyword_traverse(tree_pkg_cb func, void *priv)
 {
 	int ret;
 	size_t n;
@@ -756,9 +756,14 @@ qkeyword_traverse(cache_pkg_cb func, void *priv)
 
 	data->runfunc = func;
 	ret = 0;
-	array_for_each(overlays, n, overlay)
-		ret |= cache_foreach_pkg_sorted(portroot, overlay,
-				qkeyword_results_cb, priv, NULL, qkeyword_vercmp);
+	array_for_each(overlays, n, overlay) {
+		tree_ctx *t = tree_open(portroot, overlay);
+		if (t != NULL) {
+			ret |= tree_foreach_pkg(t, qkeyword_results_cb, priv,
+					NULL, true, NULL, qkeyword_vercmp);
+			tree_close(t);
+		}
+	}
 
 	return ret;
 }
diff --git a/qlist.c b/qlist.c
index 9314385f..abefbcf8 100644
--- a/qlist.c
+++ b/qlist.c
@@ -18,7 +18,7 @@
 
 #include "atom.h"
 #include "contents.h"
-#include "vdb.h"
+#include "tree.h"
 #include "xregex.h"
 
 #define QLIST_FLAGS "ISRUcDeados" COMMON_FLAGS
@@ -96,7 +96,7 @@ cmpstringp(const void *p1, const void *p2)
  */
 static char _umapstr_buf[BUFSIZ];
 static const char *
-umapstr(char display, vdb_pkg_ctx *pkg_ctx)
+umapstr(char display, tree_pkg_ctx *pkg_ctx)
 {
 	char *bufp = _umapstr_buf;
 	char *use = NULL;
@@ -115,10 +115,10 @@ umapstr(char display, vdb_pkg_ctx *pkg_ctx)
 	if (!display)
 		return bufp;
 
-	vdb_pkg_eat(pkg_ctx, "USE", &use, &use_len);
+	tree_pkg_vdb_eat(pkg_ctx, "USE", &use, &use_len);
 	if (!use[0])
 		return bufp;
-	vdb_pkg_eat(pkg_ctx, "IUSE", &iuse, &iuse_len);
+	tree_pkg_vdb_eat(pkg_ctx, "IUSE", &iuse, &iuse_len);
 	if (!iuse[0])
 		return bufp;
 
@@ -173,13 +173,13 @@ umapstr(char display, vdb_pkg_ctx *pkg_ctx)
 /* forward declaration necessary for misuse from qmerge.c, see HACK there */
 bool
 qlist_match(
-		vdb_pkg_ctx *pkg_ctx,
+		tree_pkg_ctx *pkg_ctx,
 		const char *name,
 		depend_atom **name_atom,
 		bool exact);
 bool
 qlist_match(
-		vdb_pkg_ctx *pkg_ctx,
+		tree_pkg_ctx *pkg_ctx,
 		const char *name,
 		depend_atom **name_atom,
 		bool exact)
@@ -200,7 +200,7 @@ qlist_match(
 			uslot = NULL;
 		else {
 			if (!pkg_ctx->slot)
-				vdb_pkg_eat(pkg_ctx, "SLOT", &pkg_ctx->slot,
+				tree_pkg_vdb_eat(pkg_ctx, "SLOT", &pkg_ctx->slot,
 						&pkg_ctx->slot_len);
 			uslot_len = strlen(uslot);
 		}
@@ -209,7 +209,7 @@ qlist_match(
 	urepo = strstr(name, "::");
 	if (urepo) {
 		if (!pkg_ctx->repo)
-			vdb_pkg_eat(pkg_ctx, "repository", &pkg_ctx->repo,
+			tree_pkg_vdb_eat(pkg_ctx, "repository", &pkg_ctx->repo,
 					&pkg_ctx->repo_len);
 		urepo += 2;
 		urepo_len = strlen(urepo);
@@ -338,7 +338,7 @@ struct qlist_opt_state {
 };
 
 static int
-qlist_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
+qlist_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	struct qlist_opt_state *state = priv;
 	int i;
@@ -359,7 +359,7 @@ qlist_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 		atom = (verbose ? NULL : atom_explode(pkgname));
 		if ((state->all + state->just_pkgname) < 2) {
 			if (state->show_slots && !pkg_ctx->slot) {
-				vdb_pkg_eat(pkg_ctx, "SLOT",
+				tree_pkg_vdb_eat(pkg_ctx, "SLOT",
 						&pkg_ctx->slot, &pkg_ctx->slot_len);
 				/* chop off the subslot if desired */
 				if (state->show_slots == 1) {
@@ -369,7 +369,7 @@ qlist_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 				}
 			}
 			if (state->show_repo && !pkg_ctx->repo)
-				vdb_pkg_eat(pkg_ctx, "repository",
+				tree_pkg_vdb_eat(pkg_ctx, "repository",
 						&pkg_ctx->repo, &pkg_ctx->repo_len);
 			/* display it */
 			printf("%s%s/%s%s%s%s%s%s%s%s%s%s%s%s%s%s%s\n",
@@ -398,7 +398,7 @@ qlist_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 		printf("%s%s/%s%s%s %sCONTENTS%s:\n",
 				BOLD, catname, BLUE, pkgname, NORM, DKBLUE, NORM);
 
-	fp = vdb_pkg_fopenat_ro(pkg_ctx, "CONTENTS");
+	fp = tree_pkg_vdb_fopenat_ro(pkg_ctx, "CONTENTS");
 	if (fp == NULL)
 		return 1;
 
@@ -444,6 +444,9 @@ qlist_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 
 int qlist_main(int argc, char **argv)
 {
+	int i;
+	int ret;
+	tree_ctx *vdb;
 	struct qlist_opt_state state = {
 		.argc = argc,
 		.argv = argv,
@@ -460,7 +463,6 @@ int qlist_main(int argc, char **argv)
 		.columns = false,
 		.buflen = _Q_PATH_MAX,
 	};
-	int i, ret;
 
 	while ((i = GETOPT_LONG(QLIST, qlist, "")) != -1) {
 		switch (i) {
@@ -489,7 +491,12 @@ int qlist_main(int argc, char **argv)
 
 	state.buf = xmalloc(state.buflen);
 	state.atoms = xcalloc(argc - optind, sizeof(*state.atoms));
-	ret = vdb_foreach_pkg_sorted(portroot, portvdb, qlist_cb, &state);
+	ret = 1;
+	vdb = tree_open_vdb(portroot, portvdb);
+	if (vdb != NULL) {
+		ret = tree_foreach_pkg_sorted(vdb, qlist_cb, &state);
+		tree_close(vdb);
+	}
 	free(state.buf);
 	for (i = optind; i < state.argc; ++i)
 		if (state.atoms[i - optind])
diff --git a/qmerge.c b/qmerge.c
index 41488fa4..e6bbdb5b 100644
--- a/qmerge.c
+++ b/qmerge.c
@@ -30,7 +30,7 @@
 #include "rmspace.h"
 #include "scandirat.h"
 #include "set.h"
-#include "vdb.h"
+#include "tree.h"
 #include "xasprintf.h"
 #include "xchdir.h"
 #include "xmkdir.h"
@@ -118,7 +118,7 @@ typedef struct llist_char_t llist_char;
 
 static void pkg_fetch(int, const depend_atom *, const struct pkg_t *);
 static void pkg_merge(int, const depend_atom *, const struct pkg_t *);
-static int pkg_unmerge(vdb_pkg_ctx *, set *, int, char **, int, char **);
+static int pkg_unmerge(tree_pkg_ctx *, set *, int, char **, int, char **);
 static struct pkg_t *grab_binpkg_info(const char *);
 static char *find_binpkg(const char *);
 
@@ -282,7 +282,7 @@ struct qmerge_bv_state {
 };
 
 static int
-qmerge_filter_cat(vdb_cat_ctx *cat_ctx, void *priv)
+qmerge_filter_cat(tree_cat_ctx *cat_ctx, void *priv)
 {
 	struct qmerge_bv_state *state = priv;
 	return !state->catname || strcmp(cat_ctx->name, state->catname) == 0;
@@ -292,13 +292,13 @@ qmerge_filter_cat(vdb_cat_ctx *cat_ctx, void *priv)
  * should however figure out how to do what match does here from e.g.
  * atom */
 extern bool qlist_match(
-		vdb_pkg_ctx *pkg_ctx,
+		tree_pkg_ctx *pkg_ctx,
 		const char *name,
 		depend_atom **name_atom,
 		bool exact);
 
 static int
-qmerge_best_version_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
+qmerge_best_version_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	struct qmerge_bv_state *state = priv;
 	if (qlist_match(pkg_ctx, state->buf, NULL, true))
@@ -312,6 +312,8 @@ best_version(const char *catname, const char *pkgname, const char *slot)
 {
 	static int vdb_check = 1;
 	static char retbuf[4096];
+
+	tree_ctx *vdb;
 	struct qmerge_bv_state state = {
 		.catname = catname,
 		.pkgname = pkgname,
@@ -338,8 +340,12 @@ best_version(const char *catname, const char *pkgname, const char *slot)
 	retbuf[0] = '\0';
 	snprintf(state.buf, sizeof(state.buf), "%s%s%s:%s",
 		 catname ? : "", catname ? "/" : "", pkgname, slot);
-	vdb_foreach_pkg(portroot, portvdb,
-			qmerge_best_version_cb, &state, qmerge_filter_cat);
+	vdb = tree_open_vdb(portroot, portvdb);
+	if (vdb != NULL) {
+		tree_foreach_pkg_fast(vdb,
+				qmerge_best_version_cb, &state, qmerge_filter_cat);
+		tree_close(vdb);
+	}
 
  done:
 	return retbuf;
@@ -999,8 +1005,8 @@ static void
 pkg_merge(int level, const depend_atom *atom, const struct pkg_t *pkg)
 {
 	set *objs;
-	vdb_ctx *vdb;
-	vdb_cat_ctx *cat_ctx;
+	tree_ctx *vdb;
+	tree_cat_ctx *cat_ctx;
 	FILE *fp, *contents;
 	static char *phases;
 	static size_t phases_len;
@@ -1122,19 +1128,19 @@ pkg_merge(int level, const depend_atom *atom, const struct pkg_t *pkg)
 	}
 
 	/* Get a handle on the main vdb repo */
-	vdb = vdb_open(portroot, portvdb);
+	vdb = tree_open(portroot, portvdb);
 	if (!vdb)
 		return;
-	cat_ctx = vdb_open_cat(vdb, pkg->CATEGORY);
+	cat_ctx = tree_open_cat(vdb, pkg->CATEGORY);
 	if (!cat_ctx) {
 		if (errno != ENOENT) {
-			vdb_close(vdb);
+			tree_close(vdb);
 			return;
 		}
-		mkdirat(vdb->vdb_fd, pkg->CATEGORY, 0755);
-		cat_ctx = vdb_open_cat(vdb, pkg->CATEGORY);
+		mkdirat(vdb->tree_fd, pkg->CATEGORY, 0755);
+		cat_ctx = tree_open_cat(vdb, pkg->CATEGORY);
 		if (!cat_ctx) {
-			vdb_close(vdb);
+			tree_close(vdb);
 			return;
 		}
 	}
@@ -1345,10 +1351,10 @@ pkg_merge(int level, const depend_atom *atom, const struct pkg_t *pkg)
 	/* TODO: Should see about merging with unmerge_packages() */
 	while (1) {
 		int ret;
-		vdb_pkg_ctx *pkg_ctx;
+		tree_pkg_ctx *pkg_ctx;
 		depend_atom *old_atom;
 
-		pkg_ctx = vdb_next_pkg(cat_ctx);
+		pkg_ctx = tree_next_pkg(cat_ctx);
 		if (!pkg_ctx)
 			break;
 
@@ -1377,7 +1383,7 @@ pkg_merge(int level, const depend_atom *atom, const struct pkg_t *pkg)
 
 		pkg_unmerge(pkg_ctx, objs, cp_argc, cp_argv, cpm_argc, cpm_argv);
  next_pkg:
-		vdb_close_pkg(pkg_ctx);
+		tree_close_pkg(pkg_ctx);
 	}
 
 	freeargv(cp_argc, cp_argv);
@@ -1416,14 +1422,14 @@ pkg_merge(int level, const depend_atom *atom, const struct pkg_t *pkg)
 	printf("%s>>>%s %s%s%s/%s%s%s\n",
 			YELLOW, NORM, WHITE, atom->CATEGORY, NORM, CYAN, atom->PN, NORM);
 
-	vdb_close(vdb);
+	tree_close(vdb);
 }
 
 static int
-pkg_unmerge(vdb_pkg_ctx *pkg_ctx, set *keep,
+pkg_unmerge(tree_pkg_ctx *pkg_ctx, set *keep,
 		int cp_argc, char **cp_argv, int cpm_argc, char **cpm_argv)
 {
-	vdb_cat_ctx *cat_ctx = pkg_ctx->cat_ctx;
+	tree_cat_ctx *cat_ctx = pkg_ctx->cat_ctx;
 	const char *cat = cat_ctx->name;
 	const char *pkgname = pkg_ctx->name;
 	size_t buflen;
@@ -1447,7 +1453,7 @@ pkg_unmerge(vdb_pkg_ctx *pkg_ctx, set *keep,
 		return 0;
 
 	/* First get a handle on the things to clean up */
-	fp = vdb_pkg_fopenat_ro(pkg_ctx, "CONTENTS");
+	fp = tree_pkg_vdb_fopenat_ro(pkg_ctx, "CONTENTS");
 	if (fp == NULL)
 		return ret;
 
@@ -1455,7 +1461,7 @@ pkg_unmerge(vdb_pkg_ctx *pkg_ctx, set *keep,
 
 	/* Then execute the pkg_prerm step */
 	if (!pretend) {
-		vdb_pkg_eat(pkg_ctx, "DEFINED_PHASES", &phases, &phases_len);
+		tree_pkg_vdb_eat(pkg_ctx, "DEFINED_PHASES", &phases, &phases_len);
 		mkdirat(pkg_ctx->fd, "temp", 0755);
 		pkg_run_func_at(pkg_ctx->fd, ".", phases, "pkg_prerm", T, T);
 	}
@@ -1587,7 +1593,7 @@ pkg_unmerge(vdb_pkg_ctx *pkg_ctx, set *keep,
 		unlinkat(cat_ctx->fd, pkg_ctx->name, AT_REMOVEDIR);
 
 		/* And prune the category if it's empty */
-		unlinkat(cat_ctx->ctx->vdb_fd, cat_ctx->name, AT_REMOVEDIR);
+		unlinkat(cat_ctx->ctx->tree_fd, cat_ctx->name, AT_REMOVEDIR);
 	}
 
 	ret = 0;
@@ -1776,7 +1782,7 @@ print_Pkg(int full, const depend_atom *atom, const struct pkg_t *pkg)
 }
 
 static int
-qmerge_unmerge_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
+qmerge_unmerge_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	int cp_argc;
 	int cpm_argc;
@@ -1804,7 +1810,13 @@ qmerge_unmerge_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 static int
 unmerge_packages(set *todo)
 {
-	return vdb_foreach_pkg(portroot, portvdb, qmerge_unmerge_cb, todo, NULL);
+	tree_ctx *vdb = tree_open_vdb(portroot, portvdb);
+	int ret = 1;
+	if (vdb != NULL) {
+		ret = tree_foreach_pkg_fast(vdb, qmerge_unmerge_cb, todo, NULL);
+		tree_close(vdb);
+	}
+	return ret;
 }
 
 static FILE *
@@ -2315,7 +2327,7 @@ qmerge_add_set(char *buf, set *q)
 	if (strcmp(buf, "world") == 0)
 		return qmerge_add_set_file("/var/lib/portage", "world", q);
 	else if (strcmp(buf, "all") == 0)
-		return get_vdb_atoms(portroot, portvdb, 0);
+		return tree_get_vdb_atoms(portroot, portvdb, 0);
 	else if (strcmp(buf, "system") == 0)
 		return q_profile_walk("packages", qmerge_add_set_system, q);
 	else if (buf[0] == '@')
diff --git a/qpkg.c b/qpkg.c
index b93823bd..26c14d1d 100644
--- a/qpkg.c
+++ b/qpkg.c
@@ -20,13 +20,12 @@
 
 #include "atom.h"
 #include "basename.h"
-#include "cache.h"
 #include "contents.h"
 #include "human_readable.h"
 #include "md5_sha1_sum.h"
 #include "scandirat.h"
 #include "set.h"
-#include "vdb.h"
+#include "tree.h"
 #include "xarray.h"
 #include "xasprintf.h"
 #include "xchdir.h"
@@ -125,7 +124,7 @@ qpkg_clean_dir(char *dirp, set *vdb)
 }
 
 static int
-qpkg_cb(cache_pkg_ctx *pkg_ctx, void *priv)
+qpkg_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	set *vdb = (set *)priv;
 	depend_atom *atom;
@@ -156,14 +155,19 @@ qpkg_clean(char *dirp)
 	if ((count = scandir(".", &dnames, filter_hidden, alphasort)) < 0)
 		return 1;
 
-	vdb = get_vdb_atoms(portroot, portvdb, 1);
+	vdb = tree_get_vdb_atoms(portroot, portvdb, 1);
 
 	if (eclean) {
 		size_t n;
 		const char *overlay;
 
-		array_for_each(overlays, n, overlay)
-			cache_foreach_pkg(portroot, overlay, qpkg_cb, vdb, NULL);
+		array_for_each(overlays, n, overlay) {
+			tree_ctx *t = tree_open(portroot, overlay);
+			if (t != NULL) {
+				tree_foreach_pkg_fast(t, qpkg_cb, vdb, NULL);
+				tree_close(t);
+			}
+		}
 	}
 
 	num_all_bytes = qpkg_clean_dir(dirp, vdb);
@@ -334,9 +338,9 @@ qpkg_make(depend_atom *atom)
 
 int qpkg_main(int argc, char **argv)
 {
-	vdb_ctx *ctx;
-	vdb_cat_ctx *cat_ctx;
-	vdb_pkg_ctx *pkg_ctx;
+	tree_ctx *ctx;
+	tree_cat_ctx *cat_ctx;
+	tree_pkg_ctx *pkg_ctx;
 	size_t s, pkgs_made;
 	int i;
 	struct stat st;
@@ -417,15 +421,15 @@ retry_mkdir:
 	}
 
 	/* now try to run through vdb and locate matches for user inputs */
-	ctx = vdb_open(portroot, portvdb);
+	ctx = tree_open_vdb(portroot, portvdb);
 	if (!ctx)
 		return EXIT_FAILURE;
 
 	/* scan all the categories */
-	while ((cat_ctx = vdb_next_cat(ctx))) {
+	while ((cat_ctx = tree_next_cat(ctx))) {
 		/* scan all the packages in this category */
 		const char *catname = cat_ctx->name;
-		while ((pkg_ctx = vdb_next_pkg(cat_ctx))) {
+		while ((pkg_ctx = tree_next_pkg(cat_ctx))) {
 			const char *pkgname = pkg_ctx->name;
 
 			/* see if user wants any of these packages */
@@ -449,7 +453,7 @@ retry_mkdir:
 			atom_implode(atom);
 
  next_pkg:
-			vdb_close_pkg(pkg_ctx);
+			tree_close_pkg(pkg_ctx);
 		}
 	}
 
diff --git a/qsearch.c b/qsearch.c
index b6d7410c..f52a5ffd 100644
--- a/qsearch.c
+++ b/qsearch.c
@@ -20,8 +20,8 @@
 
 #include "atom.h"
 #include "basename.h"
-#include "cache.h"
 #include "rmspace.h"
+#include "tree.h"
 #include "xarray.h"
 #include "xregex.h"
 
@@ -57,14 +57,14 @@ struct qsearch_state {
 };
 
 static int
-qsearch_cb(cache_pkg_ctx *pkg_ctx, void *priv)
+qsearch_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	static depend_atom *last_atom;
 
 	struct qsearch_state *state = (struct qsearch_state *)priv;
 	depend_atom *atom;
 	char buf[_Q_PATH_MAX];
-	cache_pkg_meta *meta;
+	tree_pkg_meta *meta;
 	char *desc;
 	char *repo;
 	bool match;
@@ -90,7 +90,7 @@ qsearch_cb(cache_pkg_ctx *pkg_ctx, void *priv)
 	if ((match && (state->show_homepage || state->show_desc)) ||
 			(!match && state->search_desc))
 	{
-		meta = cache_pkg_read(pkg_ctx);
+		meta = tree_pkg_read(pkg_ctx);
 		if (meta != NULL) {
 			if (state->show_homepage)
 				desc = meta->HOMEPAGE;
@@ -115,7 +115,7 @@ qsearch_cb(cache_pkg_ctx *pkg_ctx, void *priv)
 	}
 
 	if (meta != NULL)
-		cache_close_meta(meta);
+		tree_close_meta(meta);
 
 	if (last_atom != NULL)
 		atom_implode(last_atom);
@@ -167,9 +167,13 @@ int qsearch_main(int argc, char **argv)
 	xregcomp(&state.search_expr, search_me, REG_EXTENDED | REG_ICASE);
 
 	/* use sorted order here so the duplicate reduction works reliably */
-	array_for_each(overlays, n, overlay)
-		ret |= cache_foreach_pkg_sorted(portroot, overlay, qsearch_cb,
-				&state, NULL, NULL);
+	array_for_each(overlays, n, overlay) {
+		tree_ctx *t = tree_open(portroot, overlay);
+		if (t != NULL) {
+			ret |= tree_foreach_pkg_sorted(t, qsearch_cb, &state);
+			tree_close(t);
+		}
+	}
 
 	return ret;
 }
diff --git a/qsize.c b/qsize.c
index 4fbbe475..1ae942d5 100644
--- a/qsize.c
+++ b/qsize.c
@@ -51,7 +51,7 @@
 #include "atom.h"
 #include "contents.h"
 #include "human_readable.h"
-#include "vdb.h"
+#include "tree.h"
 #include "xarray.h"
 #include "xregex.h"
 
@@ -97,7 +97,7 @@ struct qsize_opt_state {
 };
 
 static int
-qsize_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
+qsize_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	struct qsize_opt_state *state = priv;
 	const char *catname = pkg_ctx->cat_ctx->name;
@@ -126,7 +126,7 @@ qsize_cb(vdb_pkg_ctx *pkg_ctx, void *priv)
 	if (!showit)
 		return EXIT_SUCCESS;
 
-	if ((fp = vdb_pkg_fopenat_ro(pkg_ctx, "CONTENTS")) == NULL)
+	if ((fp = tree_pkg_vdb_fopenat_ro(pkg_ctx, "CONTENTS")) == NULL)
 		return EXIT_SUCCESS;
 
 	num_ignored = num_files = num_nonfiles = num_bytes = 0;
@@ -181,6 +181,7 @@ int qsize_main(int argc, char **argv)
 {
 	size_t i;
 	int ret;
+	tree_ctx *vdb;
 	DECLARE_ARRAY(ignore_regexp);
 	depend_atom *atom;
 	DECLARE_ARRAY(atoms);
@@ -230,7 +231,11 @@ int qsize_main(int argc, char **argv)
 	state.buflen = _Q_PATH_MAX;
 	state.buf = xmalloc(state.buflen);
 
-	ret = vdb_foreach_pkg(portroot, portvdb, qsize_cb, &state, NULL);
+	vdb = tree_open_vdb(portroot, portvdb);
+	if (vdb != NULL) {
+		ret = tree_foreach_pkg_fast(vdb, qsize_cb, &state, NULL);
+		tree_close(vdb);
+	}
 
 	if (state.summary) {
 		printf(" %sTotals%s: %'zu files, %'zu non-files, ", BOLD, NORM,
diff --git a/quse.c b/quse.c
index 604efdf8..6def799a 100644
--- a/quse.c
+++ b/quse.c
@@ -21,8 +21,8 @@
 #include <ctype.h>
 #include <assert.h>
 
-#include "cache.h"
 #include "rmspace.h"
+#include "tree.h"
 #include "xarray.h"
 #include "xregex.h"
 
@@ -401,12 +401,12 @@ quse_describe_flag(const char *root, const char *overlay,
 }
 
 static int
-quse_results_cb(cache_pkg_ctx *pkg_ctx, void *priv)
+quse_results_cb(tree_pkg_ctx *pkg_ctx, void *priv)
 {
 	struct quse_state *state = (struct quse_state *)priv;
 	depend_atom *atom = NULL;  /* pacify compiler */
 	char buf[8192];
-	cache_pkg_meta *meta;
+	tree_pkg_meta *meta;
 	bool match;
 	char *p;
 	char *q;
@@ -436,7 +436,7 @@ quse_results_cb(cache_pkg_ctx *pkg_ctx, void *priv)
 		}
 	}
 
-	meta = cache_pkg_read(pkg_ctx);
+	meta = tree_pkg_read(pkg_ctx);
 	if (meta == NULL)
 		return 0;
 
@@ -591,7 +591,7 @@ quse_results_cb(cache_pkg_ctx *pkg_ctx, void *priv)
 		}
 	}
 
-	cache_close_meta(meta);
+	tree_close_meta(meta);
 	if (state->match && verbose)
 		atom_implode(atom);
 	if (verbose)
@@ -656,9 +656,12 @@ int quse_main(int argc, char **argv)
 			quse_describe_flag(portroot, overlay, &state);
 	} else {
 		array_for_each(overlays, n, overlay) {
+			tree_ctx *t = tree_open(portroot, overlay);
 			state.overlay = overlay;
-			cache_foreach_pkg_sorted(portroot, overlay,
-					quse_results_cb, &state, NULL, NULL);
+			if (t != NULL) {
+				tree_foreach_pkg_sorted(t, quse_results_cb, &state);
+				tree_close(t);
+			}
 		}
 	}