Andrew's git - gitweb.git/blob

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