 @@ -1,14 +1,14 @@
-/* $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>.
  * All rights reserved.
+ *
  * This code was developed as part of Google's Summer of Code 2007 program.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
+ *
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
 @@ -54,27 +54,28 @@ static int log_failed;
 SLIST_HEAD(buildhash, build_job);
 static void build_tree(void);
 static void mark_initial(void);
 static struct buildhash *get_hash_chain(const char *, size_t);
 static void hash_entries(void);
 static void add_to_build_list(struct build_job *);
 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)))
 #endif
 static void
 ts_printf(const char *fmt, ...)
+{
 	struct tm *tm;
 	time_t now;
 	va_list ap;
 	char buf[512];
 	struct build_stat st;
 @@ -183,28 +184,26 @@ compute_tree_depth(struct build_job *job
 	job->pkg_weighted_depth = 0;
 	if (compute_tree_depth_rec(job, job, seen))
 		exit(1);
+}
 void
 init_jobs(const char *scan_output, const char *success_file, const char *error_file)
+{
 	char *input, *seen;
 	const char *input_iter;
 	int fd;
 	size_t i;
 	TAILQ_INIT(&buildable_jobs);
 	if ((fd = open(scan_output, O_RDONLY, 0)) == -1)
 		err(1, "Cannot open input");
 	log_success = open(success_file, O_RDWR | O_CREAT | O_APPEND, 0666);
 	if (log_success == -1)
 		err(1, "Cannot open log file for successful builds");
 	log_failed = open(error_file, O_RDWR | O_CREAT | O_APPEND, 0666);
 	if (log_failed == -1)
 		err(1, "Cannot open log file for failed builds");
 	input = read_from_file(fd);
 	(void)close(fd);
 @@ -225,26 +224,29 @@ init_jobs(const char *scan_output, const
 			errx(1, "Invalid input");
 		input_iter = jobs[len_jobs].end;
 		++len_jobs;
 		if (len_jobs == allocated_jobs) {
 			allocated_jobs *= 2;
 			jobs = xrealloc(jobs, allocated_jobs * sizeof(*jobs));
+		}
+	}
 	if (*input_iter != '\0')
 		errx(1, "Invalid input");
 	scan_output_content = input;
 	buildable_jobs = xmalloc(len_jobs * sizeof(*buildable_jobs));
 	buildable_jobs_len = 0;
 	hash_entries();
 	build_tree();
 	seen = xmalloc(len_jobs);
 	for (i = 0; i < len_jobs; ++i)
 		compute_tree_depth(&jobs[i], seen);
 	free(seen);
 	mark_initial();
 	for (i = 0; i < len_jobs; ++i) {
 		if (jobs[i].state == JOB_INIT)
 			process_job(&jobs[i], JOB_OPEN, 0);
 @@ -325,37 +327,51 @@ mark_initial(void)
 			continue;
+		}
+	}
 	mark_initial_state(log_success, JOB_DONE, "successful");
 	mark_initial_state(log_failed, JOB_FAILED, "failing");
 	if (verbosity >= 1)
 		printf("Initialisation complete.\n");
 	post_initial = 1;
+}
 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) {
+	job->buildable_index = buildable_jobs_len++;
-		if (iter->pkg_weighted_depth < job->pkg_weighted_depth) {
+	buildable_jobs[job->buildable_index] = job;
-			TAILQ_INSERT_BEFORE(iter, job, build_link);
+	while ((idx = job->buildable_index)) {
-			return;
+		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
 build_tree(void)
+{
 	size_t i, len;
 	struct build_job *iter, *job;
 	struct dependency_list *dep;
 	const char *depends;
 	for (i = 0; i < len_jobs; ++i) {
 		job = &jobs[i];
 @@ -379,39 +395,76 @@ build_tree(void)
 			dep->dependency = job;
 			SLIST_INSERT_HEAD(&iter->depending_pkgs, dep, depends_link);
 			++job->open_depends;
 			depends += len;
 			depends += strspn(depends, " \t");
+		}
+	}
+}
 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 *
 get_job(void)
+{
 	struct build_job *job;
-	if ((job = TAILQ_FIRST(&buildable_jobs)) != NULL) {
+	if (buildable_jobs_len == 0)
-		TAILQ_REMOVE(&buildable_jobs, job, build_link);
+		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;
+}
 static void
 recursive_mark_broken(struct build_job *job, enum job_state state)
+{
 	struct dependency_list *iter;
 	SLIST_FOREACH(iter, &job->depending_pkgs, depends_link) {
 		if (iter->dependency->state == JOB_OPEN ||
 		    iter->dependency->state == JOB_INIT)
 			process_job(iter->dependency, state, 0);
+	}

 @@ -1,14 +1,14 @@
-/* $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>.
  * All rights reserved.
+ *
  * This code was developed as part of Google's Summer of Code 2007 program.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
+ *
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
 @@ -98,27 +98,27 @@ struct build_job {
 	int pkg_depth;
 	long long pkg_weighted_depth;
 	long long pkg_weight;
 	/**
 	 * The number of direct dependencies that must be built before
 	 * this package can be tried.
 	 */
 	size_t open_depends;
 	/** 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;
 };
 extern int		 verbosity;
 void			 init_jobs(const char *, const char *, const char *);
 int			 has_job(void);
 struct build_job	*get_job(void);
 void			 process_job(struct build_job *, enum job_state, int);
 int			 build_package(const char *, size_t);
 void			 finish_build(const char *);
 void			 build_stats(struct build_stat *);

 @@ -1,16 +1,16 @@
-# $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"
 USE_FEATURES=	nbcompat
 USE_TOOLS+=	nroff
 INSTALLATION_DIRS=	bin ${PKGMANDIR}/cat1 ${PKGMANDIR}/man1
 USE_BSD_MAKEFILE=	yes
 MAKE_FLAGS+=		CWARNFLAGS.clang=-Wno-error=missing-noreturn
 CONFLICTS=	pbulk<0.39