modules/cache/cache_pqueue.h

   1 /* Licensed to the Apache Software Foundation (ASF) under one or more
   2  * contributor license agreements.  See the NOTICE file distributed with
   3  * this work for additional information regarding copyright ownership.
   4  * The ASF licenses this file to You under the Apache License, Version 2.0
   5  * (the "License"); you may not use this file except in compliance with
   6  * the License.  You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /**
  18  * @file  cache_pqueue.h
  19  * @brief Cache Priority Queue function declarations
  20  *
  21  * @defgroup MOD_CACHE_QUEUE Priority Queue
  22  * @ingroup  MOD_CACHE
  23  * @{
  24  */
  25
  26 #ifndef CACHE_PQUEUE_H
  27 #define CACHE_PQUEUE_H
  28
  29 #include <apr.h>
  30 #include <apr_errno.h>
  31
  32 #if APR_HAVE_STDIO_H
  33 #include <stdio.h>
  34 #endif
  35
  36 #ifdef __cplusplus
  37 extern "C" {
  38 #endif
  39
  40 /** the cache priority queue handle */
  41 typedef struct cache_pqueue_t cache_pqueue_t;
  42
  43 /**
  44  * callback function to assign a priority for a element
  45  * @param a the element
  46  * @return  the score (the lower the score the longer it is kept int the queue)
  47  */
  48 typedef long (*cache_pqueue_set_priority)(long queue_clock, void *a);
  49 typedef long (*cache_pqueue_get_priority)(void *a);
  50
  51 /** callback function to get a position of a element */
  52 typedef apr_ssize_t (*cache_pqueue_getpos)(void *a);
  53
  54 /**
  55  * callback function to set a position of a element
  56  * @param a   the element
  57  * @param pos the position to set it to
  58  */
  59 typedef void (*cache_pqueue_setpos)(void *a, apr_ssize_t pos);
  60
  61 /** debug callback function to print a entry */
  62 typedef void (*cache_pqueue_print_entry)(FILE *out, void *a);
  63
  64 /**
  65  * initialize the queue
  66  *
  67  * @param n the initial estimate of the number of queue items for which memory
  68  *          should be preallocated
  69  * @param pri the callback function to run to assign a score to a element
  70  * @param get the callback function to get the current element's position
  71  * @param set the callback function to set the current element's position
  72  *
  73  * @Return the handle or NULL for insufficent memory
  74  */
  75 cache_pqueue_t *cache_pq_init(apr_ssize_t n,
  76                               cache_pqueue_get_priority pri,
  77                               cache_pqueue_getpos get,
  78                               cache_pqueue_setpos set);
  79 /**
  80  * free all memory used by the queue
  81  * @param q the queue
  82  */
  83 void cache_pq_free(cache_pqueue_t *q);
  84 /**
  85  * return the size of the queue.
  86  * @param q the queue
  87  */
  88 apr_ssize_t cache_pq_size(cache_pqueue_t *q);
  89
  90 /**
  91  * insert an item into the queue.
  92  * @param q the queue
  93  * @param d the item
  94  * @return APR_SUCCESS on success
  95  */
  96 apr_status_t cache_pq_insert(cache_pqueue_t *q, void *d);
  97
  98 /*
  99  * move a existing entry to a different priority
 100  * @param q the queue
 101  * @param old the old priority
 102  * @param d the entry
 103  */
 104 void cache_pq_change_priority(cache_pqueue_t *q,
 105                               long old_priority,
 106                               long new_priority,
 107                               void *d);
 108
 109 /**
 110  * pop the highest-ranking item from the queue.
 111  * @param p the queue
 112  * @param d where to copy the entry to
 113  * @return NULL on error, otherwise the entry
 114  */
 115 void *cache_pq_pop(cache_pqueue_t *q);
 116
 117 /**
 118  * remove an item from the queue.
 119  * @param p the queue
 120  * @param d the entry
 121  * @return APR_SUCCESS on success
 122  */
 123 apr_status_t cache_pq_remove(cache_pqueue_t *q, void *d);
 124
 125 /**
 126  * access highest-ranking item without removing it.
 127  * @param q the queue
 128  * @param d the entry
 129  * @return NULL on error, otherwise the entry
 130  */
 131 void *cache_pq_peek(cache_pqueue_t *q);
 132
 133 /**
 134  * print the queue
 135  * @internal
 136  * DEBUG function only
 137  * @param q the queue
 138  * @param out the output handle
 139  * @param the callback function to print the entry
 140  */
 141 void cache_pq_print(cache_pqueue_t *q,
 142                     FILE *out,
 143                     cache_pqueue_print_entry print);
 144
 145 /**
 146  * dump the queue and it's internal structure
 147  * @internal
 148  * debug function only
 149  * @param q the queue
 150  * @param out the output handle
 151  * @param the callback function to print the entry
 152  */
 153 void cache_pq_dump(cache_pqueue_t *q,
 154                    FILE *out,
 155                    cache_pqueue_print_entry print);
 156
 157 /**
 158  * checks that the pq is in the right order, etc
 159  * @internal
 160  * debug function only
 161  * @param q the queue
 162  */
 163 int cache_pq_is_valid(cache_pqueue_t *q);
 164
 165 #ifdef __cplusplus
 166 }
 167 #endif
 168
 169 #endif /* !CACHE_PQUEUE_H */
 170 /** @} */