
/*
 * Wildcard table.
 *
 * This is a simple key-value table that associates a key (\0-terminated
 * string) with a value (void *).
 *
 * The keys can end in a wildcard ('*'), and then a lookup will match them as
 * expected.
 *
 * The current implementation is a very simple dynamic array, which is good
 * enough for a small number of elements (< 100), but we should optimize this
 * in the future, in particular to speed up lookups.
 *
 * If more than one entry matches, we do not guarantee any order, although
 * this may change in the future.
 */

#include <stdbool.h>   /* for bool */
#include <stdint.h>    /* for [u]int*_t */
#include <stdio.h>     /* snprintf() */
#include <stdlib.h>    /* for malloc() */
#include <string.h>    /* for memcpy()/memcmp() */
#include <sys/types.h> /* for size_t */

#include "hash.h"
#include "wtable.h"

/* Entry of the wildcard array. */
struct wentry {
	char *key;
	size_t key_len;

	void *value;
	bool in_use;
};

struct wtable {
	/* Final (non-wildcard) entries are kept in this hash. */
	hash_t *finals;

	/* Wildcarded entries are kept in this dynamic array. */
	struct wentry *wildcards;
	size_t ws_size;
	size_t ws_used_count;

	/* And we keep a cache of lookups into the wildcards array. */
	cache_t *wcache;

	void (*destructor)(void *);
};

/* Minimum table size. */
#define MIN_SIZE 10

struct wtable *wtable_create(void (*destructor)(void *))
{
	struct wtable *t = malloc(sizeof(struct wtable));
	if (t == NULL)
		return NULL;

	t->wildcards = NULL;
	t->wcache = NULL;

	t->finals = hash_create(destructor);
	if (t->finals == NULL)
		goto error;

	t->wildcards = malloc(sizeof(struct wentry) * MIN_SIZE);
	if (t->wildcards == NULL)
		goto error;

	memset(t->wildcards, 0, sizeof(struct wentry) * MIN_SIZE);

	t->wcache = cache_create();
	if (t->wcache == NULL)
		goto error;

	t->ws_size = MIN_SIZE;
	t->ws_used_count = 0;
	t->destructor = destructor;

	return t;

error:
	if (t->finals)
		hash_free(t->finals);
	if (t->wcache)
		cache_free(t->wcache);
	free(t->wildcards);
	free(t);
	return NULL;
}

void wtable_free(struct wtable *t)
{
	int i;
	struct wentry *entry;

	hash_free(t->finals);
	cache_free(t->wcache);

	for (i = 0; i < t->ws_size; i++) {
		entry = t->wildcards + i;
		if (entry->in_use) {
			t->destructor(entry->value);
			free(entry->key);
		}
	}

	free(t->wildcards);
	free(t);
}

/* Return the last position where s1 and s2 match. */
static unsigned int strlast(const char *s1, const char *s2)
{
	unsigned int i = 0;

	while (*s1 != '\0' && *s2 != '\0' && *s1 == *s2) {
		i++;
		s1++;
		s2++;
	}

	return i;
}

/* True if s is a wildcarded string, False otherwise. */
static bool is_wildcard(const char *s, size_t len)
{
	/* Note we only support wildcards at the end of the string for now. */
	return s[len - 1] == '*';
}

/* Checks if ws matches s.
 *
 * ws is a "wildcard string", which can end in a '*', in which case we compare
 * only up to that position, to do a wildcard matching.
 */
static bool ws_matches_s(const char *ws, size_t ws_len, const char *s,
                         size_t s_len, bool exact)
{
	if (ws == NULL || s == NULL)
		return false;

	if (exact || !is_wildcard(ws, ws_len)) {
		/* Exact match */
		if (ws_len != s_len)
			return false;
		return strcmp(ws, s) == 0;
	} else {
		/* Inexact match */
		return strlast(ws, s) >= ws_len - 1;
	}
}

/* Find the entry matching the given key.
 *
 * If exact == true, then the key must match exactly (no wildcard matching).
 * If first_free is not NULL, then it will be made to point to the first free
 * entry found during the lookup.
 *
 * Returns a pointer to the entry, or NULL if not found.
 */
static struct wentry *wildcards_find_entry(struct wtable *t, const char *key,
                                           bool exact,
                                           struct wentry **first_free)
{
	size_t key_len;
	size_t pos;
	struct wentry *entry;
	bool found_free = false;

	key_len = strlen(key);

	for (pos = 0; pos < t->ws_size; pos++) {
		entry = t->wildcards + pos;
		if (!entry->in_use) {
			if (!found_free && first_free) {
				*first_free = entry;
				found_free = true;
			}
			continue;

		} else if (ws_matches_s(entry->key, entry->key_len, key,
		                        key_len, exact)) {
			/* The key matches. */
			return entry;
		}
	}

	/* No match. */
	return NULL;
}

void *wtable_get(struct wtable *t, const char *key)
{
	void *value;
	struct wentry *entry;

	/* Do an exact lookup first. */
	value = hash_get(t->finals, key);
	if (value)
		return value;

	/* Then see if we can find it in the wcache */
	if (cache_get(t->wcache, key, &value))
		return value;

	/* And then walk the wildcards array. */
	entry = wildcards_find_entry(t, key, false, NULL);
	if (entry) {
		cache_set(t->wcache, key, entry->value);
		return entry->value;
	}

	/* Cache the negative result as well. */
	cache_set(t->wcache, key, NULL);

	return NULL;
}

/* Set on our wildcards table.
 * For internal use only.
 * It uses the key as-is (it won't copy it), and it won't resize the array
 * either. */
static bool wildcards_set(struct wtable *t, char *key, void *value)
{
	struct wentry *entry, *first_free;

	first_free = NULL;
	entry = wildcards_find_entry(t, key, true, &first_free);

	if (entry) {
		/* Found a match, override the value. */
		free(entry->key);
		entry->key = key;
		t->destructor(entry->value);
		entry->value = value;
		return true;
	} else if (first_free) {
		/* We are inserting a new entry. */
		first_free->key = key;
		first_free->key_len = strlen(key);
		first_free->value = value;
		first_free->in_use = true;
		t->ws_used_count++;
		return true;
	}

	/* This should never happen, as we should always have space by the
	 * time this function is called. */
	return false;
}

static bool resize_table(struct wtable *t, size_t new_size)
{
	size_t i;
	struct wentry *old_wildcards, *e;
	size_t old_size;

	if (new_size < MIN_SIZE) {
		/* Do not resize below the minimum size. */
		return true;
	}

	old_wildcards = t->wildcards;
	old_size = t->ws_size;

	t->wildcards = malloc(sizeof(struct wentry) * new_size);
	if (t->wildcards == NULL)
		return false;

	memset(t->wildcards, 0, sizeof(struct wentry) * new_size);
	t->ws_size = new_size;
	t->ws_used_count = 0;

	/* Insert the old entries into the new table. */
	for (i = 0; i < old_size; i++) {
		e = old_wildcards + i;
		if (e->in_use) {
			wildcards_set(t, e->key, e->value);
		}
	}

	free(old_wildcards);

	/* Keep the cache the same size as our table, which works reasonably
	 * well in practise */
	cache_resize(t->wcache, new_size);

	return true;
}

bool wtable_set(struct wtable *t, const char *key, void *value)
{
	if (is_wildcard(key, strlen(key))) {
		if ((t->ws_size - t->ws_used_count) <= 1) {
			/* If we only have one entry left, grow by 30%, plus
			 * one to make sure we always increase even if the
			 * percentage isn't enough. */
			if (!resize_table(t, t->ws_size * 1.3 + 1))
				return false;
		}

		/* Invalidate the cache. We could be smart and walk it,
		 * removing only the negative hits, but it's also more
		 * expensive */
		cache_invalidate(t->wcache);

		return wildcards_set(t, strdup(key), value);
	} else {
		return hash_set(t->finals, key, value);
	}
}

bool wtable_del(struct wtable *t, const char *key)
{
	struct wentry *entry;

	if (is_wildcard(key, strlen(key))) {
		entry = wildcards_find_entry(t, key, true, NULL);

		if (!entry) {
			/* Key not found. */
			return false;
		}

		/* Mark the entry as free. */
		free(entry->key);
		entry->key = NULL;
		entry->key_len = 0;
		t->destructor(entry->value);
		entry->value = NULL;
		entry->in_use = false;

		t->ws_used_count--;

		/* Shrink if the table is less than 60% occupied. */
		if (t->ws_size > MIN_SIZE &&
		    (float)t->ws_used_count / t->ws_size < 0.6) {
			if (!resize_table(t, t->ws_used_count + 3))
				return false;
		}

		/* Invalidate the cache. We could be smart and walk it,
		 * removing only the positive hits, but it's also more
		 * expensive */
		cache_invalidate(t->wcache);

		return true;
	} else {
		return hash_del(t->finals, key);
	}
}
