/*-
 * Copyright (c) 2014--2019 Taylor R. Campbell
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. 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 BY THE AUTHOR AND CONTRIBUTORS ``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 THE AUTHOR OR CONTRIBUTORS 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 <sys/atomic.h>

#include <assert.h>
#include <err.h>
#include <errno.h>
#include <pthread.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

#include "container_of.h"
#include "critbit_alloc.h"
#include "ebr.h"

struct ent;

struct map {
	struct critbit		m_critbit;
	pthread_mutex_t		m_lock;
	ptrdiff_t		m_keyoff;
	size_t			m_keysz;

	struct {
		pthread_mutex_t		lock;
		pthread_cond_t		cond;
		ebr_t			*ebr;
		struct map_branch	*branchlist;
		struct ent		*nodelist;
		bool			dying;
		void			(*free_cb)(struct ent *);
		pthread_t		thread;
	}			m_gc;
};

struct ent {
	struct critbit_node	ent_node;
	struct ent		*ent_gcnext;
};

struct map_branch {
	struct map_branch	*mb_gcnext;
	struct critbit_branch	mb_critbit;
};

static const void *
map_critbit_key(const struct critbit *C, const struct critbit_node *N,
    size_t *keylenp)
{
	const struct map *const M = container_of(C, struct map, m_critbit);
	const struct ent *const ent = container_of(N, struct ent, ent_node);

	*keylenp = M->m_keysz;
	return (const void *)((const char *)ent + M->m_keyoff);
}

static inline void
membar_datadep_consumer(void)
{
}

static struct critbit_branch *
map_critbit_branch_alloc(struct critbit *C __unused)
{
	struct map_branch *mb;

	mb = malloc(sizeof(*mb));
	if (mb == NULL)
		return NULL;

	return &mb->mb_critbit;
}

static void
map_critbit_branch_free(struct critbit *C __unused, struct critbit_branch *B)
{
	struct map *M = container_of(C, struct map, m_critbit);
	struct map_branch *mb = container_of(B, struct map_branch, mb_critbit);
	int error;

	error = pthread_mutex_lock(&M->m_gc.lock);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}

	mb->mb_gcnext = M->m_gc.branchlist;
	M->m_gc.branchlist = mb;

	error = pthread_cond_broadcast(&M->m_gc.cond);
	if (error) {
		errno = error;
		err(1, "pthread_cond_broadcast");
	}

	error = pthread_mutex_unlock(&M->m_gc.lock);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}
}

static const struct critbit_ops map_critbit_ops = {
	.cbo_key = &map_critbit_key,
	.cbo_membar_producer = &membar_producer,
	.cbo_membar_datadep_consumer = &membar_datadep_consumer,
	.cbo_branch_alloc = &map_critbit_branch_alloc,
	.cbo_branch_free = &map_critbit_branch_free,
};

struct map_read {
	char mr_dummy;
};

struct map_txn_delete {
	char mtd_dummy;
};

static void *
map_gc_thread(void *cookie)
{
	struct map *M = cookie;
	int error;

	ebr_register(M->m_gc.ebr);
	for (;;) {
		struct map_branch *branch, *branchnext;
		struct ent *node, *nodenext;
		unsigned epoch;

		error = pthread_mutex_lock(&M->m_gc.lock);
		if (error) {
			errno = error;
			err(1, "pthread_mutex_lock");
		}
		while (M->m_gc.branchlist == NULL &&
		    M->m_gc.nodelist == NULL &&
		    !M->m_gc.dying) {
			error = pthread_cond_wait(&M->m_gc.cond,
			    &M->m_gc.lock);
			if (error) {
				errno = error;
				err(1, "pthread_cond_wait");
			}
		}
		branch = M->m_gc.branchlist;
		M->m_gc.branchlist = NULL;
		node = M->m_gc.nodelist;
		M->m_gc.nodelist = NULL;
		error = pthread_mutex_unlock(&M->m_gc.lock);
		if (error) {
			errno = error;
			err(1, "pthread_mutex_unlock");
		}

		/* If there's nothing to do, we're done.  */
		if (branch == NULL && node == NULL) {
			assert(M->m_gc.dying);
			break;
		}

		/* Wait for two epoch transitions.  */
		while (!ebr_sync(M->m_gc.ebr, &epoch))
			continue;
		while (!ebr_sync(M->m_gc.ebr, &epoch))
			continue;

		/* Free them all.  */
		for (; branch != NULL; branch = branchnext) {
			branchnext = branch->mb_gcnext;
			free(branch);
		}
		for (; node != NULL; node = nodenext) {
			nodenext = node->ent_gcnext;
			M->m_gc.free_cb(node);
		}
	}

	return NULL;
}

static void
map_gc_init(struct map *M, void (*free_cb)(struct ent *))
{
	int error;

	error = pthread_mutex_init(&M->m_gc.lock, NULL);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_init");
	}
	error = pthread_cond_init(&M->m_gc.cond, NULL);
	if (error) {
		errno = error;
		err(1, "pthread_cond_init");
	}
	if ((M->m_gc.ebr = ebr_create()) == NULL)
		err(1, "ebr_create");
	M->m_gc.branchlist = NULL;
	M->m_gc.nodelist = NULL;
	M->m_gc.dying = false;
	M->m_gc.free_cb = free_cb;

	error = pthread_create(&M->m_gc.thread, NULL, &map_gc_thread, M);
	if (error) {
		errno = error;
		err(1, "pthread_create");
	}
}

static void
map_gc_fini(struct map *M)
{
	int error;

	error = pthread_mutex_lock(&M->m_gc.lock);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}
	M->m_gc.dying = true;
	error = pthread_cond_broadcast(&M->m_gc.cond);
	if (error) {
		errno = error;
		err(1, "pthread_cond_broadcast");
	}
	error = pthread_mutex_unlock(&M->m_gc.lock);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}

	error = pthread_join(M->m_gc.thread, NULL);
	if (error) {
		errno = error;
		err(1, "pthread_join");
	}
	assert(M->m_gc.branchlist == NULL);
	assert(M->m_gc.nodelist == NULL);
}

static void
map_init(struct map *M, ptrdiff_t keyoff, size_t keysz,
    void (*free_cb)(struct ent *))
{
	int error;

	critbit_init(&M->m_critbit, &map_critbit_ops);

	error = pthread_mutex_init(&M->m_lock, NULL);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_init");
	}

	M->m_keyoff = keyoff;
	M->m_keysz = keysz;

	map_gc_init(M, free_cb);
}

static void
map_destroy(struct map *M)
{

	map_gc_fini(M);
	pthread_mutex_destroy(&M->m_lock);
	critbit_destroy(&M->m_critbit);
}

static void
map_register_thread(struct map *M __unused)
{

	ebr_register(M->m_gc.ebr);
}

static void
map_deregister_thread(struct map *M __unused)
{

	ebr_unregister(M->m_gc.ebr);
}

static void
map_read_enter(struct map *M __unused, struct map_read *mr __unused)
{

	ebr_enter(M->m_gc.ebr);
}

static void
map_read_exit(struct map *M __unused, struct map_read *mr __unused)
{

	ebr_exit(M->m_gc.ebr);
}

static struct ent *
map_lookup(struct map *M, const void *key)
{
	const size_t keylen = M->m_keysz;
	struct critbit *C = &M->m_critbit;
	struct critbit_node *N;

	N = critbit_lookup(C, key, keylen);
	if (N == NULL)
		return NULL;

	return container_of(N, struct ent, ent_node);
}

static bool
map_insert(struct map *M, const void *key __unused, struct ent *ent)
{
	struct critbit *C = &M->m_critbit;
	struct critbit_node *N = &ent->ent_node;
	struct critbit_node *N0;
	int error;

	if ((error = pthread_mutex_lock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}

	N0 = critbit_insert(C, N);

	if ((error = pthread_mutex_unlock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}

	return N0 == N;
}

static struct ent *
map_delete(struct map *M, const void *key)
{
	const size_t keylen = M->m_keysz;
	struct critbit *C = &M->m_critbit;
	struct critbit_node *N;
	struct ent *ent;
	int error;

	if ((error = pthread_mutex_lock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}

	N = critbit_delete_key(C, key, keylen);
#ifdef CRITBIT_DEBUG
	critbit_check(C);
#endif

	if ((error = pthread_mutex_unlock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}

	if (N == NULL)
		return NULL;

	ent = container_of(N, struct ent, ent_node);

	if ((error = pthread_mutex_lock(&M->m_gc.lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}
	ent->ent_gcnext = M->m_gc.nodelist;
	M->m_gc.nodelist = ent;
	error = pthread_cond_broadcast(&M->m_gc.cond);
	if (error) {
		errno = error;
		err(1, "pthread_cond_broadcast");
	}
	if ((error = pthread_mutex_unlock(&M->m_gc.lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}

	return ent;
}

static void
map_txn_delete_begin(struct map *M, struct map_txn_delete *T __unused,
    size_t n __unused)
{
	int error;

	if ((error = pthread_mutex_lock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}
}

#include <assert.h>
#include <stdio.h>
static void
map_txn_delete_commit(struct map *M, struct map_txn_delete *T __unused)
{
	int error;

	if ((error = pthread_mutex_unlock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}
}

static struct ent *
map_txn_delete(struct map *M, const void *key,
    struct map_txn_delete *T __unused)
{
	const size_t keylen = M->m_keysz;
	struct critbit *C = &M->m_critbit;
	struct critbit_node *N;
	struct ent *ent;
	int error;

	N = critbit_delete_key(C, key, keylen);
	if (N == NULL)
		return NULL;

	ent = container_of(N, struct ent, ent_node);

	if ((error = pthread_mutex_lock(&M->m_gc.lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}
	ent->ent_gcnext = M->m_gc.nodelist;
	M->m_gc.nodelist = ent;
	error = pthread_cond_broadcast(&M->m_gc.cond);
	if (error) {
		errno = error;
		err(1, "pthread_cond_broadcast");
	}
	if ((error = pthread_mutex_unlock(&M->m_gc.lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}

	return ent;
}

#define	MAP_ASYNC	1
#include "stress.i"