THIS IS A TEST INSTANCE ONLY! REPOSITORIES CAN BE DELETED AT ANY TIME!

Git Source Code Mirror - This is a publish-only repository and all pull requests are ignored. Please follow Documentation/SubmittingPatches procedure for any of your improvements.
git
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

61 lines
1.6KB

  1. #ifndef PRIO_QUEUE_H
  2. #define PRIO_QUEUE_H
  3. /*
  4. * A priority queue implementation, primarily for keeping track of
  5. * commits in the 'date-order' so that we process them from new to old
  6. * as they are discovered, but can be used to hold any pointer to
  7. * struct. The caller is responsible for supplying a function to
  8. * compare two "things".
  9. *
  10. * Alternatively, this data structure can also be used as a LIFO stack
  11. * by specifying NULL as the comparison function.
  12. */
  13. /*
  14. * Compare two "things", one and two; the third parameter is cb_data
  15. * in the prio_queue structure. The result is returned as a sign of
  16. * the return value, being the same as the sign of the result of
  17. * subtracting "two" from "one" (i.e. negative if "one" sorts earlier
  18. * than "two").
  19. */
  20. typedef int (*prio_queue_compare_fn)(const void *one, const void *two, void *cb_data);
  21. struct prio_queue_entry {
  22. unsigned ctr;
  23. void *data;
  24. };
  25. struct prio_queue {
  26. prio_queue_compare_fn compare;
  27. unsigned insertion_ctr;
  28. void *cb_data;
  29. int alloc, nr;
  30. struct prio_queue_entry *array;
  31. };
  32. /*
  33. * Add the "thing" to the queue.
  34. */
  35. void prio_queue_put(struct prio_queue *, void *thing);
  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. void *prio_queue_get(struct prio_queue *);
  42. /*
  43. * Gain access to the "thing" that would be returned by
  44. * prio_queue_get, but do not remove it from the queue.
  45. */
  46. void *prio_queue_peek(struct prio_queue *);
  47. void clear_prio_queue(struct prio_queue *);
  48. /* Reverse the LIFO elements */
  49. void prio_queue_reverse(struct prio_queue *);
  50. #endif /* PRIO_QUEUE_H */