Basic schedule initialization

9 files changed, 113 insertions, 34 deletions

diff --git a/inc/lib/pqueue.h b/inc/lib/pqueue.h
index 860a366..c576ee3 100644
--- a/inc/lib/pqueue.h
+++ b/inc/lib/pqueue.h
@@ -75,7 +75,7 @@ struct pqueue {
  * @return the handle or NULL for insufficent memory
  */
 struct pqueue *pqueue_init(size_t n, pqueue_cmp_pri_f cmppri,
-			   pqueue_get_pri_f getpri, pqueue_set_pos_f set_pos);
+			   pqueue_get_pri_f getpri, pqueue_set_pos_f setpos);
 
 /**
  * free all memory used by the queue
diff --git a/inc/map.h b/inc/map.h
index 427cee5..790d42f 100644
--- a/inc/map.h
+++ b/inc/map.h
@@ -5,10 +5,13 @@
 #define CALM_MAP_H
 
 #include <lib/hash.h>
+#include <lib/pqueue.h>
 
 struct term *map_get(hash_t hash);
 void map_set(struct term *term, hash_t hash);
 void map_initialize(void);
 void map_destroy(void);
+struct pqueue *map_to_pqueue(pqueue_cmp_pri_f cmppri, pqueue_get_pri_f getpri,
+			     pqueue_set_pos_f set_pos);
 
 #endif
diff --git a/inc/parse.h b/inc/parse.h
index c1e21b2..e79fb26 100644
--- a/inc/parse.h
+++ b/inc/parse.h
@@ -15,11 +15,11 @@ struct term {
 	size_t depth;
 	union {
 		struct {
-			hash_t term;
+			struct term *term;
 		} abs;
 		struct {
-			hash_t lhs;
-			hash_t rhs;
+			struct term *lhs;
+			struct term *rhs;
 		} app;
 		struct {
 			int index;
@@ -27,7 +27,12 @@ struct term {
 	} u;
 };
 
-hash_t parse_blc(char **term, int depth);
+struct term_handle {
+	struct term *term;
+	hash_t hash;
+};
+
+struct term_handle parse_blc(char **term, size_t depth);
 int parse_get_max_depth(void);
 
 #endif
diff --git a/inc/schedule.h b/inc/schedule.h
new file mode 100644
index 0000000..ad0e054
--- /dev/null
+++ b/inc/schedule.h
@@ -0,0 +1,10 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#ifndef CALM_SCHEDULE_H
+#define CALM_SCHEDULE_H
+
+void schedule_init(void);
+void schedule_destroy(void);
+
+#endif
diff --git a/makefile b/makefile
index c2acce0..7391b3e 100644
--- a/makefile
+++ b/makefile
@@ -11,7 +11,7 @@ SRCS = $(wildcard $(SRC)/*.c) $(wildcard $(SRC)/*/*.c)
 OBJS = $(patsubst $(SRC)/%.c, $(BUILD)/%.o, $(SRCS))
 
 CFLAGS_DEBUG = -Wno-error -g -O0 -Wno-unused -fsanitize=address,undefined,leak
-CFLAGS_WARNINGS = -Wall -Wextra -Wshadow -Wpointer-arith -Wwrite-strings -Wredundant-decls -Wnested-externs -Wmissing-declarations -Wstrict-prototypes -Wmissing-prototypes -Wcast-qual -Wswitch-default -Wswitch-enum -Wunreachable-code -Wundef -Wold-style-definition -pedantic -Wno-switch-enum
+CFLAGS_WARNINGS = -Wall -Wextra -Wshadow -Wpointer-arith -Wwrite-strings -Wredundant-decls -Wnested-externs -Wmissing-declarations -Wstrict-prototypes -Wmissing-prototypes -Wcast-qual -Wswitch-default -Wswitch-enum -Wunreachable-code -Wundef -Wold-style-definition -pedantic -Wno-switch-enum -Wframe-larger-than=512 -Wstack-usage=1024
 CFLAGS = $(CFLAGS_WARNINGS) -std=c99 -Ofast -I$(INC)
 
 ifdef DEBUG # TODO: Somehow clean automagically
diff --git a/src/main.c b/src/main.c
index 94ca4e4..922a963 100644
--- a/src/main.c
+++ b/src/main.c
@@ -7,6 +7,7 @@
 #include <string.h>
 
 #include <map.h>
+#include <schedule.h>
 #include <parse.h>
 #include <log.h>
 #include <lib/hash.h>
@@ -54,8 +55,11 @@ int main(int argc, char *argv[])
 
 	char *orig_term = term;
 	parse_blc(&term, 1);
-
 	free(orig_term);
+
+	schedule_init();
+
+	schedule_destroy();
 	map_destroy();
 	return 0;
 }
diff --git a/src/map.c b/src/map.c
index 411ba4e..d0793a2 100644
--- a/src/map.c
+++ b/src/map.c
@@ -12,10 +12,10 @@ static struct hashmap *all_terms;
 static void deref_term(struct term *term)
 {
 	if (term->type == ABS) {
-		deref_term(hashmap_get(all_terms, term->u.abs.term));
+		deref_term(term->u.abs.term);
 	} else if (term->type == APP) {
-		deref_term(hashmap_get(all_terms, term->u.app.lhs));
-		deref_term(hashmap_get(all_terms, term->u.app.rhs));
+		deref_term(term->u.app.lhs);
+		deref_term(term->u.app.rhs);
 	}
 
 	// TODO: remove from hashmap?
@@ -51,3 +51,19 @@ void map_destroy(void)
 {
 	hashmap_free(all_terms);
 }
+
+struct pqueue *map_to_pqueue(pqueue_cmp_pri_f cmppri, pqueue_get_pri_f getpri,
+			     pqueue_set_pos_f setpos)
+{
+	size_t size = hashmap_count(all_terms) + 42;
+	struct pqueue *queue = pqueue_init(size, cmppri, getpri, setpos);
+
+	size_t iter = 0;
+	void *iter_val;
+	while (hashmap_iter(all_terms, &iter, &iter_val)) {
+		struct term *term = *(struct term **)iter_val;
+		pqueue_insert(queue, term);
+	}
+
+	return queue;
+}
diff --git a/src/parse.c b/src/parse.c
index 24d2339..5445aea 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -8,9 +8,9 @@
 #include <map.h>
 #include <log.h>
 
-static int max_depth = 0;
+static size_t max_depth = 0;
 
-static struct term *new_term(term_type_t type, hash_t hash, int depth)
+static struct term *new_term(term_type_t type, hash_t hash, size_t depth)
 {
 	struct term *term = malloc(sizeof(*term));
 	if (!term)
@@ -22,63 +22,68 @@ static struct term *new_term(term_type_t type, hash_t hash, int depth)
 	return term;
 }
 
-static hash_t abs_blc(char **term, int depth)
+static void update_term(struct term *term, size_t depth)
+{
+	term->refs++;
+	if (depth < term->depth) // lower depths are more important
+		term->depth = depth;
+}
+
+static struct term_handle abs_blc(char **term, size_t depth)
 {
 	term_type_t res_type = ABS;
-	hash_t inner_hash = parse_blc(term, depth + 1);
-	hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), inner_hash);
+	struct term_handle inner = parse_blc(term, depth + 1);
+	hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), inner.hash);
 
 	struct term *res_term;
 	if ((res_term = map_get(res))) {
-		res_term->refs++;
-		res_term->depth = (res_term->depth + depth) / 2;
+		update_term(res_term, depth);
 	} else {
 		res_term = new_term(res_type, res, depth);
-		res_term->u.abs.term = inner_hash;
+		res_term->u.abs.term = inner.term;
 		map_set(res_term, res);
 	}
 
-	return res;
+	return (struct term_handle){ .term = res_term, .hash = res };
 }
 
-static hash_t app_blc(char **term, int depth)
+static struct term_handle app_blc(char **term, size_t depth)
 {
 	term_type_t res_type = APP;
-	hash_t lhs_hash = parse_blc(term, depth + 1);
-	hash_t rhs_hash = parse_blc(term, depth + 1);
+	struct term_handle lhs = parse_blc(term, depth + 1);
+	struct term_handle rhs = parse_blc(term, depth + 1);
 
-	hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), lhs_hash);
-	res = hash((uint8_t *)&res, sizeof(res), rhs_hash);
+	hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), lhs.hash);
+	res = hash((uint8_t *)&res, sizeof(res), rhs.hash);
 
 	struct term *res_term;
 	if ((res_term = map_get(res))) {
-		res_term->refs++;
-		res_term->depth = (res_term->depth + depth) / 2;
+		update_term(res_term, depth);
 	} else {
 		res_term = new_term(res_type, res, depth);
-		res_term->u.app.lhs = lhs_hash;
-		res_term->u.app.rhs = rhs_hash;
+		res_term->u.app.lhs = lhs.term;
+		res_term->u.app.rhs = rhs.term;
 		map_set(res_term, res);
 	}
 
-	return res;
+	return (struct term_handle){ .term = res_term, .hash = res };
 }
 
-static hash_t var_blc(int index, int depth)
+static struct term_handle var_blc(int index, size_t depth)
 {
 	term_type_t res_type = VAR;
 	hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), index);
 
 	struct term *res_term;
 	if ((res_term = map_get(res))) {
-		res_term->refs++;
-		res_term->depth = (res_term->depth + depth) / 2;
+		update_term(res_term, depth);
 	} else {
 		res_term = new_term(res_type, res, depth);
 		res_term->u.var.index = index;
 		map_set(res_term, res);
 	}
-	return res;
+
+	return (struct term_handle){ .term = res_term, .hash = res };
 }
 
 int parse_get_max_depth(void)
@@ -88,7 +93,7 @@ int parse_get_max_depth(void)
 
 // TODO: bit parse_bblc
 // TODO: BLoC support (needs entry reference index sth two passes)
-hash_t parse_blc(char **term, int depth)
+struct term_handle parse_blc(char **term, size_t depth)
 {
 	if (depth > max_depth)
 		max_depth = depth;
diff --git a/src/schedule.c b/src/schedule.c
index e69de29..e746a7f 100644
--- a/src/schedule.c
+++ b/src/schedule.c
@@ -0,0 +1,36 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#include <schedule.h>
+#include <lib/pqueue.h>
+#include <parse.h>
+#include <map.h>
+
+static struct pqueue *queue;
+
+static pqueue_pri_t get_pri(void *a)
+{
+	struct term *term = a;
+	return (parse_get_max_depth() - term->depth + 1) * term->refs;
+}
+
+static int cmp_pri(pqueue_pri_t next, pqueue_pri_t curr)
+{
+	return next < curr;
+}
+
+static void set_pos(void *a, size_t position)
+{
+	(void)a;
+	(void)position;
+}
+
+void schedule_init(void)
+{
+	queue = map_to_pqueue(cmp_pri, get_pri, set_pos);
+}
+
+void schedule_destroy(void)
+{
+	pqueue_free(queue);
+}