cache_pqueue.c revision 5117466ef123b1efbc2feba168f37069ef6f230b
#include "apr_general.h"
#include <stdlib.h>
#endif
#if APR_HAVE_STDIO_H
#include <stdio.h>
#endif
#include <string.h>
#endif
#include "cache_pqueue.h"
#define left(i) (2*(i))
#define parent(i) (i/2)
/*
* Priority queue structure
*/
struct cache_pqueue_t
{
void **d;
};
{
cache_pqueue_t *q;
if (!(q = malloc(sizeof(cache_pqueue_t)))) {
return NULL;
}
if (!(q->d = malloc(sizeof(void*) * n))) {
free(q);
return NULL;
}
q->size = 1;
return q;
}
/*
* cleanup
*/
void cache_pq_free(cache_pqueue_t *q)
{
free(q->d);
free(q);
}
/*
* pqsize: size of the queue.
*/
{
return q->size;
}
{
parent_node = parent(i);
void *tmp;
tmp = q->d[i];
q->d[i] = q->d[parent_node];
q->d[parent_node] = tmp;
q->set(q->d[i], i);
i = parent_node;
parent_node = parent(i);
}
}
{
apr_ssize_t y, minc;
return -1;
minc = y;
}
return minc;
}
{
{
void *tmp;
tmp = q->d[i];
q->d[i] = q->d[cx];
q->set(q->d[i], i);
i = cx;
}
}
{
void *tmp;
apr_ssize_t i;
if (!q) return APR_EGENERAL;
/* allocate more memory if necessary */
return APR_EGENERAL;
};
q->d = tmp;
}
/* insert item */
i = q->size++;
parent_node = parent(i);
/*
* this is an optimization of the bubble-up as it doesn't
* have to swap the member around
*/
q->d[i] = q->d[parent_node];
q->set(q->d[i], i);
i = parent_node;
parent_node = parent(i);
}
q->d[i] = d;
q->set(q->d[i], i);
return APR_SUCCESS;
}
/*
* move a existing entry to a new priority
*/
long old_priority,
long new_priority,
void *d)
{
if (new_priority > old_priority)
cache_pq_bubble_up(q, posn);
else
}
{
long pri_popped;
long pri_removed;
popped = cache_pq_pop(q);
if (!popped)
return APR_EGENERAL;
if (d == popped) {
return APR_SUCCESS;
}
pri_removed = q->pri(d);
if (pri_popped > pri_removed)
cache_pq_bubble_up(q, posn);
else
return APR_SUCCESS;
}
void *cache_pq_pop(cache_pqueue_t *q)
{
void *tmp;
void *d;
int i = 1;
int j;
if (!q || q->size == 1)
return NULL;
d = q->d[1];
while (i <= q->size / 2) {
j = 2 * i;
j++;
}
break;
}
q->d[i] = q->d[j];
q->set(d, i);
i = j;
}
q->d[i] = tmp;
q->set(d, i);
return d;
}
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, int val)
{
/* do nothing */
}
/*
* this is a debug function.. so it's EASY not fast
*/
void cache_pq_dump(cache_pqueue_t *q,
{
int i;
for (i = 1; i < q->size ;i++) {
"%d\t%d\t%d\t%d\t%d\t",
i,
minchild(q, i));
}
}
/*
* this is a debug function.. so it's EASY not fast
*/
void cache_pq_print(cache_pqueue_t *q,
{
void *e = NULL;
e = cache_pq_pop(dup);
if (e)
else
break;
}
}