pq.c

   1 /* pq.c - priority queue */
   2
   3 /* Copyright (C) 2007 Keith Rarick and Philotic Inc.
   4
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #include <stdlib.h>
  20 #include <stdio.h>
  21 #include <string.h>
  22
  23 #include "tube.h" /* hack to make cpp happy */
  24 #include "pq.h"
  25
  26 void
  27 pq_init(pq q, job_cmp_fn cmp)
  28 {
  29     if (!q) return;
  30
  31     q->cap = 0;
  32     q->used = 0;
  33     q->cmp = cmp;
  34     q->heap = NULL;
  35
  36     return;
  37 }
  38
  39 void
  40 pq_clear(pq q)
  41 {
  42     free(q->heap);
  43     pq_init(q, q->cmp);
  44 }
  45
  46 static void
  47 pq_grow(pq q)
  48 {
  49     job *nheap;
  50     unsigned int ncap = q->cap << 1 ? : 1;
  51
  52     nheap = malloc(ncap * sizeof(job));
  53     if (!nheap) return;
  54
  55     if (q->heap) memcpy(nheap, q->heap, q->used * sizeof(job));
  56     free(q->heap);
  57     q->heap = nheap;
  58     q->cap = ncap;
  59 }
  60
  61 static void
  62 swap(pq q, unsigned int a, unsigned int b)
  63 {
  64     job j;
  65
  66     j = q->heap[a];
  67     q->heap[a] = q->heap[b];
  68     q->heap[b] = j;
  69 }
  70
  71 #define PARENT(i) (((i-1))>>1)
  72 #define CHILD_LEFT(i) (((i)<<1)+1)
  73 #define CHILD_RIGHT(i) (((i)<<1)+2)
  74
  75 static int
  76 cmp(pq q, unsigned int a, unsigned int b)
  77 {
  78     return q->cmp(q->heap[a], q->heap[b]);
  79 }
  80
  81 static void
  82 bubble_up(pq q, unsigned int k)
  83 {
  84     int p;
  85
  86     if (k == 0) return;
  87     p = PARENT(k);
  88     if (cmp(q, p, k) <= 0) return;
  89     swap(q, k, p);
  90     bubble_up(q, p);
  91 }
  92
  93 static void
  94 bubble_down(pq q, unsigned int k)
  95 {
  96     int l, r, s;
  97
  98     l = CHILD_LEFT(k);
  99     r = CHILD_RIGHT(k);
 100
 101     s = k;
 102     if (l < q->used && cmp(q, l, k) < 0) s = l;
 103     if (r < q->used && cmp(q, r, s) < 0) s = r;
 104     if (s == k) return; /* already satisfies the heap property */
 105
 106     swap(q, k, s);
 107     bubble_down(q, s);
 108 }
 109
 110 /* assumes there is at least one item in the queue */
 111 static void
 112 delete_min(pq q)
 113 {
 114     q->heap[0] = q->heap[--q->used];
 115     if (q->used) bubble_down(q, 0);
 116 }
 117
 118 int
 119 pq_give(pq q, job j)
 120 {
 121     int k;
 122
 123     if (q->used >= q->cap) pq_grow(q);
 124     if (q->used >= q->cap) return 0;
 125
 126     k = q->used++;
 127     q->heap[k] = j;
 128     bubble_up(q, k);
 129
 130     return 1;
 131 }
 132
 133 job
 134 pq_take(pq q)
 135 {
 136     job j;
 137
 138     if (q->used == 0) return NULL;
 139
 140     j = q->heap[0];
 141     delete_min(q);
 142     return j;
 143 }
 144
 145 job
 146 pq_peek(pq q)
 147 {
 148     if (q->used == 0) return NULL;
 149     return q->heap[0];
 150 }
 151
 152 job
 153 pq_find(pq q, unsigned long long int id)
 154 {
 155     unsigned int i;
 156
 157     for (i = 0; i < q->used; i++) if (q->heap[i]->id == id) return q->heap[i];
 158     return NULL;
 159 }
 160
 161 unsigned int
 162 pq_used(pq q)
 163 {
 164     return q->used;
 165 }