Squashed 'third_party/git/' content from commit cb71568594

git-subtree-dir: third_party/git
git-subtree-split: cb715685942260375e1eb8153b0768a376e4ece7

1 files changed, 60 insertions, 0 deletions

diff --git a/prio-queue.h b/prio-queue.h
new file mode 100644
index 000000000000..4f9a37e6bee5
--- /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 */