/*-
 * 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 <err.h>
#include <errno.h>
#include <pthread.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

#include "container_of.h"
#include "critbit.h"
#include "ebr.h"

struct ent;

struct map {
	struct critbit		m_critbit;
	pthread_mutex_t		m_lock;
	struct ebr		*m_ebr;
	ptrdiff_t		m_keyoff;
	size_t			m_keysz;
};

struct ent {
	struct critbit_node	ent_node;
};

static void
map_critbit_sync(struct critbit *C)
{
	struct map *M = container_of(C, struct map, m_critbit);
	unsigned epoch;

	/*
	 * Objects are grouped into three epochs:
	 *
	 * 0. available to be seen by a new ebr_enter/exit transaction
	 * 1. currently in use by an existing ebr_enter/exit transaction
	 * 2. guaranteed not to be seen by an ebr_enter/exit transaction
	 *
	 * Objects we have deleted may be in (0) or (1), so we wait for
	 * two epoch transitions to guarantee they have transitioned to
	 * (2).
	 */
	while (!ebr_sync(M->m_ebr, &epoch))
		continue;
	while (!ebr_sync(M->m_ebr, &epoch))
		continue;
}

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 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_sync = &map_critbit_sync,
};

struct map_read {
	char mr_dummy;
};

struct map_txn_delete {
	struct critbit_txn_delete	mtd_txn;
	struct ent			**mtd_ent;
	size_t				mtd_nent;
	struct critbit_txn_delete_1	*mtd_delete;
	size_t				mtd_ndelete;
};

static void
map_init(struct map *M, ptrdiff_t keyoff, size_t keysz)
{
	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");
	}

	if ((M->m_ebr = ebr_create()) == NULL)
		err(1, "ebr_create");

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

static void
map_destroy(struct map *M)
{

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

static void
map_register_thread(struct map *M)
{

	ebr_register(M->m_ebr);
}

static void
map_deregister_thread(struct map *M __unused)
{

#if 0
	ebr_deregister(M->m_ebr);
#endif
}

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

	ebr_enter(M->m_ebr);
}

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

	(void)mr;		/* ignore */
	ebr_exit(M->m_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, struct ent *ent)
{
	const size_t keylen = M->m_keysz;
	struct critbit *C = &M->m_critbit;
	struct critbit_node *N = &ent->ent_node;
	struct critbit_node *N0;
	int error;

	critbit_node_init(N, key, keylen);

	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;
	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;
	critbit_node_destroy(N);
	return container_of(N, struct ent, ent_node);
}

static void
map_txn_delete_begin(struct map *M, struct map_txn_delete *T, size_t n)
{
	struct critbit *C = &M->m_critbit;
	int error;

	T->mtd_ent = calloc(n, sizeof(T->mtd_ent[0]));
	if (T->mtd_ent == NULL)
		err(1, "map_txn_delete_begin: calloc ent pointers");
	T->mtd_nent = 0;

	T->mtd_delete = calloc(n, sizeof(T->mtd_delete[0]));
	if (T->mtd_delete == NULL)
		err(1, "map_txn_delete_begin: calloc deletions");

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

	critbit_txn_delete_begin(C, &T->mtd_txn, T->mtd_delete, n);
}

#include <assert.h>
#include <stdio.h>
static void
map_txn_delete_commit(struct map *M, struct map_txn_delete *T)
{
	struct critbit *C = &M->m_critbit;
	unsigned i;
	int error;

	critbit_txn_delete_commit(C, &T->mtd_txn);

	for (i = 0; i < T->mtd_nent; i++) {
		uintptr_t root = C->cb_root;

		if (&T->mtd_ent[i]->ent_node ==
		    (void *)(root & ~(uintptr_t)1)) {
			critbit_print(C);
			fprintf(stderr, "node %p at root\n",
			    &T->mtd_ent[i]->ent_node);
			abort();
		}
		assert(&T->mtd_ent[i]->ent_node != (void *)C->cb_root);
		assert(&T->mtd_ent[i]->ent_node != (void *)(C->cb_root - 1));
		critbit_node_destroy(&T->mtd_ent[i]->ent_node);
	}

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

	free(T->mtd_ent);
	free(T->mtd_delete);
}

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

	N = critbit_txn_delete_key(C, key, keylen, &T->mtd_txn);
	if (N == NULL)
		return NULL;

	ent = container_of(N, struct ent, ent_node);
	T->mtd_ent[T->mtd_nent++] = ent;
	return ent;
}

#include "stress.i"