Merge branch 'js/xread-in-full'
[git] / prio-queue.h
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  */
22 typedef int (*prio_queue_compare_fn)(const void *one, const void *two, void *cb_data);
23
24 struct prio_queue {
25         prio_queue_compare_fn compare;
26         void *cb_data;
27         int alloc, nr;
28         void **array;
29 };
30
31 /*
32  * Add the "thing" to the queue.
33  */
34 extern void prio_queue_put(struct prio_queue *, void *thing);
35
36 /*
37  * Extract the "thing" that compares the smallest out of the queue,
38  * or NULL.  If compare function is NULL, the queue acts as a LIFO
39  * stack.
40  */
41 extern void *prio_queue_get(struct prio_queue *);
42
43 extern void clear_prio_queue(struct prio_queue *);
44
45 /* Reverse the LIFO elements */
46 extern void prio_queue_reverse(struct prio_queue *);
47
48 #endif /* PRIO_QUEUE_H */