---

cache.c

 /*
  * share/cache.c : implements a cache  to speed up procedure  calls & variable
  *                 referencing (source)
  * 
  * Time-stamp: <2002-12-21 14:19:58 gseba>
  * 
  * Copyright (C) Sebastian Glita, email: gseba@users.sourceforge.net
  * 
  * This file is part of plint.
  * 
  * plint is free software; you can  redistribute it and/or modify it under the
  * terms of the  GNU General Public License as published  by the Free Software
  * Foundation; either version 2, or (at your option) any later version.
  *
  * plint  is distributed  in the  hope  that it  will be  useful, but  WITHOUT
  * ANY  WARRANTY; without  even  the implied  warranty  of MERCHANTABILITY  or
  * FITNESS FOR A  PARTICULAR PURLEVE.  See the GNU  General Public License for
  * more details.
  * 
  * You should  have received a  copy of the  GNU General Public  License along
  * with  plint; see  the file  COPYING.  If  not, write  to the  Free Software
  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA USA.
  *
  */

#include "common.h"
#include "cache.h"

typedef struct _cache_entry
{

  hashindex_t tag;              
  size_t lev;                   
  void * data;                  
} cache_entry_t;

struct _cache
{

  struct _cache_entry * cache;  
  size_t size;                  
  size_t lru;                   
  size_t fill;                  
  cache_missfunc_t miss;        
  cache_invfunc_t inv;          
  int dis:1;                    
#ifndef NDEBUG
  unsigned long hits;           
  unsigned long misses;         
  unsigned long invalidates;    
#endif

};



static void cache_reset(cache_t cache) {
  size_t i;

  /* preconditions */
  cache->fill = 0;
  for (i = 0; i < cache->size; ++i)
    cache->cache[i].lev = i;
  cache->lru = 0;

#ifndef NDEBUG
  cache->hits = 1;
  cache->misses = cache->invalidates = 0;
#endif
}

void cache_init(cache_t * pcache, size_t size, cache_missfunc_t miss, cache_invfunc_t inv)
{
  cache_t cache;
  cache = (cache_t)malloc(sizeof(*cache));
  cache->miss = miss;
  cache->inv = inv;
  cache->cache = (cache_entry_t *)malloc((cache->size = size) * sizeof(cache_entry_t));
  cache_reset(cache);
  cache_enable(cache);

  *pcache = cache;
}

void cache_finish(cache_t cache)
{
  free(cache->cache);
  free(cache);
}


#define CACHE_UPDATE()                                  \
{                                                       \
  size_t _i;                                            \
  for (_i = cache->fill; _i;)                           \
    if (ce[--_i].lev > lev && --ce[_i].lev == 0)        \
      cache->lru = _i;                                  \
}


static void * cache_hit(cache_t cache, size_t mru)
{
  cache_entry_t * ce = cache->cache;
  size_t lev = ce[mru].lev;
  if (cache->fill == cache->size)
    CACHE_UPDATE();
  ce[mru].lev = cache->fill-1;

  return ce[mru].data;
}

void * cache_lookup(cache_t cache, hashindex_t tag, void * parm)
{
  size_t i;

  if (cache->dis)
    return cache->miss(tag, parm);

  /* look it up, maybe it's already in cache ? */
  for (i = 0; i < cache->fill; ++i)
    if (HASH_INDEX_EQU(tag, cache->cache[i].tag))
      break; /* yes, i've been hit !!! */
  
  if (i == cache->fill)
    {
      /* no it's not in the cache, look it up trivially */
#ifndef NDEBUG
      ++cache->misses;
#endif

      if (i == cache->size)
        i = cache->lru;
      else
        ++cache->fill;

      cache->cache[i].data = cache->miss(cache->cache[i].tag = tag, parm);
    }
#ifndef NDEBUG
  else
    ++cache->hits;
#endif

  /* in the end, it's a hit */
  return cache_hit(cache, i);
}

int cache_invalidate(cache_t cache, void * parm)
{
  int ret = 0;
  if (!cache->dis)
    {
      cache_entry_t * ce = cache->cache;
      size_t i, lev;

      /* once and for all invalidate */
      hashindex_t bad_tag;
      HASH_INDEX_DOBAD(bad_tag);
      if (cache->inv(&bad_tag, 0, parm))
        {
          cache_reset(cache);
          ret = !0;
        }
      else
        for (i = 0; i < cache->fill; ++i)
          if (cache->inv(&ce[i].tag, &ce[i].data, parm))
            {
              size_t j;

              lev = ce[i].lev;
              CACHE_UPDATE();

              --cache->fill;

              for (j = i; j < cache->fill; ++j)
                ce[j] = ce[j+1];

              ce[j].lev = j;

              --i;

              ret = !0;
            }
    }

  return ret;
}

inline void cache_disable(cache_t cache) {
  cache->dis = !0;
}

inline void cache_enable(cache_t cache) {
  cache->dis = 0;
}

#ifndef NDEBUG

void cache_status(cache_t cache, FILE * f, char const * name, int prec)
{
  if (prec == 0)
    prec = 4;
  fprintf(f, "%s cache is %sabled: size %d, hits = %ld, misses = %ld, hit rate = %.*lf.", name,
          cache->dis ? "dis" : "en",
          cache->size,
          cache->hits,
          cache->misses,
          prec,
          (double)1.*cache->hits/(cache->hits+cache->misses));
}
#endif

#undef CACHE_UPDATE

---