You are viewing a plain text version of this content. The canonical link for it is here.
Posted to cvs@httpd.apache.org by ia...@apache.org on 2002/06/06 21:07:10 UTC
cvs commit: httpd-2.0/modules/experimental cache_cache.c cache_cache.h cache_pqueue.c cache_pqueue.h mod_mem_cache.c config.m4 mod_cache.imp
ianh 2002/06/06 12:07:10
Modified: . CHANGES
modules/experimental mod_mem_cache.c config.m4 mod_cache.imp
Added: modules/experimental cache_cache.c cache_cache.h
cache_pqueue.c cache_pqueue.h
Log:
implement a fixed size cache in mod_mem_cache using a priority queue
Revision Changes Path
1.814 +3 -0 httpd-2.0/CHANGES
Index: CHANGES
===================================================================
RCS file: /home/cvs/httpd-2.0/CHANGES,v
retrieving revision 1.813
retrieving revision 1.814
diff -u -r1.813 -r1.814
--- CHANGES 6 Jun 2002 18:16:07 -0000 1.813
+++ CHANGES 6 Jun 2002 19:07:08 -0000 1.814
@@ -1,5 +1,8 @@
Changes with Apache 2.0.37
+ *) Implement a fixed size memory cache using a priority queue
+ [Ian Holsman]
+
*) Fix apxs to allow "apxs -q installbuilddir" and to allow
querying certain other variables from config_vars.mk. PR 9316
[Jeff Trawick]
1.68 +190 -42 httpd-2.0/modules/experimental/mod_mem_cache.c
Index: mod_mem_cache.c
===================================================================
RCS file: /home/cvs/httpd-2.0/modules/experimental/mod_mem_cache.c,v
retrieving revision 1.67
retrieving revision 1.68
diff -u -r1.67 -r1.68
--- mod_mem_cache.c 5 Jun 2002 21:47:58 -0000 1.67
+++ mod_mem_cache.c 6 Jun 2002 19:07:09 -0000 1.68
@@ -58,7 +58,8 @@
#define CORE_PRIVATE
#include "mod_cache.h"
-#include "cache_hash.h"
+#include "cache_pqueue.h"
+#include "cache_cache.h"
#include "ap_mpm.h"
#include "apr_thread_mutex.h"
#if APR_HAVE_UNISTD_H
@@ -95,11 +96,14 @@
apr_size_t m_len;
void *m;
apr_os_file_t fd;
+ long priority; /**< the priority of this entry */
+ long total_refs; /**< total number of references this entry has had */
+ apr_ssize_t pos; /**< the position of this entry in the cache */
} mem_cache_object_t;
typedef struct {
apr_thread_mutex_t *lock;
- cache_hash_t *cacheht;
+ cache_cache_t *cache_cache;
apr_size_t cache_size;
apr_size_t object_cnt;
@@ -108,6 +112,7 @@
apr_size_t max_cache_object_size; /* in bytes */
apr_size_t max_cache_size; /* in bytes */
apr_size_t max_object_cnt;
+ cache_pqueue_set_priority *cache_remove_algorithm;
} mem_cache_conf;
static mem_cache_conf *sconf;
@@ -125,6 +130,102 @@
static apr_status_t read_headers(cache_handle_t *h, request_rec *r);
static apr_status_t read_body(cache_handle_t *h, apr_pool_t *p, apr_bucket_brigade *bb);
+static void cleanup_cache_object(cache_object_t *obj);
+
+static long memcache_get_priority(void*a)
+{
+ cache_object_t *obj = (cache_object_t *)a;
+ mem_cache_object_t *mobj = obj->vobj;
+
+#ifdef USE_ATOMICS
+ return (long)apr_atomic_read(&mobj->priority);
+#else
+ return mobj->priority;
+#endif
+
+}
+
+static void memcache_inc_frequency(void*a)
+{
+ cache_object_t *obj = (cache_object_t *)a;
+ mem_cache_object_t *mobj = obj->vobj;
+
+ mobj->total_refs++;
+ mobj->priority = 0;
+}
+
+static void memcache_set_pos(void *a, apr_ssize_t pos)
+{
+ cache_object_t *obj = (cache_object_t *)a;
+ mem_cache_object_t *mobj = obj->vobj;
+
+#ifdef USE_ATOMICS
+ apr_atomic_set(&mobj->pos, pos);
+#else
+ mobj->pos = pos;
+#endif
+}
+static apr_ssize_t memcache_get_pos(void *a)
+{
+ cache_object_t *obj = (cache_object_t *)a;
+ mem_cache_object_t *mobj = obj->vobj;
+
+#ifdef USE_ATOMICS
+ return apr_atomic_read(&mobj->pos);
+#else
+ return mobj->pos;
+#endif
+}
+
+static apr_size_t memcache_cache_get_size(void*a)
+{
+ cache_object_t *obj = (cache_object_t *)a;
+ mem_cache_object_t *mobj = obj->vobj;
+ return mobj->m_len;
+}
+/** callback to get the key of a item */
+static const char* memcache_cache_get_key(void*a)
+{
+ cache_object_t *obj = (cache_object_t *)a;
+ return obj->key;
+}
+/**
+ * callback to free an entry
+ * XXX: just call cleanup_cache_object ?
+ */
+static void memcache_cache_free(void*a)
+{
+ cache_object_t *obj = (cache_object_t *)a;
+ cleanup_cache_object(obj);
+}
+/*
+ * functions return a 'negative' score as lower is better in a priority Q
+ */
+static long memcache_lru_algorithm(long queue_clock, void *a)
+{
+ cache_object_t *obj = (cache_object_t *)a;
+ mem_cache_object_t *mobj = obj->vobj;
+ if (mobj->priority == 0)
+ mobj->priority = ((long)(queue_clock + mobj->total_refs));
+
+ /*
+ * a 'proper' LRU function would just be
+ * mobj->priority = mobj->total_refs;
+ */
+ return -1*mobj->priority;
+}
+
+static long memcache_gdsf_algorithm(long queue_clock, void *a)
+{
+ cache_object_t *obj = (cache_object_t *)a;
+ mem_cache_object_t *mobj = obj->vobj;
+
+ if (mobj->priority == 0)
+ mobj->priority = queue_clock + (long)(mobj->total_refs*1000 / mobj->m_len);
+
+ return -1*mobj->priority;
+}
+
static void cleanup_cache_object(cache_object_t *obj)
{
mem_cache_object_t *mobj = obj->vobj;
@@ -188,7 +289,6 @@
}
free(mobj);
}
- return;
}
static apr_status_t decrement_refcount(void *arg)
{
@@ -207,7 +307,7 @@
* removed the object from the cache (and set obj->cleanup)
*/
if (!obj->cleanup) {
- cache_hash_set(sconf->cacheht, obj->key, strlen(obj->key), NULL);
+ cache_remove(sconf->cache_cache, obj);
sconf->object_cnt--;
sconf->cache_size -= mobj->m_len;
obj->cleanup = 1;
@@ -244,39 +344,37 @@
static apr_status_t cleanup_cache_mem(void *sconfv)
{
cache_object_t *obj;
- cache_hash_index_t *hi;
mem_cache_conf *co = (mem_cache_conf*) sconfv;
if (!co) {
return APR_SUCCESS;
}
+ if (!co->cache_cache) {
+ return APR_SUCCESS;
+ }
if (sconf->lock) {
apr_thread_mutex_lock(sconf->lock);
}
- /* Iterate over the cache and clean up each entry */
- while ((hi = cache_hash_first(co->cacheht)) != NULL) {
- /* Fetch the object from the cache */
- cache_hash_this(hi, NULL, NULL, (void **)&obj);
- if (obj) {
- /* Remove the object from the cache */
- cache_hash_set(sconf->cacheht, obj->key, strlen(obj->key), NULL);
- /* Free the object if the recount == 0 */
+ obj = cache_pop(co->cache_cache);
+ while (obj) {
+ /* Iterate over the cache and clean up each entry */
+ /* Free the object if the recount == 0 */
#ifdef USE_ATOMICS
- apr_atomic_inc(&obj->refcount);
- obj->cleanup = 1;
- if (!apr_atomic_dec(&obj->refcount)) {
+ apr_atomic_inc(&obj->refcount);
+ obj->cleanup = 1;
+ if (!apr_atomic_dec(&obj->refcount)) {
#else
- obj->cleanup = 1;
- if (!obj->refcount) {
+ obj->cleanup = 1;
+ if (!obj->refcount) {
#endif
- cleanup_cache_object(obj);
- }
+ cleanup_cache_object(obj);
}
+ obj = cache_pop(co->cache_cache);
}
/* Cache is empty, free the cache table */
- cache_hash_free(co->cacheht);
+ cache_free(co->cache_cache);
if (sconf->lock) {
apr_thread_mutex_unlock(sconf->lock);
@@ -298,6 +396,8 @@
/* Size of the cache in bytes */
sconf->max_cache_size = DEFAULT_MAX_CACHE_SIZE;
sconf->cache_size = 0;
+ sconf->cache_cache = NULL;
+ sconf->cache_remove_algorithm = memcache_gdsf_algorithm;
return sconf;
}
@@ -325,19 +425,27 @@
* TODO: Get smarter about managing the cache size. If the cache is
* full, we need to garbage collect stale/infrequently referenced
* objects.
- */
+ * we have a self-sizing cache now
if (sconf->object_cnt >= sconf->max_object_cnt) {
return DECLINED;
}
+ */
if (type_e == CACHE_TYPE_HEAP) {
/* We can safely ignore these measures when caching open fds */
if (len < sconf->min_cache_object_size ||
len > sconf->max_cache_object_size) {
+ ap_log_error(APLOG_MARK, APLOG_DEBUG, 0, r->server,
+ "cache_mem: URL %s failed the size check, "
+ "or is incomplete",
+ key);
return DECLINED;
}
+ /*
+ * not needed now we have a self-sizing cache.
if ((sconf->cache_size + len) > sconf->max_cache_size) {
return DECLINED;
}
+ */
} else {
/* CACHE_TYPE_FILE is only valid for local content
* handled by the default handler?
@@ -361,6 +469,7 @@
strncpy(obj->key, key, strlen(key) + 1);
obj->info.len = len;
+
/* Allocate and init mem_cache_object_t */
mobj = calloc(1, sizeof(*mobj));
if (!mobj) {
@@ -374,6 +483,7 @@
#else
obj->refcount = 1;
#endif
+ mobj->total_refs = 1;
obj->complete = 0;
obj->cleanup = 0;
obj->vobj = mobj;
@@ -395,11 +505,10 @@
if (sconf->lock) {
apr_thread_mutex_lock(sconf->lock);
}
- tmp_obj = (cache_object_t *) cache_hash_get(sconf->cacheht,
- key,
- CACHE_HASH_KEY_STRING);
+ tmp_obj = (cache_object_t *) cache_find(sconf->cache_cache, key);
+
if (!tmp_obj) {
- cache_hash_set(sconf->cacheht, obj->key, strlen(obj->key), obj);
+ cache_insert(sconf->cache_cache, obj);
sconf->object_cnt++;
sconf->cache_size += len;
}
@@ -441,17 +550,18 @@
if (sconf->lock) {
apr_thread_mutex_lock(sconf->lock);
}
- obj = (cache_object_t *) cache_hash_get(sconf->cacheht, key,
- CACHE_HASH_KEY_STRING);
+ obj = (cache_object_t *) cache_find(sconf->cache_cache, key);
if (obj) {
if (obj->complete) {
request_rec *rmain=r, *rtmp;
-
#ifdef USE_ATOMICS
apr_atomic_inc(&obj->refcount);
#else
obj->refcount++;
#endif
+ /* cache is worried about overall counts, not 'open' ones */
+ cache_update(sconf->cache_cache, obj);
+
/* If this is a subrequest, register the cleanup against
* the main request. This will prevent the cache object
* from being cleaned up from under the request after the
@@ -504,7 +614,7 @@
*/
if (!obj->cleanup) {
mem_cache_object_t *mobj = (mem_cache_object_t *) obj->vobj;
- cache_hash_set(sconf->cacheht, obj->key, strlen(obj->key), NULL);
+ cache_remove(sconf->cache_cache, obj);
sconf->object_cnt--;
sconf->cache_size -= mobj->m_len;
obj->cleanup = 1;
@@ -594,11 +704,12 @@
if (sconf->lock) {
apr_thread_mutex_lock(sconf->lock);
}
- /* This call will return a pointer to the cache_object just removed */
- obj = cache_hash_set(sconf->cacheht, key, CACHE_HASH_KEY_STRING, NULL);
+
+ obj = cache_find(sconf->cache_cache, key);
if (obj) {
- /* obj has been removed from the cache */
- mem_cache_object_t *mobj = (mem_cache_object_t *) obj->vobj;
+ mem_cache_object_t *mobj;
+ cache_remove(sconf->cache_cache, obj);
+ mobj = (mem_cache_object_t *) obj->vobj;
sconf->object_cnt--;
sconf->cache_size -= mobj->m_len;
@@ -635,11 +746,13 @@
int rc;
mem_cache_object_t *mobj = (mem_cache_object_t*) h->cache_obj->vobj;
cache_info *info = &(h->cache_obj->info);
-
+
info->req_hdrs = apr_table_make(r->pool, mobj->num_req_hdrs);
- r->headers_out = apr_table_make(r->pool,mobj->num_header_out);
+
+ r->headers_out = apr_table_make(r->pool, mobj->num_header_out);
r->subprocess_env = apr_table_make(r->pool, mobj->num_subprocess_env);
r->notes = apr_table_make(r->pool, mobj->num_notes);
+
rc = unserialize_table(mobj->req_hdrs,
mobj->num_req_hdrs,
info->req_hdrs);
@@ -689,7 +802,7 @@
cache_object_t *obj = h->cache_obj;
mem_cache_object_t *mobj = (mem_cache_object_t*) obj->vobj;
int rc;
-
+
/*
* The cache needs to keep track of the following information:
* - Date, LastMod, Version, ReqTime, RespTime, ContentLength
@@ -703,6 +816,8 @@
if (rc != APR_SUCCESS) {
return rc;
}
+
+ /* Precompute how much storage we need to hold the headers */
rc = serialize_table(&mobj->header_out,
&mobj->num_header_out,
r->headers_out);
@@ -861,7 +976,7 @@
/* This should not happen, but if it does, we are in BIG trouble
* cause we just stomped all over the heap.
*/
- AP_DEBUG_ASSERT(obj->count > mobj->m_len);
+ AP_DEBUG_ASSERT(obj->count >= mobj->m_len);
}
return APR_SUCCESS;
}
@@ -876,12 +991,26 @@
if (threaded_mpm) {
apr_thread_mutex_create(&sconf->lock, APR_THREAD_MUTEX_DEFAULT, p);
}
- sconf->cacheht = cache_hash_make(sconf->max_object_cnt);
+
+ sconf->cache_cache = cache_init(sconf->max_object_cnt,
+ sconf->max_cache_size,
+ memcache_get_priority,
+ sconf->cache_remove_algorithm,
+ memcache_get_pos,
+ memcache_set_pos,
+ memcache_inc_frequency,
+ memcache_cache_get_size,
+ memcache_cache_get_key,
+ memcache_cache_free);
apr_pool_cleanup_register(p, sconf, cleanup_cache_mem, apr_pool_cleanup_null);
- return OK;
-}
+ if (sconf->cache_cache)
+ return OK;
+ return -1;
+
+}
+
static const char
*set_max_cache_size(cmd_parms *parms, void *in_struct_ptr, const char *arg)
{
@@ -927,6 +1056,23 @@
return NULL;
}
+static const char
+*set_cache_removal_algorithm(cmd_parms *parms, void *name, const char *arg)
+{
+ if (strcasecmp("LRU", arg)) {
+ sconf->cache_remove_algorithm = memcache_lru_algorithm;
+ }
+ else {
+ if (strcasecmp("GDSF", arg)) {
+ sconf->cache_remove_algorithm = memcache_gdsf_algorithm;
+ }
+ else {
+ return "currently implemented algorithms are LRU and GDSF";
+ }
+ }
+ return NULL;
+}
+
static const command_rec cache_cmds[] =
{
AP_INIT_TAKE1("MCacheSize", set_max_cache_size, NULL, RSRC_CONF,
@@ -937,6 +1083,8 @@
"The minimum size (in bytes) of an object to be placed in the cache"),
AP_INIT_TAKE1("MCacheMaxObjectSize", set_max_cache_object_size, NULL, RSRC_CONF,
"The maximum size (in bytes) of an object to be placed in the cache"),
+ AP_INIT_TAKE1("MCacheRemovalAlgorithm", set_cache_removal_algorithm, NULL, RSRC_CONF,
+ "The algorithm used to remove entries from the cache (default: GDSF)"),
{NULL}
};
@@ -944,7 +1092,7 @@
{
ap_hook_post_config(mem_cache_post_config, NULL, NULL, APR_HOOK_MIDDLE);
/* cache initializer */
- /* cache_hook_cache_init(cache_init, NULL, NULL, AP_HOOK_FIRST); */
+ /* cache_hook_init(cache_mem_init, NULL, NULL, APR_HOOK_MIDDLE); */
cache_hook_create_entity(create_entity, NULL, NULL, APR_HOOK_MIDDLE);
cache_hook_open_entity(open_entity, NULL, NULL, APR_HOOK_MIDDLE);
cache_hook_remove_url(remove_url, NULL, NULL, APR_HOOK_MIDDLE);
1.22 +2 -0 httpd-2.0/modules/experimental/config.m4
Index: config.m4
===================================================================
RCS file: /home/cvs/httpd-2.0/modules/experimental/config.m4,v
retrieving revision 1.21
retrieving revision 1.22
diff -u -r1.21 -r1.22
--- config.m4 6 May 2002 22:23:52 -0000 1.21
+++ config.m4 6 Jun 2002 19:07:09 -0000 1.22
@@ -18,6 +18,8 @@
dnl # list of object files for mod_mem_cache
mem_cache_objs="dnl
mod_mem_cache.lo dnl
+cache_cache.lo dnl
+cache_pqueue.lo dnl
cache_hash.lo dnl
"
APACHE_MODULE(cache, dynamic file caching, $cache_objs, , no)
1.3 +21 -21 httpd-2.0/modules/experimental/mod_cache.imp
Index: mod_cache.imp
===================================================================
RCS file: /home/cvs/httpd-2.0/modules/experimental/mod_cache.imp,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- mod_cache.imp 24 May 2002 15:34:53 -0000 1.2
+++ mod_cache.imp 6 Jun 2002 19:07:09 -0000 1.3
@@ -1,21 +1,21 @@
- (MODCACHE)
- ap_cache_request_is_conditional,
- ap_cache_reset_output_filters,
- ap_cache_get_cachetype,
- ap_cache_liststr,
- ap_cache_tokstr,
- ap_cache_hex2usec,
- ap_cache_usec2hex,
- generate_name,
- cache_hook_create_entity,
- cache_hook_open_entity,
- cache_hook_remove_url,
- cache_hash_set,
- cache_hash_this,
- cache_hash_first,
- cache_hash_make,
- cache_hash_get,
- cache_hash_next,
- cache_hash_count,
- cache_hash_free,
-
+ (MODCACHE)
+ ap_cache_request_is_conditional,
+ ap_cache_reset_output_filters,
+ ap_cache_get_cachetype,
+ ap_cache_liststr,
+ ap_cache_tokstr,
+ ap_cache_hex2usec,
+ ap_cache_usec2hex,
+ generate_name,
+ cache_hook_create_entity,
+ cache_hook_open_entity,
+ cache_hook_remove_url,
+ cache_hash_set,
+ cache_hash_this,
+ cache_hash_first,
+ cache_hash_make,
+ cache_hash_get,
+ cache_hash_next,
+ cache_hash_count,
+ cache_hash_free,
+
1.1 httpd-2.0/modules/experimental/cache_cache.c
Index: cache_cache.c
===================================================================
/* cache.c */
#include "apr_general.h"
#include "mod_cache.h"
#include "cache_hash.h"
#include "cache_pqueue.h"
#include "cache_cache.h"
#if APR_HAVE_STDLIB_H
#include <stdlib.h>
#endif
#if APR_HAVE_STRING_H
#include <string.h>
#endif
struct cache_cache_t {
int max_entries;
apr_size_t max_size;
apr_size_t current_size;
int total_purges;
long queue_clock;
cache_hash_t *ht;
cache_pqueue_t *pq;
cache_pqueue_set_priority* set_pri;
cache_pqueue_get_priority* get_pri;
cache_cache_inc_frequency *inc_entry;
cache_cache_get_size *size_entry;
cache_cache_get_key *key_entry;
cache_cache_free *free_entry;
};
CACHE_DECLARE(cache_cache_t *)cache_init(int max_entries,
apr_size_t max_size,
cache_pqueue_get_priority *get_pri,
cache_pqueue_set_priority *set_pri,
cache_pqueue_getpos get_pos,
cache_pqueue_setpos set_pos,
cache_cache_inc_frequency *inc_entry,
cache_cache_get_size *size_entry,
cache_cache_get_key* key_entry,
cache_cache_free *free_entry)
{
cache_cache_t *tmp;
tmp = malloc(sizeof(cache_cache_t));
tmp->max_entries = max_entries;
tmp->max_size = max_size;
tmp->current_size = 0;
tmp->total_purges = 0;
tmp->queue_clock = 0;
tmp->get_pri = get_pri;
tmp->set_pri = set_pri;
tmp->inc_entry = inc_entry;
tmp->size_entry = size_entry;
tmp->key_entry = key_entry;
tmp->free_entry = free_entry;
tmp->ht = cache_hash_make(max_entries);
tmp->pq = cache_pq_init(max_entries, get_pri, get_pos, set_pos);
return tmp;
}
CACHE_DECLARE(void) cache_free(cache_cache_t *c)
{
cache_pq_free(c->pq);
cache_hash_free(c->ht);
free(c);
}
CACHE_DECLARE(void*) cache_find(cache_cache_t* c, const char *key)
{
void *e;
e = cache_hash_get(c->ht, key, CACHE_HASH_KEY_STRING);
if (!e)
return NULL;
return e;
}
CACHE_DECLARE(void) cache_update(cache_cache_t* c, void *entry)
{
long old_priority;
long new_priority;
old_priority = c->set_pri(c->queue_clock, entry);
c->inc_entry(entry);
new_priority = c->set_pri(c->queue_clock, entry);
cache_pq_change_priority(c->pq, old_priority, new_priority, entry);
}
CACHE_DECLARE(void) cache_insert(cache_cache_t* c, void *entry)
{
void *ejected = NULL;
long priority;
c->set_pri(c->queue_clock, entry);
/* FIX: check if priority of bottom item is greater than inserted one */
while ((cache_pq_size(c->pq) >= c->max_entries) ||
((c->current_size + c->size_entry(entry)) > c->max_size)) {
ejected = cache_pq_pop(c->pq);
priority = c->get_pri(ejected);
if (c->queue_clock < priority)
c->queue_clock = priority;
cache_hash_set(c->ht,
c->key_entry(ejected),
CACHE_HASH_KEY_STRING,
NULL);
ap_log_error(APLOG_MARK, APLOG_DEBUG, 0, NULL, "Cache Purge of %s",c->key_entry(ejected));
c->current_size -= c->size_entry(ejected);
c->free_entry(ejected);
c->total_purges++;
}
c->current_size += c->size_entry(entry);
cache_pq_insert(c->pq, entry);
cache_hash_set(c->ht, c->key_entry(entry), CACHE_HASH_KEY_STRING, entry);
}
CACHE_DECLARE(void *) cache_pop(cache_cache_t *c)
{
void *entry;
if (!c)
return NULL;
entry = cache_pq_pop(c->pq);
if (!entry)
return NULL;
c->current_size -= c->size_entry(entry);
cache_hash_set(c->ht, c->key_entry(entry), CACHE_HASH_KEY_STRING, NULL);
return entry;
}
CACHE_DECLARE(apr_status_t) cache_remove(cache_cache_t *c, void *entry)
{
apr_size_t entry_size = c->size_entry(entry);
apr_status_t rc;
rc = cache_pq_remove(c->pq, entry);
if (rc != APR_SUCCESS)
return rc;
cache_hash_set(c->ht, c->key_entry(entry), CACHE_HASH_KEY_STRING, NULL);
c->current_size -= entry_size;
return APR_SUCCESS;
}
1.1 httpd-2.0/modules/experimental/cache_cache.h
Index: cache_cache.h
===================================================================
/* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2000-2002 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Apache" and "Apache Software Foundation" must
* not be used to endorse or promote products derived from this
* software without prior written permission. For written
* permission, please contact apache@apache.org.
*
* 5. Products derived from this software may not be called "Apache",
* nor may "Apache" appear in their name, without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*
* Portions of this software are based upon public domain software
* originally written at the National Center for Supercomputing Applications,
* University of Illinois, Urbana-Champaign.
*/
#ifndef CACHE_CACHE_H
#define CACHE_CACHE_H
#ifdef __cplusplus
extern "C" {
#endif
#include "mod_cache.h"
/**
* @file cache_hash.h
* @brief Cache Cache Functions
*/
/**
* @defgroup Cache_cache Cache Functions
* @ingroup CACHE
* @{
*/
/** ADT for the cache */
typedef struct cache_cache_t cache_cache_t;
/** callback to increment the frequency of a item */
typedef void cache_cache_inc_frequency(void*a);
/** callback to get the size of a item */
typedef apr_size_t cache_cache_get_size(void*a);
/** callback to get the key of a item */
typedef const char* cache_cache_get_key(void *a);
/** callback to free an entry */
typedef void cache_cache_free(void *a);
/**
* initialize the cache ADT
* @param max_entries the number of entries in the cache
* @param max_size the size of the cache
* @param get_pri callback to get a priority of a entry
* @param set_pri callback to set a priority of a entry
* @param get_pos callback to get the position of a entry in the cache
* @param set_pos callback to set the position of a entry in the cache
* @param inc_entry callback to increment the frequency of a entry
* @param size_entry callback to get the size of a entry
* @param key_entry callback to get the key of a entry
* @param free_entry callback to free an entry
*/
CACHE_DECLARE(cache_cache_t *)cache_init(int max_entries,
apr_size_t max_size,
cache_pqueue_get_priority *get_pri,
cache_pqueue_set_priority *set_pri,
cache_pqueue_getpos get_pos,
cache_pqueue_setpos set_pos,
cache_cache_inc_frequency *inc_entry,
cache_cache_get_size *size_entry,
cache_cache_get_key *key_entry,
cache_cache_free *free_entry);
/**
* free up the cache
* @param c the cache
*/
CACHE_DECLARE(void) cache_free(cache_cache_t *c);
/**
* find a entry in the cache, incrementing the frequency if found
* @param c the cache
* @param key the key
*/
CACHE_DECLARE(void*) cache_find(cache_cache_t* c, const char *key);
/**
* insert a entry into the cache
* @param c the cache
* @param entry the entry
*/
CACHE_DECLARE(void) cache_update(cache_cache_t* c, void *entry);
/**
* insert a entry into the cache
* @param c the cache
* @param entry the entry
*/
CACHE_DECLARE(void) cache_insert(cache_cache_t* c, void *entry);
/**
* pop the lowest priority item off
* @param c the cache
* @returns the entry or NULL
*/
CACHE_DECLARE(void *)cache_pop(cache_cache_t* c);
/**
* remove an item from the cache
* @param c the cache
* @param entry the actual entry (from a find)
*/
CACHE_DECLARE(apr_status_t) cache_remove(cache_cache_t* c, void *entry);
/** @} */
#ifdef __cplusplus
}
#endif
#endif /* !CACHE_CACHE_H */
1.1 httpd-2.0/modules/experimental/cache_pqueue.c
Index: cache_pqueue.c
===================================================================
#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;
}
if (!(q->d = malloc(sizeof(void*) * n))) {
free(q);
return NULL;
}
q->avail = q->step = n;
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)
{
return q->size;
}
static void cache_pq_bubble_up(cache_pqueue_t*q, apr_ssize_t i)
{
apr_ssize_t parent_node;
parent_node = parent(i);
while (i > 1 && q->pri(q->d[parent_node]) < q->pri(q->d[i])) {
void *tmp;
tmp = q->d[i];
q->d[i] = q->d[parent_node];
q->d[parent_node] = tmp;
q->set(q->d[i], i);
q->set(q->d[parent_node], parent_node);
i = parent_node;
parent_node = parent(i);
}
}
static apr_ssize_t minchild(cache_pqueue_t *q, apr_ssize_t i)
{
apr_ssize_t y, minc;
minc = left(i);
if (minc >= q->size)
return -1;
for (y = minc + 1; y <= right(i) && y < q->size; y++) {
if (q->pri(q->d[y]) > q->pri(q->d[minc]))
minc = y;
}
return minc;
}
static void cache_pq_percolate_down(cache_pqueue_t*q, apr_ssize_t i)
{
apr_ssize_t cx = minchild(q, i);
while ((cx != -1) && (q->pri(q->d[cx]) > q->pri(q->d[i])))
{
void *tmp;
tmp = q->d[i];
q->d[i] = q->d[cx];
q->d[cx] = tmp;
q->set(q->d[i], i);
q->set(q->d[cx], cx);
i = cx;
cx = minchild(q, i);
}
}
apr_status_t cache_pq_insert(cache_pqueue_t *q, void* d)
{
void *tmp;
apr_ssize_t i;
apr_ssize_t parent_node;
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++;
parent_node = parent(i);
/*
* this is an optimization of the bubble-up as it doesn't
* have to swap the member around
*/
while ((i > 1) && q->pri(q->d[parent_node]) < q->pri(d)) {
q->d[i] = q->d[parent_node];
q->set(q->d[i], i);
i = parent_node;
parent_node = parent(i);
}
q->d[i] = d;
q->set(q->d[i], 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;
void *popped = NULL;
long pri_popped;
long pri_removed;
posn = q->get(d);
popped = cache_pq_pop(q);
if (!popped)
return APR_EGENERAL;
if (d == popped) {
return APR_SUCCESS;
}
pri_popped = q->pri(popped);
pri_removed = q->pri(d);
q->d[posn] = popped;
q->set(popped,posn);
if (pri_popped > pri_removed)
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 *tmp;
void *d;
int i = 1;
int j;
if (!q || q->size == 1)
return NULL;
d = q->d[1];
tmp = q->d[--q->size];
while (i <= q->size / 2) {
j = 2 * i;
if (j < q->size && q->pri(q->d[j]) < q->pri(q->d[j + 1])) {
j++;
}
if (q->pri(q->d[j]) <= q->pri(tmp)) {
break;
}
q->d[i] = q->d[j];
q->set(d, i);
i = j;
}
q->d[i] = tmp;
q->set(d, i);
return d;
}
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, int 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\tminchild\t...\n");
for (i = 1; i < q->size ;i++) {
fprintf(stdout,
"%d\t%d\t%d\t%d\t%d\t",
i,
left(i), right(i), parent(i),
minchild(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);
}
1.1 httpd-2.0/modules/experimental/cache_pqueue.h
Index: cache_pqueue.h
===================================================================
/* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2000-2002 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Apache" and "Apache Software Foundation" must
* not be used to endorse or promote products derived from this
* software without prior written permission. For written
* permission, please contact apache@apache.org.
*
* 5. Products derived from this software may not be called "Apache",
* nor may "Apache" appear in their name, without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*
* Portions of this software are based upon public domain software
* originally written at the National Center for Supercomputing Applications,
* University of Illinois, Urbana-Champaign.
*/
#ifndef CACHE_PQUEUE_H
#define CACHE_PQUEUE_H
#ifdef __cplusplus
extern "C" {
#endif
/** the cache priority queue handle */
typedef struct cache_pqueue_t cache_pqueue_t;
/**
* callback function to assign a priority for a element
* @param a the element
* @return the score (the lower the score the longer it is kept int the queue)
*/
typedef long cache_pqueue_set_priority(long queue_clock, void*a);
typedef long cache_pqueue_get_priority(void*a);
/** callback function to get a position of a element */
typedef apr_ssize_t cache_pqueue_getpos(void *a);
/**
* callback function to set a position of a element
* @param a the element
* @param pos the position to set it to
*/
typedef void cache_pqueue_setpos(void *a, apr_ssize_t pos);
/** debug callback function to print a entry */
typedef void cache_pqueue_print_entry(FILE *out, void *a);
/**
* initialize the queue
*
* @param n the intial estimate of the number of queue items for which memory
* should be preallocated
* @param pri the callback function to run to assign a score to a element
* @param get the callback function to get the current element's position
* @param set the callback function to set the current element's position
*
* @Return the handle or NULL for insufficent memory
*/
cache_pqueue_t *cache_pq_init(apr_ssize_t n,
cache_pqueue_get_priority* pri,
cache_pqueue_getpos get,
cache_pqueue_setpos set);
/**
* free all memory used by the queue
* @param q the queue
*/
void cache_pq_free(cache_pqueue_t *q);
/**
* return the size of the queue.
* @param q the queue
*/
apr_ssize_t cache_pq_size(cache_pqueue_t *q);
/**
* insert an item into the queue.
* @param q the queue
* @param d the item
* @return APR_SUCCESS on success
*/
apr_status_t cache_pq_insert(cache_pqueue_t *q, void* d);
/*
* move a existing entry to a different priority
* @param q the queue
* @param old the old priority
* @param d the entry
*/
void cache_pq_change_priority(cache_pqueue_t *q,
long old_priority,
long new_priority,
void *d);
/**
* pop the highest-ranking item from the queue.
* @param p the queue
* @param d where to copy the entry to
* @return NULL on error, otherwise the entry
*/
void *cache_pq_pop(cache_pqueue_t *q);
/**
* remove an item from the queue.
* @param p the queue
* @param d the entry
* @return APR_SUCCESS on success
*/
apr_status_t cache_pq_remove(cache_pqueue_t *q, void *d);
/**
* access highest-ranking item without removing it.
* @param q the queue
* @param d the entry
* @return NULL on error, otherwise the entry
*/
void *cache_pq_peek(cache_pqueue_t *q);
/**
* print the queue
* @internal
* DEBUG function only
* @param q the queue
* @param out the output handle
* @param the callback function to print the entry
*/
void cache_pq_print(cache_pqueue_t *q,
FILE *out,
cache_pqueue_print_entry print);
/**
* dump the queue and it's internal structure
* @internal
* debug function only
* @param q the queue
* @param out the output handle
* @param the callback function to print the entry
*/
void cache_pq_dump(cache_pqueue_t *q,
FILE *out,
cache_pqueue_print_entry print);
#ifdef __cplusplus
}
#endif
#endif /* !CACHE_PQUEUE_H */