]>
Commit | Line | Data |
---|---|---|
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 | */ | |
22 | typedef int (*prio_queue_compare_fn)(const void *one, const void *two, void *cb_data); | |
23 | ||
e8f91e3d JK |
24 | struct prio_queue_entry { |
25 | unsigned ctr; | |
26 | void *data; | |
27 | }; | |
28 | ||
b4b594a3 JH |
29 | struct 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 | */ | |
40 | extern 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 | */ | |
47 | extern 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 | */ | |
53 | extern void *prio_queue_peek(struct prio_queue *); | |
54 | ||
b4b594a3 JH |
55 | extern void clear_prio_queue(struct prio_queue *); |
56 | ||
da24b104 JH |
57 | /* Reverse the LIFO elements */ |
58 | extern void prio_queue_reverse(struct prio_queue *); | |
59 | ||
b4b594a3 | 60 | #endif /* PRIO_QUEUE_H */ |