summaryrefslogtreecommitdiffstats
path: root/src/util/ctable.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/util/ctable.c321
1 files changed, 321 insertions, 0 deletions
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.h>
+/*
+/* 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 <sys_defs.h>
+#include <stdlib.h>
+#include <stddef.h>
+
+/* Utility library. */
+
+#include <msg.h>
+#include <mymalloc.h>
+#include <ring.h>
+#include <htable.h>
+#include <ctable.h>
+
+ /*
+ * 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 <unistd.h>
+#include <vstream.h>
+#include <vstring.h>
+#include <vstring_vstream.h>
+#include <msg_vstream.h>
+
+#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
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-02 04:43:28 +0000