httpd-cvs mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From i...@apache.org
Subject 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
Date Thu, 06 Jun 2002 19:07:10 GMT
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 */
  
  
  

Mime
View raw message