modules/cache/cache_pqueue.c

   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 #include "apr_general.h"
  18
  19 #if APR_HAVE_STDLIB_H
  20 #include <stdlib.h>
  21 #endif
  22 #if APR_HAVE_STDIO_H
  23 #include <stdio.h>
  24 #endif
  25
  26 #if APR_HAVE_STRING_H
  27 #include <string.h>
  28 #endif
  29
  30 #include "cache_pqueue.h"
  31 #define left(i) (2*(i))
  32 #define right(i) ((2*(i))+1)
  33 #define parent(i) ((i)/2)
  34 /*
  35  *  Priority queue structure
  36  */
  37 struct cache_pqueue_t
  38 {
  39     apr_ssize_t size;
  40     apr_ssize_t avail;
  41     apr_ssize_t step;
  42     cache_pqueue_get_priority pri;
  43     cache_pqueue_getpos get;
  44     cache_pqueue_setpos set;
  45     void **d;
  46 };
  47
  48 cache_pqueue_t *cache_pq_init(apr_ssize_t n,
  49                               cache_pqueue_get_priority pri,
  50                               cache_pqueue_getpos get,
  51                               cache_pqueue_setpos set)
  52 {
  53     cache_pqueue_t *q;
  54
  55     if (!(q = malloc(sizeof(cache_pqueue_t)))) {
  56         return NULL;
  57     }
  58
  59     /* Need to allocate n+1 elements since element 0 isn't used. */
  60     if (!(q->d = malloc(sizeof(void*) * (n+1)))) {
  61         free(q);
  62         return NULL;
  63     }
  64     q->avail = q->step = (n+1);  /* see comment above about n+1 */
  65     q->pri = pri;
  66     q->size = 1;
  67     q->get = get;
  68     q->set = set;
  69     return q;
  70 }
  71 /*
  72  * cleanup
  73  */
  74 void cache_pq_free(cache_pqueue_t *q)
  75 {
  76     free(q->d);
  77     free(q);
  78 }
  79 /*
  80  * pqsize: size of the queue.
  81  */
  82 apr_ssize_t cache_pq_size(cache_pqueue_t *q)
  83 {
  84     /* queue element 0 exists but doesn't count since it isn't used. */
  85     return (q->size - 1);
  86 }
  87
  88 static void cache_pq_bubble_up(cache_pqueue_t *q, apr_ssize_t i)
  89 {
  90     apr_ssize_t parent_node;
  91     void *moving_node = q->d[i];
  92     long moving_pri = q->pri(moving_node);
  93
  94     for (parent_node = parent(i);
  95          ((i > 1) && (q->pri(q->d[parent_node]) < moving_pri));
  96          i = parent_node, parent_node = parent(i))
  97     {
  98         q->d[i] = q->d[parent_node];
  99         q->set(q->d[i], i);
 100     }
 101
 102     q->d[i] = moving_node;
 103     q->set(moving_node, i);
 104 }
 105
 106 static apr_ssize_t maxchild(cache_pqueue_t *q, apr_ssize_t i)
 107 {
 108     apr_ssize_t child_node = left(i);
 109
 110     if (child_node >= q->size)
 111         return 0;
 112
 113     if ((child_node+1 < q->size) &&
 114         (q->pri(q->d[child_node+1]) > q->pri(q->d[child_node])))
 115     {
 116         child_node++; /* use right child instead of left */
 117     }
 118
 119     return child_node;
 120 }
 121
 122 static void cache_pq_percolate_down(cache_pqueue_t *q, apr_ssize_t i)
 123 {
 124     apr_ssize_t child_node;
 125     void *moving_node = q->d[i];
 126     long moving_pri = q->pri(moving_node);
 127
 128     while ((child_node = maxchild(q, i)) &&
 129            (moving_pri < q->pri(q->d[child_node])))
 130     {
 131         q->d[i] = q->d[child_node];
 132         q->set(q->d[i], i);
 133         i = child_node;
 134     }
 135
 136     q->d[i] = moving_node;
 137     q->set(moving_node, i);
 138 }
 139
 140 apr_status_t cache_pq_insert(cache_pqueue_t *q, void *d)
 141 {
 142     void *tmp;
 143     apr_ssize_t i;
 144     apr_ssize_t newsize;
 145
 146     if (!q) return APR_EGENERAL;
 147
 148     /* allocate more memory if necessary */
 149     if (q->size >= q->avail) {
 150         newsize = q->size + q->step;
 151         if (!(tmp = realloc(q->d, sizeof(void*) * newsize))) {
 152             return APR_EGENERAL;
 153         };
 154         q->d = tmp;
 155         q->avail = newsize;
 156     }
 157
 158     /* insert item */
 159     i = q->size++;
 160     q->d[i] = d;
 161     cache_pq_bubble_up(q, i);
 162     return APR_SUCCESS;
 163 }
 164
 165 /*
 166  * move a existing entry to a new priority
 167  */
 168 void cache_pq_change_priority(cache_pqueue_t *q,
 169                               long old_priority,
 170                               long new_priority,
 171                               void *d)
 172 {
 173     apr_ssize_t posn;
 174
 175     posn = q->get(d);
 176     if (new_priority > old_priority)
 177         cache_pq_bubble_up(q, posn);
 178     else
 179         cache_pq_percolate_down(q, posn);
 180 }
 181
 182 apr_status_t cache_pq_remove(cache_pqueue_t *q, void *d)
 183 {
 184     apr_ssize_t posn = q->get(d);
 185     q->d[posn] = q->d[--q->size];
 186     if (q->pri(q->d[posn]) > q->pri(d))
 187         cache_pq_bubble_up(q, posn);
 188     else
 189         cache_pq_percolate_down(q, posn);
 190
 191     return APR_SUCCESS;
 192 }
 193
 194 void *cache_pq_pop(cache_pqueue_t *q)
 195 {
 196     void *head;
 197
 198     if (!q || q->size == 1)
 199         return NULL;
 200
 201     head = q->d[1];
 202     q->d[1] = q->d[--q->size];
 203     cache_pq_percolate_down(q, 1);
 204
 205     return head;
 206 }
 207
 208 void *cache_pq_peek(cache_pqueue_t *q)
 209 {
 210     void *d;
 211     if (!q || q->size == 1)
 212         return NULL;
 213     d = q->d[1];
 214     return d;
 215 }
 216
 217 static void cache_pq_set_null( void*d, apr_ssize_t val)
 218 {
 219     /* do nothing */
 220 }
 221
 222 /*
 223  * this is a debug function.. so it's EASY not fast
 224  */
 225 void cache_pq_dump(cache_pqueue_t *q,
 226                    FILE*out,
 227                    cache_pqueue_print_entry print)
 228 {
 229     int i;
 230
 231     fprintf(stdout,"posn\tleft\tright\tparent\tmaxchild\t...\n");
 232     for (i = 1; i < q->size ;i++) {
 233         fprintf(stdout,
 234                 "%d\t%d\t%d\t%d\t%" APR_SSIZE_T_FMT "\t",
 235                 i,
 236                 left(i), right(i), parent(i),
 237                 maxchild(q, i));
 238         print(out, q->d[i]);
 239     }
 240 }
 241
 242 /*
 243  * this is a debug function.. so it's EASY not fast
 244  */
 245 void cache_pq_print(cache_pqueue_t *q,
 246                     FILE*out,
 247                     cache_pqueue_print_entry print)
 248 {
 249     cache_pqueue_t *dup;
 250     dup = cache_pq_init(q->size, q->pri, q->get, cache_pq_set_null);
 251     dup->size = q->size;
 252     dup->avail = q->avail;
 253     dup->step = q->step;
 254
 255     memcpy(dup->d, q->d, q->size*sizeof(void*));
 256
 257     while (cache_pq_size(dup) > 1) {
 258         void *e = NULL;
 259         e = cache_pq_pop(dup);
 260         if (e)
 261             print(out, e);
 262         else
 263             break;
 264     }
 265     cache_pq_free(dup);
 266 }
 267
 268 static int cache_pq_subtree_is_valid(cache_pqueue_t *q, int pos)
 269 {
 270     if (left(pos) < q->size) {
 271         /* has a left child */
 272         if (q->pri(q->d[pos]) < q->pri(q->d[left(pos)]))
 273             return 0;
 274         if (!cache_pq_subtree_is_valid(q, left(pos)))
 275             return 0;
 276     }
 277     if (right(pos) < q->size) {
 278         /* has a right child */
 279         if (q->pri(q->d[pos]) < q->pri(q->d[right(pos)]))
 280             return 0;
 281         if (!cache_pq_subtree_is_valid(q, right(pos)))
 282             return 0;
 283     }
 284     return 1;
 285 }
 286
 287 int cache_pq_is_valid(cache_pqueue_t *q)
 288 {
 289     return cache_pq_subtree_is_valid(q, 1);
 290 }