More scheduling

10 files changed, 99 insertions, 47 deletions

diff --git a/inc/lib/pqueue.h b/inc/lib/pqueue.h
index 86c4080..732002e 100644
--- a/inc/lib/pqueue.h
+++ b/inc/lib/pqueue.h
@@ -42,6 +42,7 @@ typedef unsigned long long pqueue_pri_t;
 
 /** callback functions to get/set/compare the priority of an element */
 typedef pqueue_pri_t (*pqueue_get_pri_f)(void *a);
+typedef void (*pqueue_set_pri_f)(void *a, pqueue_pri_t pri);
 typedef int (*pqueue_cmp_pri_f)(pqueue_pri_t next, pqueue_pri_t curr);
 
 /** callback functions to get/set the position of an element */
@@ -58,6 +59,8 @@ struct pqueue {
 	size_t step; /**< growth stepping setting */
 	pqueue_cmp_pri_f cmppri; /**< callback to compare nodes */
 	pqueue_get_pri_f getpri; /**< callback to get priority of a node */
+	pqueue_set_pri_f setpri; /**< callback to set priority of a node */
+	pqueue_get_pos_f getpos; /**< callback to get position of a node */
 	pqueue_set_pos_f setpos; /**< callback to set position of a node */
 	void **d; /**< The actualy queue in binary heap form */
 };
@@ -70,12 +73,16 @@ struct pqueue {
  * @param cmppri The callback function to run to compare two elements
  *     This callback should return 0 for 'lower' and non-zero
  *     for 'higher', or vice versa if reverse priority is desired
+ * @param setpri the callback function to run to assign a score to an element
  * @param getpri the callback function to run to set a score to an element
+ * @param getpos the callback function to get the current element's position
+ * @param setpos the callback function to set the current element's position
  *
  * @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 setpos);
+			   pqueue_get_pri_f getpri, pqueue_set_pri_f setpri,
+			   pqueue_get_pos_f getpos, pqueue_set_pos_f setpos);
 
 /**
  * free all memory used by the queue
@@ -98,6 +105,14 @@ size_t pqueue_size(struct pqueue *q);
 int pqueue_insert(struct pqueue *q, void *d);
 
 /**
+ * move an existing entry to a different priority
+ * @param q the queue
+ * @param new_pri the new priority
+ * @param d the entry
+ */
+void pqueue_change_priority(struct pqueue *q, pqueue_pri_t new_pri, void *d);
+
+/**
  * pop the highest-ranking item from the queue.
  * @param q the queue
  * @return NULL on error, otherwise the entry
diff --git a/inc/map.h b/inc/map.h
index c66f850..3759a27 100644
--- a/inc/map.h
+++ b/inc/map.h
@@ -15,7 +15,5 @@ void map_delete(struct hashmap *map, struct term *term);
 void map_initialize(void);
 void map_destroy(struct hashmap *map);
 void map_dump(struct hashmap *map); // TODO: remove
-struct pqueue *map_to_pqueue(struct hashmap *map, pqueue_cmp_pri_f cmppri,
-			     pqueue_get_pri_f getpri, pqueue_set_pos_f set_pos);
 
 #endif
diff --git a/inc/schedule.h b/inc/schedule.h
index 7c76a66..eaf1e0c 100644
--- a/inc/schedule.h
+++ b/inc/schedule.h
@@ -4,7 +4,11 @@
 #ifndef CALM_SCHEDULE_H
 #define CALM_SCHEDULE_H
 
-void schedule_init(void);
+#include <term.h>
+
+void schedule_initialize(void);
+void schedule_sync_priorities(void);
+void schedule_add(struct term *term);
 void schedule(void);
 void schedule_destroy(void);
 
diff --git a/inc/term.h b/inc/term.h
index 019fa82..62b93dd 100644
--- a/inc/term.h
+++ b/inc/term.h
@@ -4,6 +4,7 @@
 #ifndef CALM_TERM_H
 #define CALM_TERM_H
 
+#include <lib/pqueue.h>
 #include <lib/hash.h>
 #include <lib/hashmap.h>
 
@@ -15,6 +16,10 @@ struct term {
 	struct hashmap *parents;
 	size_t refs;
 	size_t depth;
+
+	pqueue_pri_t priority;
+	size_t position;
+
 	union {
 		struct {
 			struct term *term;
diff --git a/src/lib/pqueue.c b/src/lib/pqueue.c
index c080bb2..cf0611f 100644
--- a/src/lib/pqueue.c
+++ b/src/lib/pqueue.c
@@ -35,7 +35,8 @@
 #define parent(i) ((i) >> 1)
 
 struct pqueue *pqueue_init(size_t n, pqueue_cmp_pri_f cmppri,
-			   pqueue_get_pri_f getpri, pqueue_set_pos_f setpos)
+			   pqueue_get_pri_f getpri, pqueue_set_pri_f setpri,
+			   pqueue_get_pos_f getpos, pqueue_set_pos_f setpos)
 {
 	struct pqueue *q;
 
@@ -51,7 +52,9 @@ struct pqueue *pqueue_init(size_t n, pqueue_cmp_pri_f cmppri,
 	q->size = 1;
 	q->avail = q->step = (n + 1); /* see comment above about n+1 */
 	q->cmppri = cmppri;
+	q->setpri = setpri;
 	q->getpri = getpri;
+	q->getpos = getpos;
 	q->setpos = setpos;
 
 	return q;
@@ -144,6 +147,19 @@ int pqueue_insert(struct pqueue *q, void *d)
 	return 0;
 }
 
+void pqueue_change_priority(struct pqueue *q, pqueue_pri_t new_pri, void *d)
+{
+	size_t posn;
+	pqueue_pri_t old_pri = q->getpri(d);
+
+	q->setpri(d, new_pri);
+	posn = q->getpos(d);
+	if (q->cmppri(old_pri, new_pri))
+		bubble_up(q, posn);
+	else
+		percolate_down(q, posn);
+}
+
 void *pqueue_pop(struct pqueue *q)
 {
 	void *head;
diff --git a/src/main.c b/src/main.c
index a2a5105..6a12afb 100644
--- a/src/main.c
+++ b/src/main.c
@@ -53,24 +53,21 @@ int main(int argc, char *argv[])
 
 	char *term = read_path(argv[1]);
 	map_initialize();
+	schedule_initialize();
 
 	char *orig_term = term;
-	struct term_handle handle = parse_blc(&term, 1);
+	parse_blc(&term, 1);
 	free(orig_term);
 
-	term_print(handle.term);
-	fprintf(stderr, "\n");
-	struct term *reduced = reduce(handle.term->u.abs.term);
-	fprintf(stderr, "after\n");
-	term_print(reduced);
-	fprintf(stderr, "\n");
+	schedule_sync_priorities();
 
-	map_dump(map_all_terms());
+	/* map_dump(map_all_terms()); */
+	debug("reducing...\n");
 
-	/* schedule_init(); */
-	/* schedule(); */
-	/* schedule_destroy(); */
+	schedule();
 
+	map_dump(map_all_terms());
 	map_destroy(map_all_terms());
+	schedule_destroy();
 	return 0;
 }
diff --git a/src/map.c b/src/map.c
index 16518e2..9f6a050 100644
--- a/src/map.c
+++ b/src/map.c
@@ -6,6 +6,7 @@
 #include <lib/hashmap.h>
 #include <map.h>
 #include <parse.h>
+#include <schedule.h>
 
 static struct hashmap *all_terms;
 
@@ -30,6 +31,8 @@ struct term *map_get(struct hashmap *map, hash_t hash)
 
 void map_set(struct hashmap *map, struct term *term)
 {
+	if (!hashmap_get(map, term->hash))
+		schedule_add(term); // also add to schedule
 	hashmap_set(map, &term, term->hash);
 }
 
@@ -70,21 +73,3 @@ void map_dump(struct hashmap *map)
 	}
 	fprintf(stderr, "---\n\n");
 }
-
-struct pqueue *map_to_pqueue(struct hashmap *map, pqueue_cmp_pri_f cmppri,
-			     pqueue_get_pri_f getpri, pqueue_set_pos_f setpos)
-{
-	size_t size = hashmap_count(map) + 42;
-	struct pqueue *queue = pqueue_init(size, cmppri, getpri, setpos);
-
-	size_t iter = 0;
-	void *iter_val;
-	while (hashmap_iter(map, &iter, &iter_val)) {
-		struct term *term = *(struct term **)iter_val;
-		if (term->type == APP && term->u.app.lhs->type == ABS) {
-			pqueue_insert(queue, term);
-		}
-	}
-
-	return queue;
-}
diff --git a/src/reduce.c b/src/reduce.c
index aa17655..9e7520d 100644
--- a/src/reduce.c
+++ b/src/reduce.c
@@ -11,12 +11,6 @@
 static struct term *substitute(struct term *term, struct term *substitution,
 			       size_t level)
 {
-	/* fprintf(stderr, "substitute: "); */
-	/* term_print(term); */
-	/* fprintf(stderr, " with "); */
-	/* term_print(substitution); */
-	/* fprintf(stderr, " at level %ld\n", level); */
-
 	if (term->type == VAR) {
 		if (term->u.var.index == level) {
 			// TODO: deref index
diff --git a/src/schedule.c b/src/schedule.c
index 3465752..93cd700 100644
--- a/src/schedule.c
+++ b/src/schedule.c
@@ -18,7 +18,13 @@ 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;
+	return term->priority;
+}
+
+static void set_pri(void *a, pqueue_pri_t pri)
+{
+	struct term *term = a;
+	term->priority = pri;
 }
 
 static int cmp_pri(pqueue_pri_t next, pqueue_pri_t curr)
@@ -26,10 +32,16 @@ static int cmp_pri(pqueue_pri_t next, pqueue_pri_t curr)
 	return next < curr;
 }
 
+static size_t get_pos(void *a)
+{
+	struct term *term = a;
+	return term->position;
+}
+
 static void set_pos(void *a, size_t position)
 {
-	(void)a;
-	(void)position;
+	struct term *term = a;
+	term->position = position;
 }
 
 // skewed random number generator
@@ -40,6 +52,20 @@ static size_t choose_position(void)
 	return size - (size_t)sqrt(((size_t)rand() % (size_t)pow(size, 2)));
 }
 
+static pqueue_pri_t calculate_priority(struct term *term)
+{
+	return (parse_get_max_depth() - term->depth + 1) * term->refs;
+}
+
+void schedule_add(struct term *term)
+{
+	if (!(term->type == APP && term->u.app.lhs->type == ABS))
+		return; // no beta redex
+
+	set_pri(term, calculate_priority(term));
+	pqueue_insert(queue, term);
+}
+
 void schedule(void)
 {
 	while (pqueue_size(queue) > 0) {
@@ -51,10 +77,24 @@ void schedule(void)
 	debug("no more redexes!\n");
 }
 
-void schedule_init(void)
+void schedule_sync_priorities(void)
+{
+	size_t iter = 0;
+	void *iter_val;
+	while (hashmap_iter(map_all_terms(), &iter, &iter_val)) {
+		struct term *term = *(struct term **)iter_val;
+		if (term->type == APP && term->u.app.lhs->type == ABS) {
+			pqueue_change_priority(queue, calculate_priority(term),
+					       term);
+		}
+	}
+}
+
+void schedule_initialize(void)
 {
 	srand(time(0));
-	queue = map_to_pqueue(map_all_terms(), cmp_pri, get_pri, set_pos);
+	size_t size = hashmap_count(map_all_terms()) + 42;
+	queue = pqueue_init(size, cmp_pri, get_pri, set_pri, get_pos, set_pos);
 }
 
 void schedule_destroy(void)
diff --git a/src/term.c b/src/term.c
index 0982f5c..a2f361b 100644
--- a/src/term.c
+++ b/src/term.c
@@ -143,10 +143,8 @@ void term_rehash_parents(struct term *term)
 		parents = new;
 	}
 
-	fprintf(stderr, "NEW\n");
 	struct parent_list *iterator = parents;
 	while (iterator && iterator->term) {
-		fprintf(stderr, "rehashing parent\n");
 		struct term *parent = iterator->term;
 		hash_t previous = parent->hash;
 		struct term *new = term_rehash(parent);