1
/* Copyright (C) 1995 Bjoern Beutel. */
3
/* Description. =============================================================*/
5
/* Manages the storage of analysis results for faster access. */
7
/* Includes. ================================================================*/
17
#include "avl_trees.h"
20
/* Types. ===================================================================*/
22
typedef struct cache_entry /* An entry of the cache tree. */
24
avl_node_t avl_node; /* A node in an AVL tree. */
25
struct cache_entry *prev_ref, *next_ref; /* LRU chain. */
27
int_t fs_count; /* Number of feature structures in fs_vector. */
28
value_t *fs_vector; /* A vector of feature structures. */
31
/* Global Variables. ========================================================*/
33
int_t cache_accesses; /* Number of calls of "word_in_cache". */
34
int_t cache_hits; /* Number of successful calls of "word_in_cache". */
36
/* Variables. ===============================================================*/
38
static cache_entry_t *cache_tree; /* The cache tree. */
39
static int_t max_entry_count; /* Maximum of entries in CACHE_TREE. */
40
static int_t entry_count; /* Actual number of entries in CACHE_TREE. */
42
static cache_entry_t *first_ref; /* The entry that was referenced first. */
43
static cache_entry_t *last_ref; /* The entry that was referenced last. */
45
/* These are needed for "next_result_in_cache". */
46
static cache_entry_t *current_entry;
47
static int_t current_result;
49
/* Functions. ===============================================================*/
52
compare_cache_entries( avl_node_t *node1, avl_node_t *node2 )
53
/* A callback function for "avl_tree_insert", "avl_tree_remove",
54
* used to compare "cache_entry_t" nodes. */
56
return strcmp( ((cache_entry_t *) node1)->surface,
57
((cache_entry_t *) node2)->surface );
60
/*---------------------------------------------------------------------------*/
62
static cache_entry_t *
63
new_cache_entry( string_t surf_start, string_t surf_end,
64
int_t fs_count, value_t fs_vector[] )
65
/* Create cache entry for string at SURF_START..SURF_END.
66
* It has FS_COUNT feature structures stored in FS_VECTOR.
67
* Return the created entry. */
69
cache_entry_t *cache_entry;
71
/* Allocate a cache entry. */
72
cache_entry = new_mem( sizeof( cache_entry_t ) );
73
cache_entry->surface = new_string( surf_start, surf_end );
74
cache_entry->fs_count = fs_count;
75
cache_entry->fs_vector = fs_vector;
81
/*---------------------------------------------------------------------------*/
84
free_cache_entry( cache_entry_t **cache_entry )
85
/* Free the memory allocated for *CACHE_ENTRY. */
89
if (*cache_entry != NULL)
91
for (i = 0; i < (*cache_entry)->fs_count; i++)
92
free_mem( &(*cache_entry)->fs_vector[i] );
93
free_mem( &(*cache_entry)->fs_vector );
94
free_mem( &(*cache_entry)->surface );
95
free_mem( cache_entry );
100
/*---------------------------------------------------------------------------*/
103
reference_entry( cache_entry_t *entry )
104
/* Put ENTRY at end of LRU-list if it is not already there. */
106
if (entry != last_ref)
108
/* Remove entry from old position. */
109
entry->next_ref->prev_ref = entry->prev_ref;
110
if (entry != first_ref)
111
entry->prev_ref->next_ref = entry->next_ref;
113
first_ref = entry->next_ref;
115
/* Enter entry in new position. */
116
entry->prev_ref = last_ref;
117
entry->next_ref = NULL;
118
last_ref->next_ref = entry;
123
/*---------------------------------------------------------------------------*/
126
word_in_cache( string_t surf_start, string_t surf_end )
127
/* Check if word in [SURF_START..SURF_END].
128
* Return TRUE if word found. Use "next_result_in_cache" to get next result. */
130
cache_entry_t *entry;
135
while (entry != NULL)
137
result = strncmp( surf_start, entry->surface, surf_end - surf_start );
138
if (result == 0 && entry->surface[ surf_end - surf_start ] != EOS)
141
entry = (cache_entry_t *) entry->avl_node.left;
143
entry = (cache_entry_t *) entry->avl_node.right;
144
else /* Word found. */
146
reference_entry( entry );
147
current_entry = entry;
156
/*---------------------------------------------------------------------------*/
159
next_result_in_cache( void )
160
/* Return the next feature structure for the word found by "word_in_cache".
161
* Return NULL if no more feature structure exists. */
165
if (current_result >= current_entry->fs_count)
167
result = current_entry->fs_vector[ current_result ];
172
/*---------------------------------------------------------------------------*/
175
remove_entry_from_cache( void )
176
/* Delete an entry from cache. */
178
cache_entry_t *entry;
180
/* Remove first element from LRU list. */
182
first_ref = entry->next_ref;
183
if (first_ref != NULL)
184
first_ref->prev_ref = NULL;
188
/* Remove ENTRY from tree. */
189
remove_avl_node( (avl_node_t *) entry, (avl_node_t **) &cache_tree,
190
compare_cache_entries );
191
free_cache_entry( &entry );
194
/*---------------------------------------------------------------------------*/
197
enter_in_cache( string_t surf_start, string_t surf_end,
198
int_t fs_count, value_t fs_vector[] )
199
/* Enter the word in [SURF_START..SURF_END] in the cache.
200
* It has FS_COUNT feature structures, stored in FS_VECTOR[].
201
* Be sure that the word is not yet in the cache. */
203
cache_entry_t *cache_entry;
205
if (entry_count >= max_entry_count)
206
remove_entry_from_cache();
207
cache_entry = new_cache_entry( surf_start, surf_end, fs_count, fs_vector );
209
/* Enter entry in cache tree. */
210
insert_avl_node( (avl_node_t *) cache_entry, (avl_node_t **) &cache_tree,
211
compare_cache_entries );
213
/* Put entry at end of LRU table. */
214
if (last_ref != NULL)
215
last_ref->next_ref = cache_entry;
216
cache_entry->prev_ref = last_ref;
217
cache_entry->next_ref = NULL;
218
last_ref = cache_entry;
219
if (first_ref == NULL)
220
first_ref = cache_entry;
223
/*---------------------------------------------------------------------------*/
227
/* Remove all entries from the cache. */
229
while (entry_count > 0)
230
remove_entry_from_cache();
233
/*---------------------------------------------------------------------------*/
236
set_cache_size( int_t size )
237
/* Set maximum number of cache entries to SIZE. */
239
max_entry_count = size;
240
while (entry_count > max_entry_count)
241
remove_entry_from_cache();
244
/*---------------------------------------------------------------------------*/
247
get_cache_size( void )
248
/* Get actual number of cache entries. */
253
/*---------------------------------------------------------------------------*/
256
get_cache_maximum( void )
257
/* Get maximum number of cache entries. */
259
return max_entry_count;
262
/* End of file. =============================================================*/
added
removed
cache.c
