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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include "apr_general.h"
30 #include "cache_pqueue.h"
31 #define left(i) (2*(i))
32 #define right(i) ((2*(i))+1)
33 #define parent(i) ((i)/2)
35 * Priority queue structure
42 cache_pqueue_get_priority pri;
43 cache_pqueue_getpos get;
44 cache_pqueue_setpos set;
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)
55 if (!(q = malloc(sizeof(cache_pqueue_t)))) {
59 /* Need to allocate n+1 elements since element 0 isn't used. */
60 if (!(q->d = malloc(sizeof(void*) * (n+1)))) {
64 q->avail = q->step = (n+1); /* see comment above about n+1 */
74 void cache_pq_free(cache_pqueue_t *q)
80 * pqsize: size of the queue.
82 apr_ssize_t cache_pq_size(cache_pqueue_t *q)
84 /* queue element 0 exists but doesn't count since it isn't used. */
88 static void cache_pq_bubble_up(cache_pqueue_t *q, apr_ssize_t i)
90 apr_ssize_t parent_node;
91 void *moving_node = q->d[i];
92 long moving_pri = q->pri(moving_node);
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))
98 q->d[i] = q->d[parent_node];
102 q->d[i] = moving_node;
103 q->set(moving_node, i);
106 static apr_ssize_t maxchild(cache_pqueue_t *q, apr_ssize_t i)
108 apr_ssize_t child_node = left(i);
110 if (child_node >= q->size)
113 if ((child_node+1 < q->size) &&
114 (q->pri(q->d[child_node+1]) > q->pri(q->d[child_node])))
116 child_node++; /* use right child instead of left */
122 static void cache_pq_percolate_down(cache_pqueue_t *q, apr_ssize_t i)
124 apr_ssize_t child_node;
125 void *moving_node = q->d[i];
126 long moving_pri = q->pri(moving_node);
128 while ((child_node = maxchild(q, i)) &&
129 (moving_pri < q->pri(q->d[child_node])))
131 q->d[i] = q->d[child_node];
136 q->d[i] = moving_node;
137 q->set(moving_node, i);
140 apr_status_t cache_pq_insert(cache_pqueue_t *q, void *d)
146 if (!q) return APR_EGENERAL;
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))) {
161 cache_pq_bubble_up(q, i);
166 * move a existing entry to a new priority
168 void cache_pq_change_priority(cache_pqueue_t *q,
176 if (new_priority > old_priority)
177 cache_pq_bubble_up(q, posn);
179 cache_pq_percolate_down(q, posn);
182 apr_status_t cache_pq_remove(cache_pqueue_t *q, void *d)
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);
189 cache_pq_percolate_down(q, posn);
194 void *cache_pq_pop(cache_pqueue_t *q)
198 if (!q || q->size == 1)
202 q->d[1] = q->d[--q->size];
203 cache_pq_percolate_down(q, 1);
208 void *cache_pq_peek(cache_pqueue_t *q)
211 if (!q || q->size == 1)
217 static void cache_pq_set_null( void*d, apr_ssize_t val)
223 * this is a debug function.. so it's EASY not fast
225 void cache_pq_dump(cache_pqueue_t *q,
227 cache_pqueue_print_entry print)
231 fprintf(stdout,"posn\tleft\tright\tparent\tmaxchild\t...\n");
232 for (i = 1; i < q->size ;i++) {
234 "%d\t%d\t%d\t%d\t%" APR_SSIZE_T_FMT "\t",
236 left(i), right(i), parent(i),
243 * this is a debug function.. so it's EASY not fast
245 void cache_pq_print(cache_pqueue_t *q,
247 cache_pqueue_print_entry print)
250 dup = cache_pq_init(q->size, q->pri, q->get, cache_pq_set_null);
252 dup->avail = q->avail;
255 memcpy(dup->d, q->d, q->size*sizeof(void*));
257 while (cache_pq_size(dup) > 1) {
259 e = cache_pq_pop(dup);
268 static int cache_pq_subtree_is_valid(cache_pqueue_t *q, int pos)
270 if (left(pos) < q->size) {
271 /* has a left child */
272 if (q->pri(q->d[pos]) < q->pri(q->d[left(pos)]))
274 if (!cache_pq_subtree_is_valid(q, left(pos)))
277 if (right(pos) < q->size) {
278 /* has a right child */
279 if (q->pri(q->d[pos]) < q->pri(q->d[right(pos)]))
281 if (!cache_pq_subtree_is_valid(q, right(pos)))
287 int cache_pq_is_valid(cache_pqueue_t *q)
289 return cache_pq_subtree_is_valid(q, 1);