aboutsummaryrefslogtreecommitdiff
path: root/tests/lru_cache
diff options
context:
space:
mode:
Diffstat (limited to 'tests/lru_cache')
-rw-r--r--tests/lru_cache/Makefile21
-rw-r--r--tests/lru_cache/cache.c221
-rw-r--r--tests/lru_cache/cache.h31
-rw-r--r--tests/lru_cache/main.c191
4 files changed, 464 insertions, 0 deletions
diff --git a/tests/lru_cache/Makefile b/tests/lru_cache/Makefile
new file mode 100644
index 000000000..aa3a2cb89
--- /dev/null
+++ b/tests/lru_cache/Makefile
@@ -0,0 +1,21 @@
+CC=gcc
+
+CFLAGS+=-W -Werror -Wall -Wextra -std=c99 \
+ -D_FORTIFY_SOURCE=2 -fstack-protector -g \
+ -Wformat=2 -pedantic -pedantic-errors \
+ -D_GNU_SOURCE=1 -D_BSD_SOURCE=1 \
+ -I../../src
+
+LDFLAGS+=-pthread
+
+cache: main.o cache.o
+ $(CC) $(CPPFLAGS) $(CFLAGS) $(LDFLAGS) main.o cache.o -o cache
+
+main.o: main.c
+ $(CC) $(CPPFLAGS) $(CFLAGS) -c main.c -o main.o
+
+cache.o: cache.c
+ $(CC) $(CPPFLAGS) $(CFLAGS) -c cache.c -o cache.o
+
+clean:
+ rm -f cache *.o
diff --git a/tests/lru_cache/cache.c b/tests/lru_cache/cache.c
new file mode 100644
index 000000000..632c55862
--- /dev/null
+++ b/tests/lru_cache/cache.c
@@ -0,0 +1,221 @@
+/*
+ * =====================================================================================
+ *
+ * Filename: cache.c
+ *
+ * Description: A simple cache
+ *
+ * Version: 1.0
+ * Created: 04/11/2013 02:31:02 PM
+ * Revision: none
+ * Compiler: gcc
+ *
+ * Author: Oliver Lorenz (ol), olli@olorenz.org
+ * Company: https://olorenz.org
+ * License: This is licensed under the same terms as uthash itself
+ *
+ * =====================================================================================
+ */
+
+#include <errno.h>
+#include <pthread.h>
+#include <stdlib.h>
+#include "cache.h"
+#include "uthash.h"
+
+/**
+ * A cache entry
+ */
+struct foo_cache_entry {
+ char *key; /**<The key */
+ void *data; /**<Payload */
+ UT_hash_handle hh; /**<Hash Handle for uthash */
+};
+#define KEY_MAX_LENGTH 32
+
+/**
+ * A cache object
+ */
+struct foo_cache {
+ size_t max_entries; /**<Amount of entries this cache object can hold */
+ pthread_rwlock_t cache_lock; /**<A lock for concurrent access */
+ struct foo_cache_entry *entries; /**<Head pointer for uthash */
+ void (*free_cb) (void *element);/**<Callback function to free cache entries */
+};
+
+/** Creates a new cache object
+
+ @param dst
+ Where the newly allocated cache object will be stored in
+
+ @param capacity
+ The maximum number of elements this cache object can hold
+
+ @return EINVAL if dst is NULL, ENOMEM if malloc fails, 0 otherwise
+*/
+int foo_cache_create(struct foo_cache **dst, const size_t capacity,
+ void (*free_cb) (void *element))
+{
+ struct foo_cache *new = NULL;
+ int rv;
+
+ if (!dst)
+ return EINVAL;
+
+ if ((new = malloc(sizeof(*new))) == NULL)
+ return ENOMEM;
+
+ if ((rv = pthread_rwlock_init(&(new->cache_lock), NULL)) != 0)
+ goto err_out;
+
+ new->max_entries = capacity;
+ new->entries = NULL;
+ new->free_cb = free_cb;
+ *dst = new;
+ return 0;
+
+err_out:
+ if (new)
+ free(new);
+ return rv;
+}
+
+/** Frees an allocated cache object
+
+ @param cache
+ The cache object to free
+
+ @param keep_data
+ Whether to free contained data or just delete references to it
+
+ @return EINVAL if cache is NULL, 0 otherwise
+*/
+int foo_cache_delete(struct foo_cache *cache, int keep_data)
+{
+ struct foo_cache_entry *entry, *tmp;
+ int rv;
+
+ if (!cache)
+ return EINVAL;
+
+ rv = pthread_rwlock_wrlock(&(cache->cache_lock));
+ if (rv)
+ return rv;
+
+ if (keep_data) {
+ HASH_CLEAR(hh, cache->entries);
+ } else {
+ HASH_ITER(hh, cache->entries, entry, tmp) {
+ HASH_DEL(cache->entries, entry);
+ if (cache->free_cb)
+ cache->free_cb(entry->data);
+ free(entry);
+ }
+ }
+ (void)pthread_rwlock_unlock(&(cache->cache_lock));
+ (void)pthread_rwlock_destroy(&(cache->cache_lock));
+ free(cache);
+ cache = NULL;
+ return 0;
+}
+
+/** Checks if a given key is in the cache
+
+ @param cache
+ The cache object
+
+ @param key
+ The key to look-up
+
+ @param result
+ Where to store the result if key is found.
+
+ A warning: Even though result is just a pointer,
+ you have to call this function with a **ptr,
+ otherwise this will blow up in your face.
+
+ @return EINVAL if cache is NULL, 0 otherwise
+*/
+int foo_cache_lookup(struct foo_cache *cache, char *key, void *result)
+{
+ int rv;
+ struct foo_cache_entry *tmp = NULL;
+ char **dirty_hack = result;
+
+ if (!cache || !key || !result)
+ return EINVAL;
+
+ rv = pthread_rwlock_wrlock(&(cache->cache_lock));
+ if (rv)
+ return rv;
+
+ HASH_FIND_STR(cache->entries, key, tmp);
+ if (tmp) {
+ size_t key_len = strnlen(tmp->key, KEY_MAX_LENGTH);
+ HASH_DELETE(hh, cache->entries, tmp);
+ HASH_ADD_KEYPTR(hh, cache->entries, tmp->key, key_len, tmp);
+ *dirty_hack = tmp->data;
+ } else {
+ *dirty_hack = result = NULL;
+ }
+ rv = pthread_rwlock_unlock(&(cache->cache_lock));
+ return rv;
+}
+
+/** Inserts a given <key, value> pair into the cache
+
+ @param cache
+ The cache object
+
+ @param key
+ The key that identifies <value>
+
+ @param data
+ Data associated with <key>
+
+ @return EINVAL if cache is NULL, ENOMEM if malloc fails, 0 otherwise
+*/
+int foo_cache_insert(struct foo_cache *cache, char *key, void *data)
+{
+ struct foo_cache_entry *entry = NULL;
+ struct foo_cache_entry *tmp_entry = NULL;
+ size_t key_len = 0;
+ int rv;
+
+ if (!cache || !data)
+ return EINVAL;
+
+ if ((entry = malloc(sizeof(*entry))) == NULL)
+ return ENOMEM;
+
+ if ((rv = pthread_rwlock_wrlock(&(cache->cache_lock))) != 0)
+ goto err_out;
+
+ entry->key = key;
+ entry->data = data;
+ key_len = strnlen(entry->key, KEY_MAX_LENGTH);
+ HASH_ADD_KEYPTR(hh, cache->entries, entry->key, key_len, entry);
+
+ if (HASH_COUNT(cache->entries) >= cache->max_entries) {
+ HASH_ITER(hh, cache->entries, entry, tmp_entry) {
+ HASH_DELETE(hh, cache->entries, entry);
+ if (cache->free_cb)
+ cache->free_cb(entry->data);
+ else
+ free(entry->data);
+ /* free(key->key) if data has been copied */
+ free(entry);
+ break;
+ }
+ }
+
+ rv = pthread_rwlock_unlock(&(cache->cache_lock));
+ return rv;
+
+err_out:
+ if (entry)
+ free(entry);
+ (void)pthread_rwlock_unlock(&(cache->cache_lock));
+ return rv;
+
+}
diff --git a/tests/lru_cache/cache.h b/tests/lru_cache/cache.h
new file mode 100644
index 000000000..350576d4f
--- /dev/null
+++ b/tests/lru_cache/cache.h
@@ -0,0 +1,31 @@
+/*
+ * =====================================================================================
+ *
+ * Filename: cache.h
+ *
+ * Description: A simple cache
+ *
+ * Version: 1.0
+ * Created: 04/11/2013 02:30:46 PM
+ * Revision: none
+ * Compiler: gcc
+ *
+ * Author: Oliver Lorenz (ol), olli@olorenz.org
+ * Company: https://olorenz.org
+ * License: This is licensed under the same terms as uthash itself
+ *
+ * =====================================================================================
+ */
+
+#ifndef _CACHE_
+#define _CACHE_
+
+struct foo_cache;
+
+extern int foo_cache_create(struct foo_cache **dst, const size_t capacity,
+ void (*free_cb) (void *element));
+extern int foo_cache_delete(struct foo_cache *cache, int keep_data);
+extern int foo_cache_lookup(struct foo_cache *cache, char *key, void *result);
+extern int foo_cache_insert(struct foo_cache *cache, char *key, void *data);
+
+#endif
diff --git a/tests/lru_cache/main.c b/tests/lru_cache/main.c
new file mode 100644
index 000000000..7f0eae2f2
--- /dev/null
+++ b/tests/lru_cache/main.c
@@ -0,0 +1,191 @@
+#include <errno.h>
+#include <pthread.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include "cache.h"
+
+#define MAX_RANDOM_ENTRIES 32
+
+struct key_record {
+ char *key;
+ char *value;
+};
+
+int generate_random_entry(struct key_record **entry);
+int generate_random_string(char **dst, const size_t len);
+void free_random_entry(void *entry);
+
+void *producer(void *arg)
+{
+ struct foo_cache *cache = arg;
+ int i;
+
+ for (i = 0; i < MAX_RANDOM_ENTRIES; i++) {
+ struct key_record *entry = NULL;
+ if (generate_random_entry(&entry)) {
+ fprintf(stderr, "generate_random_entry() failed\n");
+ continue;
+ }
+#if defined(DEBUG)
+ printf("Random Entry:\n");
+ printf(" key: %s\n", entry->key);
+ printf(" Key: %s\n", entry->value);
+#else
+ printf("inserted %s (%d)\n", entry->key,
+ (int)strlen(entry->key));
+#endif
+ if (foo_cache_insert(cache, entry->key, entry)) {
+ fprintf(stderr, "foo_cache_insert() failed\n");
+ continue;
+ }
+ }
+
+ pthread_exit(NULL);
+}
+
+void *consumer(void *arg)
+{
+ struct foo_cache *cache = arg;
+ struct key_record *result = NULL;
+ char *buffer = malloc(64);
+ char key[33];
+ int stop = 0;
+
+ if (!buffer)
+ goto out;
+
+ /* give producer time to populate the cache */
+ sleep(2);
+ printf("\n\n");
+
+ do {
+ memset(key, 0, 64);
+ result = NULL;
+
+ printf("Enter key for lookup: ");
+ fgets(buffer, sizeof(key), stdin);
+ sscanf(buffer, "%s\n", key);
+ /* read '\n' from stdin */
+ getchar();
+
+ if (strncmp(key, "exit", 4) == 0) {
+ stop = 1;
+ continue;
+ }
+
+ printf("Got key %s (%d)\n", key, (int)strlen(key));
+
+ if (foo_cache_lookup(cache, key, &result)) {
+ fprintf(stderr, "Could not retrieve key %s\n", key);
+ continue;
+ }
+
+ if (!result) {
+ printf("MISS\n");
+ continue;
+ }
+
+ printf("HIT\n");
+ printf("key: %s\n", result->key);
+ printf("key : %s\n", result->value);
+ } while (!stop);
+
+out:
+ if (buffer)
+ free(buffer);
+ pthread_exit(NULL);
+}
+
+int main()
+{
+ int rv;
+ struct foo_cache *cache = NULL;
+ pthread_t workers[2];
+
+ rv = foo_cache_create(&cache, MAX_RANDOM_ENTRIES / 2,
+ free_random_entry);
+ if (rv) {
+ fprintf(stderr, "Could not create cache\n");
+ exit(1);
+ }
+
+ (void)pthread_create(&workers[0], NULL, producer, (void *)cache);
+ (void)pthread_create(&workers[1], NULL, consumer, (void *)cache);
+
+ pthread_join(workers[0], NULL);
+ pthread_join(workers[1], NULL);
+
+ (void)foo_cache_delete(cache, 0);
+ return 0;
+}
+
+int generate_random_entry(struct key_record **entry)
+{
+ struct key_record *new = NULL;
+ char *key = NULL;
+ char *value = NULL;
+ int rv;
+
+ if (!entry)
+ return EINVAL;
+
+ rv = generate_random_string(&key, 33);
+ if (rv)
+ return rv;
+
+ rv = generate_random_string(&value, 129);
+ if (rv)
+ return rv;
+
+ if ((new = malloc(sizeof(*new))) == NULL) {
+ free(key);
+ free(value);
+ return ENOMEM;
+ }
+
+ new->key = key;
+ new->value = value;
+
+ *entry = new;
+ return 0;
+}
+
+int generate_random_string(char **dst, const size_t len)
+{
+ static const char alphanum[] =
+ "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
+ size_t i;
+ char *s;
+
+ if (!dst || len == 0)
+ return EINVAL;
+
+ if ((s = malloc(len)) == NULL)
+ return ENOMEM;
+
+ for (i = 0; i < len - 1; i++) {
+ s[i] = alphanum[rand() % (sizeof(alphanum) - 1)];
+ }
+
+ s[len - 1] = '\0';
+ *dst = s;
+ return 0;
+}
+
+void free_random_entry(void *entry)
+{
+#if defined(DEBUG)
+ fprintf(stderr, "In %s: entry @ %p\n", __func__, entry);
+#endif
+ struct key_record *record = entry;
+ if (!record)
+ return;
+ if (record->key)
+ free(record->key);
+ if (record->value)
+ free(record->value);
+ free(record);
+ record = NULL;
+}
Powered by cgit, Themed by Ted Yin.