From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by finch.gentoo.org (Postfix) with ESMTPS id 0561A138334 for ; Fri, 10 May 2019 15:33:05 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 53128E0831; Fri, 10 May 2019 15:33:03 +0000 (UTC) Received: from smtp.gentoo.org (smtp.gentoo.org [140.211.166.183]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id 052DEE0844 for ; Fri, 10 May 2019 15:33:02 +0000 (UTC) Received: from oystercatcher.gentoo.org (unknown [IPv6:2a01:4f8:202:4333:225:90ff:fed9:fc84]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.gentoo.org (Postfix) with ESMTPS id 690D1343F79 for ; Fri, 10 May 2019 15:33:01 +0000 (UTC) Received: from localhost.localdomain (localhost [IPv6:::1]) by oystercatcher.gentoo.org (Postfix) with ESMTP id D3E3E5E2 for ; Fri, 10 May 2019 15:32:59 +0000 (UTC) From: "Fabian Groffen" To: gentoo-commits@lists.gentoo.org Content-Transfer-Encoding: 8bit Content-type: text/plain; charset=UTF-8 Reply-To: gentoo-dev@lists.gentoo.org, "Fabian Groffen" Message-ID: <1557501805.f855d0f4f7c3e6e570a1ad3dc98d737e78996e4a.grobian@gentoo> Subject: [gentoo-commits] proj/portage-utils:master commit in: libq/ X-VCS-Repository: proj/portage-utils X-VCS-Files: libq/tree.c libq/tree.h X-VCS-Directories: libq/ X-VCS-Committer: grobian X-VCS-Committer-Name: Fabian Groffen X-VCS-Revision: f855d0f4f7c3e6e570a1ad3dc98d737e78996e4a X-VCS-Branch: master Date: Fri, 10 May 2019 15:32:59 +0000 (UTC) Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-commits@lists.gentoo.org X-Auto-Response-Suppress: DR, RN, NRN, OOF, AutoReply X-Archives-Salt: 25d0b09b-b710-465e-bd17-6e0cc2439ebd X-Archives-Hash: 97c1b7ed7037bbe38b42fe8159b5d2d7 commit: f855d0f4f7c3e6e570a1ad3dc98d737e78996e4a Author: Fabian Groffen gentoo org> AuthorDate: Fri May 10 15:23:25 2019 +0000 Commit: Fabian Groffen gentoo org> CommitDate: Fri May 10 15:23:25 2019 +0000 URL: https://gitweb.gentoo.org/proj/portage-utils.git/commit/?id=f855d0f4 libq/tree: make pkg sorting based on atom_compare Using alphasort on pkgs makes little sense because they include version information that needs careful extraction and matching rules as implemented by atom_compare. In order to use atom_compare efficiently, that is, reusing the atom_explode work done for the elements while running qsort, use tree_get_atom, which caches the retrieved atom. Extra bonus is that any function that retrieves the atom afterwards gets it for free. This speeds up significantly apps that need to construct atoms, such as qkeywords. Signed-off-by: Fabian Groffen gentoo.org> libq/tree.c | 65 +++++++++++++++++++++++++++++++++++++++++++++++-------------- libq/tree.h | 2 +- 2 files changed, 51 insertions(+), 16 deletions(-) diff --git a/libq/tree.c b/libq/tree.c index c8b4b5e..86dd18f 100644 --- a/libq/tree.c +++ b/libq/tree.c @@ -25,6 +25,8 @@ #include #include +static int tree_pkg_compar(const void *l, const void *r); + static tree_ctx * tree_open_int(const char *sroot, const char *tdir, bool quiet) { @@ -56,7 +58,7 @@ tree_open_int(const char *sroot, const char *tdir, bool quiet) ctx->do_sort = false; ctx->cat_de = NULL; ctx->catsortfunc = alphasort; - ctx->pkgsortfunc = alphasort; + ctx->pkgsortfunc = tree_pkg_compar; ctx->repo = NULL; ctx->ebuilddir_ctx = NULL; ctx->ebuilddir_pkg_ctx = NULL; @@ -208,7 +210,7 @@ tree_open_cat(tree_ctx *ctx, const char *name) cat_ctx->fd = fd; cat_ctx->dir = dir; cat_ctx->ctx = ctx; - cat_ctx->pkg_de = NULL; + cat_ctx->pkg_ctxs = NULL; return cat_ctx; } @@ -260,7 +262,7 @@ tree_close_cat(tree_cat_ctx *cat_ctx) /* 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->pkg_ctxs); free(cat_ctx); } @@ -309,30 +311,63 @@ tree_open_pkg(tree_cat_ctx *cat_ctx, const char *name) return pkg_ctx; } +static int +tree_pkg_compar(const void *l, const void *r) +{ + tree_pkg_ctx *pl = *(tree_pkg_ctx **)l; + tree_pkg_ctx *pr = *(tree_pkg_ctx **)r; + depend_atom *al = tree_get_atom(pl, false); + depend_atom *ar = tree_get_atom(pr, false); + + switch (atom_compare(al, ar)) { + case EQUAL: return 0; + case NEWER: return -1; + case OLDER: return 1; + default: return strcmp(al->PN, ar->PN); + } + + /* unreachable */ +} + 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; + const struct dirent *de; 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); + if (cat_ctx->pkg_ctxs == NULL) { + size_t pkg_size = 0; + cat_ctx->pkg_ctxs = NULL; + cat_ctx->pkg_cnt = 0; cat_ctx->pkg_cur = 0; - } + while ((de = readdir(cat_ctx->dir)) != NULL) { + if (tree_filter_pkg(de) == 0) + continue; + + if (cat_ctx->pkg_cnt == pkg_size) { + pkg_size += 256; + cat_ctx->pkg_ctxs = xrealloc(cat_ctx->pkg_ctxs, + sizeof(*cat_ctx->pkg_ctxs) * pkg_size); + } + pkg_ctx = cat_ctx->pkg_ctxs[cat_ctx->pkg_cnt++] = + tree_open_pkg(cat_ctx, de->d_name); + if (pkg_ctx == NULL) + cat_ctx->pkg_cnt--; + } - 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; + if (cat_ctx->ctx->pkgsortfunc != NULL) { + qsort(cat_ctx->pkg_ctxs, cat_ctx->pkg_cnt, + sizeof(*cat_ctx->pkg_ctxs), cat_ctx->ctx->pkgsortfunc); + } } + + pkg_ctx = NULL; + if (cat_ctx->pkg_cur < cat_ctx->pkg_cnt) + pkg_ctx = cat_ctx->pkg_ctxs[cat_ctx->pkg_cur++]; } else { - const struct dirent *de; do { de = readdir(cat_ctx->dir); if (!de) diff --git a/libq/tree.h b/libq/tree.h index 7f05819..36554be 100644 --- a/libq/tree.h +++ b/libq/tree.h @@ -48,7 +48,7 @@ struct tree_cat_ctx { int fd; DIR *dir; tree_ctx *ctx; - struct dirent **pkg_de; + tree_pkg_ctx **pkg_ctxs; size_t pkg_cnt; size_t pkg_cur; };