cache_pqueue.c revision 3d81f57512275ca06a60a9bcbd23c1f8b429fdf2
/* Copyright 2002-2006 The Apache Software Foundation or its licensors, as
* applicable.
*
* 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 "apr_general.h"
#if APR_HAVE_STDLIB_H
#include <stdlib.h>
#endif
#if APR_HAVE_STDIO_H
#include <stdio.h>
#endif
#if APR_HAVE_STRING_H
#include <string.h>
#endif
#include "cache_pqueue.h"
#define left(i) (2*(i))
#define right(i) ((2*(i))+1)
#define parent(i) ((i)/2)
/*
* Priority queue structure
*/
struct cache_pqueue_t
{
apr_ssize_t size;
apr_ssize_t avail;
apr_ssize_t step;
cache_pqueue_get_priority pri;
cache_pqueue_getpos get;
cache_pqueue_setpos set;
void **d;
};
cache_pqueue_t *cache_pq_init(apr_ssize_t n,
cache_pqueue_get_priority pri,
cache_pqueue_getpos get,
cache_pqueue_setpos set)
{
cache_pqueue_t *q;
if (!(q = malloc(sizeof(cache_pqueue_t)))) {
return NULL;
}
/* Need to allocate n+1 elements since element 0 isn't used. */
if (!(q->d = malloc(sizeof(void*) * (n+1)))) {
free(q);
return NULL;
}
q->avail = q->step = (n+1); /* see comment above about n+1 */
q->pri = pri;
q->size = 1;
q->get = get;
q->set = set;
return q;
}
/*
* cleanup
*/
void cache_pq_free(cache_pqueue_t *q)
{
free(q->d);
free(q);
}
/*
* pqsize: size of the queue.
*/
apr_ssize_t cache_pq_size(cache_pqueue_t *q)
{
/* queue element 0 exists but doesn't count since it isn't used. */
return (q->size - 1);
}
static void cache_pq_bubble_up(cache_pqueue_t *q, apr_ssize_t i)
{
apr_ssize_t parent_node;
void *moving_node = q->d[i];
long moving_pri = q->pri(moving_node);
for (parent_node = parent(i);
((i > 1) && (q->pri(q->d[parent_node]) < moving_pri));
i = parent_node, parent_node = parent(i))
{
q->d[i] = q->d[parent_node];
q->set(q->d[i], i);
}
q->d[i] = moving_node;
q->set(moving_node, i);
}
static apr_ssize_t maxchild(cache_pqueue_t *q, apr_ssize_t i)
{
apr_ssize_t child_node = left(i);
if (child_node >= q->size)
return 0;
if ((child_node+1 < q->size) &&
(q->pri(q->d[child_node+1]) > q->pri(q->d[child_node])))
{
child_node++; /* use right child instead of left */
}
return child_node;
}
static void cache_pq_percolate_down(cache_pqueue_t *q, apr_ssize_t i)
{
apr_ssize_t child_node;
void *moving_node = q->d[i];
long moving_pri = q->pri(moving_node);
while ((child_node = maxchild(q, i)) &&
(moving_pri < q->pri(q->d[child_node])))
{
q->d[i] = q->d[child_node];
q->set(q->d[i], i);
i = child_node;
}
q->d[i] = moving_node;
q->set(moving_node, i);
}
apr_status_t cache_pq_insert(cache_pqueue_t *q, void *d)
{
void *tmp;
apr_ssize_t i;
apr_ssize_t newsize;
if (!q) return APR_EGENERAL;
/* allocate more memory if necessary */
if (q->size >= q->avail) {
newsize = q->size + q->step;
if (!(tmp = realloc(q->d, sizeof(void*) * newsize))) {
return APR_EGENERAL;
};
q->d = tmp;
q->avail = newsize;
}
/* insert item */
i = q->size++;
q->d[i] = d;
cache_pq_bubble_up(q, i);
return APR_SUCCESS;
}
/*
* move a existing entry to a new priority
*/
void cache_pq_change_priority(cache_pqueue_t *q,
long old_priority,
long new_priority,
void *d)
{
apr_ssize_t posn;
posn = q->get(d);
if (new_priority > old_priority)
cache_pq_bubble_up(q, posn);
else
cache_pq_percolate_down(q, posn);
}
apr_status_t cache_pq_remove(cache_pqueue_t *q, void *d)
{
apr_ssize_t posn = q->get(d);
q->d[posn] = q->d[--q->size];
if (q->pri(q->d[posn]) > q->pri(d))
cache_pq_bubble_up(q, posn);
else
cache_pq_percolate_down(q, posn);
return APR_SUCCESS;
}
void *cache_pq_pop(cache_pqueue_t *q)
{
void *head;
if (!q || q->size == 1)
return NULL;
head = q->d[1];
q->d[1] = q->d[--q->size];
cache_pq_percolate_down(q, 1);
return head;
}
void *cache_pq_peek(cache_pqueue_t *q)
{
void *d;
if (!q || q->size == 1)
return NULL;
d = q->d[1];
return d;
}
static void cache_pq_set_null( void*d, apr_ssize_t val)
{
/* do nothing */
}
/*
* this is a debug function.. so it's EASY not fast
*/
void cache_pq_dump(cache_pqueue_t *q,
FILE*out,
cache_pqueue_print_entry print)
{
int i;
fprintf(stdout,"posn\tleft\tright\tparent\tmaxchild\t...\n");
for (i = 1; i < q->size ;i++) {
fprintf(stdout,
"%d\t%d\t%d\t%d\t%" APR_SSIZE_T_FMT "\t",
i,
left(i), right(i), parent(i),
maxchild(q, i));
print(out, q->d[i]);
}
}
/*
* this is a debug function.. so it's EASY not fast
*/
void cache_pq_print(cache_pqueue_t *q,
FILE*out,
cache_pqueue_print_entry print)
{
cache_pqueue_t *dup;
dup = cache_pq_init(q->size, q->pri, q->get, cache_pq_set_null);
dup->size = q->size;
dup->avail = q->avail;
dup->step = q->step;
memcpy(dup->d, q->d, q->size*sizeof(void*));
while (cache_pq_size(dup) > 1) {
void *e = NULL;
e = cache_pq_pop(dup);
if (e)
print(out, e);
else
break;
}
cache_pq_free(dup);
}
static int cache_pq_subtree_is_valid(cache_pqueue_t *q, int pos)
{
if (left(pos) < q->size) {
/* has a left child */
if (q->pri(q->d[pos]) < q->pri(q->d[left(pos)]))
return 0;
if (!cache_pq_subtree_is_valid(q, left(pos)))
return 0;
}
if (right(pos) < q->size) {
/* has a right child */
if (q->pri(q->d[pos]) < q->pri(q->d[right(pos)]))
return 0;
if (!cache_pq_subtree_is_valid(q, right(pos)))
return 0;
}
return 1;
}
int cache_pq_is_valid(cache_pqueue_t *q)
{
return cache_pq_subtree_is_valid(q, 1);
}