/*
 * NAME:	cache.c
 * DESCRIPTION:	new generic cache
 */

inherit "/std/string";

# define DEFAULT_SIZE  10

private	string *keys;		/* array of cache keys */
private	mixed  *values;		/* array of cache values */

private	mapping	cache;		/* key -> index pairs */

private	string	next;		/* pointers to next cache items */
private	string	prev;		/* pointers to previous cache items */

private	int	head;		/* most recent inserted item */
private	int	tail;		/* least recent inserted item */

/*
 * NAME:	reset()
 * DESCRIPTION:	clear the cache
 */
static varargs
void reset(int size)
{
  int i;

  if (size <= 0)
    size = sizeof(keys);

  keys   = allocate(size);
  values = allocate(size);

  cache  = ([ ]);

  next = prev = space(size);

  for (i = 0; i < size; ++i)
    {
      next[i] = i + 1;
      prev[i] = i - 1;
    }

  head = 0;
  tail = size - 1;
}

/*
 * NAME:	create()
 * DESCRIPTION:	initialize data
 */
static
void create(void)
{
  reset(DEFAULT_SIZE);
}

/*
 * NAME:	hit()
 * DESCRIPTION:	move an item to the head of the cache
 */
private
mixed hit(int item)
{
  if (item != head)
    {
      if (item == tail)
	tail = prev[item];
      else
	{
	  int n, p;

	  n = next[item];
	  p = prev[item];

	  next[p] = n;
	  prev[n] = p;
	}

      next[item] = head;
      prev[head] = item;

      head = item;
    }

  return values[item];
}

static mixed cache_miss(string key);

/*
 * NAME:	miss()
 * DESCRIPTION:	insert a new item into the cache
 */
private
mixed miss(string key)
{
  int item;

  cache[keys[item = tail]] = 0;
  cache[keys[item] = key]  = item + 1;

  tail = prev[item];
  next[item] = head;
  prev[head] = item;

  return values[head = item] = cache_miss(key);
}

/*
 * NAME:	fetch()
 * DESCRIPTION:	return an item from the cache
 */
static
mixed fetch(string key)
{
  int item;

  if ((item = cache[key]) != 0)
    return hit(item - 1);
  else
    return miss(key);
}

/*
 * NAME:	dump()
 * DESCRIPTION:	return cache contents (debugging)
 */
static
mixed *dump(void)
{
  int *nlist, *plist, i;

  nlist = allocate(strlen(next));
  plist = allocate(strlen(prev));

  for (i = sizeof(nlist); i--; )
    nlist[i] = next[i];
  for (i = sizeof(plist); i--; )
    plist[i] = prev[i];

  return ({ keys, values, cache, nlist, plist, head, tail });
}