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 {
  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
  45 /* Reverse the LIFO elements */
  46 extern void prio_queue_reverse(struct prio_queue *);
  47
  48 #endif /* PRIO_QUEUE_H */