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