about summary refs log tree commit diff
path: root/third_party/git/prio-queue.h
blob: 4f9a37e6bee5b537c10458c9ec18792cfd5de348 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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_entry {
	unsigned ctr;
	void *data;
};

struct prio_queue {
	prio_queue_compare_fn compare;
	unsigned insertion_ctr;
	void *cb_data;
	int alloc, nr;
	struct prio_queue_entry *array;
};

/*
 * Add the "thing" to the queue.
 */
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.
 */
void *prio_queue_get(struct prio_queue *);

/*
 * Gain access to the "thing" that would be returned by
 * prio_queue_get, but do not remove it from the queue.
 */
void *prio_queue_peek(struct prio_queue *);

void clear_prio_queue(struct prio_queue *);

/* Reverse the LIFO elements */
void prio_queue_reverse(struct prio_queue *);

#endif /* PRIO_QUEUE_H */