/* 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. =============================================================*/