Adding upstream version 3.8.5.upstream/3.8.5

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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