cache_pqueue.c revision 3a59bb90be3bc6246632384c3d885b875ae507d5
/* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You 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
*
*
* 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"
#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;
};
{
/* Need to allocate n+1 elements since element 0 isn't used. */
q->d = ap_malloc(sizeof(void*) * (n+1));
q->size = 1;
return q;
}
/*
* cleanup
*/
void cache_pq_free(cache_pqueue_t *q)
{
free(q->d);
free(q);
}
/*
* pqsize: size of the queue.
*/
{
/* queue element 0 exists but doesn't count since it isn't used. */
return (q->size - 1);
}
{
void *moving_node = q->d[i];
for (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);
}
{
if (child_node >= q->size)
return 0;
{
child_node++; /* use right child instead of left */
}
return child_node;
}
{
void *moving_node = q->d[i];
while ((child_node = maxchild(q, i)) &&
{
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);
}
{
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++;
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)
{
if (new_priority > old_priority)
cache_pq_bubble_up(q, posn);
else
}
{
cache_pq_bubble_up(q, posn);
else
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;
}
{
/* 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++) {
i,
maxchild(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;
}
}
{
/* has a left child */
return 0;
return 0;
}
/* has a right child */
return 0;
return 0;
}
return 1;
}
int cache_pq_is_valid(cache_pqueue_t *q)
{
return cache_pq_subtree_is_valid(q, 1);
}