[gentoo-commits] proj/portage-utils:master commit in: libq/

[Fabian Groffen]

commit:     dadb2666f54fed0478e0914d9fc4349f27730d58
Author:     Fabian Groffen <grobian <AT> gentoo <DOT> org>
AuthorDate: Sun Jan 19 09:46:18 2020 +0000
Commit:     Fabian Groffen <grobian <AT> gentoo <DOT> org>
CommitDate: Sun Jan 19 09:46:18 2020 +0000
URL:        https://gitweb.gentoo.org/proj/portage-utils.git/commit/?id=dadb2666

libq/tree: add initial tree_match_atom with caching

tree_match_atom is meant for retrieving the best matching element from a
tree based on a query.  It caches the underlying packages it traverses,
such that repetitive lookups will benefit from previous lookups.  This
comes in handy for recursive scenarios such as when
calculating/resolving dependencies.

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

 libq/tree.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 libq/tree.h |  4 ++++
 2 files changed, 84 insertions(+)

diff --git a/libq/tree.c b/libq/tree.c
index 0df2e0d..f87e751 100644
--- a/libq/tree.c
+++ b/libq/tree.c
@@ -148,6 +148,24 @@ tree_open_binpkg(const char *sroot, const char *spkg)
 void
 tree_close(tree_ctx *ctx)
 {
+	if (ctx->cache.categories != NULL) {
+		DECLARE_ARRAY(t);
+		size_t n;
+		tree_cat_ctx *cat;
+
+		values_set(ctx->cache.categories, t);
+		free_set(ctx->cache.categories);
+		ctx->cache.categories = NULL;  /* must happen before close_cat */
+
+		array_for_each(t, n, cat) {
+			/* ensure we cleanup all pkgs */
+			cat->pkg_cur = 0;
+			tree_close_cat(cat);
+		}
+
+		xarrayfree_int(t);
+	}
+
 	closedir(ctx->dir);
 	/* closedir() above does this for us: */
 	/* close(ctx->tree_fd); */
@@ -212,6 +230,21 @@ tree_open_cat(tree_ctx *ctx, const char *name)
 	int fd;
 	DIR *dir;
 
+	/* lookup in the cache, if any */
+	if (ctx->cache.categories != NULL) {
+		cat_ctx = get_set(name, ctx->cache.categories);
+		if (cat_ctx != NULL) {
+			/* reset state so it can be re-iterated (sort benefits the
+			 * most here) */
+			if (ctx->do_sort) {
+				cat_ctx->pkg_cur = 0;
+			} else {
+				rewinddir(cat_ctx->dir);
+			}
+			return cat_ctx;
+		}
+	}
+
 	/* Cannot use O_PATH as we want to use fdopendir() */
 	fd = openat(ctx->tree_fd, name, O_RDONLY | O_CLOEXEC);
 	if (fd == -1)
@@ -229,6 +262,13 @@ tree_open_cat(tree_ctx *ctx, const char *name)
 	cat_ctx->dir = dir;
 	cat_ctx->ctx = ctx;
 	cat_ctx->pkg_ctxs = NULL;
+
+	if (ctx->cache.categories != NULL) {
+		add_set_value(name, cat_ctx, ctx->cache.categories);
+		/* ensure name doesn't expire after this instantiation is closed */
+		cat_ctx->name = contains_set(name, ctx->cache.categories);
+	}
+
 	return cat_ctx;
 }
 
@@ -289,6 +329,14 @@ tree_next_cat(tree_ctx *ctx)
 void
 tree_close_cat(tree_cat_ctx *cat_ctx)
 {
+	if (cat_ctx->ctx->cache.categories != NULL &&
+			contains_set(cat_ctx->name, cat_ctx->ctx->cache.categories))
+		return;
+
+	/* cleanup unreturned pkgs when sorted (or cache in use) */
+	while (cat_ctx->pkg_cur < cat_ctx->pkg_cnt)
+		tree_close_pkg(cat_ctx->pkg_ctxs[cat_ctx->pkg_cur++]);
+
 	closedir(cat_ctx->dir);
 	/* closedir() above does this for us: */
 	/* close(ctx->fd); */
@@ -1439,3 +1487,35 @@ tree_get_atoms(tree_ctx *ctx, bool fullcpv, set *satoms)
 
 	return state.cpf;
 }
+
+tree_pkg_ctx *
+tree_match_atom(tree_ctx *ctx, depend_atom *a)
+{
+	tree_cat_ctx *cat_ctx;
+	tree_pkg_ctx *pkg_ctx;
+	depend_atom *atom;
+
+	if (ctx->cache.categories == NULL)
+		ctx->cache.categories = create_set();
+
+	if (a->P == NULL) {
+		return NULL;
+	} else if (a->CATEGORY == NULL) {
+		/* loop through all cats and recurse */
+		/* TODO: some day */
+		return NULL;
+	} else {
+		/* try CAT, and PN for latest version */
+		if ((cat_ctx = tree_open_cat(ctx, a->CATEGORY)) == NULL)
+			return NULL;
+		ctx->do_sort = true;     /* sort uses buffer, which cache relies on */
+		ctx->query_atom = NULL;  /* ensure the cache contains ALL pkgs */
+		while ((pkg_ctx = tree_next_pkg(cat_ctx)) != NULL) {
+			atom = tree_get_atom(pkg_ctx, a->SLOT != NULL);
+			if (atom_compare(atom, a) == EQUAL)
+				return pkg_ctx;
+		}
+
+		return NULL;
+	}
+}

diff --git a/libq/tree.h b/libq/tree.h
index 6627e80..eaee7ad 100644
--- a/libq/tree.h
+++ b/libq/tree.h
@@ -44,6 +44,9 @@ struct tree_ctx {
 	char *pkgs;
 	size_t pkgslen;
 	depend_atom *query_atom;
+	struct tree_cache {
+		set *categories;
+	} cache;
 };
 
 /* Category context */
@@ -135,5 +138,6 @@ int tree_foreach_pkg(tree_ctx *ctx, tree_pkg_cb callback, void *priv,
 	tree_foreach_pkg(ctx, cb, priv, true, query);
 set *tree_get_atoms(tree_ctx *ctx, bool fullcpv, set *satoms);
 depend_atom *tree_get_atom(tree_pkg_ctx *pkg_ctx, bool complete);
+tree_pkg_ctx *tree_match_atom(tree_ctx *t, depend_atom *a);
 
 #endif