git.oblomov.eu Git - git/blob - prio-queue.c

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