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.

97 lines
2.0KB

  1. #include "cache.h"
  2. #include "prio-queue.h"
  3. static inline int compare(struct prio_queue *queue, int i, int j)
  4. {
  5. int cmp = queue->compare(queue->array[i].data, queue->array[j].data,
  6. queue->cb_data);
  7. if (!cmp)
  8. cmp = queue->array[i].ctr - queue->array[j].ctr;
  9. return cmp;
  10. }
  11. static inline void swap(struct prio_queue *queue, int i, int j)
  12. {
  13. SWAP(queue->array[i], queue->array[j]);
  14. }
  15. void prio_queue_reverse(struct prio_queue *queue)
  16. {
  17. int i, j;
  18. if (queue->compare != NULL)
  19. BUG("prio_queue_reverse() on non-LIFO queue");
  20. for (i = 0; i < (j = (queue->nr - 1) - i); i++)
  21. swap(queue, i, j);
  22. }
  23. void clear_prio_queue(struct prio_queue *queue)
  24. {
  25. FREE_AND_NULL(queue->array);
  26. queue->nr = 0;
  27. queue->alloc = 0;
  28. queue->insertion_ctr = 0;
  29. }
  30. void prio_queue_put(struct prio_queue *queue, void *thing)
  31. {
  32. int ix, parent;
  33. /* Append at the end */
  34. ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
  35. queue->array[queue->nr].ctr = queue->insertion_ctr++;
  36. queue->array[queue->nr].data = thing;
  37. queue->nr++;
  38. if (!queue->compare)
  39. return; /* LIFO */
  40. /* Bubble up the new one */
  41. for (ix = queue->nr - 1; ix; ix = parent) {
  42. parent = (ix - 1) / 2;
  43. if (compare(queue, parent, ix) <= 0)
  44. break;
  45. swap(queue, parent, ix);
  46. }
  47. }
  48. void *prio_queue_get(struct prio_queue *queue)
  49. {
  50. void *result;
  51. int ix, child;
  52. if (!queue->nr)
  53. return NULL;
  54. if (!queue->compare)
  55. return queue->array[--queue->nr].data; /* LIFO */
  56. result = queue->array[0].data;
  57. if (!--queue->nr)
  58. return result;
  59. queue->array[0] = queue->array[queue->nr];
  60. /* Push down the one at the root */
  61. for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
  62. child = ix * 2 + 1; /* left */
  63. if (child + 1 < queue->nr &&
  64. compare(queue, child, child + 1) >= 0)
  65. child++; /* use right child */
  66. if (compare(queue, ix, child) <= 0)
  67. break;
  68. swap(queue, child, ix);
  69. }
  70. return result;
  71. }
  72. void *prio_queue_peek(struct prio_queue *queue)
  73. {
  74. if (!queue->nr)
  75. return NULL;
  76. if (!queue->compare)
  77. return queue->array[queue->nr - 1].data;
  78. return queue->array[0].data;
  79. }