]>
Commit | Line | Data |
---|---|---|
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_entry { | |
25 | unsigned ctr; | |
26 | void *data; | |
27 | }; | |
28 | ||
29 | struct prio_queue { | |
30 | prio_queue_compare_fn compare; | |
31 | unsigned insertion_ctr; | |
32 | void *cb_data; | |
33 | int alloc, nr; | |
34 | struct prio_queue_entry *array; | |
35 | }; | |
36 | ||
37 | /* | |
38 | * Add the "thing" to the queue. | |
39 | */ | |
40 | 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 | void *prio_queue_get(struct prio_queue *); | |
48 | ||
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 | void *prio_queue_peek(struct prio_queue *); | |
54 | ||
55 | void clear_prio_queue(struct prio_queue *); | |
56 | ||
57 | /* Reverse the LIFO elements */ | |
58 | void prio_queue_reverse(struct prio_queue *); | |
59 | ||
60 | #endif /* PRIO_QUEUE_H */ |