prio-queue.h

   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         size_t ctr;
  26         void *data;
  27 };
  28
  29 struct prio_queue {
  30         prio_queue_compare_fn compare;
  31         size_t insertion_ctr;
  32         void *cb_data;
  33         size_t 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 /*
  56  * Replace the "thing" that compares the smallest with a new "thing",
  57  * like prio_queue_get()+prio_queue_put() would do, but in a more
  58  * efficient way.  Does the same as prio_queue_put() if the queue is
  59  * empty.
  60  */
  61 void prio_queue_replace(struct prio_queue *queue, void *thing);
  62
  63 void clear_prio_queue(struct prio_queue *);
  64
  65 /* Reverse the LIFO elements */
  66 void prio_queue_reverse(struct prio_queue *);
  67
  68 #endif /* PRIO_QUEUE_H */