Andrew's git - gitweb.git/blob

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