queue: switch to uthash

10 files changed, 26 insertions, 203 deletions

diff --git a/flake.nix b/flake.nix
index 496151f..3505d12 100644
--- a/flake.nix
+++ b/flake.nix
@@ -29,6 +29,7 @@
               jq
               highs
               cjson
+              uthash
               nix-eval-jobs
 
               pkg-config
@@ -59,6 +60,7 @@
 
             src = ./.;
             nativeBuildInputs = with pkgs; [
+              uthash
               meson
               ninja
               pkg-config
diff --git a/include/htab.h b/include/htab.h
deleted file mode 100644
index 7ea1730..0000000
--- a/include/htab.h
+++ /dev/null
@@ -1,18 +0,0 @@
-#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(size_t nel, 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 ecf9d96..cbcce74 100644
--- a/include/jobs.h
+++ b/include/jobs.h
@@ -2,6 +2,7 @@
 #include <stdint.h>
 #include <stdio.h>
 #include <sys/queue.h>
+#include <uthash.h>
 
 #ifndef JOBS_H
 
@@ -21,6 +22,7 @@ struct job {
 	struct job **deps;
 	size_t parents_size, parents_filled;
 	struct job **parents;
+	UT_hash_handle hh;
 
 	/* queue */
 	CIRCLEQ_ENTRY(job) clist;
diff --git a/include/queue.h b/include/queue.h
index cfc67ef..ca318cf 100644
--- a/include/queue.h
+++ b/include/queue.h
@@ -4,7 +4,6 @@
 #include <stdint.h>
 #include <sys/queue.h>
 
-#include "htab.h"
 #include "jobs.h"
 #include "solver_util.h"
 
@@ -20,7 +19,7 @@ struct queue {
 	sem_t sem;
 	queue_state_t state;
 	pthread_mutex_t mutex;
-	struct htab *htab;
+	struct job *htab;
 
 	/* solver */
 	struct jobid *jobid;
@@ -36,7 +35,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 htab *htab);
+int queue_pop(struct queue *queue, struct job **job);
 int queue_isempty(struct job_clist *jobs);
 
 #define QUEUE_H
diff --git a/python-package.nix b/python-package.nix
index 648899e..faedbb9 100644
--- a/python-package.nix
+++ b/python-package.nix
@@ -7,6 +7,7 @@
   makeWrapper,
   cjson,
   highs,
+  uthash,
 }:
 
 buildPythonPackage {
@@ -38,5 +39,6 @@ buildPythonPackage {
   buildInputs = [
     cjson
     highs
+    uthash
   ];
 }
diff --git a/src/build.c b/src/build.c
index bca1550..405f9d1 100644
--- a/src/build.c
+++ b/src/build.c
@@ -50,7 +50,7 @@ static int build(struct queue *queue)
 
 	char out_link[NAME_MAX] = "result";
 
-	ret = queue_pop(queue, &job, queue->htab);
+	ret = queue_pop(queue, &job);
 	if (ret == -ESRCH)
 		return EAGAIN;
 	if (ret < 0)
diff --git a/src/htab.c b/src/htab.c
deleted file mode 100644
index 11d5a98..0000000
--- a/src/htab.c
+++ /dev/null
@@ -1,149 +0,0 @@
-/* since hsearch_r does not support deletions dirctly (gotta go fast), 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 an external library
- */
-
-#include <errno.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "htab.h"
-#include "util.h"
-
-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;
-	}
-
-	ret = hsearch_r(e, ENTER, &ep, htab->table);
-	if (ret == 0) {
-		print_err("%s", strerror(errno));
-		return -errno;
-	}
-	ep->data = data;
-
-	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(size_t nel, 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(nel, 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);
-
-	hdestroy_r(htab->table);
-	free(htab->table);
-
-	free(htab);
-}
diff --git a/src/meson.build b/src/meson.build
index 2578b51..b908721 100644
--- a/src/meson.build
+++ b/src/meson.build
@@ -7,7 +7,6 @@ e = executable(
 		'util.c',
 		'queue.c',
 		'build.c',
-		'htab.c',
 		'solver_util.c',
 		'solver_greedy.c',
 	],
diff --git a/src/queue.c b/src/queue.c
index af96630..1496242 100644
--- a/src/queue.c
+++ b/src/queue.c
@@ -13,12 +13,12 @@
 #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 htab *htab);
+static int queue_htab_job_merge(struct job **job, struct job **htab);
 static int queue_dag_isolate(struct job *job, struct job *keep_parent,
-			     struct job_clist *jobs, struct htab *htab);
+			     struct job_clist *jobs, struct job **htab);
 
 static int queue_dag_isolate(struct job *job, struct job *keep_parent,
-			     struct job_clist *jobs, struct htab *htab)
+			     struct job_clist *jobs, struct job **htab)
 {
 	int ret;
 
@@ -46,9 +46,7 @@ static int queue_dag_isolate(struct job *job, struct job *keep_parent,
 	if (job->scheduled)
 		CIRCLEQ_REMOVE(jobs, job, clist);
 
-	ret = htab_delete(htab, job->drv_path);
-	if (ret < 0)
-		return ret;
+	HASH_DEL(*htab, job);
 
 	return 0;
 }
@@ -94,7 +92,7 @@ void *queue_thread_entry(void *queue_thread)
 	pthread_exit(NULL);
 }
 
-int queue_pop(struct queue *queue, struct job **job, struct htab *htab)
+int queue_pop(struct queue *queue, struct job **job)
 {
 	int ret;
 	struct job *j;
@@ -112,7 +110,7 @@ int queue_pop(struct queue *queue, struct job **job, struct htab *htab)
 	} else {
 		j = CIRCLEQ_FIRST(&queue->jobs);
 	}
-	ret = queue_dag_isolate(j, NULL, &queue->jobs, htab);
+	ret = queue_dag_isolate(j, NULL, &queue->jobs, &queue->htab);
 	if (ret < 0)
 		goto out_mutex_unlock;
 
@@ -130,19 +128,15 @@ out_mutex_unlock:
  * - only childrens or dependencies have parent node
  * - only root node have dependencies
  */
-static int queue_htab_job_merge(struct job **job, struct htab *htab)
+static int queue_htab_job_merge(struct job **job, struct job **htab)
 {
-	struct job *jtab;
-	ENTRY *ep;
 	int ret;
+	struct job *jtab = NULL;
+	struct job *j = *job;
 
-	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;
+	HASH_FIND_STR(*htab, j->drv_path, jtab);
+	if (jtab == NULL) {
+		HASH_ADD_STR(*htab, drv_path, j);
 
 		for (size_t i = 0; i < (*job)->deps_filled; i++) {
 			ret = queue_htab_job_merge(&(*job)->deps[i], htab);
@@ -155,7 +149,6 @@ static int queue_htab_job_merge(struct job **job, struct htab *htab)
 
 	/* if it's already inside htab, it's deps should also be in htab, hence
 	 * not merging deps */
-	jtab = ep->data;
 	if (jtab->name == NULL) {
 		/* steal name from new job struct */
 		jtab->name = (*job)->name;
@@ -185,7 +178,7 @@ static int queue_push(struct queue *queue, struct job *job)
 	int ret;
 
 	pthread_mutex_lock(&queue->mutex);
-	ret = queue_htab_job_merge(&job, queue->htab);
+	ret = queue_htab_job_merge(&job, &queue->htab);
 	if (ret < 0) {
 		pthread_mutex_unlock(&queue->mutex);
 		return ret;
@@ -213,13 +206,12 @@ void queue_thread_free(struct queue_thread *queue_thread)
 	while (!CIRCLEQ_EMPTY(&queue_thread->queue->jobs)) {
 		j = CIRCLEQ_FIRST(&queue_thread->queue->jobs);
 		ret = queue_dag_isolate(j, NULL, &queue_thread->queue->jobs,
-					queue_thread->queue->htab);
+					&queue_thread->queue->htab);
 		if (ret < 0)
 			return;
 		job_free(j);
 	}
 
-	htab_free(queue_thread->queue->htab);
 	ret = sem_destroy(&queue_thread->queue->sem);
 	if (ret < 0)
 		print_err("%s", strerror(errno));
@@ -250,6 +242,7 @@ int queue_thread_new(struct queue_thread **queue_thread, FILE *stream)
 		ret = -errno;
 		goto out_free_qt;
 	}
+	qt->queue->htab = NULL;
 	qt->queue->resources = evanix_opts.max_build;
 	qt->queue->jobid = NULL;
 	qt->queue->state = Q_SEM_WAIT;
@@ -260,16 +253,9 @@ int queue_thread_new(struct queue_thread **queue_thread, FILE *stream)
 		goto out_free_queue;
 	}
 
-	ret = htab_init(MAX_NIX_PKG_COUNT, &qt->queue->htab);
-	if (ret < 0)
-		goto out_free_sem;
-
 	CIRCLEQ_INIT(&qt->queue->jobs);
 	pthread_mutex_init(&qt->queue->mutex, NULL);
 
-out_free_sem:
-	if (ret < 0)
-		sem_destroy(&qt->queue->sem);
 out_free_queue:
 	if (ret < 0)
 		free(qt->queue);
diff --git a/src/solver_greedy.c b/src/solver_greedy.c
index 7b7ccaa..9dd852e 100644
--- a/src/solver_greedy.c
+++ b/src/solver_greedy.c
@@ -83,8 +83,8 @@ int solver_greedy(struct job_clist *q, int32_t *max_build, struct job **job)
 
 		if (!evanix_opts.solver_report)
 			continue;
-		printf("ℹ️ cost: %2d, conformity: %.2f -> %s\n",
-		       job_cost(j), conformity_cur, j->drv_path);
+		printf("ℹ️ cost: %2d, conformity: %.2f -> %s\n", job_cost(j),
+		       conformity_cur, j->drv_path);
 	}
 
 	if (selected == NULL)