summaryrefslogtreecommitdiff
path: root/prio-queue.h
diff options
context:
space:
mode:
authorJunio C Hamano <gitster@pobox.com>2013-06-06 19:13:50 -0700
committerJunio C Hamano <gitster@pobox.com>2013-06-11 15:15:21 -0700
commitb4b594a3154078430b04fad4f6ffbed9c7274be5 (patch)
tree71bb8164f9e98ca159fbb952b6a289fd899337ad /prio-queue.h
parent08f704f294e4a3525b405c2cb1f4ee85e73fd92c (diff)
downloadgit-b4b594a3154078430b04fad4f6ffbed9c7274be5.tar.gz
prio-queue: priority queue of pointers to structs
Traditionally we used a singly linked list of commits to hold a set of in-flight commits while traversing history. The most typical use of the list is to add commits that are newly discovered to it, keep the list sorted by commit timestamp, pick up the newest one from the list, and keep digging. The cost of keeping the singly linked list sorted is nontrivial, and this typical use pattern better matches a priority queue. Introduce a prio-queue structure, that can be used either as a LIFO stack, or a priority queue. This will be used in the next patch to hold in-flight commits during sort-in-topological-order. Tests and the idea to make it usable for any "void *" pointers to "things" are by Jeff King. Bugs are mine. Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'prio-queue.h')
-rw-r--r--prio-queue.h45
1 files changed, 45 insertions, 0 deletions
diff --git a/prio-queue.h b/prio-queue.h
new file mode 100644
index 0000000000..c766abec3d
--- /dev/null
+++ b/prio-queue.h
@@ -0,0 +1,45 @@
+#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 {
+ prio_queue_compare_fn compare;
+ void *cb_data;
+ int alloc, nr;
+ void **array;
+};
+
+/*
+ * Add the "thing" to the queue.
+ */
+extern 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.
+ */
+extern void *prio_queue_get(struct prio_queue *);
+
+extern void clear_prio_queue(struct prio_queue *);
+
+#endif /* PRIO_QUEUE_H */