Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: 0917df3bb9
Fetching contributors…

Cannot retrieve contributors at this time

183 lines (141 sloc) 3.283 kb
/* pq.c - priority queue */
/* Copyright (C) 2007 Keith Rarick and Philotic Inc.
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "tube.h" /* hack to make cpp happy */
#include "pq.h"
void
pq_init(pq q, job_cmp_fn cmp)
{
if (!q) return;
q->cap = 0;
q->used = 0;
q->cmp = cmp;
q->heap = NULL;
return;
}
void
pq_clear(pq q)
{
free(q->heap);
pq_init(q, q->cmp);
}
static void
pq_grow(pq q)
{
job *nheap;
unsigned int ncap = q->cap << 1 ? : 1;
nheap = malloc(ncap * sizeof(job));
if (!nheap) return;
if (q->heap) memcpy(nheap, q->heap, q->used * sizeof(job));
free(q->heap);
q->heap = nheap;
q->cap = ncap;
}
static void
swap(pq q, unsigned int a, unsigned int b)
{
job j;
j = q->heap[a];
q->heap[a] = q->heap[b];
q->heap[b] = j;
q->heap[a]->heap_index = a;
q->heap[b]->heap_index = b;
}
#define PARENT(i) (((i-1))>>1)
#define CHILD_LEFT(i) (((i)<<1)+1)
#define CHILD_RIGHT(i) (((i)<<1)+2)
static int
cmp(pq q, unsigned int a, unsigned int b)
{
return q->cmp(q->heap[a], q->heap[b]);
}
static void
bubble_up(pq q, unsigned int k)
{
int p;
if (k == 0) return;
p = PARENT(k);
if (cmp(q, p, k) <= 0) return;
swap(q, k, p);
bubble_up(q, p);
}
static void
bubble_down(pq q, unsigned int k)
{
int l, r, s;
l = CHILD_LEFT(k);
r = CHILD_RIGHT(k);
s = k;
if (l < q->used && cmp(q, l, k) < 0) s = l;
if (r < q->used && cmp(q, r, s) < 0) s = r;
if (s == k) return; /* already satisfies the heap property */
swap(q, k, s);
bubble_down(q, s);
}
/* assumes there is at least one item in the queue */
static void
delete_min(pq q)
{
q->heap[0] = q->heap[--q->used];
q->heap[0]->heap_index = 0;
if (q->used) bubble_down(q, 0);
}
int
pq_give(pq q, job j)
{
int k;
if (q->used >= q->cap) pq_grow(q);
if (q->used >= q->cap) return 0;
k = q->used++;
q->heap[k] = j;
j->heap_index = k;
bubble_up(q, k);
return 1;
}
job
pq_take(pq q)
{
job j;
if (q->used == 0) return NULL;
j = q->heap[0];
delete_min(q);
return j;
}
job
pq_peek(pq q)
{
if (q->used == 0) return NULL;
return q->heap[0];
}
job
pq_remove(pq q, job j)
{
uint64_t id;
unsigned int pri;
if (j->heap_index >= q->used) return NULL;
if (q->heap[j->heap_index] != j) return NULL;
id = j->id;
j->id = 0;
pri = j->pri;
j->pri = 0;
bubble_up(q, j->heap_index);
j->id = id;
j->pri = pri;
/* can't happen */
if (q->heap[0] != j) return NULL;
delete_min(q);
return j;
}
Jump to Line
Something went wrong with that request. Please try again.