/* Copyright (c) 2011, Vsevolod Stakhov
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *       * Redistributions of source code must retain the above copyright
 *         notice, this list of conditions and the following disclaimer.
 *       * Redistributions in binary form must reproduce the above copyright
 *         notice, this list of conditions and the following disclaimer in the
 *         documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED ''AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL AUTHOR BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"
#include "kvstorage.h"
#include "main.h"
#include "radix.h"
#ifdef WITH_JUDY
#include <Judy.h>
#endif

#define MAX_EXPIRE_STEPS 10

/** Create new kv storage */
struct rspamd_kv_storage *
rspamd_kv_storage_new (gint id,
	const gchar *name,
	struct rspamd_kv_cache *cache,
	struct rspamd_kv_backend *backend,
	struct rspamd_kv_expire *expire,
	gsize max_elts,
	gsize max_memory,
	gboolean no_overwrite)
{
	struct rspamd_kv_storage *new;

	new = g_slice_alloc (sizeof (struct rspamd_kv_storage));
	new->elts = 0;
	new->memory = 0;

	new->cache = cache;
	new->backend = backend;
	new->expire = expire;

	new->max_elts = max_elts;
	new->max_memory = max_memory;

	new->id = id;

	new->no_overwrite = no_overwrite;

	if (name != NULL) {
		new->name = g_strdup (name);
	}
	else {
		/* Name is absent, use ID as name */
		new->name = g_malloc (sizeof ("18446744073709551616"));
		rspamd_snprintf (new->name, sizeof ("18446744073709551616"), "%d", id);
	}
#if ((GLIB_MAJOR_VERSION == 2) && (GLIB_MINOR_VERSION > 30))
	g_rw_lock_init (&new->rwlock);
#else
	g_static_rw_lock_init (&new->rwlock);
#endif


	/* Init structures */
	if (new->cache->init_func) {
		new->cache->init_func (new->cache);
	}
	if (new->backend && new->backend->init_func) {
		new->backend->init_func (new->backend);
	}
	if (new->expire && new->expire->init_func) {
		new->expire->init_func (new->expire);
	}

	return new;
}

/** Internal insertion to the kv storage from backend */
gboolean
rspamd_kv_storage_insert_cache (struct rspamd_kv_storage *storage,
	gpointer key,
	guint keylen,
	gpointer data,
	gsize len,
	gint flags,
	guint expire,
	struct rspamd_kv_element **pelt)
{
	gint steps = 0;
	struct rspamd_kv_element *elt;

	RW_W_LOCK (&storage->rwlock);
	/* Hard limit */
	if (storage->max_memory > 0) {
		if (len > storage->max_memory) {
			msg_info (
				"<%s>: trying to insert value of length %z while limit is %z",
				storage->name,
				len,
				storage->max_memory);
			RW_W_UNLOCK (&storage->rwlock);
			return FALSE;
		}

		/* Now check limits */
		while (storage->memory + len > storage->max_memory) {
			if (storage->expire) {
				storage->expire->step_func (storage->expire, storage, time (
						NULL), steps);
			}
			else {
				msg_warn (
					"<%s>: storage is full and no expire function is defined",
					storage->name);
			}
			if (++steps > MAX_EXPIRE_STEPS) {
				RW_W_UNLOCK (&storage->rwlock);
				msg_warn ("<%s>: cannot expire enough keys in storage",
					storage->name);
				return FALSE;
			}
		}
	}

	/* Insert elt to the cache */

	elt = storage->cache->insert_func (storage->cache, key, keylen, data, len);


	/* Copy data */
	elt->flags = flags;
	elt->expire = expire;

	if (pelt != NULL) {
		*pelt = elt;
	}

	/* Insert to the expire */
	if (storage->expire) {
		storage->expire->insert_func (storage->expire, elt);
	}

	storage->elts++;
	storage->memory += ELT_SIZE (elt);
	RW_W_UNLOCK (&storage->rwlock);

	return TRUE;
}

/** Insert new element to the kv storage */
gboolean
rspamd_kv_storage_insert (struct rspamd_kv_storage *storage,
	gpointer key,
	guint keylen,
	gpointer data,
	gsize len,
	gint flags,
	guint expire)
{
	gint steps = 0;
	struct rspamd_kv_element *elt;
	gboolean res = TRUE;
	glong longval;

	/* Hard limit */
	RW_W_LOCK (&storage->rwlock);
	if (storage->max_memory > 0) {
		if (len + sizeof (struct rspamd_kv_element) + keylen >=
			storage->max_memory) {
			msg_warn (
				"<%s>: trying to insert value of length %z while limit is %z",
				storage->name,
				len,
				storage->max_memory);
			RW_W_UNLOCK (&storage->rwlock);
			return FALSE;
		}

		/* Now check limits */
		while (storage->memory + len + keylen > storage->max_memory) {
			if (storage->expire) {
				storage->expire->step_func (storage->expire, storage, time (
						NULL), steps);
			}
			else {
				msg_warn (
					"<%s>: storage is full and no expire function is defined",
					storage->name);
			}
			if (++steps > MAX_EXPIRE_STEPS) {
				RW_W_UNLOCK (&storage->rwlock);
				msg_warn ("<%s>: cannot expire enough keys in storage",
					storage->name);
				return FALSE;
			}
		}
	}
	if (storage->max_elts > 0 && storage->elts > storage->max_elts) {
		/* More expire */
		steps = 0;
		while (storage->elts > storage->max_elts) {
			if (storage->expire) {
				storage->expire->step_func (storage->expire, storage, time (
						NULL), steps);
			}
			else {
				msg_warn (
					"<%s>: storage is full and no expire function is defined",
					storage->name);
			}
			if (++steps > MAX_EXPIRE_STEPS) {
				RW_W_UNLOCK (&storage->rwlock);
				msg_warn ("<%s>: cannot expire enough keys in storage",
					storage->name);
				return FALSE;
			}
		}
	}

	/* First try to search it in cache */

	elt = storage->cache->lookup_func (storage->cache, key, keylen);
	if (elt) {
		if (!storage->no_overwrite) {
			/* Remove old elt */
			if (storage->expire) {
				storage->expire->delete_func (storage->expire, elt);
			}
			storage->memory -= ELT_SIZE (elt);
			storage->cache->steal_func (storage->cache, elt);
			if (elt->flags & KV_ELT_DIRTY) {
				/* Element is in backend storage queue */
				elt->flags |= KV_ELT_NEED_FREE;
			}
			else {
				g_slice_free1 (ELT_SIZE (elt), elt);
			}
		}
		else {
			/* Just do incref and nothing more */
			if (storage->backend && storage->backend->incref_func) {
				if (storage->backend->incref_func (storage->backend, key,
					keylen)) {
					RW_W_UNLOCK (&storage->rwlock);
					return TRUE;
				}
				else {
					RW_W_UNLOCK (&storage->rwlock);
					return FALSE;
				}
			}
		}
	}

	/* Insert elt to the cache */

	/* First of all check element for integer */
	if (rspamd_strtol (data, len, &longval)) {
		elt = storage->cache->insert_func (storage->cache,
				key,
				keylen,
				&longval,
				sizeof (glong));
		if (elt == NULL) {
			return FALSE;
		}
		else {
			elt->flags |= KV_ELT_INTEGER;
		}
	}
	else {
		elt = storage->cache->insert_func (storage->cache,
				key,
				keylen,
				data,
				len);
		if (elt == NULL) {
			RW_W_UNLOCK (&storage->rwlock);
			return FALSE;
		}
	}

	elt->flags |= flags;
	elt->expire = expire;
	if (expire == 0) {
		elt->flags |= KV_ELT_PERSISTENT;
	}

	/* Place to the backend */
	if (storage->backend) {
		res =
			storage->backend->insert_func (storage->backend, key, keylen, elt);
	}

	/* Insert to the expire */
	if (storage->expire) {
		storage->expire->insert_func (storage->expire, elt);
	}

	storage->elts++;
	storage->memory += ELT_SIZE (elt);
	RW_W_UNLOCK (&storage->rwlock);

	return res;
}

/** Replace an element in the kv storage */
gboolean
rspamd_kv_storage_replace (struct rspamd_kv_storage *storage,
	gpointer key,
	guint keylen,
	struct rspamd_kv_element *elt)
{
	gboolean res = TRUE;
	gint steps = 0;

	/* Hard limit */
	if (storage->max_memory > 0) {
		if (elt->size > storage->max_memory) {
			msg_info (
				"<%s>: trying to replace value of length %z while limit is %z",
				storage->name,
				elt->size,
				storage->max_memory);
			return FALSE;
		}

		/* Now check limits */
		while (storage->memory + ELT_SIZE (elt) > storage->max_memory) {
			if (storage->expire) {
				RW_W_LOCK (&storage->rwlock);
				storage->expire->step_func (storage->expire, storage, time (
						NULL), steps);
				RW_W_UNLOCK (&storage->rwlock);
			}
			else {
				msg_warn (
					"<%s>: storage is full and no expire function is defined",
					storage->name);
			}
			if (++steps > MAX_EXPIRE_STEPS) {
				msg_warn ("<%s>: cannot expire enough keys in storage",
					storage->name);
				return FALSE;
			}
		}
	}

	RW_W_LOCK (&storage->rwlock);
	/* Insert elt to the cache */
	res = storage->cache->replace_func (storage->cache, key, keylen, elt);

	/* Place to the backend */
	if (res && storage->backend) {
		res =
			storage->backend->replace_func (storage->backend, key, keylen, elt);
	}
	RW_W_UNLOCK (&storage->rwlock);

	return res;
}

/** Increment value in kvstorage */
gboolean
rspamd_kv_storage_increment (struct rspamd_kv_storage *storage,
	gpointer key,
	guint keylen,
	glong *value)
{
	struct rspamd_kv_element *elt = NULL, *belt;
	glong *lp;

	/* First try to look at cache */
	RW_W_LOCK (&storage->rwlock);
	elt = storage->cache->lookup_func (storage->cache, key, keylen);

	if (elt == NULL && storage->backend) {
		belt = storage->backend->lookup_func (storage->backend, key, keylen);
		if (belt) {
			/* Put this element into cache */
			if ((belt->flags & KV_ELT_INTEGER) != 0) {
				RW_W_UNLOCK (&storage->rwlock);
				rspamd_kv_storage_insert_cache (storage, ELT_KEY (
						belt), keylen, ELT_DATA (belt),
					belt->size, belt->flags,
					belt->expire, &elt);
				RW_W_LOCK (&storage->rwlock);
			}
			if ((belt->flags & KV_ELT_DIRTY) == 0) {
				g_free (belt);
			}
		}
	}
	if (elt && (elt->flags & KV_ELT_INTEGER) != 0) {
		lp = &ELT_LONG (elt);
		/* Handle need expire here */
		if (elt->flags & KV_ELT_NEED_EXPIRE) {
			*lp = *value;
		}
		else {
			*lp += *value;
			*value = *lp;
		}
		elt->age = time (NULL);
		if (storage->backend) {
			if (storage->backend->replace_func (storage->backend, key, keylen,
				elt)) {
				RW_W_UNLOCK (&storage->rwlock);
				return TRUE;
			}
			else {
				RW_W_UNLOCK (&storage->rwlock);
				return FALSE;
			}
		}
		else {
			RW_W_UNLOCK (&storage->rwlock);
			return TRUE;
		}
	}

	RW_W_UNLOCK (&storage->rwlock);

	return FALSE;
}

/** Lookup an element inside kv storage */
struct rspamd_kv_element *
rspamd_kv_storage_lookup (struct rspamd_kv_storage *storage,
	gpointer key,
	guint keylen,
	time_t now)
{
	struct rspamd_kv_element *elt = NULL, *belt;

	/* First try to look at cache */
	RW_R_LOCK (&storage->rwlock);
	elt = storage->cache->lookup_func (storage->cache, key, keylen);

	/* Next look at the backend */
	if (elt == NULL && storage->backend) {
		belt = storage->backend->lookup_func (storage->backend, key, keylen);

		if (belt) {
			/* Put this element into cache */
			if ((belt->flags & KV_ELT_DIRTY) == 0) {
				belt->flags |= KV_ELT_NEED_INSERT;
				return belt;
			}
			else {
				elt = belt;
			}
		}
	}

	if (elt && (elt->flags & KV_ELT_PERSISTENT) == 0 && elt->expire > 0) {
		/* Check expiration */
		if (now - elt->age > (gint)elt->expire) {
			/* Set need expire as we have no write lock here */
			elt->flags |= KV_ELT_NEED_EXPIRE;
			elt = NULL;
		}
	}

	/* RWlock is still locked */
	return elt;
}

/** Expire an element from kv storage */
struct rspamd_kv_element *
rspamd_kv_storage_delete (struct rspamd_kv_storage *storage,
	gpointer key,
	guint keylen)
{
	struct rspamd_kv_element *elt;

	/* First delete key from cache */
	RW_W_LOCK (&storage->rwlock);
	elt = storage->cache->delete_func (storage->cache, key, keylen);

	/* Now delete from backend */
	if (storage->backend) {
		storage->backend->delete_func (storage->backend, key, keylen);
	}
	/* Notify expire */
	if (elt) {
		if (storage->expire) {
			storage->expire->delete_func (storage->expire, elt);
		}
		storage->elts--;
		storage->memory -= elt->size;
		if ((elt->flags & KV_ELT_DIRTY) != 0) {
			elt->flags |= KV_ELT_NEED_FREE;
		}
		else {
			g_slice_free1 (ELT_SIZE (elt), elt);
		}
	}

	RW_W_UNLOCK (&storage->rwlock);

	return elt;
}

/** Destroy kv storage */
void
rspamd_kv_storage_destroy (struct rspamd_kv_storage *storage)
{
	RW_W_LOCK (&storage->rwlock);
	if (storage->backend && storage->backend->destroy_func) {
		storage->backend->destroy_func (storage->backend);
	}
	if (storage->expire && storage->expire->destroy_func) {
		storage->expire->destroy_func (storage->expire);
	}
	if (storage->cache && storage->cache->destroy_func) {
		storage->cache->destroy_func (storage->cache);
	}

	g_free (storage->name);

	RW_W_UNLOCK (&storage->rwlock);
	g_slice_free1 (sizeof (struct rspamd_kv_storage), storage);
}

/** Insert array */
gboolean
rspamd_kv_storage_insert_array (struct rspamd_kv_storage *storage,
	gpointer key,
	guint keylen,
	guint elt_size,
	gpointer data,
	gsize len,
	gint flags,
	guint expire)
{
	struct rspamd_kv_element *elt;
	guint *es;
	gpointer arr_data;

	/* Make temporary copy */
	arr_data = g_slice_alloc (len + sizeof (guint));
	es = arr_data;
	*es = elt_size;
	memcpy (arr_data, (gchar *)data + sizeof (guint), len);
	if (!rspamd_kv_storage_insert_cache (storage, key, keylen, arr_data, len +
		sizeof (guint),
		flags, expire, &elt)) {
		g_slice_free1 (len + sizeof (guint), arr_data);
		return FALSE;
	}
	/* Now set special data of element */
	elt->flags |= KV_ELT_ARRAY;
	g_slice_free1 (len + sizeof (guint), arr_data);
	/* Place to the backend */

	if (storage->backend) {
		return storage->backend->insert_func (storage->backend, key, keylen,
				   elt);
	}

	return TRUE;
}

/** Set element inside array */
gboolean
rspamd_kv_storage_set_array (struct rspamd_kv_storage *storage,
	gpointer key,
	guint keylen,
	guint elt_num,
	gpointer data,
	gsize len,
	time_t now)
{
	struct rspamd_kv_element *elt;
	guint *es;
	gpointer target;

	elt = rspamd_kv_storage_lookup (storage, key, keylen, now);
	if (elt == NULL) {
		return FALSE;
	}

	if ((elt->flags & KV_ELT_ARRAY) == 0) {
		return FALSE;
	}
	/* Get element size */
	es = (guint *)ELT_DATA (elt);
	if (elt_num > (elt->size - sizeof (guint)) / (*es)) {
		/* Invalid index */
		return FALSE;
	}
	target = (gchar *)ELT_DATA (elt) + sizeof (guint) + (*es) * elt_num;
	if (len != *es) {
		/* Invalid size */
		return FALSE;
	}
	memcpy (target, data, len);
	/* Place to the backend */
	if (storage->backend) {
		return storage->backend->replace_func (storage->backend,
				   key,
				   keylen,
				   elt);
	}

	return TRUE;
}

/** Get element inside array */
gboolean
rspamd_kv_storage_get_array (struct rspamd_kv_storage *storage,
	gpointer key,
	guint keylen,
	guint elt_num,
	gpointer *data,
	gsize *len,
	time_t now)
{
	struct rspamd_kv_element *elt;
	guint *es;
	gpointer target;

	elt = rspamd_kv_storage_lookup (storage, key, keylen, now);
	if (elt == NULL) {
		return FALSE;
	}

	if ((elt->flags & KV_ELT_ARRAY) == 0) {
		return FALSE;
	}
	/* Get element size */
	es = (guint *)ELT_DATA (elt);
	if (elt_num > (elt->size - sizeof (guint)) / (*es)) {
		/* Invalid index */
		return FALSE;
	}
	target = ELT_DATA (elt) + sizeof (guint) + (*es) * elt_num;

	*len = *es;
	*data = target;

	return TRUE;
}

/**
 * LRU expire functions
 */

struct rspamd_kv_lru_expire {
	expire_init init_func;                      /*< this callback is called on kv storage initialization */
	expire_insert insert_func;                  /*< this callback is called when element is inserted */
	expire_step step_func;                      /*< this callback is used when cache is full */
	expire_delete delete_func;                  /*< this callback is called when an element is deleted */
	expire_destroy destroy_func;                /*< this callback is used for destroying all elements inside expire */

	TAILQ_HEAD (eltq, rspamd_kv_element) head;
};

/**
 * Insert an element into expire queue
 */
static void
rspamd_lru_insert (struct rspamd_kv_expire *e, struct rspamd_kv_element *elt)
{
	struct rspamd_kv_lru_expire *expire = (struct rspamd_kv_lru_expire *)e;

	/* Get a proper queue */
	TAILQ_INSERT_TAIL (&expire->head, elt, entry);
}
/**
 * Delete an element from expire queue
 */
static void
rspamd_lru_delete (struct rspamd_kv_expire *e, struct rspamd_kv_element *elt)
{
	struct rspamd_kv_lru_expire *expire = (struct rspamd_kv_lru_expire *)e;

	/* Unlink element */
	TAILQ_REMOVE (&expire->head, elt, entry);
}

/**
 * Expire elements
 */
static gboolean
rspamd_lru_expire_step (struct rspamd_kv_expire *e,
	struct rspamd_kv_storage *storage,
	time_t now,
	gboolean forced)
{
	struct rspamd_kv_lru_expire *expire = (struct rspamd_kv_lru_expire *)e;
	struct rspamd_kv_element *elt, *oldest_elt = NULL, *temp;
	time_t diff;
	gboolean res = FALSE;

	elt = TAILQ_FIRST (&expire->head);
	if (elt &&
		(forced || (elt->flags & (KV_ELT_PERSISTENT | KV_ELT_DIRTY)) == 0)) {
		diff = elt->expire - (now - elt->age);
		if (diff > 0 || (forced && elt->expire == 0)) {
			oldest_elt = elt;
		}
		else {
			/* This element is already expired */
			storage->cache->steal_func (storage->cache, elt);
			storage->memory -= ELT_SIZE (elt);
			storage->elts--;
			TAILQ_REMOVE (&expire->head, elt, entry);
			/* Free memory */
			if ((elt->flags & (KV_ELT_DIRTY | KV_ELT_NEED_INSERT)) != 0) {
				elt->flags |= KV_ELT_NEED_FREE;
			}
			else {
				g_slice_free1 (ELT_SIZE (elt), elt);
			}
			res = TRUE;
			/* Check other elements in this queue */
			TAILQ_FOREACH_SAFE (elt, &expire->head, entry, temp)
			{
				if ((!forced &&
					(elt->flags & (KV_ELT_PERSISTENT | KV_ELT_DIRTY)) != 0) ||
					(gint)elt->expire < (now - elt->age)) {
					break;
				}
				storage->memory -= ELT_SIZE (elt);
				storage->elts--;
				storage->cache->steal_func (storage->cache, elt);
				TAILQ_REMOVE (&expire->head, elt, entry);
				/* Free memory */
				if ((elt->flags & (KV_ELT_DIRTY | KV_ELT_NEED_INSERT)) != 0) {
					elt->flags |= KV_ELT_NEED_FREE;
				}
				else {
					g_slice_free1 (ELT_SIZE (elt), elt);
				}

			}
		}
	}

	if (!res && oldest_elt != NULL) {
		storage->memory -= ELT_SIZE (oldest_elt);
		storage->elts--;
		storage->cache->steal_func (storage->cache, oldest_elt);
		TAILQ_REMOVE (&expire->head, oldest_elt, entry);
		/* Free memory */
		if ((oldest_elt->flags & (KV_ELT_DIRTY | KV_ELT_NEED_INSERT)) != 0) {
			oldest_elt->flags |= KV_ELT_NEED_FREE;
		}
		else {
			g_slice_free1 (ELT_SIZE (oldest_elt), oldest_elt);
		}
	}

	return TRUE;
}

/**
 * Destroy LRU expire memory
 */
static void
rspamd_lru_destroy (struct rspamd_kv_expire *e)
{
	struct rspamd_kv_lru_expire *expire = (struct rspamd_kv_lru_expire *)e;

	g_slice_free1 (sizeof (struct rspamd_kv_lru_expire), expire);
}

/**
 * Create new LRU cache
 */
struct rspamd_kv_expire *
rspamd_lru_expire_new (void)
{
	struct rspamd_kv_lru_expire *new;

	new = g_slice_alloc (sizeof (struct rspamd_kv_lru_expire));
	TAILQ_INIT (&new->head);

	/* Set callbacks */
	new->init_func = NULL;
	new->insert_func = rspamd_lru_insert;
	new->delete_func = rspamd_lru_delete;
	new->step_func = rspamd_lru_expire_step;
	new->destroy_func = rspamd_lru_destroy;

	return (struct rspamd_kv_expire *)new;
}

/*
 * KV cache hash table
 */
struct rspamd_kv_hash_cache {
	cache_init init_func;                       /*< this callback is called on kv storage initialization */
	cache_insert insert_func;                   /*< this callback is called when element is inserted */
	cache_replace replace_func;                 /*< this callback is called when element is replace */
	cache_lookup lookup_func;                   /*< this callback is used for lookup of element */
	cache_delete delete_func;                   /*< this callback is called when an element is deleted */
	cache_steal steal_func;                     /*< this callback is used to replace duplicates in cache */
	cache_destroy destroy_func;                 /*< this callback is used for destroying all elements inside cache */
	GHashTable *hash;
};

/**
 * Insert an element inside cache
 */
static struct rspamd_kv_element *
rspamd_kv_hash_insert (struct rspamd_kv_cache *c,
	gpointer key,
	guint keylen,
	gpointer value,
	gsize len)
{
	struct rspamd_kv_element *elt;
	struct rspamd_kv_hash_cache *cache = (struct rspamd_kv_hash_cache *)c;
	struct rspamd_kv_element search_elt;

	search_elt.keylen = keylen;
	search_elt.p = key;

	if ((elt = g_hash_table_lookup (cache->hash, &search_elt)) == NULL) {
		elt = g_slice_alloc (
			sizeof (struct rspamd_kv_element) + len + keylen + 1);
		elt->age = time (NULL);
		elt->keylen = keylen;
		elt->size = len;
		elt->flags = 0;
		memcpy (ELT_KEY (elt),	key,   keylen + 1);
		memcpy (ELT_DATA (elt), value, len);
		elt->p = &elt->data;
		g_hash_table_insert (cache->hash, elt, elt);
	}
	else {
		g_hash_table_steal (cache->hash, elt);
		if ((elt->flags & KV_ELT_DIRTY) != 0) {
			elt->flags |= KV_ELT_NEED_FREE;
		}
		else {
			/* Free it by self */
			g_slice_free1 (ELT_SIZE (elt), elt);
		}
		elt = g_slice_alloc (
			sizeof (struct rspamd_kv_element) + len + keylen + 1);
		elt->age = time (NULL);
		elt->keylen = keylen;
		elt->size = len;
		elt->flags = 0;
		memcpy (ELT_KEY (elt),	key,   keylen + 1);
		memcpy (ELT_DATA (elt), value, len);
		elt->p = &elt->data;
		g_hash_table_insert (cache->hash, elt, elt);
	}

	return elt;
}

/**
 * Lookup an item inside hash
 */
static struct rspamd_kv_element *
rspamd_kv_hash_lookup (struct rspamd_kv_cache *c, gpointer key, guint keylen)
{
	struct rspamd_kv_hash_cache *cache = (struct rspamd_kv_hash_cache *)c;
	struct rspamd_kv_element search_elt;

	search_elt.keylen = keylen;
	search_elt.p = key;

	return g_hash_table_lookup (cache->hash, &search_elt);
}

/**
 * Replace an element inside cache
 */
static gboolean
rspamd_kv_hash_replace (struct rspamd_kv_cache *c,
	gpointer key,
	guint keylen,
	struct rspamd_kv_element *elt)
{
	struct rspamd_kv_hash_cache *cache = (struct rspamd_kv_hash_cache *)c;
	struct rspamd_kv_element *oldelt, search_elt;

	search_elt.keylen = keylen;
	search_elt.p = key;

	if ((oldelt = g_hash_table_lookup (cache->hash, &search_elt)) != NULL) {
		g_hash_table_steal (cache->hash, oldelt);

		if ((oldelt->flags & KV_ELT_DIRTY) != 0) {
			oldelt->flags |= KV_ELT_NEED_FREE;
		}
		else {
			/* Free it by self */
			g_slice_free1 (ELT_SIZE (oldelt), oldelt);
		}
		g_hash_table_insert (cache->hash, elt, elt);
		return TRUE;
	}

	return FALSE;
}

/**
 * Delete an element from cache
 */
static struct rspamd_kv_element *
rspamd_kv_hash_delete (struct rspamd_kv_cache *c, gpointer key, guint keylen)
{
	struct rspamd_kv_hash_cache *cache = (struct rspamd_kv_hash_cache *)c;
	struct rspamd_kv_element *elt;
	struct rspamd_kv_element search_elt;

	search_elt.keylen = keylen;
	search_elt.p = key;

	elt = g_hash_table_lookup (cache->hash, &search_elt);
	if (elt) {
		g_hash_table_steal (cache->hash, &search_elt);
	}
	return elt;
}

/**
 * Steal an element from cache
 */
static void
rspamd_kv_hash_steal (struct rspamd_kv_cache *c, struct rspamd_kv_element *elt)
{
	struct rspamd_kv_hash_cache *cache = (struct rspamd_kv_hash_cache *)c;

	g_hash_table_steal (cache->hash, elt);
}

/**
 * Destroy the whole cache
 */

static void
rspamd_kv_hash_destroy_cb (gpointer key, gpointer value, gpointer unused)
{
	struct rspamd_kv_element *elt = value;

	g_slice_free1 (ELT_SIZE (elt), elt);
}

static void
rspamd_kv_hash_destroy (struct rspamd_kv_cache *c)
{
	struct rspamd_kv_hash_cache *cache = (struct rspamd_kv_hash_cache *)c;

	g_hash_table_foreach (cache->hash, rspamd_kv_hash_destroy_cb, NULL);
	g_hash_table_destroy (cache->hash);
	g_slice_free1 (sizeof (struct rspamd_kv_hash_cache), cache);
}

/**
 * Make hash for element
 */
#define rot(x,k) (((x) << (k)) ^ ((x) >> (32 - (k))))
#define mix(a,b,c) \
	{ \
		a -= c;  a ^= rot (c, 4);  c += b; \
		b -= a;  b ^= rot (a, 6);  a += c; \
		c -= b;  c ^= rot (b, 8);  b += a; \
		a -= c;  a ^= rot (c,16);  c += b; \
		b -= a;  b ^= rot (a,19);  a += c; \
		c -= b;  c ^= rot (b, 4);  b += a; \
	}
#define final(a,b,c) \
	{ \
		c ^= b; c -= rot (b,14); \
		a ^= c; a -= rot (c,11); \
		b ^= a; b -= rot (a,25); \
		c ^= b; c -= rot (b,16); \
		a ^= c; a -= rot (c,4);  \
		b ^= a; b -= rot (a,14); \
		c ^= b; c -= rot (b,24); \
	}
/*
 *    The hash function used here is by Bob Jenkins, 1996:
 *    <http://burtleburtle.net/bob/hash/doobs.html>
 *       "By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.
 *       You may use this code any way you wish, private, educational,
 *       or commercial.  It's free."
 *
 */
guint
kv_elt_hash_func (gconstpointer e)
{
	struct rspamd_kv_element *elt = (struct rspamd_kv_element *)e;
	guint32 a, b, c;
	union { const void *ptr; size_t i; } u;
	guint length;

	/* Set up the internal state */
	length = elt->keylen;
	a = b = c = 0xdeadbeef + length;

	u.ptr = elt->p;
	if (((u.i & 0x3) == 0)) {
		const guint32 *k = (const guint32 *)elt->p; /* read 32-bit chunks */

		/*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
		while (length > 12) {
			a += k[0];
			b += k[1];
			c += k[2];
			mix (a,b,c);
			length -= 12;
			k += 3;
		}

		/*----------------------------- handle the last (probably partial) block */
		/*
		 * "k[2]&0xffffff" actually reads beyond the end of the string, but
		 * then masks off the part it's not allowed to read.  Because the
		 * string is aligned, the masked-off tail is in the same word as the
		 * rest of the string.  Every machine with memory protection I've seen
		 * does it on word boundaries, so is OK with this.  But VALGRIND will
		 * still catch it and complain.  The masking trick does make the hash
		 * noticably faster for short strings (like English words).
		 */
		switch (length)
		{
		case 12: c += k[2]; b += k[1]; a += k[0]; break;
		case 11: c += k[2] & 0xffffff; b += k[1]; a += k[0]; break;
		case 10: c += k[2] & 0xffff; b += k[1]; a += k[0]; break;
		case 9: c += k[2] & 0xff; b += k[1]; a += k[0]; break;
		case 8: b += k[1]; a += k[0]; break;
		case 7: b += k[1] & 0xffffff; a += k[0]; break;
		case 6: b += k[1] & 0xffff; a += k[0]; break;
		case 5: b += k[1] & 0xff; a += k[0]; break;
		case 4: a += k[0]; break;
		case 3: a += k[0] & 0xffffff; break;
		case 2: a += k[0] & 0xffff; break;
		case 1: a += k[0] & 0xff; break;
		case 0: return c;   /* zero length strings require no mixing */
		}

	} else if (((u.i & 0x1) == 0)) {
		const guint16 *k = (const guint16 *)elt->p;                           /* read 16-bit chunks */
		const guint8 *k8;

		/*--------------- all but last block: aligned reads and different mixing */
		while (length > 12) {
			a += k[0] + (((guint32)k[1]) << 16);
			b += k[2] + (((guint32)k[3]) << 16);
			c += k[4] + (((guint32)k[5]) << 16);
			mix (a,b,c);
			length -= 12;
			k += 6;
		}

		/*----------------------------- handle the last (probably partial) block */
		k8 = (const guint8 *)k;
		switch (length)
		{
		case 12: c += k[4] + (((guint32)k[5]) << 16);
			b += k[2] + (((guint32)k[3]) << 16);
			a += k[0] + (((guint32)k[1]) << 16);
			break;
		case 11: c += ((guint32)k8[10]) << 16;     /* @fallthrough */
		case 10: c += k[4];                       /* @fallthrough@ */
			b += k[2] + (((guint32)k[3]) << 16);
			a += k[0] + (((guint32)k[1]) << 16);
			break;
		case 9: c += k8[8];                      /* @fallthrough */
		case 8: b += k[2] + (((guint32)k[3]) << 16);
			a += k[0] + (((guint32)k[1]) << 16);
			break;
		case 7: b += ((guint32)k8[6]) << 16;      /* @fallthrough */
		case 6: b += k[2];
			a += k[0] + (((guint32)k[1]) << 16);
			break;
		case 5: b += k8[4];                      /* @fallthrough */
		case 4: a += k[0] + (((guint32)k[1]) << 16);
			break;
		case 3: a += ((guint32)k8[2]) << 16;      /* @fallthrough */
		case 2: a += k[0];
			break;
		case 1: a += k8[0];
			break;
		case 0: return c;   /* zero length strings require no mixing */
		}

	} else {                        /* need to read the key one byte at a time */
		const guint8 *k = elt->p;

		/*--------------- all but the last block: affect some 32 bits of (a,b,c) */
		while (length > 12)
		{
			a += k[0];
			a += ((guint32)k[1]) << 8;
			a += ((guint32)k[2]) << 16;
			a += ((guint32)k[3]) << 24;
			b += k[4];
			b += ((guint32)k[5]) << 8;
			b += ((guint32)k[6]) << 16;
			b += ((guint32)k[7]) << 24;
			c += k[8];
			c += ((guint32)k[9]) << 8;
			c += ((guint32)k[10]) << 16;
			c += ((guint32)k[11]) << 24;
			mix (a,b,c);
			length -= 12;
			k += 12;
		}

		/*-------------------------------- last block: affect all 32 bits of (c) */
		switch (length)                   /* all the case statements fall through */
		{
		case 12: c += ((guint32)k[11]) << 24;
		case 11: c += ((guint32)k[10]) << 16;
		case 10: c += ((guint32)k[9]) << 8;
		case 9: c += k[8];
		case 8: b += ((guint32)k[7]) << 24;
		case 7: b += ((guint32)k[6]) << 16;
		case 6: b += ((guint32)k[5]) << 8;
		case 5: b += k[4];
		case 4: a += ((guint32)k[3]) << 24;
		case 3: a += ((guint32)k[2]) << 16;
		case 2: a += ((guint32)k[1]) << 8;
		case 1: a += k[0];
			break;
		case 0: return c;   /* zero length strings require no mixing */
		}
	}

	final (a,b,c);
	return c;             /* zero length strings require no mixing */
}

gboolean
kv_elt_compare_func (gconstpointer e1, gconstpointer e2)
{
	struct rspamd_kv_element *elt1 = (struct rspamd_kv_element *) e1,
	*elt2 = (struct rspamd_kv_element *) e2;

	if (elt1->keylen == elt2->keylen) {
		return memcmp (elt1->p, elt2->p, elt1->keylen) == 0;
	}

	return FALSE;
}

/**
 * Create new hash kv cache
 */
struct rspamd_kv_cache *
rspamd_kv_hash_new (void)
{
	struct rspamd_kv_hash_cache *new;

	new = g_slice_alloc (sizeof (struct rspamd_kv_hash_cache));
	new->hash = g_hash_table_new_full (kv_elt_hash_func,
			kv_elt_compare_func,
			NULL,
			NULL);
	new->init_func = NULL;
	new->insert_func = rspamd_kv_hash_insert;
	new->lookup_func = rspamd_kv_hash_lookup;
	new->replace_func = rspamd_kv_hash_replace;
	new->delete_func = rspamd_kv_hash_delete;
	new->steal_func = rspamd_kv_hash_steal;
	new->destroy_func = rspamd_kv_hash_destroy;

	return (struct rspamd_kv_cache *)new;
}

/*
 * Radix cache hash table
 */
struct rspamd_kv_radix_cache {
	cache_init init_func;                       /*< this callback is called on kv storage initialization */
	cache_insert insert_func;                   /*< this callback is called when element is inserted */
	cache_replace replace_func;                 /*< this callback is called when element is replace */
	cache_lookup lookup_func;                   /*< this callback is used for lookup of element */
	cache_delete delete_func;                   /*< this callback is called when an element is deleted */
	cache_steal steal_func;                     /*< this callback is used to replace duplicates in cache */
	cache_destroy destroy_func;                 /*< this callback is used for destroying all elements inside cache */
	radix_tree_t *tree;
};

/**
 * Validate a key for radix
 */
static guint32
rspamd_kv_radix_validate (gpointer key, guint keylen)
{
	struct in_addr addr;

	if (inet_aton (key, &addr) == 0) {
		return 0;
	}

	return addr.s_addr;
}

/**
 * Insert an element inside cache
 */
static struct rspamd_kv_element *
rspamd_kv_radix_insert (struct rspamd_kv_cache *c,
	gpointer key,
	guint keylen,
	gpointer value,
	gsize len)
{
	struct rspamd_kv_element *elt;
	struct rspamd_kv_radix_cache *cache = (struct rspamd_kv_radix_cache *)c;
	guint32 rkey = rspamd_kv_radix_validate (key, keylen);

	if (rkey == 0) {
		return NULL;
	}

	elt = (struct rspamd_kv_element *)radix32tree_find (cache->tree, rkey);
	if ((uintptr_t)elt == RADIX_NO_VALUE) {
		elt = g_slice_alloc (
			sizeof (struct rspamd_kv_element) + len + keylen + 1);
		elt->age = time (NULL);
		elt->keylen = keylen;
		elt->size = len;
		elt->flags = 0;
		memcpy (ELT_KEY (elt),	key,   keylen + 1);
		memcpy (ELT_DATA (elt), value, len);
		elt->p = &elt->data;
		radix32tree_insert (cache->tree, rkey, 0xffffffff, (uintptr_t)elt);
	}
	else {
		radix32tree_delete (cache->tree, rkey, 0xffffffff);
		if ((elt->flags & KV_ELT_DIRTY) != 0) {
			elt->flags |= KV_ELT_NEED_FREE;
		}
		else {
			/* Free it by self */
			g_slice_free1 (ELT_SIZE (elt), elt);
		}
		elt = g_slice_alloc (
			sizeof (struct rspamd_kv_element) + len + keylen + 1);
		elt->age = time (NULL);
		elt->keylen = keylen;
		elt->size = len;
		elt->flags = 0;
		memcpy (ELT_KEY (elt),	key,   keylen + 1);
		memcpy (ELT_DATA (elt), value, len);
		elt->p = &elt->data;
		radix32tree_insert (cache->tree, rkey, 0xffffffff, (uintptr_t)elt);
	}

	return elt;
}

/**
 * Lookup an item inside radix
 */
static struct rspamd_kv_element *
rspamd_kv_radix_lookup (struct rspamd_kv_cache *c, gpointer key, guint keylen)
{
	struct rspamd_kv_radix_cache *cache = (struct rspamd_kv_radix_cache *)c;
	guint32 rkey = rspamd_kv_radix_validate (key, keylen);
	struct rspamd_kv_element *elt;

	elt = (struct rspamd_kv_element *)radix32tree_find (cache->tree, rkey);
	if ((uintptr_t)elt == RADIX_NO_VALUE) {
		return NULL;
	}

	return elt;
}

/**
 * Replace an element inside cache
 */
static gboolean
rspamd_kv_radix_replace (struct rspamd_kv_cache *c,
	gpointer key,
	guint keylen,
	struct rspamd_kv_element *elt)
{
	struct rspamd_kv_radix_cache *cache = (struct rspamd_kv_radix_cache *)c;
	guint32 rkey = rspamd_kv_radix_validate (key, keylen);
	struct rspamd_kv_element *oldelt;

	oldelt = (struct rspamd_kv_element *)radix32tree_find (cache->tree, rkey);
	if ((uintptr_t)oldelt != RADIX_NO_VALUE) {
		radix32tree_delete (cache->tree, rkey, 0xffffffff);

		if ((oldelt->flags & KV_ELT_DIRTY) != 0) {
			oldelt->flags |= KV_ELT_NEED_FREE;
		}
		else {
			/* Free it by self */
			g_slice_free1 (ELT_SIZE (oldelt), oldelt);
		}
		radix32tree_insert (cache->tree, rkey, 0xffffffff, (uintptr_t)elt);
		return TRUE;
	}

	return FALSE;
}

/**
 * Delete an element from cache
 */
static struct rspamd_kv_element *
rspamd_kv_radix_delete (struct rspamd_kv_cache *c, gpointer key, guint keylen)
{
	struct rspamd_kv_radix_cache *cache = (struct rspamd_kv_radix_cache *)c;
	struct rspamd_kv_element *elt;
	guint32 rkey = rspamd_kv_radix_validate (key, keylen);

	elt = (struct rspamd_kv_element *)radix32tree_find (cache->tree, rkey);
	if ((uintptr_t)elt != RADIX_NO_VALUE) {
		radix32tree_delete (cache->tree, rkey, 0xffffffff);
	}
	else {
		return NULL;
	}
	return elt;
}

/**
 * Delete an element from cache
 */
static void
rspamd_kv_radix_steal (struct rspamd_kv_cache *c, struct rspamd_kv_element *elt)
{
	struct rspamd_kv_radix_cache *cache = (struct rspamd_kv_radix_cache *)c;
	guint32 rkey = rspamd_kv_radix_validate (ELT_KEY (elt), elt->keylen);


	radix32tree_delete (cache->tree, rkey, 0xffffffff);
}

/**
 * Destroy the whole cache
 */
static void
rspamd_kv_radix_destroy (struct rspamd_kv_cache *c)
{
	struct rspamd_kv_radix_cache *cache = (struct rspamd_kv_radix_cache *)c;

	radix_tree_free (cache->tree);
	g_slice_free1 (sizeof (struct rspamd_kv_radix_cache), cache);
}

/**
 * Create new radix kv cache
 */
struct rspamd_kv_cache *
rspamd_kv_radix_new (void)
{
	struct rspamd_kv_radix_cache *new;

	new = g_slice_alloc (sizeof (struct rspamd_kv_radix_cache));
	new->tree = radix_tree_create ();
	new->init_func = NULL;
	new->insert_func = rspamd_kv_radix_insert;
	new->lookup_func = rspamd_kv_radix_lookup;
	new->replace_func = rspamd_kv_radix_replace;
	new->delete_func = rspamd_kv_radix_delete;
	new->steal_func = rspamd_kv_radix_steal;
	new->destroy_func = rspamd_kv_radix_destroy;

	return (struct rspamd_kv_cache *)new;
}


#ifdef WITH_JUDY
/*
 * KV cache hash table
 */
struct rspamd_kv_judy_cache {
	cache_init init_func;                       /*< this callback is called on kv storage initialization */
	cache_insert insert_func;                   /*< this callback is called when element is inserted */
	cache_replace replace_func;                 /*< this callback is called when element is replace */
	cache_lookup lookup_func;                   /*< this callback is used for lookup of element */
	cache_delete delete_func;                   /*< this callback is called when an element is deleted */
	cache_steal steal_func;                     /*< this callback is used to replace duplicates in cache */
	cache_destroy destroy_func;                 /*< this callback is used for destroying all elements inside cache */
	Pvoid_t judy;
};


/**
 * Lookup an item inside judy
 */
static struct rspamd_kv_element *
rspamd_kv_judy_lookup (struct rspamd_kv_cache *c, gpointer key, guint keylen)
{
	struct rspamd_kv_judy_cache *cache = (struct rspamd_kv_judy_cache *)c;
	struct rspamd_kv_element *elt = NULL, **pelt;

	JHSG (pelt, cache->judy, key, keylen);
	if (pelt != NULL) {
		elt = *pelt;
	}
	return elt;
}

/**
 * Delete an element from cache
 */
static struct rspamd_kv_element *
rspamd_kv_judy_delete (struct rspamd_kv_cache *c, gpointer key, guint keylen)
{
	struct rspamd_kv_judy_cache *cache = (struct rspamd_kv_judy_cache *)c;
	struct rspamd_kv_element *elt;
	gint rc;

	elt = rspamd_kv_judy_lookup (c, key, keylen);
	if (elt) {
		JHSD (rc, cache->judy, ELT_KEY (elt), elt->keylen);
	}
	return elt;
}

/**
 * Steal an element from cache
 */
static void
rspamd_kv_judy_steal (struct rspamd_kv_cache *c, struct rspamd_kv_element *elt)
{
	struct rspamd_kv_judy_cache *cache = (struct rspamd_kv_judy_cache *)c;
	gint rc;

	JHSD (rc, cache->judy, ELT_KEY (elt), elt->keylen);
}

/**
 * Insert an element inside cache
 */
static struct rspamd_kv_element *
rspamd_kv_judy_insert (struct rspamd_kv_cache *c,
	gpointer key,
	guint keylen,
	gpointer value,
	gsize len)
{
	struct rspamd_kv_element *elt, **pelt;
	struct rspamd_kv_judy_cache *cache = (struct rspamd_kv_judy_cache *)c;

	if ((elt = rspamd_kv_judy_lookup (c, key, keylen)) == NULL) {
		elt = g_slice_alloc (
			sizeof (struct rspamd_kv_element) + len + keylen + 1);
		elt->age = time (NULL);
		elt->keylen = keylen;
		elt->size = len;
		elt->flags = 0;
		memcpy (ELT_KEY (elt),	key,   keylen);
		memcpy (ELT_DATA (elt), value, len);
		JHSI (pelt, cache->judy, ELT_KEY (elt), elt->keylen);
		elt->p = &elt->data;
		*pelt = elt;
	}
	else {
		rspamd_kv_judy_steal (c, elt);
		if ((elt->flags & KV_ELT_DIRTY) != 0) {
			elt->flags |= KV_ELT_NEED_FREE;
		}
		else {
			/* Free it by self */
			g_slice_free1 (ELT_SIZE (elt), elt);
		}
		elt = g_slice_alloc0 (
			sizeof (struct rspamd_kv_element) + len + keylen + 1);
		elt->age = time (NULL);
		elt->keylen = keylen;
		elt->size = len;
		elt->flags = 0;
		memcpy (ELT_KEY (elt),	key,   keylen);
		memcpy (ELT_DATA (elt), value, len);
		elt->p = &elt->data;
		JHSI (pelt, cache->judy, ELT_KEY (elt), elt->keylen);
		*pelt = elt;
	}

	return elt;
}

/**
 * Replace an element inside cache
 */
static gboolean
rspamd_kv_judy_replace (struct rspamd_kv_cache *c,
	gpointer key,
	guint keylen,
	struct rspamd_kv_element *elt)
{
	struct rspamd_kv_judy_cache *cache = (struct rspamd_kv_judy_cache *)c;
	struct rspamd_kv_element *oldelt, **pelt;

	if ((oldelt = rspamd_kv_judy_lookup (c, key, keylen)) != NULL) {
		rspamd_kv_judy_steal (c, elt);

		if ((oldelt->flags & KV_ELT_DIRTY) != 0) {
			oldelt->flags |= KV_ELT_NEED_FREE;
		}
		else {
			/* Free it by self */
			g_slice_free1 (ELT_SIZE (oldelt), oldelt);
		}
		JHSI (pelt, cache->judy, ELT_KEY (elt), elt->keylen);
		*pelt = elt;
		return TRUE;
	}

	return FALSE;
}

/**
 * Destroy the whole cache
 */
static void
rspamd_kv_judy_destroy (struct rspamd_kv_cache *c)
{
	struct rspamd_kv_judy_cache *cache = (struct rspamd_kv_judy_cache *)c;
	glong bytes;

	JHSFA (bytes, cache->judy);
	g_slice_free1 (sizeof (struct rspamd_kv_judy_cache), cache);
}

/**
 * Judy tree
 */
struct rspamd_kv_cache *
rspamd_kv_judy_new (void)
{
	struct rspamd_kv_judy_cache *new;

	new = g_slice_alloc (sizeof (struct rspamd_kv_judy_cache));
	new->judy = NULL;
	new->init_func = NULL;
	new->insert_func = rspamd_kv_judy_insert;
	new->lookup_func = rspamd_kv_judy_lookup;
	new->replace_func = rspamd_kv_judy_replace;
	new->delete_func = rspamd_kv_judy_delete;
	new->steal_func = rspamd_kv_judy_steal;
	new->destroy_func = rspamd_kv_judy_destroy;

	return (struct rspamd_kv_cache *)new;
}
#endif