pkgsrc-Changes archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
CVS commit: pkgsrc/pkgtools
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.
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 <joerg%NetBSD.org@localhost>.
@@ -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 <joerg%NetBSD.org@localhost>.
@@ -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;
};
Home |
Main Index |
Thread Index |
Old Index