/* Copyright (C) 1996 Bjoern Beutel. */

/* Description. =============================================================*/

/* Manages the storage of analysis results for faster access. */

/* Includes. ================================================================*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <setjmp.h>
#include <stdarg.h>
#include <glib.h>
#include "basic.h"
#include "pools.h"
#include "values.h"
#include "avl_trees.h"
#include "cache.h"

/* Types. ===================================================================*/

typedef struct cache_entry /* An entry of the cache tree. */
{ 
  avl_node_t avl_node; /* A node in an AVL tree. */
  struct cache_entry *prev_ref, *next_ref; /* LRU chain. */
  string_t surface;
  int_t feat_count; /* Number of feature structures in feat_vector. */
  value_t *feat_vector; /* A vector of feature structures. */
} cache_entry_t;

/* Global Variables. ========================================================*/

int_t cache_accesses; /* Number of calls of "word_in_cache". */
int_t cache_hits; /* Number of successful calls of "word_in_cache". */

/* Variables. ===============================================================*/

static avl_node_t *cache_tree; /* The cache tree. Actually points to 
				* cache_entry_t. */
static int_t max_entry_count; /* Maximum of entries in CACHE_TREE. */
static int_t entry_count; /* Actual number of entries in CACHE_TREE. */

static cache_entry_t *first_ref; /* The entry that was referenced first. */
static cache_entry_t *last_ref; /* The entry that was referenced last. */

/* These are needed for "next_result_in_cache". */
static cache_entry_t *current_entry;
static int_t current_result;

/* Functions. ===============================================================*/

static int_t 
compare_cache_entries( avl_node_t *node1, avl_node_t *node2 )
/* A callback function for "avl_tree_insert", "avl_tree_remove",
 * used to compare "cache_entry_t" nodes. */
{ 
  return strcmp( ((cache_entry_t *) node1)->surface, 
                 ((cache_entry_t *) node2)->surface );
}

/*---------------------------------------------------------------------------*/

static cache_entry_t *
new_cache_entry( string_t surf_start, string_t surf_end,
                 int_t feat_count, value_t feat_vector[] )
/* Create cache entry for string at SURF_START..SURF_END. 
 * It has FEAT_COUNT feature structures stored in FEAT_VECTOR. 
 * Return the created entry. */
{ 
  cache_entry_t *cache_entry;

  /* Allocate a cache entry. */
  cache_entry = new_mem( sizeof( cache_entry_t ) );
  cache_entry->surface = new_string( surf_start, surf_end );
  cache_entry->feat_count = feat_count;
  cache_entry->feat_vector = feat_vector;

  entry_count++;
  return cache_entry;
}

/*---------------------------------------------------------------------------*/

static void 
free_cache_entry( cache_entry_t **cache_entry )
/* Free the memory allocated for *CACHE_ENTRY. */
{ 
  int_t i;

  if (*cache_entry != NULL) 
  { 
    for (i = 0; i < (*cache_entry)->feat_count; i++) 
      free_mem( &(*cache_entry)->feat_vector[i] );
    free_mem( &(*cache_entry)->feat_vector );
    free_mem( &(*cache_entry)->surface );
    free_mem( cache_entry );
    entry_count--;
  }
}

/*---------------------------------------------------------------------------*/

static void 
reference_entry( cache_entry_t *entry )
/* Put ENTRY at end of LRU-list if it is not already there. */
{ 
  if (entry != last_ref) 
  { 
    /* Remove entry from old position. */
    entry->next_ref->prev_ref = entry->prev_ref;
    if (entry != first_ref) 
      entry->prev_ref->next_ref = entry->next_ref;
    else 
      first_ref = entry->next_ref;

    /* Enter entry in new position. */
    entry->prev_ref = last_ref;
    entry->next_ref = NULL;
    last_ref->next_ref = entry;
    last_ref = entry;
  }
}

/*---------------------------------------------------------------------------*/

bool_t 
word_in_cache( string_t surf_start, string_t surf_end )
/* Check if word in [SURF_START..SURF_END] is in the cache. 
 * Return TRUE if word found. Use "next_result_in_cache" to get next result. */
{ 
  cache_entry_t *entry;
  int_t result;

  cache_accesses++;
  entry = (cache_entry_t *) cache_tree;
  while (entry != NULL) 
  { 
    result = strncmp( surf_start, entry->surface, surf_end - surf_start );
    if (result == 0 && entry->surface[ surf_end - surf_start ] != EOS) 
      result = -1;
    if (result < 0) 
      entry = (cache_entry_t *) entry->avl_node.left;
    else if (result > 0) 
      entry = (cache_entry_t *) entry->avl_node.right;
    else /* Word found. */
    { 
      reference_entry( entry );
      current_entry = entry;
      current_result = 0;
      cache_hits++;
      return TRUE;
    }
  }
  return FALSE;
}

/*---------------------------------------------------------------------------*/

value_t 
next_result_in_cache( void )
/* Return the next feature structure for the word found by "word_in_cache".
 * Return NULL if no more feature structure exists. */
{
  value_t result;

  if (current_result >= current_entry->feat_count) 
    return NULL;
  result = current_entry->feat_vector[ current_result ];
  current_result++;
  return result;
}

/*---------------------------------------------------------------------------*/

static void 
remove_entry_from_cache( void )
/* Delete an entry from cache. */
{ 
  cache_entry_t *entry;
  
  /* Remove first element from LRU list. */
  entry = first_ref;
  first_ref = entry->next_ref;
  if (first_ref != NULL) 
    first_ref->prev_ref = NULL;
  else 
    last_ref = NULL;

  /* Remove ENTRY from tree. */
  remove_avl_node( (avl_node_t *) entry, (avl_node_t **) &cache_tree, 
                   compare_cache_entries );
  free_cache_entry( &entry );
}

/*---------------------------------------------------------------------------*/

void 
enter_in_cache( string_t surf_start, string_t surf_end,
                int_t feat_count, value_t feat_vector[] )
/* Enter the word in [SURF_START..SURF_END] in the cache.
 * It has FEAT_COUNT feature structures, stored in FEAT_VECTOR[].
 * Be sure that the word is not yet in the cache. */
{ 
  cache_entry_t *cache_entry;

  if (entry_count >= max_entry_count) 
    remove_entry_from_cache();
  cache_entry = new_cache_entry( surf_start, surf_end, 
				 feat_count, feat_vector );

  /* Enter entry in cache tree. */
  insert_avl_node( (avl_node_t *) cache_entry, (avl_node_t **) &cache_tree, 
                   compare_cache_entries );

  /* Put entry at end of LRU table. */
  if (last_ref != NULL) 
    last_ref->next_ref = cache_entry;
  cache_entry->prev_ref = last_ref;
  cache_entry->next_ref = NULL;
  last_ref = cache_entry;
  if (first_ref == NULL) 
    first_ref = cache_entry;
}

/*---------------------------------------------------------------------------*/

void 
clear_cache( void )
/* Remove all entries from the cache. */
{ 
  while (entry_count > 0) 
    remove_entry_from_cache();
}

/*---------------------------------------------------------------------------*/

void 
set_cache_size( int_t size )
/* Set maximum number of cache entries to SIZE. */
{ 
  max_entry_count = size;
  while (entry_count > max_entry_count) 
    remove_entry_from_cache();
}

/*---------------------------------------------------------------------------*/

int_t 
get_cache_size( void )
/* Get actual number of cache entries. */
{ 
  return entry_count; 
}

/*---------------------------------------------------------------------------*/

int_t 
get_cache_maximum( void )
/* Get maximum number of cache entries. */
{ 
  return max_entry_count; 
}

/* End of file. =============================================================*/