htab: init

7 files changed, 238 insertions, 85 deletions

diff --git a/include/htab.h b/include/htab.h
new file mode 100644
index 0000000..70a0893
--- /dev/null
+++ b/include/htab.h
@@ -0,0 +1,18 @@
+#include <search.h>
+
+#ifndef HTAB_H
+
+struct htab {
+	struct hsearch_data *table;
+	char **keys;
+	size_t keys_size, key_filled;
+};
+
+void htab_free(struct htab *htab);
+int htab_init(struct htab **htab);
+int htab_delete(struct htab *htab, const char *key);
+int htab_enter(struct htab *htab, const char *key, void *data);
+int htab_search(struct htab *htab, char *key, ENTRY **ep);
+
+#define HTAB_H
+#endif
diff --git a/include/jobs.h b/include/jobs.h
index 623eaea..d4916f7 100644
--- a/include/jobs.h
+++ b/include/jobs.h
@@ -1,5 +1,5 @@
-#include <stdio.h>
 #include <stdbool.h>
+#include <stdio.h>
 #include <sys/queue.h>
 
 #ifndef JOBS_H
@@ -36,6 +36,7 @@ int job_read(FILE *stream, struct job **jobs);
 int jobs_init(FILE **stream);
 void job_free(struct job *j);
 int job_parents_list_insert(struct job *job, struct job *parent);
+void job_deps_list_rm(struct job *job, struct job *dep);
 
 #define JOBS_H
 #endif
diff --git a/include/queue.h b/include/queue.h
index c454339..4aca54b 100644
--- a/include/queue.h
+++ b/include/queue.h
@@ -3,6 +3,7 @@
 #include <semaphore.h>
 #include <sys/queue.h>
 
+#include "htab.h"
 #include "jobs.h"
 
 #ifndef QUEUE_H
@@ -14,7 +15,7 @@ typedef enum {
 
 struct queue {
 	struct job_clist jobs;
-	struct hsearch_data *htab;
+	struct htab *htab;
 	sem_t sem;
 	queue_state_t state;
 	pthread_mutex_t mutex;
@@ -29,7 +30,7 @@ struct queue_thread {
 int queue_thread_new(struct queue_thread **queue_thread, FILE *stream);
 void queue_thread_free(struct queue_thread *queue_thread);
 void *queue_thread_entry(void *queue_thread);
-int queue_pop(struct queue *queue, struct job **job, struct hsearch_data *htab);
+int queue_pop(struct queue *queue, struct job **job, struct htab *htab);
 
 #define QUEUE_H
 #endif
diff --git a/src/htab.c b/src/htab.c
new file mode 100644
index 0000000..dde8430
--- /dev/null
+++ b/src/htab.c
@@ -0,0 +1,150 @@
+/* since hsearch_r does not support deletions dirctly, this is an abstraction on
+ * top of it with support for deletions, for this to work properly we have to
+ * strdup the key, this is not a big issue for 100k drv_path strings, it's
+ * either this or pulling in a external library
+ */
+
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "htab.h"
+#include "util.h"
+
+#define MAX_NIX_PKG_COUNT 200000
+
+static int htab_keys_insert(struct htab *htab, char *key);
+
+static int htab_keys_insert(struct htab *htab, char *key)
+{
+	size_t newsize;
+	void *ret;
+
+	if (htab->key_filled < htab->keys_size) {
+		htab->keys[htab->key_filled++] = key;
+		return 0;
+	}
+
+	newsize = htab->keys_size == 0 ? 1 : htab->keys_size * 2;
+	ret = realloc(htab->keys, newsize * sizeof(*htab->keys));
+	if (ret == NULL) {
+		print_err("%s", strerror(errno));
+		return -errno;
+	}
+
+	htab->keys = ret;
+	htab->keys_size = newsize;
+	htab->keys[htab->key_filled++] = key;
+
+	return 0;
+}
+
+int htab_search(struct htab *htab, char *key, ENTRY **ep)
+{
+	ENTRY e;
+	int ret;
+
+	e.key = key;
+	e.data = NULL;
+	ret = hsearch_r(e, FIND, ep, htab->table);
+	if (ret == 0) {
+		if (errno != ESRCH) {
+			print_err("%s", strerror(errno));
+			return -errno;
+		}
+		return ESRCH;
+	}
+
+	if ((*ep)->data == NULL) {
+		return ESRCH;
+	} else {
+		return 0;
+	}
+}
+
+int htab_enter(struct htab *htab, const char *key, void *data)
+{
+	ENTRY e, *ep;
+	int ret;
+
+	e.key = strdup(key);
+	if (e.key == NULL) {
+		print_err("%s", strerror(errno));
+		return -errno;
+	}
+
+	e.data = data;
+	ret = hsearch_r(e, ENTER, &ep, htab->table);
+	if (ret == 0) {
+		print_err("%s", strerror(errno));
+		return -errno;
+	}
+	ep->data = NULL;
+
+	if (ep->key != e.key) {
+		free(e.key);
+	} else {
+		ret = htab_keys_insert(htab, e.key);
+		if (ret < 0)
+			free(e.key);
+	}
+
+	return ret;
+}
+
+int htab_delete(struct htab *htab, const char *key)
+{
+	return htab_enter(htab, key, NULL);
+}
+
+int htab_init(struct htab **htab)
+{
+	int ret;
+	struct htab *h;
+
+	h = malloc(sizeof(*h));
+	if (h == NULL) {
+		print_err("%s", strerror(errno));
+		return -errno;
+	}
+
+	h->table = calloc(1, sizeof(*h->table));
+	if (h == NULL) {
+		print_err("%s", strerror(errno));
+		ret = -errno;
+		goto out_free_h;
+	}
+
+	ret = hcreate_r(MAX_NIX_PKG_COUNT, h->table);
+	if (ret == 0) {
+		print_err("%s", strerror(errno));
+		ret = -errno;
+		goto out_free_table;
+	}
+	ret = 0;
+
+	h->keys = NULL;
+	h->keys_size = 0;
+	h->key_filled = 0;
+
+out_free_table:
+	if (ret < 0)
+		free(h->table);
+out_free_h:
+	if (ret < 0)
+		free(h);
+	else
+		*htab = h;
+
+	return ret;
+}
+
+void htab_free(struct htab *htab)
+{
+	for (size_t i = 0; i < htab->key_filled; i++)
+		free(htab->keys[i]);
+
+	free(htab->keys);
+	free(htab->table);
+	free(htab);
+}
diff --git a/src/jobs.c b/src/jobs.c
index 28273dd..3e38b07 100644
--- a/src/jobs.c
+++ b/src/jobs.c
@@ -16,7 +16,6 @@ static int job_read_inputdrvs(struct job *job, cJSON *input_drvs);
 static int job_read_outputs(struct job *job, cJSON *outputs);
 static int job_deps_list_insert(struct job *job, struct job *dep);
 static int job_output_list_insert(struct job *job, struct output *output);
-static void job_deps_list_rm(struct job *job, struct job *dep);
 
 static void output_free(struct output *output)
 {
@@ -53,7 +52,7 @@ static int job_output_list_insert(struct job *job, struct output *output)
 	return 0;
 }
 
-static void job_deps_list_rm(struct job *job, struct job *dep)
+void job_deps_list_rm(struct job *job, struct job *dep)
 {
 	for (size_t i = 0; i < job->deps_filled; i++) {
 		if (job->deps[i] != dep)
@@ -370,7 +369,7 @@ int jobs_init(FILE **stream)
 	char *const args[] = {
 		"nix-eval-jobs",
 		"--flake",
-		"github:sinanmohd/evanix#packages.x86_64-linux",
+		"github:NixOS/nixpkgs#legacyPackages.x86_64-linux.python310Packages",
 		NULL,
 	};
 
diff --git a/src/meson.build b/src/meson.build
index 41b31da..ea955bc 100644
--- a/src/meson.build
+++ b/src/meson.build
@@ -6,6 +6,7 @@ e = executable(
 		'util.c',
 		'queue.c',
 		'build.c',
+		'htab.c',
 	],
 
 	include_directories: evanix_inc,
diff --git a/src/queue.c b/src/queue.c
index 1fb5ae7..b02474e 100644
--- a/src/queue.c
+++ b/src/queue.c
@@ -11,8 +11,45 @@
 #define MAX_NIX_PKG_COUNT 200000
 
 static int queue_push(struct queue *queue, struct job *job);
-static int queue_htab_job_merge(struct job **job, struct hsearch_data *htab);
-static int queue_htab_parent_merge(struct job *to, struct job *from);
+static int queue_htab_job_merge(struct job **job, struct htab *htab);
+static int queue_dag_isolate(struct job *job, struct job *keep_parent,
+			     struct job_clist *jobs, struct htab *htab);
+
+static int queue_dag_isolate(struct job *job, struct job *keep_parent,
+			     struct job_clist *jobs, struct htab *htab)
+{
+	int ret;
+
+	for (size_t i = 0; i < job->deps_filled; i++) {
+		ret = queue_dag_isolate(job->deps[i], job, jobs, htab);
+		if (ret < 0)
+			return ret;
+	}
+
+	for (size_t i = 0; i < job->parents_filled; i++) {
+		if (job->parents[i] == keep_parent)
+			continue;
+
+		job_deps_list_rm(job->parents[i], job);
+	}
+
+	if (keep_parent != NULL) {
+		job->parents[0] = keep_parent;
+		job->parents_filled = 1;
+	} else {
+		/* it must be tha parent */
+		job->parents_filled = 0;
+	}
+
+	if (!job->transitive)
+		CIRCLEQ_REMOVE(jobs, job, clist);
+
+	ret = htab_delete(htab, job->drv_path);
+	if (ret < 0)
+		return ret;
+
+	return 0;
+}
 
 void *queue_thread_entry(void *queue_thread)
 {
@@ -41,9 +78,8 @@ void *queue_thread_entry(void *queue_thread)
 	pthread_exit(NULL);
 }
 
-int queue_pop(struct queue *queue, struct job **job, struct hsearch_data *htab)
+int queue_pop(struct queue *queue, struct job **job, struct htab *htab)
 {
-	ENTRY e, *ep;
 	int ret;
 
 	struct job *j = CIRCLEQ_FIRST(&queue->jobs);
@@ -54,50 +90,12 @@ int queue_pop(struct queue *queue, struct job **job, struct hsearch_data *htab)
 	}
 
 	pthread_mutex_lock(&queue->mutex);
-
-	CIRCLEQ_REMOVE(&queue->jobs, j, clist);
-	if (j->parents_filled <= 0) {
-		e.key = j->drv_path;
-		ret = hsearch_r(e, FIND, &ep, htab);
-		if (ret == 0) {
-			print_err("%s", strerror(errno));
-		}
-		else
-			ep->data = NULL;
-	}
-
-	pthread_mutex_unlock(&queue->mutex);
-
-	*job = j;
-	return 0;
-}
-
-static int queue_htab_parent_merge(struct job *to, struct job *from)
-{
-	int ret;
-
-	/* the output from nix-eval-jobs("from") can only have maximum one
-	 * parent */
-	for (size_t i = 0; i < to->parents_filled; i++) {
-		if (strcmp(to->parents[i]->drv_path,
-			   from->parents[0]->drv_path))
-			continue;
-
-		/* steal name from "from" */
-		if (to->parents[i]->name == NULL) {
-			to->parents[i]->name =
-				from->parents[0]->name;
-			from->parents[0]->name = NULL;
-		}
-
-		return 0;
-	}
-
-	ret = job_parents_list_insert(to, from->parents[0]);
+	ret = queue_dag_isolate(j, NULL, &queue->jobs, htab);
 	if (ret < 0)
 		return ret;
-	from->parents_filled = 0;
+	pthread_mutex_unlock(&queue->mutex);
 
+	*job = j;
 	return 0;
 }
 
@@ -107,26 +105,21 @@ static int queue_htab_parent_merge(struct job *to, struct job *from)
  * - only childrens or dependencies have parent node
  * - only root node have dependencies
  */
-static int queue_htab_job_merge(struct job **job, struct hsearch_data *htab)
+static int queue_htab_job_merge(struct job **job, struct htab *htab)
 {
 	struct job *jtab;
-	ENTRY e, *ep;
+	ENTRY *ep;
 	int ret;
 
-	e.key = (*job)->drv_path;
-	ret = hsearch_r(e, FIND, &ep, htab);
-	if (ret == 0) {
-		if (errno != ESRCH) {
-			print_err("%s", strerror(errno));
-			return -errno;
-		}
-
-		e.data = *job;
-		ret = hsearch_r(e, ENTER, &ep, htab);
-		if (ret == 0) {
-			print_err("%s", strerror(errno));
-			return -errno;
-		}
+	// e.key = (*job)->drv_path;
+	// ret = hsearch_r(e, FIND, &ep, htab);
+	ret = htab_search(htab, (*job)->drv_path, &ep);
+	if (ret < 0) {
+		return ret;
+	} else if (ret == ESRCH) {
+		ret = htab_enter(htab, (*job)->drv_path, *job);
+		if (ret < 0)
+			return ret;
 
 		for (size_t i = 0; i < (*job)->deps_filled; i++) {
 			ret = queue_htab_job_merge(&(*job)->deps[i], htab);
@@ -148,12 +141,15 @@ static int queue_htab_job_merge(struct job **job, struct hsearch_data *htab)
 
 	/* only recursive calls with childrens or dependencies can enter this
 	 * for a recursive call to happen the parent was just entered into htab
-	 * so, update the parent's deps reference to point to the node in htab
+	 * so,
+	 * - update parent's reference to point to jtab (done by *job = jtab)
+	 * - insert the parent to jtab
 	 */
 	if ((*job)->parents_filled > 0) {
-		ret = queue_htab_parent_merge(jtab, *job);
+		ret = job_parents_list_insert(jtab, (*job)->parents[0]);
 		if (ret < 0)
 			return ret;
+		(*job)->parents_filled = 0;
 	}
 
 	job_free(*job);
@@ -194,8 +190,7 @@ void queue_thread_free(struct queue_thread *queue_thread)
 	CIRCLEQ_FOREACH_FREE(cur, next, &queue_thread->queue->jobs, clist,
 			     job_free);
 
-	hdestroy_r(queue_thread->queue->htab);
-	free(queue_thread->queue->htab);
+	htab_free(queue_thread->queue->htab);
 	ret = sem_destroy(&queue_thread->queue->sem);
 	if (ret < 0)
 		print_err("%s", strerror(errno));
@@ -234,25 +229,13 @@ int queue_thread_new(struct queue_thread **queue_thread, FILE *stream)
 		goto out_free_queue;
 	}
 
-	qt->queue->htab = malloc(sizeof(*qt->queue->htab));
-	if (qt->queue->htab == NULL) {
-		print_err("%s", strerror(errno));
-		ret = -errno;
+	ret = htab_init(&qt->queue->htab);
+	if (ret < 0)
 		goto out_free_sem;
-	}
-	ret = hcreate_r(MAX_NIX_PKG_COUNT, qt->queue->htab);
-	if (ret == 0) {
-		print_err("%s", strerror(errno));
-		ret = -errno;
-		goto out_free_htab;
-	}
 
 	CIRCLEQ_INIT(&qt->queue->jobs);
 	pthread_mutex_init(&qt->queue->mutex, NULL);
 
-out_free_htab:
-	if (ret < 0)
-		free(qt->queue->htab);
 out_free_sem:
 	if (ret < 0)
 		sem_destroy(&qt->queue->sem);