1/*++
2/* NAME
3/*	ctable 3
4/* SUMMARY
5/*	cache manager
6/* SYNOPSIS
7/*	#include <ctable.h>
8/*
9/*	CTABLE	*ctable_create(limit, create, delete, context)
10/*	int	limit;
11/*	void	*(*create)(const char *key, void *context);
12/*	void	(*delete)(void *value, void *context);
13/*	void	*context;
14/*
15/*	const void *ctable_locate(cache, key)
16/*	CTABLE	*cache;
17/*	const char *key;
18/*
19/*	const void *ctable_refresh(cache, key)
20/*	CTABLE	*cache;
21/*	const char *key;
22/*
23/*	const void *ctable_newcontext(cache, context)
24/*	CTABLE	*cache;
25/*	void	*context;
26/*
27/*	void	ctable_free(cache)
28/*	CTABLE	*cache;
29/*
30/*	void	ctable_walk(cache, action)
31/*	CTABLE	*cache;
32/*	void	(*action)(const char *key, const void *value);
33/* DESCRIPTION
34/*	This module maintains multiple caches. Cache items are purged
35/*	automatically when the number of items exceeds a configurable
36/*	limit. Caches never shrink. Each cache entry consists of a
37/*	string-valued lookup key and a generic data pointer value.
38/*
39/*	ctable_create() creates a cache with the specified size limit, and
40/*	returns a pointer to the result. The create and delete arguments
41/*	specify pointers to call-back functions that create a value, given
42/*	a key, and delete a given value, respectively. The context argument
43/*	is passed on to the call-back routines.
44/*	The create() and delete() functions must not modify the cache.
45/*
46/*	ctable_locate() looks up or generates the value that corresponds to
47/*	the specified key, and returns that value.
48/*
49/*	ctable_refresh() flushes the value (if any) associated with
50/*	the specified key, and returns the same result as ctable_locate().
51/*
52/*	ctable_newcontext() updates the context that is passed on
53/*	to call-back routines.
54/*
55/*	ctable_free() destroys the specified cache, including its contents.
56/*
57/*	ctable_walk() iterates over all elements in the cache, and invokes
58/*	the action function for each cache element with the corresponding
59/*	key and value as arguments. This function is useful mainly for
60/*	cache performance debugging.
61/*	Note: the action() function must not modify the cache.
62/* DIAGNOSTICS
63/*	Fatal errors: out of memory. Panic: interface violation.
64/* LICENSE
65/* .ad
66/* .fi
67/*	The Secure Mailer license must be distributed with this software.
68/* AUTHOR(S)
69/*	Wietse Venema
70/*	IBM T.J. Watson Research
71/*	P.O. Box 704
72/*	Yorktown Heights, NY 10598, USA
73/*--*/
74
75/* System library. */
76
77#include <sys_defs.h>
78#include <stdlib.h>
79#include <stddef.h>
80
81/* Utility library. */
82
83#include <msg.h>
84#include <mymalloc.h>
85#include <ring.h>
86#include <htable.h>
87#include <ctable.h>
88
89 /*
90  * Cache entries are kept in most-recently used order. We use a hash table
91  * to quickly locate cache entries.
92  */
93#define	CTABLE_ENTRY struct ctable_entry
94
95struct ctable_entry {
96    RING    ring;			/* MRU linkage */
97    const char *key;			/* lookup key */
98    void   *value;			/* corresponding value */
99};
100
101#define RING_TO_CTABLE_ENTRY(ring_ptr)	\
102	RING_TO_APPL(ring_ptr, CTABLE_ENTRY, ring)
103#define RING_PTR_OF(x)	(&((x)->ring))
104
105struct ctable {
106    HTABLE *table;			/* table with key, ctable_entry pairs */
107    unsigned limit;			/* max nr of entries */
108    unsigned used;			/* current nr of entries */
109    CTABLE_CREATE_FN create;		/* constructor */
110    CTABLE_DELETE_FN delete;		/* destructor */
111    RING    ring;			/* MRU linkage */
112    void   *context;			/* application context */
113};
114
115#define CTABLE_MIN_SIZE	5
116
117/* ctable_create - create empty cache */
118
119CTABLE *ctable_create(int limit, CTABLE_CREATE_FN create,
120		              CTABLE_DELETE_FN delete, void *context)
121{
122    CTABLE *cache = (CTABLE *) mymalloc(sizeof(CTABLE));
123    const char *myname = "ctable_create";
124
125    if (limit < 1)
126	msg_panic("%s: bad cache limit: %d", myname, limit);
127
128    cache->table = htable_create(limit);
129    cache->limit = (limit < CTABLE_MIN_SIZE ? CTABLE_MIN_SIZE : limit);
130    cache->used = 0;
131    cache->create = create;
132    cache->delete = delete;
133    ring_init(RING_PTR_OF(cache));
134    cache->context = context;
135    return (cache);
136}
137
138/* ctable_locate - look up or create cache item */
139
140const void *ctable_locate(CTABLE *cache, const char *key)
141{
142    const char *myname = "ctable_locate";
143    CTABLE_ENTRY *entry;
144
145    /*
146     * If the entry is not in the cache, make sure there is room for a new
147     * entry and install it at the front of the MRU chain. Otherwise, move
148     * the entry to the front of the MRU chain if it is not already there.
149     * All this means that the cache never shrinks.
150     */
151    if ((entry = (CTABLE_ENTRY *) htable_find(cache->table, key)) == 0) {
152	if (cache->used >= cache->limit) {
153	    entry = RING_TO_CTABLE_ENTRY(ring_pred(RING_PTR_OF(cache)));
154	    if (msg_verbose)
155		msg_info("%s: purge entry key %s", myname, entry->key);
156	    ring_detach(RING_PTR_OF(entry));
157	    cache->delete(entry->value, cache->context);
158	    htable_delete(cache->table, entry->key, (void (*) (char *)) 0);
159	} else {
160	    entry = (CTABLE_ENTRY *) mymalloc(sizeof(CTABLE_ENTRY));
161	    cache->used++;
162	}
163	entry->value = cache->create(key, cache->context);
164	entry->key = htable_enter(cache->table, key, (char *) entry)->key;
165	ring_append(RING_PTR_OF(cache), RING_PTR_OF(entry));
166	if (msg_verbose)
167	    msg_info("%s: install entry key %s", myname, entry->key);
168    } else if (entry == RING_TO_CTABLE_ENTRY(ring_succ(RING_PTR_OF(cache)))) {
169	if (msg_verbose)
170	    msg_info("%s: leave existing entry key %s", myname, entry->key);
171    } else {
172	ring_detach(RING_PTR_OF(entry));
173	ring_append(RING_PTR_OF(cache), RING_PTR_OF(entry));
174	if (msg_verbose)
175	    msg_info("%s: move existing entry key %s", myname, entry->key);
176    }
177    return (entry->value);
178}
179
180/* ctable_refresh - page-in fresh data for given key */
181
182const void *ctable_refresh(CTABLE *cache, const char *key)
183{
184    const char *myname = "ctable_refresh";
185    CTABLE_ENTRY *entry;
186
187    /* Materialize entry if missing. */
188    if ((entry = (CTABLE_ENTRY *) htable_find(cache->table, key)) == 0)
189	return ctable_locate(cache, key);
190
191    /* Otherwise, refresh its content. */
192    cache->delete(entry->value, cache->context);
193    entry->value = cache->create(key, cache->context);
194
195    /* Update its MRU linkage. */
196    if (entry != RING_TO_CTABLE_ENTRY(ring_succ(RING_PTR_OF(cache)))) {
197	ring_detach(RING_PTR_OF(entry));
198	ring_append(RING_PTR_OF(cache), RING_PTR_OF(entry));
199    }
200    if (msg_verbose)
201	msg_info("%s: refresh entry key %s", myname, entry->key);
202    return (entry->value);
203}
204
205/* ctable_newcontext - update call-back context */
206
207void    ctable_newcontext(CTABLE *cache, void *context)
208{
209    cache->context = context;
210}
211
212static CTABLE *ctable_free_cache;
213
214/* ctable_free_callback - callback function */
215
216static void ctable_free_callback(char *ptr)
217{
218    CTABLE_ENTRY *entry = (CTABLE_ENTRY *) ptr;
219
220    ctable_free_cache->delete(entry->value, ctable_free_cache->context);
221    myfree((char *) entry);
222}
223
224/* ctable_free - destroy cache and contents */
225
226void    ctable_free(CTABLE *cache)
227{
228    CTABLE *saved_cache = ctable_free_cache;
229
230    /*
231     * XXX the hash table does not pass application context so we have to
232     * store it in a global variable.
233     */
234    ctable_free_cache = cache;
235    htable_free(cache->table, ctable_free_callback);
236    myfree((char *) cache);
237    ctable_free_cache = saved_cache;
238}
239
240/* ctable_walk - iterate over all cache entries */
241
242void    ctable_walk(CTABLE *cache, void (*action) (const char *, const void *))
243{
244    RING   *entry = RING_PTR_OF(cache);
245
246    /* Walking down the MRU chain is less work than using ht_walk(). */
247
248    while ((entry = ring_succ(entry)) != RING_PTR_OF(cache))
249	action((RING_TO_CTABLE_ENTRY(entry)->key),
250	       (RING_TO_CTABLE_ENTRY(entry)->value));
251}
252
253#ifdef TEST
254
255 /*
256  * Proof-of-concept test program. Read keys from stdin, ask for values not
257  * in cache.
258  */
259#include <unistd.h>
260#include <vstream.h>
261#include <vstring.h>
262#include <vstring_vstream.h>
263#include <msg_vstream.h>
264
265#define STR(x)	vstring_str(x)
266
267static void *ask(const char *key, void *context)
268{
269    VSTRING *data_buf = (VSTRING *) context;
270
271    vstream_printf("ask: %s = ", key);
272    vstream_fflush(VSTREAM_OUT);
273    if (vstring_get_nonl(data_buf, VSTREAM_IN) == VSTREAM_EOF)
274	vstream_longjmp(VSTREAM_IN, 1);
275    if (!isatty(0)) {
276	vstream_printf("%s\n", STR(data_buf));
277	vstream_fflush(VSTREAM_OUT);
278    }
279    return (mystrdup(STR(data_buf)));
280}
281
282static void drop(void *data, void *unused_context)
283{
284    myfree(data);
285}
286
287int     main(int unused_argc, char **argv)
288{
289    VSTRING *key_buf;
290    VSTRING *data_buf;
291    CTABLE *cache;
292    const char *value;
293
294    msg_vstream_init(argv[0], VSTREAM_ERR);
295    key_buf = vstring_alloc(100);
296    data_buf = vstring_alloc(100);
297    cache = ctable_create(1, ask, drop, (void *) data_buf);
298    msg_verbose = 1;
299    vstream_control(VSTREAM_IN, VSTREAM_CTL_EXCEPT, VSTREAM_CTL_END);
300
301    if (vstream_setjmp(VSTREAM_IN) == 0) {
302	for (;;) {
303	    vstream_printf("key = ");
304	    vstream_fflush(VSTREAM_OUT);
305	    if (vstring_get_nonl(key_buf, VSTREAM_IN) == VSTREAM_EOF)
306		vstream_longjmp(VSTREAM_IN, 1);
307	    if (!isatty(0)) {
308		vstream_printf("%s\n", STR(key_buf));
309		vstream_fflush(VSTREAM_OUT);
310	    }
311	    value = ctable_locate(cache, STR(key_buf));
312	    vstream_printf("result: %s\n", value);
313	}
314    }
315    ctable_free(cache);
316    vstring_free(key_buf);
317    vstring_free(data_buf);
318    return (0);
319}
320
321#endif
322