]> git.ipfire.org Git - thirdparty/git.git/blame - prio-queue.h
git-submodule.sh: shorten submodule SHA-1s using rev-parse
[thirdparty/git.git] / prio-queue.h
CommitLineData
b4b594a3
JH
1#ifndef PRIO_QUEUE_H
2#define PRIO_QUEUE_H
3
4/*
5 * A priority queue implementation, primarily for keeping track of
6 * commits in the 'date-order' so that we process them from new to old
7 * as they are discovered, but can be used to hold any pointer to
8 * struct. The caller is responsible for supplying a function to
9 * compare two "things".
10 *
11 * Alternatively, this data structure can also be used as a LIFO stack
12 * by specifying NULL as the comparison function.
13 */
14
15/*
16 * Compare two "things", one and two; the third parameter is cb_data
17 * in the prio_queue structure. The result is returned as a sign of
18 * the return value, being the same as the sign of the result of
19 * subtracting "two" from "one" (i.e. negative if "one" sorts earlier
20 * than "two").
21 */
22typedef int (*prio_queue_compare_fn)(const void *one, const void *two, void *cb_data);
23
e8f91e3d
JK
24struct prio_queue_entry {
25 unsigned ctr;
26 void *data;
27};
28
b4b594a3
JH
29struct prio_queue {
30 prio_queue_compare_fn compare;
e8f91e3d 31 unsigned insertion_ctr;
b4b594a3
JH
32 void *cb_data;
33 int alloc, nr;
e8f91e3d 34 struct prio_queue_entry *array;
b4b594a3
JH
35};
36
37/*
38 * Add the "thing" to the queue.
39 */
40extern void prio_queue_put(struct prio_queue *, void *thing);
41
42/*
43 * Extract the "thing" that compares the smallest out of the queue,
44 * or NULL. If compare function is NULL, the queue acts as a LIFO
45 * stack.
46 */
47extern void *prio_queue_get(struct prio_queue *);
48
aca4240f
DS
49/*
50 * Gain access to the "thing" that would be returned by
51 * prio_queue_get, but do not remove it from the queue.
52 */
53extern void *prio_queue_peek(struct prio_queue *);
54
b4b594a3
JH
55extern void clear_prio_queue(struct prio_queue *);
56
da24b104
JH
57/* Reverse the LIFO elements */
58extern void prio_queue_reverse(struct prio_queue *);
59
b4b594a3 60#endif /* PRIO_QUEUE_H */