summaryrefslogtreecommitdiffstats
path: root/prio-queue.h
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-09 13:34:27 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-09 13:34:27 +0000
commit4dbdc42d9e7c3968ff7f690d00680419c9b8cb0f (patch)
tree47c1d492e9c956c1cd2b74dbd3b9d8b0db44dc4e /prio-queue.h
parentInitial commit. (diff)
downloadgit-4dbdc42d9e7c3968ff7f690d00680419c9b8cb0f.tar.xz
git-4dbdc42d9e7c3968ff7f690d00680419c9b8cb0f.zip
Adding upstream version 1:2.43.0.upstream/1%2.43.0
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'prio-queue.h')
-rw-r--r--prio-queue.h60
1 files changed, 60 insertions, 0 deletions
diff --git a/prio-queue.h b/prio-queue.h
new file mode 100644
index 0000000..4f9a37e
--- /dev/null
+++ b/prio-queue.h
@@ -0,0 +1,60 @@
+#ifndef PRIO_QUEUE_H
+#define PRIO_QUEUE_H
+
+/*
+ * A priority queue implementation, primarily for keeping track of
+ * commits in the 'date-order' so that we process them from new to old
+ * as they are discovered, but can be used to hold any pointer to
+ * struct. The caller is responsible for supplying a function to
+ * compare two "things".
+ *
+ * Alternatively, this data structure can also be used as a LIFO stack
+ * by specifying NULL as the comparison function.
+ */
+
+/*
+ * Compare two "things", one and two; the third parameter is cb_data
+ * in the prio_queue structure. The result is returned as a sign of
+ * the return value, being the same as the sign of the result of
+ * subtracting "two" from "one" (i.e. negative if "one" sorts earlier
+ * than "two").
+ */
+typedef int (*prio_queue_compare_fn)(const void *one, const void *two, void *cb_data);
+
+struct prio_queue_entry {
+ unsigned ctr;
+ void *data;
+};
+
+struct prio_queue {
+ prio_queue_compare_fn compare;
+ unsigned insertion_ctr;
+ void *cb_data;
+ int alloc, nr;
+ struct prio_queue_entry *array;
+};
+
+/*
+ * Add the "thing" to the queue.
+ */
+void prio_queue_put(struct prio_queue *, void *thing);
+
+/*
+ * Extract the "thing" that compares the smallest out of the queue,
+ * or NULL. If compare function is NULL, the queue acts as a LIFO
+ * stack.
+ */
+void *prio_queue_get(struct prio_queue *);
+
+/*
+ * Gain access to the "thing" that would be returned by
+ * prio_queue_get, but do not remove it from the queue.
+ */
+void *prio_queue_peek(struct prio_queue *);
+
+void clear_prio_queue(struct prio_queue *);
+
+/* Reverse the LIFO elements */
+void prio_queue_reverse(struct prio_queue *);
+
+#endif /* PRIO_QUEUE_H */