#include "../config.h"
#include <stdio.h>
#include <stdlib.h>
#ifdef HAVE_UNISTD_H
#  include <unistd.h>
#endif
#ifdef HAVE_MALLOC_H
#  include <malloc.h>
#endif
#include "dvi-2_6.h"
#include "defs.h"
#include "cache.h"

Private void        *get_elem(CACHE,void*,int);
Private void        lru_move_top(CACHE,CACHE_ELEM);
Private void        lru_put_top(CACHE,CACHE_ELEM);
Private CACHE_ELEM  lru_delete_tail(CACHE);
Private int         hash(CACHE,void*,int);
Private CACHE_ELEM  hash_is_interned(CACHE,void*,int);
Private void        hash_intern(CACHE,CACHE_ELEM,void*,int);
Private void        hash_unintern(CACHE,CACHE_ELEM);


/* dvi_cache_create()
 *   --- Creates a cache object. 
 */
Public CACHE
dvi_cache_create(int cache_size, int hash_size, 
		 void* (*load_func)(CACHE,void*,int),
		 void (*flush_func)(void*))
{
  int          i;
  CACHE        cache;
  CACHE_ELEM   celem;

  if ((cache_size < 1) || (hash_size < 1)
      || (cache = (CACHE)calloc(1, sizeof(struct s_cache))) == NULL)
    return NULL;

  /* alloc a cache elemants */
  celem = (CACHE_ELEM)calloc(cache_size, sizeof(struct s_cache_elem));
  if (celem == NULL){
    free(cache);
    return NULL;
  }
 
  /* make a free list */
  cache->free_list = &celem[0];
  for (i = 0; i < cache_size; i++){
    celem[i].h_forw = &celem[i+1];
    celem[i].key    = NULL;
    celem[i].object = NULL;
  }
  celem[cache_size-1].h_forw = NULL;
#if 0
  printf("%p\n", &celem[0]);
  printf("%p\n", &celem[cache_size-1]);
#endif

  /* alloc a hash table */
  cache->hash_table
    = (CACHE_ELEM)calloc(hash_size, sizeof(struct s_cache_elem));
  if (cache->hash_table == NULL){
    free(celem);
    free(cache);
    return NULL;
  }

  /* init */
  cache->cache_size  = cache_size;
  cache->hash_size   = hash_size;
  cache->get         = get_elem;
  cache->flush_elem  = flush_func;
  cache->load_elem   = load_func;
  cache->lru_list.l_forw = &cache->lru_list; 
  cache->lru_list.l_back = &cache->lru_list;
  for (i = 0; i < hash_size; i++){
    cache->hash_table[i].h_forw = &cache->hash_table[i];
    cache->hash_table[i].h_back = &cache->hash_table[i];
  }
  cache->elem_tbl    = celem;

  return cache;
}



/* dvi_cache_delete()
 *   --- Release a cache object. 
 */
Public void
dvi_cache_delete(CACHE cache)
{
  int          i;

  if (cache == NULL)
    return;

  if (cache->elem_tbl != NULL){
    for (i = 0; i < cache->cache_size; i++){
      if (cache->elem_tbl[i].key != NULL)
	free(cache->elem_tbl[i].key);
      if (cache->elem_tbl[i].object != NULL)
	free(cache->elem_tbl[i].object);
    }
    free(cache->elem_tbl);
  }

  if (cache->hash_table != NULL){
    free(cache->hash_table);
  }

  free(cache);
}



/* get_elem() 
 *   --- returns a elem. If not chached, reload it.
 */
Private void*
get_elem(CACHE cache, void* key, int key_len)
{
  CACHE_ELEM   ce;
  void         *key2;

  if ((ce = hash_is_interned(cache, key, key_len)) != NULL){
    lru_move_top(cache, ce);
  } else {
    if ((ce = cache->free_list) != NULL){
      ce->object = NULL;
      ce->key = NULL;
      cache->free_list = ce->h_forw;
    } else {
      ce = lru_delete_tail(cache);
      if (cache->flush_elem != NULL)
	(cache->flush_elem)(ce->object);
      else if (ce->object != NULL)
	free(ce->object);
      ce->object = NULL;
      if (ce->key != NULL)
	free(ce->key);
      ce->key = NULL;
    }
#if 0
    ce->object = (cache->load_elem)(cache, key, key_len);
    if ((key2 = (void*)malloc(key_len)) == NULL)
      return NULL;
    memcpy(key2, key, key_len);
    hash_intern(cache, ce, key2, key_len);
    ce->key     = key2;
    ce->key_len = key_len;
#else
    cache->free_list = ce->h_forw;
    if ((key2 = (void*)malloc(key_len)) == NULL)
      return NULL;
    memcpy(key2, key, key_len);
    ce->object = (cache->load_elem)(cache, key, key_len);
    ce->key     = key2;
    ce->key_len = key_len;
    hash_intern(cache, ce, key2, key_len);
#endif
    lru_put_top(cache, ce);
  }
  return (ce->object);
}


/* lru_move_top() 
 *   --- moves an ELEM at the top of LRU list.
 *       ELEM must be in LRU list.
 */
Private void
lru_move_top(CACHE cache, CACHE_ELEM ce)
{
  CACHE_ELEM  ce_b, ce_f;

  ce_b         = ce->l_back;
  ce_f         = ce->l_forw;
  ce_b->l_forw = ce_f;
  ce_f->l_back = ce_b;
  lru_put_top(cache, ce);
}

/* lru_put_top()
 *   --- puts an ELEM at the head of LRU list. 
 *       The ELEM must not be in LRU list.
 */
Private void 
lru_put_top(CACHE cache, CACHE_ELEM ce)
{
  CACHE_ELEM  ce_f;

  ce_f           = cache->lru_list.l_forw;
  ce->l_forw     = ce_f;
  ce_f->l_back   = ce;
  ce->l_back             = &cache->lru_list;
  cache->lru_list.l_forw = ce;
}

Private CACHE_ELEM
lru_delete_tail(CACHE cache)  /* NOTE: There must be at least one 
			               ELEM in LRU list */
{
  CACHE_ELEM  ce, ce_b;

  if ((ce = cache->lru_list.l_back) == &cache->lru_list)
    return NULL;

  /* delete from lru list */
  ce_b                   = ce->l_back;
  ce_b->l_forw           = &cache->lru_list;
  cache->lru_list.l_back = ce_b;

  /* delete from hash table */
  hash_unintern(cache, ce);

  /* return to free list */
  ce->h_forw       = cache->free_list;
  cache->free_list = ce;

  return ce;
}



Private int
hash(CACHE cache, void* key, int key_len)
{
  char          *p;
  int           i;
  unsigned int  h;

  h = 0;
  for (i = 0, p = key; i < key_len; i++, p++)
    h = (h + (unsigned int)*p) % cache->hash_size;
  return  h;
} 

Private CACHE_ELEM
hash_is_interned(CACHE cache, void* key, int key_len)
{
  int         h;
  CACHE_ELEM  ce, ce0;

  h = hash(cache, key, key_len);
  ce0 = &cache->hash_table[h]; 
  for (ce = ce0->h_forw; ce != ce0; ce = ce->h_forw)
    if ((ce->key_len == key_len) && (memcmp(ce->key, key, key_len) == 0)){
      if (ce != ce0->h_forw){
	hash_unintern(cache, ce);
	hash_intern(cache, ce, NULL, h);  /* MAGIC */
      }
      return ce;
    }
  return NULL;
}

Private void
hash_intern(CACHE cache, CACHE_ELEM ce, void* key, int key_len)
{
  int         h;
  CACHE_ELEM  ce1;

  if (key == NULL)  /* MAGIC */
    h = key_len;  
  else
    h = hash(cache, key, key_len);
  ce1                         = cache->hash_table[h].h_forw;
  cache->hash_table[h].h_forw = ce;
  ce->h_forw                  = ce1;
  ce1->h_back                 = ce;
  ce->h_back                  = &cache->hash_table[h];
}

Private void
hash_unintern(CACHE cache, CACHE_ELEM ce)
{
  CACHE_ELEM  ce_b, ce_f;

  ce_b         = ce->h_back;
  ce_f         = ce->h_forw;
  ce_b->h_forw = ce_f;
  ce_f->h_back = ce_b;
}

/*EOF*/