/*
   "cache.c" - part of "RAGMAAN, een anagrammengenerator"

   Copyright (C) 1999 Raymond Zandbergen

   This program 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 of the License, or
   (at your option) any later version.

   This program 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 PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

   The maintainer of this program is Raymond Zandbergen (ray@wirehub.nl)
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "cache.h"

int sync_cache_flag;

static int current_depth = 0;
static int seq = 0;
static int cache_hits = 0;
static int cache_misses = 0;

static anagram_set_t *cache[CACHE_DEPTH][CACHE_SIZE];

static int cache_search (char *target, int *px, int *py);
/*
 * searches all cache slots for target (returns 0 or 1)
 */

static void cache_lru (int x, int *py);
/*
 * returns least recently used cache slot for a given depth x in py
 */

anagram_set_t *
get_working_set (char *target)
{

  int x, y;
  anagram_set_t *working_set;

  seq++;
  if (cache_search (target, &x, &y))
    {				/* cache hit! */

      current_depth = x;
      working_set = cache[x][y];
      working_set->seq = seq;
      working_set->cache_hit = 1;
      cache_hits++;
      return working_set;
    }
  else
    {				/* cache miss */
      if (sync_cache_flag)
	{
	  sync_cache_flag = 0;
	  current_depth = 0;
	}
      else
	{
	  if (current_depth < CACHE_DEPTH - 1)
	    current_depth++;
	}
      x = current_depth;
      cache_lru (x, &y);
      working_set = cache[x][y];
      set_init (working_set);
      working_set->seq = seq;
      cache_misses++;
      return working_set;
    }
}

static void
cache_lru (int x, int *py)
{
  int seq_min = cache[x][0]->seq;
  int min_idx = 0;
  int i;

  for (i = 1; i < CACHE_SIZE; i++)
    {

      int cache_seq = cache[x][i]->seq;

      if (cache_seq < seq_min)
	{

	  seq_min = cache_seq;
	  min_idx = i;
	}
    }
  *py = min_idx;
}

static int
cache_search (char *target, int *px, int *py)
{
  int i, j;

  for (i = 0; i < CACHE_DEPTH; i++)
    for (j = 0; j < CACHE_SIZE; j++)
      {

	if (strcmp (target, cache[i][j]->target) == 0)
	  {

	    *px = i;
	    *py = j;
	    return 1;
	  }
      }
  return 0;
}

void
cache_init (void)
{
  int i, j;
  anagram_set_t *p;

  for (i = 0; i < CACHE_DEPTH; i++)
    for (j = 0; j < CACHE_SIZE; j++)
      {

	p = malloc (sizeof (anagram_set_t));

	if (!p)
	  {
	    fputs ("out of memory "
		   "while allocating cache", stderr);
	    exit (1);
	  }

	set_init (p);
	cache[i][j] = p;

      }
  sync_cache_flag = 1;
  current_depth = 0;
}

void
set_init (anagram_set_t * p)
{
  p->target[0] = 0;
  p->regexp[0] = 0;
  p->nof_anagrams = 0;
  p->nof_filtered_anagrams = 0;
  p->seq = 0;
  p->cache_hit = 0;
  p->use_filter = 0;
  p->use_reverse = 0;
  p->use_sort = 0;
  p->sort_valid = 0;
  p->use_filter_sort = 0;
  p->filter_sort_valid = 0;
}

void
cache_flush (void)
{
  int i, j;

  for (i = 0; i < CACHE_DEPTH; i++)
    for (j = 0; j < CACHE_SIZE; j++)
      {
	set_init (cache[i][j]);
      }
  sync_cache_flag = 1;
  current_depth = 0;
}

void
cache_stats (char *s, int n)
{
  snprintf (s, n, "TCACHE: %d x %d slots = %d KB, "
	    "target hits: %d / %d\n",
	    CACHE_DEPTH, CACHE_SIZE,
	    CACHE_DEPTH * CACHE_SIZE * sizeof (anagram_set_t) / 1024,
	    cache_hits, cache_misses + cache_hits);
}