1 files changed, 290 insertions, 0 deletions

diff --git a/rubbos/app/httpd-2.0.64/modules/experimental/cache_pqueue.c b/rubbos/app/httpd-2.0.64/modules/experimental/cache_pqueue.c
new file mode 100644
index 00000000..580b47e7
--- /dev/null
+++ b/rubbos/app/httpd-2.0.64/modules/experimental/cache_pqueue.c
@@ -0,0 +1,290 @@
+/* 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
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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"
+
+#if APR_HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+#if APR_HAVE_STDIO_H
+#include <stdio.h>
+#endif
+
+#if APR_HAVE_STRING_H
+#include <string.h>
+#endif
+
+#include "cache_pqueue.h"
+#define left(i) (2*(i))
+#define right(i) ((2*(i))+1)
+#define parent(i) ((i)/2)
+/*
+ *  Priority queue structure
+ */
+struct cache_pqueue_t
+{
+    apr_ssize_t size;
+    apr_ssize_t avail;
+    apr_ssize_t step;
+    cache_pqueue_get_priority pri;
+    cache_pqueue_getpos get;
+    cache_pqueue_setpos set;
+    void **d;
+};
+
+cache_pqueue_t *cache_pq_init(apr_ssize_t n,
+                              cache_pqueue_get_priority pri,
+                              cache_pqueue_getpos get,
+                              cache_pqueue_setpos set)
+{
+    cache_pqueue_t *q;
+
+    if (!(q = malloc(sizeof(cache_pqueue_t)))) {
+        return NULL;
+    }
+
+    /* Need to allocate n+1 elements since element 0 isn't used. */
+    if (!(q->d = malloc(sizeof(void*) * (n+1)))) {
+        free(q);
+        return NULL;
+    }
+    q->avail = q->step = (n+1);  /* see comment above about n+1 */
+    q->pri = pri;
+    q->size = 1;
+    q->get = get;
+    q->set = set;
+    return q;
+}
+/*
+ * cleanup
+ */
+void cache_pq_free(cache_pqueue_t *q)
+{
+    free(q->d);
+    free(q);
+}
+/*
+ * pqsize: size of the queue.
+ */
+apr_ssize_t cache_pq_size(cache_pqueue_t *q)
+{
+    /* queue element 0 exists but doesn't count since it isn't used. */
+    return (q->size - 1);
+}
+
+static void cache_pq_bubble_up(cache_pqueue_t *q, apr_ssize_t i)
+{
+    apr_ssize_t parent_node;
+    void *moving_node = q->d[i];
+    long moving_pri = q->pri(moving_node);
+
+    for (parent_node = parent(i);
+         ((i > 1) && (q->pri(q->d[parent_node]) < moving_pri));
+         i = parent_node, 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);
+}
+
+static apr_ssize_t maxchild(cache_pqueue_t *q, apr_ssize_t i)
+{
+    apr_ssize_t child_node = left(i);
+
+    if (child_node >= q->size)
+        return 0;
+
+    if ((child_node+1 < q->size) &&
+        (q->pri(q->d[child_node+1]) > q->pri(q->d[child_node])))
+    {
+        child_node++; /* use right child instead of left */
+    }
+
+    return child_node;
+}
+
+static void cache_pq_percolate_down(cache_pqueue_t *q, apr_ssize_t i)
+{
+    apr_ssize_t child_node;
+    void *moving_node = q->d[i];
+    long moving_pri = q->pri(moving_node);
+
+    while ((child_node = maxchild(q, i)) &&
+           (moving_pri < q->pri(q->d[child_node])))
+    {
+        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);
+}
+
+apr_status_t cache_pq_insert(cache_pqueue_t *q, void *d)
+{
+    void *tmp;
+    apr_ssize_t i;
+    apr_ssize_t newsize;
+
+    if (!q) return APR_EGENERAL;
+
+    /* allocate more memory if necessary */
+    if (q->size >= q->avail) {
+        newsize = q->size + q->step;
+        if (!(tmp = realloc(q->d, sizeof(void*) * newsize))) {
+            return APR_EGENERAL;
+        };
+        q->d = tmp;
+        q->avail = newsize;
+    }
+
+    /* 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)
+{
+    apr_ssize_t posn;
+
+    posn = q->get(d);
+    if (new_priority > old_priority)
+        cache_pq_bubble_up(q, posn);
+    else
+        cache_pq_percolate_down(q, posn);
+}
+
+apr_status_t cache_pq_remove(cache_pqueue_t *q, void *d)
+{
+    apr_ssize_t posn = q->get(d);
+    q->d[posn] = q->d[--q->size];
+    if (q->pri(q->d[posn]) > q->pri(d))
+        cache_pq_bubble_up(q, posn);
+    else
+        cache_pq_percolate_down(q, posn);
+
+    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;
+}
+
+static void cache_pq_set_null( void*d, apr_ssize_t val)
+{
+    /* do nothing */
+}
+
+/*
+ * this is a debug function.. so it's EASY not fast
+ */
+void cache_pq_dump(cache_pqueue_t *q,
+                   FILE*out,
+                   cache_pqueue_print_entry print)
+{
+    int i;
+
+    fprintf(stdout,"posn\tleft\tright\tparent\tmaxchild\t...\n");
+    for (i = 1; i < q->size ;i++) {
+        fprintf(stdout,
+                "%d\t%d\t%d\t%d\t%" APR_SSIZE_T_FMT "\t",
+                i,
+                left(i), right(i), parent(i),
+                maxchild(q, i));
+        print(out, q->d[i]);
+    }
+}
+
+/*
+ * this is a debug function.. so it's EASY not fast
+ */
+void cache_pq_print(cache_pqueue_t *q,
+                    FILE*out,
+                    cache_pqueue_print_entry print)
+{
+    cache_pqueue_t *dup;
+    dup = cache_pq_init(q->size, q->pri, q->get, cache_pq_set_null);
+    dup->size = q->size;
+    dup->avail = q->avail;
+    dup->step = q->step;
+
+    memcpy(dup->d, q->d, q->size*sizeof(void*));
+
+    while (cache_pq_size(dup) > 1) {
+        void *e = NULL;
+        e = cache_pq_pop(dup);
+        if (e)
+            print(out, e);
+        else
+            break;
+    }
+    cache_pq_free(dup);
+}
+
+static int cache_pq_subtree_is_valid(cache_pqueue_t *q, int pos)
+{
+    if (left(pos) < q->size) {
+        /* has a left child */
+        if (q->pri(q->d[pos]) < q->pri(q->d[left(pos)]))
+            return 0;
+        if (!cache_pq_subtree_is_valid(q, left(pos)))
+            return 0;
+    }
+    if (right(pos) < q->size) {
+        /* has a right child */
+        if (q->pri(q->d[pos]) < q->pri(q->d[right(pos)]))
+            return 0;
+        if (!cache_pq_subtree_is_valid(q, right(pos)))
+            return 0;
+    }
+    return 1;
+}
+
+int cache_pq_is_valid(cache_pqueue_t *q)
+{
+    return cache_pq_subtree_is_valid(q, 1);
+}