Received: by mail.netbsd.org (Postfix, from userid 605) id 9B39D84EF3; Sun, 12 Feb 2023 21:17:26 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id CA69784D13 for ; Sun, 12 Feb 2023 21:17:25 +0000 (UTC) X-Virus-Scanned: amavisd-new at netbsd.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.netbsd.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id gQubRbgFPrkb for ; Sun, 12 Feb 2023 21:17:25 +0000 (UTC) Received: from cvs.NetBSD.org (ivanova.NetBSD.org [IPv6:2001:470:a085:999:28c:faff:fe03:5984]) by mail.netbsd.org (Postfix) with ESMTP id E9B4484CEA for ; Sun, 12 Feb 2023 21:17:24 +0000 (UTC) Received: by cvs.NetBSD.org (Postfix, from userid 500) id DDCECFA90; Sun, 12 Feb 2023 21:17:24 +0000 (UTC) Content-Transfer-Encoding: 7bit Content-Type: multipart/mixed; boundary="_----------=_1676236644248140" MIME-Version: 1.0 Date: Sun, 12 Feb 2023 21:17:24 +0000 From: "Joerg Sonnenberger" Subject: CVS commit: pkgsrc/pkgtools To: pkgsrc-changes@NetBSD.org Reply-To: joerg@netbsd.org X-Mailer: log_accum Message-Id: <20230212211724.DDCECFA90@cvs.NetBSD.org> Sender: pkgsrc-changes-owner@NetBSD.org List-Id: Precedence: bulk List-Unsubscribe: This is a multi-part message in MIME format. --_----------=_1676236644248140 Content-Disposition: inline Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII" Module Name: pkgsrc Committed By: joerg Date: Sun Feb 12 21:17:24 UTC 2023 Modified Files: pkgsrc/pkgtools/pbulk-base: Makefile pkgsrc/pkgtools/pbulk/files/pbulk/pbuild: jobs.c pbuild.h Log Message: pbulk-0.57: switch to a binary heap for the build queue To generate a diff of this commit: cvs rdiff -u -r1.27 -r1.28 pkgsrc/pkgtools/pbulk-base/Makefile cvs rdiff -u -r1.19 -r1.20 pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c cvs rdiff -u -r1.9 -r1.10 pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files. --_----------=_1676236644248140 Content-Disposition: inline Content-Length: 5035 Content-Transfer-Encoding: binary Content-Type: text/x-diff; charset=us-ascii Modified files: Index: pkgsrc/pkgtools/pbulk-base/Makefile diff -u pkgsrc/pkgtools/pbulk-base/Makefile:1.27 pkgsrc/pkgtools/pbulk-base/Makefile:1.28 --- pkgsrc/pkgtools/pbulk-base/Makefile:1.27 Sun Feb 12 04:12:54 2023 +++ pkgsrc/pkgtools/pbulk-base/Makefile Sun Feb 12 21:17:24 2023 @@ -1,6 +1,6 @@ -# $NetBSD: Makefile,v 1.27 2023/02/12 04:12:54 joerg Exp $ +# $NetBSD: Makefile,v 1.28 2023/02/12 21:17:24 joerg Exp $ -DISTNAME= pbulk-base-0.56 +DISTNAME= pbulk-base-0.57 COMMENT= Core components of the modular bulk build framework .include "../../pkgtools/pbulk/Makefile.common" Index: pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c diff -u pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c:1.19 pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c:1.20 --- pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c:1.19 Sun Feb 12 04:12:54 2023 +++ pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c Sun Feb 12 21:17:24 2023 @@ -1,4 +1,4 @@ -/* $NetBSD: jobs.c,v 1.19 2023/02/12 04:12:54 joerg Exp $ */ +/* $NetBSD: jobs.c,v 1.20 2023/02/12 21:17:24 joerg Exp $ */ /*- * Copyright (c) 2007, 2009, 2011 Joerg Sonnenberger . @@ -64,7 +64,8 @@ static struct build_job *jobs; static size_t allocated_jobs, len_jobs; static char *scan_output_content; -static TAILQ_HEAD(, build_job) buildable_jobs; +static struct build_job **buildable_jobs; +static size_t buildable_jobs_len; #if defined(__GNUC__) && __GNUC__ >= 2 __attribute__((__format__(__printf__, 1, 2))) @@ -193,8 +194,6 @@ init_jobs(const char *scan_output, const int fd; size_t i; - TAILQ_INIT(&buildable_jobs); - if ((fd = open(scan_output, O_RDONLY, 0)) == -1) err(1, "Cannot open input"); @@ -235,6 +234,9 @@ init_jobs(const char *scan_output, const errx(1, "Invalid input"); scan_output_content = input; + buildable_jobs = xmalloc(len_jobs * sizeof(*buildable_jobs)); + buildable_jobs_len = 0; + hash_entries(); build_tree(); @@ -335,17 +337,31 @@ mark_initial(void) } static void +swap_buildable_entries(size_t i, size_t j) +{ + struct build_job *job1, *job2; + + job1 = buildable_jobs[i]; + job2 = buildable_jobs[j]; + job1->buildable_index = j; + job2->buildable_index = i; + buildable_jobs[i] = job2; + buildable_jobs[j] = job1; +} + +static void add_to_build_list(struct build_job *job) { - struct build_job *iter; + size_t idx; - TAILQ_FOREACH(iter, &buildable_jobs, build_link) { - if (iter->pkg_weighted_depth < job->pkg_weighted_depth) { - TAILQ_INSERT_BEFORE(iter, job, build_link); - return; - } + job->buildable_index = buildable_jobs_len++; + buildable_jobs[job->buildable_index] = job; + while ((idx = job->buildable_index)) { + if (buildable_jobs[(idx - 1) / 2]->pkg_weighted_depth >= + job->pkg_weighted_depth) + break; + swap_buildable_entries(idx, (idx - 1) / 2); } - TAILQ_INSERT_TAIL(&buildable_jobs, job, build_link); } static void @@ -389,7 +405,41 @@ build_tree(void) int has_job(void) { - return !TAILQ_EMPTY(&buildable_jobs); + return buildable_jobs_len != 0; +} + +static void +buildable_jobs_remove_head(void) +{ + size_t idx, idx2; + + --buildable_jobs_len; + if (buildable_jobs_len == 0) + return; + + /* Move last element to head */ + buildable_jobs[0] = buildable_jobs[buildable_jobs_len]; + buildable_jobs[0]->buildable_index = 0; + + idx = 0; + for (;;) { + /* Find biggest child. */ + idx2 = idx; + if (idx * 2 + 1 < buildable_jobs_len && + buildable_jobs[2 * idx + 1]->pkg_weighted_depth > + buildable_jobs[idx2]->pkg_weighted_depth) { + idx2 = 2 * idx + 1; + } + if (idx * 2 + 2 < buildable_jobs_len && + buildable_jobs[2 * idx + 2]->pkg_weighted_depth > + buildable_jobs[idx2]->pkg_weighted_depth) { + idx2 = 2 * idx + 2; + } + if (idx == idx2) + break; + swap_buildable_entries(idx, idx2); + idx = idx2; + } } struct build_job * @@ -397,11 +447,14 @@ get_job(void) { struct build_job *job; - if ((job = TAILQ_FIRST(&buildable_jobs)) != NULL) { - TAILQ_REMOVE(&buildable_jobs, job, build_link); + if (buildable_jobs_len == 0) + return NULL; + + job = buildable_jobs[0]; + process_job(job, JOB_IN_PROCESSING, 0); + + buildable_jobs_remove_head(); - process_job(job, JOB_IN_PROCESSING, 0); - } return job; } Index: pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h diff -u pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h:1.9 pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h:1.10 --- pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h:1.9 Sun Feb 12 04:12:54 2023 +++ pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h Sun Feb 12 21:17:24 2023 @@ -1,4 +1,4 @@ -/* $NetBSD: pbuild.h,v 1.9 2023/02/12 04:12:54 joerg Exp $ */ +/* $NetBSD: pbuild.h,v 1.10 2023/02/12 21:17:24 joerg Exp $ */ /*- * Copyright (c) 2007 Joerg Sonnenberger . @@ -108,7 +108,7 @@ struct build_job { /** The packages that depend on this package. */ SLIST_HEAD(, dependency_list) depending_pkgs; - TAILQ_ENTRY(build_job) build_link; + size_t buildable_index; SLIST_ENTRY(build_job) hash_link; }; --_----------=_1676236644248140--