nagios4/lib/pqueue.c

304 lines
5.4 KiB
C
Raw Permalink Normal View History

2017-05-19 23:37:19 +02:00
/*
* Copyright 2010 Volkan Yazıcı <volkan.yazici@gmail.com>
* Copyright 2006-2010 The Apache Software Foundation
*
* Licensed under the Apache License, Version 2.0 (the "License"); you may not
* use this file except in compliance with the License. You may obtain a copy
* of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
* License for the specific language governing permissions and limitations
* under the License.
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "pqueue.h"
#define left(i) (unsigned long)((i) << 1)
#define right(i) (unsigned long)(((i) << 1) + 1)
#define parent(i) (unsigned long)((i) >> 1)
pqueue_t *
pqueue_init(unsigned int n,
pqueue_cmp_pri_f cmppri,
pqueue_get_pri_f getpri,
pqueue_set_pri_f setpri,
pqueue_get_pos_f getpos,
pqueue_set_pos_f setpos)
{
pqueue_t *q;
if (!(q = calloc(1, sizeof(pqueue_t)))) {
return NULL;
}
/* Need to allocate n+1 elements since element 0 isn't used. */
if (!(q->d = calloc(n + 1, sizeof(void *)))) {
free(q);
return NULL;
}
q->size = 1;
q->avail = q->step = (n + 1); /* see comment above about n+1 */
q->cmppri = cmppri;
q->setpri = setpri;
q->getpri = getpri;
q->getpos = getpos;
q->setpos = setpos;
return q;
}
void
pqueue_free(pqueue_t *q)
{
free(q->d);
free(q);
}
unsigned int
pqueue_size(pqueue_t *q)
{
/* queue element 0 exists but doesn't count since it isn't used. */
return (q->size - 1);
}
static void
bubble_up(pqueue_t *q, unsigned int i)
{
unsigned int parent_node;
void *moving_node = q->d[i];
pqueue_pri_t moving_pri = q->getpri(moving_node);
for (parent_node = parent(i);
((i > 1) && q->cmppri(q->getpri(q->d[parent_node]), moving_pri));
i = parent_node, parent_node = parent(i)) {
q->d[i] = q->d[parent_node];
q->setpos(q->d[i], i);
}
q->d[i] = moving_node;
q->setpos(moving_node, i);
}
static unsigned int
maxchild(pqueue_t *q, unsigned int i)
{
unsigned int child_node = left(i);
if (child_node >= q->size) {
return 0;
}
if ((child_node + 1) < q->size && q->cmppri(q->getpri(q->d[child_node]), q->getpri(q->d[child_node + 1]))) {
child_node++; /* use right child instead of left */
}
return child_node;
}
static void
percolate_down(pqueue_t *q, unsigned int i)
{
unsigned int child_node;
void *moving_node = q->d[i];
pqueue_pri_t moving_pri = q->getpri(moving_node);
while ((child_node = maxchild(q, i)) &&
q->cmppri(moving_pri, q->getpri(q->d[child_node]))) {
q->d[i] = q->d[child_node];
q->setpos(q->d[i], i);
i = child_node;
}
q->d[i] = moving_node;
q->setpos(moving_node, i);
}
int
pqueue_insert(pqueue_t *q, void *d)
{
void *tmp;
unsigned int i;
unsigned int newsize;
if (!q) {
return 1;
}
/* allocate more memory if necessary */
if (q->size >= q->avail) {
newsize = q->size + q->step;
if (!(tmp = realloc(q->d, sizeof(void *) * newsize))) {
return 1;
}
q->d = tmp;
q->avail = newsize;
}
/* insert item */
i = q->size++;
q->d[i] = d;
bubble_up(q, i);
return 0;
}
void
pqueue_change_priority(pqueue_t *q, pqueue_pri_t new_pri, void *d)
{
unsigned int posn;
pqueue_pri_t old_pri = q->getpri(d);
q->setpri(d, new_pri);
posn = q->getpos(d);
if (q->cmppri(old_pri, new_pri)) {
bubble_up(q, posn);
} else {
percolate_down(q, posn);
}
}
int
pqueue_remove(pqueue_t *q, void *d)
{
unsigned int posn = q->getpos(d);
q->d[posn] = q->d[--q->size];
if (q->cmppri(q->getpri(d), q->getpri(q->d[posn]))) {
bubble_up(q, posn);
} else {
percolate_down(q, posn);
}
return 0;
}
void *
pqueue_pop(pqueue_t *q)
{
void *head;
if (!q || q->size == 1) {
return NULL;
}
head = q->d[1];
q->d[1] = q->d[--q->size];
percolate_down(q, 1);
return head;
}
void *
pqueue_peek(pqueue_t *q)
{
if (!q || q->size == 1) {
return NULL;
}
return q->d[1];
}
#if 0
void
pqueue_dump(pqueue_t *q, FILE *out, pqueue_print_entry_f print)
{
int i;
fprintf(out, "posn\tleft\tright\tparent\tmaxchild\t...\n");
for (i = 1; i < q->size ; i++) {
fprintf(out, "%d\t%d\t%d\t%d\t%ul\t",
i,
left(i), right(i), parent(i),
(unsigned int)maxchild(q, i));
print(out, q->d[i]);
}
}
static void
set_pos(void *d, unsigned int val)
{
/* do nothing */
}
static void
set_pri(void *d, pqueue_pri_t pri)
{
/* do nothing */
}
void
pqueue_print(pqueue_t *q, FILE *out, pqueue_print_entry_f print)
{
pqueue_t *dup;
void *e;
dup = pqueue_init(q->size, q->cmppri, q->getpri, set_pri,
q->getpos, set_pos);
dup->size = q->size;
dup->avail = q->avail;
dup->step = q->step;
memcpy(dup->d, q->d, (q->size * sizeof(void *)));
while ((e = pqueue_pop(dup))) {
print(out, e);
}
pqueue_free(dup);
}
#endif
static int
subtree_is_valid(pqueue_t *q, int pos)
{
if (left(pos) < q->size) {
/* has a left child */
if (q->cmppri(q->getpri(q->d[pos]), q->getpri(q->d[left(pos)]))) {
return 0;
}
if (!subtree_is_valid(q, left(pos))) {
return 0;
}
}
if (right(pos) < q->size) {
/* has a right child */
if (q->cmppri(q->getpri(q->d[pos]), q->getpri(q->d[right(pos)]))) {
return 0;
}
if (!subtree_is_valid(q, right(pos))) {
return 0;
}
}
return 1;
}
int
pqueue_is_valid(pqueue_t *q)
{
return subtree_is_valid(q, 1);
}