More scheduling and probabilisticity

6 files changed, 51 insertions, 1 deletions

diff --git a/inc/lib/pqueue.h b/inc/lib/pqueue.h
index c576ee3..86c4080 100644
--- a/inc/lib/pqueue.h
+++ b/inc/lib/pqueue.h
@@ -104,4 +104,12 @@ int pqueue_insert(struct pqueue *q, void *d);
  */
 void *pqueue_pop(struct pqueue *q);
 
+/**
+ * pop an item from the queue at a position
+ * @param q the queue
+ * @param p the position
+ * @return NULL on error, otherwise the entry
+ */
+void *pqueue_pop_at(struct pqueue *q, size_t p);
+
 #endif
diff --git a/inc/schedule.h b/inc/schedule.h
index ad0e054..7c76a66 100644
--- a/inc/schedule.h
+++ b/inc/schedule.h
@@ -5,6 +5,7 @@
 #define CALM_SCHEDULE_H
 
 void schedule_init(void);
+void schedule(void);
 void schedule_destroy(void);
 
 #endif
diff --git a/src/lib/pqueue.c b/src/lib/pqueue.c
index 6f21e5f..c080bb2 100644
--- a/src/lib/pqueue.c
+++ b/src/lib/pqueue.c
@@ -157,3 +157,19 @@ void *pqueue_pop(struct pqueue *q)
 
 	return head;
 }
+
+void *pqueue_pop_at(struct pqueue *q, size_t p)
+{
+	void *head;
+	if (!q || q->size == 1 || p >= q->size)
+		return NULL;
+
+	head = q->d[p];
+	q->d[p] = q->d[--q->size];
+	if (q->cmppri(q->getpri(head), q->getpri(q->d[p])))
+		bubble_up(q, p);
+	else
+		percolate_down(q, p);
+
+	return head;
+}
diff --git a/src/main.c b/src/main.c
index 922a963..9aaed3c 100644
--- a/src/main.c
+++ b/src/main.c
@@ -58,6 +58,7 @@ int main(int argc, char *argv[])
 	free(orig_term);
 
 	schedule_init();
+	schedule();
 
 	schedule_destroy();
 	map_destroy();
diff --git a/src/map.c b/src/map.c
index d0793a2..1862c9c 100644
--- a/src/map.c
+++ b/src/map.c
@@ -62,7 +62,9 @@ struct pqueue *map_to_pqueue(pqueue_cmp_pri_f cmppri, pqueue_get_pri_f getpri,
 	void *iter_val;
 	while (hashmap_iter(all_terms, &iter, &iter_val)) {
 		struct term *term = *(struct term **)iter_val;
-		pqueue_insert(queue, term);
+		if (term->type == APP) {
+			pqueue_insert(queue, term);
+		}
 	}
 
 	return queue;
diff --git a/src/schedule.c b/src/schedule.c
index e746a7f..dda08f3 100644
--- a/src/schedule.c
+++ b/src/schedule.c
@@ -1,6 +1,10 @@
 // Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
 // SPDX-License-Identifier: MIT
 
+#include <math.h>
+#include <time.h>
+#include <stdlib.h>
+
 #include <schedule.h>
 #include <lib/pqueue.h>
 #include <parse.h>
@@ -25,8 +29,26 @@ static void set_pos(void *a, size_t position)
 	(void)position;
 }
 
+// skewed random number generator
+// prefers smaller numbers
+static size_t choose_position(void)
+{
+	size_t size = pqueue_size(queue);
+	return size - (size_t)sqrt(((size_t)rand() % (size_t)pow(size, 2)));
+}
+
+void schedule(void)
+{
+	while (pqueue_size(queue) > 0) {
+		size_t position = choose_position();
+		struct term *term = pqueue_pop_at(queue, position);
+		// TODO: reduce term
+	}
+}
+
 void schedule_init(void)
 {
+	srand(time(0));
 	queue = map_to_pqueue(cmp_pri, get_pri, set_pos);
 }