/*
 * Copyright 2016-2018, Intel Corporation
 *
 * 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.
 *
 *     * Neither the name of the copyright holder nor the names of its
 *       contributors may be used to endorse or promote products derived
 *       from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT
 * OWNER 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.
 */

#ifndef LIBPMEMOBJ_CPP_EXAMPLES_CTREE_MAP_VOLATILE_HPP
#define LIBPMEMOBJ_CPP_EXAMPLES_CTREE_MAP_VOLATILE_HPP

#include <cstdint>
#include <cstdlib>
#include <functional>
#include <libpmemobj_cpp_examples_common.hpp>
#ifdef _WIN32
#include <windows.h>
#endif

#define BIT_IS_SET(n, i) (!!((n) & (1ULL << (i))))

namespace examples
{

/**
 * C++ implementation of a volatile ctree.
 *
 * Based on the C implementation.
 */
template <typename K, typename T>
class ctree_map_transient {
public:
	/** Convenience typedef for the key type. */
	typedef K key_type;

	/** Convenience typedef for the value type. */
	typedef T *value_type;

	/** Convenience typedef for the callback function. */
	typedef std::function<int(key_type, value_type, void *)> callback;

	/**
	 * Default constructor.
	 */
	ctree_map_transient() : root(new entry())
	{
	}

	ctree_map_transient(const ctree_map_transient &other) = delete;

	ctree_map_transient &
	operator=(const ctree_map_transient &other) = delete;

	/**
	 * Insert or update the given value under the given key.
	 *
	 * The map takes ownership of the value.
	 *
	 * @param key The key to insert under.
	 * @param value The value to be inserted.
	 *
	 * @return 0 on success, negative values on error.
	 */
	int
	insert(uint64_t key, value_type value)
	{
		auto dest_entry = root;
		while (dest_entry->inode != nullptr) {
			auto n = dest_entry->inode;
			dest_entry = n->entries[BIT_IS_SET(key, n->diff)];
		}

		entry e(key, value);
		if (dest_entry->key == 0 || dest_entry->key == key) {
			delete dest_entry->value;
			*dest_entry = e;
		} else {
			insert_leaf(&e,
				    ctree_map_transient::find_crit_bit(
					    dest_entry->key, key));
		}

		return 0;
	}

	/**
	 * Allocating insert.
	 *
	 * Creates a new value_type instance and inserts it into the tree.
	 *
	 * @param key The key to insert under.
	 * @param args variadic template parameter for object construction
	 *	arguments.
	 *
	 * @return 0 on success, negative values on error.
	 */
	template <typename... Args>
	int
	insert_new(key_type key, const Args &... args)
	{
		return insert(key, new T(args...));
	}

	/**
	 * Remove a value from the tree.
	 *
	 * The tree no longer owns the value.
	 *
	 * @param key The key for which the value will be removed.
	 *
	 * @return The value if it is in the tree, nullptr otherwise.
	 */
	value_type
	remove(key_type key)
	{
		entry *parent = nullptr;
		auto leaf = get_leaf(key, &parent);

		if (leaf == nullptr)
			return nullptr;

		auto ret = leaf->value;

		if (parent == nullptr) {
			leaf->key = 0;
			leaf->value = nullptr;
		} else {
			auto n = parent->inode;
			*parent = *(n->entries[parent->inode->entries[0]->key ==
					       leaf->key]);

			/* cleanup both entries and the unnecessary node */
			delete n->entries[0];
			delete n->entries[1];
			delete n;
		}

		return ret;
	}

	/**
	 * Remove entry from tree and deallocate it.
	 *
	 * @param key The key denoting the entry to be removed.
	 *
	 * @return 0 on success, negative values on error.
	 */
	int
	remove_free(key_type key)
	{
		delete remove(key);
		return 0;
	}

	/**
	 * Clear the tree and deallocate all entries.
	 */
	int
	clear()
	{
		if (root->inode) {
			root->inode->clear();
			delete root->inode;
			root->inode = nullptr;
		}

		delete root->value;
		root->value = nullptr;
		root->key = 0;
		return 0;
	}

	/**
	 * Return the value from the tree for the given key.
	 *
	 * @param key The key for which the value will be returned.
	 *
	 * @return The value if it is in the tree, nullptr otherwise.
	 */
	value_type
	get(key_type key)
	{
		auto ret = get_leaf(key, nullptr);

		return ret ? ret->value : nullptr;
	}

	/**
	 * Check if an entry for the given key is in the tree.
	 *
	 * @param key The key to check.
	 *
	 * @return 0 on
	 */
	int
	lookup(key_type key) const
	{
		return get(key) != nullptr;
	}

	/**
	 * Call clb for each element in the tree.
	 *
	 * @param clb The callback to be called.
	 * @param args The arguments forwarded to the callback.
	 *
	 * @return 0 if tree empty, clb return value otherwise.
	 */
	int foreach (callback clb, void *args)
	{
		if (is_empty())
			return 0;

		return foreach_node(root, clb, args);
	}

	/**
	 * Check if tree is empty.
	 *
	 * @return 1 if empty, 0 otherwise.
	 */
	int
	is_empty() const
	{
		return root->value == nullptr && root->inode == nullptr;
	}

	/**
	 * Check tree consistency.
	 *
	 * @return 0 on success, negative values on error.
	 */
	int
	check() const
	{
		return 0;
	}

	/**
	 * Destructor.
	 */
	~ctree_map_transient()
	{
		clear();
		delete root;
	}

private:
	struct node;

	/*
	 * Entry holding the value.
	 */
	struct entry {
		entry() : key(0), inode(nullptr), value(nullptr)
		{
		}

		entry(key_type _key, value_type _value)
		    : key(_key), inode(nullptr), value(_value)
		{
		}

		key_type key;
		node *inode;
		value_type value;

		/*
		 * Clear the entry.
		 */
		void
		clear()
		{
			if (inode) {
				inode->clear();
				delete inode;
			}
			delete value;
		}
	};

	/*
	 * Internal node pointing to two entries.
	 */
	struct node {
		node() : diff(0)
		{
			entries[0] = nullptr;
			entries[1] = nullptr;
		}

		int diff; /* most significant differing bit */
		entry *entries[2];

		/*
		 * Clear the node.
		 */
		void
		clear()
		{
			if (entries[0]) {
				entries[0]->clear();
				delete entries[0];
			}
			if (entries[1]) {
				entries[1]->clear();
				delete entries[1];
			}
		}
	};

	/*
	 * Find critical bit.
	 */
	static int
	find_crit_bit(key_type lhs, key_type rhs)
	{
		return find_last_set_64(lhs ^ rhs);
	}

	/*
	 * Insert leaf into the tree.
	 */
	void
	insert_leaf(const entry *e, int diff)
	{
		auto new_node = new node();
		new_node->diff = diff;

		int d = BIT_IS_SET(e->key, new_node->diff);
		new_node->entries[d] = new entry(*e);

		auto dest_entry = root;
		while (dest_entry->inode != nullptr) {
			auto n = dest_entry->inode;
			if (n->diff < new_node->diff)
				break;

			dest_entry = n->entries[BIT_IS_SET(e->key, n->diff)];
		}

		new_node->entries[!d] = new entry(*dest_entry);
		dest_entry->key = 0;
		dest_entry->inode = new_node;
		dest_entry->value = nullptr;
	}

	/*
	 * Fetch leaf from the tree.
	 */
	entry *
	get_leaf(uint64_t key, entry **parent)
	{
		auto n = root;
		entry *p = nullptr;

		while (n->inode != nullptr) {
			p = n;
			n = n->inode->entries[BIT_IS_SET(key, n->inode->diff)];
		}

		if (n->key == key) {
			if (parent)
				*parent = p;

			return n;
		}

		return nullptr;
	}

	/*
	 * Recursive foreach on nodes.
	 */
	int
	foreach_node(const entry *e, callback clb, void *arg)
	{
		int ret = 0;

		if (e->inode != nullptr) {
			auto n = e->inode;
			if (foreach_node(n->entries[0], clb, arg) == 0)
				foreach_node(n->entries[1], clb, arg);
		} else {
			ret = clb(e->key, e->value, arg);
		}

		return ret;
	}

	/* Tree root */
	entry *root;
};

} /* namespace examples */

#endif /* LIBPMEMOBJ_CPP_EXAMPLES_CTREE_MAP_VOLATILE_HPP */