[thirdparty/git.git] / prio-queue.h

#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 {
	prio_queue_compare_fn compare;
	void *cb_data;
	int alloc, nr;
	void **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 */
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
	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
da24b104 JH	45	/* Reverse the LIFO elements */
	46	extern void prio_queue_reverse(struct prio_queue *);
	47
b4b594a3	48	#endif /* PRIO_QUEUE_H */