From b7c15c31519dc44c1f691e0466badd556ffe9423 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 18:18:56 +0200 Subject: Adding upstream version 3.7.10. Signed-off-by: Daniel Baumann --- src/util/ctable.c | 321 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 321 insertions(+) create mode 100644 src/util/ctable.c (limited to 'src/util/ctable.c') diff --git a/src/util/ctable.c b/src/util/ctable.c new file mode 100644 index 0000000..4993671 --- /dev/null +++ b/src/util/ctable.c @@ -0,0 +1,321 @@ +/*++ +/* NAME +/* ctable 3 +/* SUMMARY +/* cache manager +/* SYNOPSIS +/* #include +/* +/* CTABLE *ctable_create(limit, create, delete, context) +/* ssize_t limit; +/* void *(*create)(const char *key, void *context); +/* void (*delete)(void *value, void *context); +/* void *context; +/* +/* const void *ctable_locate(cache, key) +/* CTABLE *cache; +/* const char *key; +/* +/* const void *ctable_refresh(cache, key) +/* CTABLE *cache; +/* const char *key; +/* +/* const void *ctable_newcontext(cache, context) +/* CTABLE *cache; +/* void *context; +/* +/* void ctable_free(cache) +/* CTABLE *cache; +/* +/* void ctable_walk(cache, action) +/* CTABLE *cache; +/* void (*action)(const char *key, const void *value); +/* DESCRIPTION +/* This module maintains multiple caches. Cache items are purged +/* automatically when the number of items exceeds a configurable +/* limit. Caches never shrink. Each cache entry consists of a +/* string-valued lookup key and a generic data pointer value. +/* +/* ctable_create() creates a cache with the specified size limit, and +/* returns a pointer to the result. The create and delete arguments +/* specify pointers to call-back functions that create a value, given +/* a key, and delete a given value, respectively. The context argument +/* is passed on to the call-back routines. +/* The create() and delete() functions must not modify the cache. +/* +/* ctable_locate() looks up or generates the value that corresponds to +/* the specified key, and returns that value. +/* +/* ctable_refresh() flushes the value (if any) associated with +/* the specified key, and returns the same result as ctable_locate(). +/* +/* ctable_newcontext() updates the context that is passed on +/* to call-back routines. +/* +/* ctable_free() destroys the specified cache, including its contents. +/* +/* ctable_walk() iterates over all elements in the cache, and invokes +/* the action function for each cache element with the corresponding +/* key and value as arguments. This function is useful mainly for +/* cache performance debugging. +/* Note: the action() function must not modify the cache. +/* DIAGNOSTICS +/* Fatal errors: out of memory. Panic: interface violation. +/* LICENSE +/* .ad +/* .fi +/* The Secure Mailer license must be distributed with this software. +/* AUTHOR(S) +/* Wietse Venema +/* IBM T.J. Watson Research +/* P.O. Box 704 +/* Yorktown Heights, NY 10598, USA +/*--*/ + +/* System library. */ + +#include +#include +#include + +/* Utility library. */ + +#include +#include +#include +#include +#include + + /* + * Cache entries are kept in most-recently used order. We use a hash table + * to quickly locate cache entries. + */ +#define CTABLE_ENTRY struct ctable_entry + +struct ctable_entry { + RING ring; /* MRU linkage */ + const char *key; /* lookup key */ + void *value; /* corresponding value */ +}; + +#define RING_TO_CTABLE_ENTRY(ring_ptr) \ + RING_TO_APPL(ring_ptr, CTABLE_ENTRY, ring) +#define RING_PTR_OF(x) (&((x)->ring)) + +struct ctable { + HTABLE *table; /* table with key, ctable_entry pairs */ + size_t limit; /* max nr of entries */ + size_t used; /* current nr of entries */ + CTABLE_CREATE_FN create; /* constructor */ + CTABLE_DELETE_FN delete; /* destructor */ + RING ring; /* MRU linkage */ + void *context; /* application context */ +}; + +#define CTABLE_MIN_SIZE 5 + +/* ctable_create - create empty cache */ + +CTABLE *ctable_create(ssize_t limit, CTABLE_CREATE_FN create, + CTABLE_DELETE_FN delete, void *context) +{ + CTABLE *cache = (CTABLE *) mymalloc(sizeof(CTABLE)); + const char *myname = "ctable_create"; + + if (limit < 1) + msg_panic("%s: bad cache limit: %ld", myname, (long) limit); + + cache->table = htable_create(limit); + cache->limit = (limit < CTABLE_MIN_SIZE ? CTABLE_MIN_SIZE : limit); + cache->used = 0; + cache->create = create; + cache->delete = delete; + ring_init(RING_PTR_OF(cache)); + cache->context = context; + return (cache); +} + +/* ctable_locate - look up or create cache item */ + +const void *ctable_locate(CTABLE *cache, const char *key) +{ + const char *myname = "ctable_locate"; + CTABLE_ENTRY *entry; + + /* + * If the entry is not in the cache, make sure there is room for a new + * entry and install it at the front of the MRU chain. Otherwise, move + * the entry to the front of the MRU chain if it is not already there. + * All this means that the cache never shrinks. + */ + if ((entry = (CTABLE_ENTRY *) htable_find(cache->table, key)) == 0) { + if (cache->used >= cache->limit) { + entry = RING_TO_CTABLE_ENTRY(ring_pred(RING_PTR_OF(cache))); + if (msg_verbose) + msg_info("%s: purge entry key %s", myname, entry->key); + ring_detach(RING_PTR_OF(entry)); + cache->delete(entry->value, cache->context); + htable_delete(cache->table, entry->key, (void (*) (void *)) 0); + } else { + entry = (CTABLE_ENTRY *) mymalloc(sizeof(CTABLE_ENTRY)); + cache->used++; + } + entry->value = cache->create(key, cache->context); + entry->key = htable_enter(cache->table, key, (void *) entry)->key; + ring_append(RING_PTR_OF(cache), RING_PTR_OF(entry)); + if (msg_verbose) + msg_info("%s: install entry key %s", myname, entry->key); + } else if (entry == RING_TO_CTABLE_ENTRY(ring_succ(RING_PTR_OF(cache)))) { + if (msg_verbose) + msg_info("%s: leave existing entry key %s", myname, entry->key); + } else { + ring_detach(RING_PTR_OF(entry)); + ring_append(RING_PTR_OF(cache), RING_PTR_OF(entry)); + if (msg_verbose) + msg_info("%s: move existing entry key %s", myname, entry->key); + } + return (entry->value); +} + +/* ctable_refresh - page-in fresh data for given key */ + +const void *ctable_refresh(CTABLE *cache, const char *key) +{ + const char *myname = "ctable_refresh"; + CTABLE_ENTRY *entry; + + /* Materialize entry if missing. */ + if ((entry = (CTABLE_ENTRY *) htable_find(cache->table, key)) == 0) + return ctable_locate(cache, key); + + /* Otherwise, refresh its content. */ + cache->delete(entry->value, cache->context); + entry->value = cache->create(key, cache->context); + + /* Update its MRU linkage. */ + if (entry != RING_TO_CTABLE_ENTRY(ring_succ(RING_PTR_OF(cache)))) { + ring_detach(RING_PTR_OF(entry)); + ring_append(RING_PTR_OF(cache), RING_PTR_OF(entry)); + } + if (msg_verbose) + msg_info("%s: refresh entry key %s", myname, entry->key); + return (entry->value); +} + +/* ctable_newcontext - update call-back context */ + +void ctable_newcontext(CTABLE *cache, void *context) +{ + cache->context = context; +} + +static CTABLE *ctable_free_cache; + +/* ctable_free_callback - callback function */ + +static void ctable_free_callback(void *ptr) +{ + CTABLE_ENTRY *entry = (CTABLE_ENTRY *) ptr; + + ctable_free_cache->delete(entry->value, ctable_free_cache->context); + myfree((void *) entry); +} + +/* ctable_free - destroy cache and contents */ + +void ctable_free(CTABLE *cache) +{ + CTABLE *saved_cache = ctable_free_cache; + + /* + * XXX the hash table does not pass application context so we have to + * store it in a global variable. + */ + ctable_free_cache = cache; + htable_free(cache->table, ctable_free_callback); + myfree((void *) cache); + ctable_free_cache = saved_cache; +} + +/* ctable_walk - iterate over all cache entries */ + +void ctable_walk(CTABLE *cache, void (*action) (const char *, const void *)) +{ + RING *entry = RING_PTR_OF(cache); + + /* Walking down the MRU chain is less work than using ht_walk(). */ + + while ((entry = ring_succ(entry)) != RING_PTR_OF(cache)) + action((RING_TO_CTABLE_ENTRY(entry)->key), + (RING_TO_CTABLE_ENTRY(entry)->value)); +} + +#ifdef TEST + + /* + * Proof-of-concept test program. Read keys from stdin, ask for values not + * in cache. + */ +#include +#include +#include +#include +#include + +#define STR(x) vstring_str(x) + +static void *ask(const char *key, void *context) +{ + VSTRING *data_buf = (VSTRING *) context; + + vstream_printf("ask: %s = ", key); + vstream_fflush(VSTREAM_OUT); + if (vstring_get_nonl(data_buf, VSTREAM_IN) == VSTREAM_EOF) + vstream_longjmp(VSTREAM_IN, 1); + if (!isatty(0)) { + vstream_printf("%s\n", STR(data_buf)); + vstream_fflush(VSTREAM_OUT); + } + return (mystrdup(STR(data_buf))); +} + +static void drop(void *data, void *unused_context) +{ + myfree(data); +} + +int main(int unused_argc, char **argv) +{ + VSTRING *key_buf; + VSTRING *data_buf; + CTABLE *cache; + const char *value; + + msg_vstream_init(argv[0], VSTREAM_ERR); + key_buf = vstring_alloc(100); + data_buf = vstring_alloc(100); + cache = ctable_create(1, ask, drop, (void *) data_buf); + msg_verbose = 1; + vstream_control(VSTREAM_IN, CA_VSTREAM_CTL_EXCEPT, CA_VSTREAM_CTL_END); + + if (vstream_setjmp(VSTREAM_IN) == 0) { + for (;;) { + vstream_printf("key = "); + vstream_fflush(VSTREAM_OUT); + if (vstring_get_nonl(key_buf, VSTREAM_IN) == VSTREAM_EOF) + vstream_longjmp(VSTREAM_IN, 1); + if (!isatty(0)) { + vstream_printf("%s\n", STR(key_buf)); + vstream_fflush(VSTREAM_OUT); + } + value = ctable_locate(cache, STR(key_buf)); + vstream_printf("result: %s\n", value); + } + } + ctable_free(cache); + vstring_free(key_buf); + vstring_free(data_buf); + return (0); +} + +#endif -- cgit v1.2.3