File: prio-queue.h

package info (click to toggle)
cgit 1.1%2Bgit2.10.2-3~bpo8%2B1
  • links: PTS, VCS
  • area: main
  • in suites: jessie-backports
  • size: 31,812 kB
  • sloc: ansic: 179,975; sh: 150,940; perl: 29,466; tcl: 21,429; python: 7,116; makefile: 3,424; lisp: 1,786; php: 120; asm: 98; csh: 45
file content (54 lines) | stat: -rw-r--r-- 1,528 bytes parent folder | download | duplicates (7)
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
#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.
 */
extern 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.
 */
extern void *prio_queue_get(struct prio_queue *);

extern void clear_prio_queue(struct prio_queue *);

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

#endif /* PRIO_QUEUE_H */