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
