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     q->heap[a]->heap_index = a;
  71     q->heap[b]->heap_index = b;
  72 }
  73
  74 #define PARENT(i) (((i-1))>>1)
  75 #define CHILD_LEFT(i) (((i)<<1)+1)
  76 #define CHILD_RIGHT(i) (((i)<<1)+2)
  77
  78 static int
  79 cmp(pq q, unsigned int a, unsigned int b)
  80 {
  81     return q->cmp(q->heap[a], q->heap[b]);
  82 }
  83
  84 static void
  85 bubble_up(pq q, unsigned int k)
  86 {
  87     int p;
  88
  89     if (k == 0) return;
  90     p = PARENT(k);
  91     if (cmp(q, p, k) <= 0) return;
  92     swap(q, k, p);
  93     bubble_up(q, p);
  94 }
  95
  96 static void
  97 bubble_down(pq q, unsigned int k)
  98 {
  99     int l, r, s;
 100
 101     l = CHILD_LEFT(k);
 102     r = CHILD_RIGHT(k);
 103
 104     s = k;
 105     if (l < q->used && cmp(q, l, k) < 0) s = l;
 106     if (r < q->used && cmp(q, r, s) < 0) s = r;
 107     if (s == k) return; /* already satisfies the heap property */
 108
 109     swap(q, k, s);
 110     bubble_down(q, s);
 111 }
 112
 113 /* assumes there is at least one item in the queue */
 114 static void
 115 delete_min(pq q)
 116 {
 117     q->heap[0] = q->heap[--q->used];
 118     q->heap[0]->heap_index = 0;
 119     if (q->used) bubble_down(q, 0);
 120 }
 121
 122 int
 123 pq_give(pq q, job j)
 124 {
 125     int k;
 126
 127     if (q->used >= q->cap) pq_grow(q);
 128     if (q->used >= q->cap) return 0;
 129
 130     k = q->used++;
 131     q->heap[k] = j;
 132     j->heap_index = k;
 133     bubble_up(q, k);
 134
 135     return 1;
 136 }
 137
 138 job
 139 pq_take(pq q)
 140 {
 141     job j;
 142
 143     if (q->used == 0) return NULL;
 144
 145     j = q->heap[0];
 146     delete_min(q);
 147     return j;
 148 }
 149
 150 job
 151 pq_peek(pq q)
 152 {
 153     if (q->used == 0) return NULL;
 154     return q->heap[0];
 155 }
 156
 157 job
 158 pq_remove(pq q, job j)
 159 {
 160     unsigned long long int id;
 161     unsigned int pri;
 162
 163     if (q->used == 0) return NULL;
 164     if (q->heap[j->heap_index] != j) return NULL;
 165
 166     id = j->id;
 167     j->id = 0;
 168     pri = j->pri;
 169     j->pri = 0;
 170
 171     bubble_up(q, j->heap_index);
 172
 173     j->id = id;
 174     j->pri = pri;
 175
 176     /* can't happen */
 177     if (q->heap[0] != j) return NULL;
 178
 179     delete_min(q);
 180
 181     return j;
 182 }