From f881fe7d158287b25381a90760fd441e7dff7a65 Mon Sep 17 00:00:00 2001 From: sinanmohd Date: Thu, 18 Jul 2024 09:43:42 +0530 Subject: queue: switch to uthash --- flake.nix | 2 + include/htab.h | 18 ------- include/jobs.h | 2 + include/queue.h | 5 +- python-package.nix | 2 + src/build.c | 2 +- src/htab.c | 149 ---------------------------------------------------- src/meson.build | 1 - src/queue.c | 44 ++++++---------- src/solver_greedy.c | 4 +- 10 files changed, 26 insertions(+), 203 deletions(-) delete mode 100644 include/htab.h delete mode 100644 src/htab.c 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 - -#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 #include #include +#include #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 #include -#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 -#include -#include - -#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) -- cgit v1.2.3