/* cache.c */

#include "copyright.h"
#include "config.h"

#include <stdio.h>

#include "teeny.h"
#include "db.h"

/*
 * Cache management stuff. Also handles allocating chunks from the chunkfile
 * and so on. Note: This DOES NOT mess with the disk, only with internal data
 * structures. Basically the low level object management. Messes with
 * descriptors to indicate whether things are or are not in cache. 
 *
 * This also has routines for managing descriptors efficiently. malloc()ing them
 * one at a time is death, 'cause we have absolutely *fuckloads* of them
 * around. 
 */

/*
 * The cache is stored as a chain, in order by most recently used. Use
 * touch() to indicate a usage. 
 */

struct obj_data *main_cache = NULL;
int             cache_usage = 0;/* Total cache usage at present */
long            cache_size;

/*
 * If this is a 1, cache_trim() will NOT freeze things to disk. This can be
 * used to protect the chunkfile from writes for a bit, if you are copyinf it
 * around. 
 */

int             cache_locked = 0;

/*
 * The free chunks are stored as a list of descriptors, biggest chunk first.
 * This leads to a fast worst-fit algorithm. Forward points toward less
 * recently used objects. 
 */

struct dsc     *free_chunks = NULL;
long            chunk_eof = 0L;	/* Contains the offset of the end of the
				 * chunkfile */

/*
 * Initialize the cache to some size or other. 
 */

void 
initialize_cache(size)
  long            size;
{
  cache_size = size;
  cache_usage = 0;
}

/*
 * Deletes an object from cache. 
 */
void 
cache_delete(obj)
  struct obj_data *obj;
{
  if (obj == obj->back)
  {				/* Only thing here.. */
    main_cache = NULL;
    return;
  }
  if (main_cache == obj)
  {
    main_cache = obj->fwd;
  }
  /* Unlink this sucker */

  (obj->back)->fwd = obj->fwd;
  (obj->fwd)->back = obj->back;

  cache_usage -= DSC_SIZE(obj->descriptor);
#ifdef CACHEDEBUG
  printf("cache_delete ");
  cache_dump();
#endif				/* CACHEDEBUG */
}

/*
 * This moves an object to the head of the usage list, making it the most
 * recently used. Call this whenever you reference an object. 
 */
void 
touch(obj)
  struct obj_data *obj;
{
  if (obj == main_cache)
  {				/* Already at the top */
    return;
  }
  /* Unlink it */

  (obj->back)->fwd = obj->fwd;
  (obj->fwd)->back = obj->back;

  /* Link it back in at the head. Remember, fwd is */
  /* the next most recently used object. */

  obj->fwd = main_cache;
  obj->back = main_cache->back;
  (main_cache->back)->fwd = obj;
  main_cache->back = obj;

  /* This is now the most recently used. */

  main_cache = obj;
#ifdef CACHEDEBUG
  printf("touch: ");
  cache_dump();
#endif				/* CACHEDEBUG */
}

/*
 * This stuffs the object into cache, and then trims the cache down. All
 * cache 'size' data goes by the size field on the descriptor, which is *on
 * disk* size, not actual in memory size. Too bad. 
 *
 * This and cache_flush() are the only things that should *ever* freeze an
 * object to disk. Do it otherwise, and you better have a good reason. 
 *
 * NOTE: The object better NOT be in cache when this is called. 
 */
void 
cache_insert(obj)
  struct obj_data *obj;
{
  if (main_cache == NULL)
  {				/* Empty cache */
    main_cache = obj->back = obj->fwd = obj;
    cache_usage = DSC_SIZE(obj->descriptor);
    return;
  }
  /* Stuff it in at the head -- it's the most recently used. */

  obj->fwd = main_cache;
  obj->back = main_cache->back;
  (main_cache->back)->fwd = obj;
  main_cache->back = obj;

  /* This is now the most recently used. */

  main_cache = obj;

  /* Now update cache usage, and trim the cache down to size */

  cache_usage += DSC_SIZE(obj->descriptor);
  cache_trim();
#ifdef CACHEDEBUG
  printf("cache_insert");
  cache_dump();
#endif				/* CACHEDEBUG */
}

#ifdef CACHEDEBUG
cache_dump()
{
  struct obj_data *obj;

  obj = main_cache;
  if (obj == NULL)
  {
    printf("cache is empty\n");
    return;
  }
  do
  {
    printf(" %s", DSC_NAME(obj->descriptor));
    obj = obj->fwd;
  } while (obj != main_cache);
  printf("\n");
}

#endif				/* CACHEDEBUG */

/*
 * Locks the cache so stuff is guaranteed to remain resident. 
 */

void 
lock_cache()
{
  cache_locked = 1;
}

/*
 * Unlocks the cache so things can get flushed to disk. 
 */
void 
unlock_cache()
{
  cache_locked = 0;
}

/*
 * Trims the cache down to size, unless it's locked. 
 */

cache_trim()
{
  struct obj_data *obj;
  struct dsc     *thedsc;

  if (cache_locked)
    return;

  while (cache_usage > cache_size)
  {
    /* Unlink the object back of the head */
    obj = main_cache->back;
    if (obj == main_cache)
    {
      warning("cache_trim", "cache WAY too small!");
      return;
    }
    (obj->back)->fwd = obj->fwd;
    (obj->fwd)->back = obj->back;

    thedsc = obj->descriptor;
    cache_usage -= DSC_SIZE(thedsc);

    /* Chill this object */

    disk_freeze(obj->descriptor);
  }
}

/*
 * This flushes the entire cache to disk (for dump-like purposes). 
 */
void 
cache_flush()
{
  struct obj_data *obj, *next;

  if (main_cache == NULL)
  {
    return;
  }
  obj = main_cache;
  do
  {
    /* Be careful here. disk_freeze() blows away the obj */

    next = obj->fwd;
    disk_freeze(obj->descriptor);
    obj = next;
  } while (obj != main_cache);
  main_cache = NULL;
  cache_usage = 0;
}

/*
 * Places a descriptor on the free chunk list. 
 */

void 
free_chunk(dsc)
  struct dsc     *dsc;
{
  struct dsc     *current, *last, *here;
  long            start, end;

  if (free_chunks == NULL)
  {
    (dsc->ptr).next = NULL;
    free_chunks = dsc;
    return;
  }
  current = free_chunks;
  last = here = NULL;

  /* Charge down the list, seeing if this amalgamates with any   */
  /* existing free blocks. Track where to insert it, in case not */

  start = DSC_CHUNK(dsc);
  end = start + DSC_SIZE(dsc);

  while (current != NULL)
  {
    /* If no amalgamation, insert it here? If the first    */
    /* chunk is smaller, or if all the chunks are bigger   */
    /* here will be NULL. Be careful at the end, therefore */

    if (here == NULL && DSC_SIZE(current) < DSC_SIZE(dsc))
    {
      here = last;
    }
    /* Now see if it amalgamates. */
    if (start == (DSC_CHUNK(current) + DSC_SIZE(current)))
    {
      DSC_SIZE(current) += DSC_SIZE(dsc);
      free_descriptor(dsc);
      del_free_chunk(current, last);
      free_chunk(current);
      return;
    } else
    if (end == DSC_CHUNK(current))
    {
      DSC_SIZE(dsc) += DSC_SIZE(current);
      del_free_chunk(current, last);
      free_descriptor(current);
      free_chunk(dsc);
      return;
    }
    last = current;
    current = (current->ptr).next;
  }

  /* Post mortem. Only get here we didn't amalgamate */

  if (here == NULL)
  {
    /* Either it gos in at the head, or at the tail. */

    if (DSC_SIZE(last) > DSC_SIZE(dsc))
    {
      /* Tail */
      (dsc->ptr).next = NULL;
      (last->ptr).next = dsc;
    } else
    {
      /* Head */
      (dsc->ptr).next = free_chunks;
      free_chunks = dsc;
    }
  } else
  {
    /* Insert it immediately after here */

    (dsc->ptr).next = (here->ptr).next;
    (here->ptr).next = dsc;
  }
}

/*
 * This allocates a chunk from the free list of chunks, if it can, otherwise
 * it just specifies the and of the chunkfile. It returns an offset to write
 * at, in either case. In particular it DOES NOT return a descriptor. 
 */
long 
get_chunk(n)
  int             n;
{
  long            ret;
  struct dsc     *tmp;

  if (free_chunks == NULL)
  {				/* No free chunks. */
#ifdef CACHEDEBUG
    printf("No free chunks. Allocating from EOF\n");
#endif				/* CACHEDEBUG */
    ret = chunk_eof;
    chunk_eof += n;
    return (ret);
  }
  /* See if the first (biggest) chunk is big enough. */

  tmp = free_chunks;
  if (DSC_SIZE(tmp) > n)
  {

    /* Return the offset of the start */
#ifdef CACHEDEBUG
    printf("Biggest chunk was big enough. Pruning it.");
#endif				/* CACHEDEBUG */
    ret = DSC_CHUNK(tmp);

    /*
     * Adjust the size & offset, unlink it, and re-insert it in order 
     */

    DSC_SIZE(tmp) -= n;
    DSC_CHUNK(tmp) += n;
    free_chunks = (tmp->ptr).next;
    free_chunk(tmp);
    return (ret);

  } else
  if (DSC_SIZE(tmp) == n)
  {				/* Exact match! */
    /* Nuke this descriptor completely */
#ifdef CACHEDEBUG
    printf("Biggest chunk was exact match, allocating it\n");
#endif				/* CACHEDEBUG */
    ret = DSC_CHUNK(tmp);
    free_chunks = (tmp->ptr).next;
    free_descriptor(tmp);
    return (ret);
  }
  /* If we can't find a big enough chunk, do this */
#ifdef CACHEDEBUG
  printf("No big enough chunks. Allocating from EOF.\n");
#endif				/* CACHEDEBUG */
  ret = chunk_eof;
  chunk_eof += n;
  return (ret);
}

/*
 * Deletes a descriptor from the list of free chunk descriptors. 
 */
void 
del_free_chunk(dsc, last)
  struct dsc     *dsc;
  struct dsc     *last;
{
  if (free_chunks == dsc)
  {
    free_chunks = (dsc->ptr).next;
    return;
  }
  /* Last had better only be NULL when dsc == free_chunks */

  (last->ptr).next = (dsc->ptr).next;
}

/*
 * Descriptor management code. 
 */

struct dsc     *free_descriptors = NULL;

/*
 * Allocate a bunch of descriptors, and shove them on the free descriptor
 * list. 
 */
void 
alloc_dsc(n)
  int             n;
{
  struct dsc     *tmp1, *tmp2;

  tmp1 = tmp2 = (struct dsc *) ty_malloc(n * sizeof(struct dsc), "alloc_dsc");

  /* String them together into a list */

  for (; n > 1; n--)
  {
    (tmp2->ptr).next = &(tmp2[1]);	/* Point at the next */
    tmp2++;
  }

  /* Link this mess in */

  (tmp2->ptr).next = free_descriptors;
  free_descriptors = tmp1;
}

/*
 * Grab a descriptor. 
 */
struct dsc     *
get_descriptor()
{
  struct dsc     *ret;

  if (free_descriptors == NULL)
  {
    alloc_dsc(32);		/* Get a bunch more */
  }
  ret = free_descriptors;
  free_descriptors = (ret->ptr).next;	/* Might be NULL. OK. */

  return (ret);
}

/*
 * Give a descriptor back. 
 */

void 
free_descriptor(dsc)
  struct dsc     *dsc;
{
  (dsc->ptr).next = free_descriptors;
  free_descriptors = dsc;
}