src/pqueue.c

   1 /*
   2  * Copyright (C) 2009-2012 the libgit2 contributors
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #include "common.h"
   9 #include "pqueue.h"
  10
  11 #define left(i) ((i) << 1)
  12 #define right(i) (((i) << 1) + 1)
  13 #define parent(i) ((i) >> 1)
  14
  15 int git_pqueue_init(git_pqueue *q, size_t n, git_pqueue_cmp cmppri)
  16 {
  17         assert(q);
  18
  19         /* Need to allocate n+1 elements since element 0 isn't used. */
  20         q->d = git__malloc((n + 1) * sizeof(void *));
  21         GITERR_CHECK_ALLOC(q->d);
  22
  23         q->size = 1;
  24         q->avail = q->step = (n + 1); /* see comment above about n+1 */
  25         q->cmppri = cmppri;
  26
  27         return 0;
  28 }
  29
  30
  31 void git_pqueue_free(git_pqueue *q)
  32 {
  33         git__free(q->d);
  34         q->d = NULL;
  35 }
  36
  37 void git_pqueue_clear(git_pqueue *q)
  38 {
  39         q->size = 1;
  40 }
  41
  42 size_t git_pqueue_size(git_pqueue *q)
  43 {
  44         /* queue element 0 exists but doesn't count since it isn't used. */
  45         return (q->size - 1);
  46 }
  47
  48
  49 static void bubble_up(git_pqueue *q, size_t i)
  50 {
  51         size_t parent_node;
  52         void *moving_node = q->d[i];
  53
  54         for (parent_node = parent(i);
  55                         ((i > 1) && q->cmppri(q->d[parent_node], moving_node));
  56                         i = parent_node, parent_node = parent(i)) {
  57                 q->d[i] = q->d[parent_node];
  58         }
  59
  60         q->d[i] = moving_node;
  61 }
  62
  63
  64 static size_t maxchild(git_pqueue *q, size_t i)
  65 {
  66         size_t child_node = left(i);
  67
  68         if (child_node >= q->size)
  69                 return 0;
  70
  71         if ((child_node + 1) < q->size &&
  72                 q->cmppri(q->d[child_node], q->d[child_node + 1]))
  73                 child_node++; /* use right child instead of left */
  74
  75         return child_node;
  76 }
  77
  78
  79 static void percolate_down(git_pqueue *q, size_t i)
  80 {
  81         size_t child_node;
  82         void *moving_node = q->d[i];
  83
  84         while ((child_node = maxchild(q, i)) != 0 &&
  85                         q->cmppri(moving_node, q->d[child_node])) {
  86                 q->d[i] = q->d[child_node];
  87                 i = child_node;
  88         }
  89
  90         q->d[i] = moving_node;
  91 }
  92
  93
  94 int git_pqueue_insert(git_pqueue *q, void *d)
  95 {
  96         void *tmp;
  97         size_t i;
  98         size_t newsize;
  99
 100         if (!q) return 1;
 101
 102         /* allocate more memory if necessary */
 103         if (q->size >= q->avail) {
 104                 newsize = q->size + q->step;
 105                 tmp = git__realloc(q->d, sizeof(void *) * newsize);
 106                 GITERR_CHECK_ALLOC(tmp);
 107
 108                 q->d = tmp;
 109                 q->avail = newsize;
 110         }
 111
 112         /* insert item */
 113         i = q->size++;
 114         q->d[i] = d;
 115         bubble_up(q, i);
 116
 117         return 0;
 118 }
 119
 120
 121 void *git_pqueue_pop(git_pqueue *q)
 122 {
 123         void *head;
 124
 125         if (!q || q->size == 1)
 126                 return NULL;
 127
 128         head = q->d[1];
 129         q->d[1] = q->d[--q->size];
 130         percolate_down(q, 1);
 131
 132         return head;
 133 }
 134
 135
 136 void *git_pqueue_peek(git_pqueue *q)
 137 {
 138         if (!q || q->size == 1)
 139                 return NULL;
 140         return q->d[1];
 141 }