/*
 * Copyright (c) 2012 Sean Bartell
 * 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.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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.
 */

/** @addtogroup bithenge
 * @{
 */
/**
 * @file
 * Trees and nodes.
 */

#ifndef BITHENGE_TREE_H_
#define BITHENGE_TREE_H_

#include <assert.h>
#include <stdbool.h>
#include "os.h"

/** Indicates the type of a tree node. */
typedef enum {
	/** An internal node with labelled edges to other nodes. */
	BITHENGE_NODE_INTERNAL = 1,
	/** A leaf node holding a boolean value. */
	BITHENGE_NODE_BOOLEAN,
	/** A leaf node holding an integer. */
	BITHENGE_NODE_INTEGER,
	/** A leaf node holding a string. */
	BITHENGE_NODE_STRING,
	/** A leaf node holding a binary blob. */
	BITHENGE_NODE_BLOB,
} bithenge_node_type_t;

/** A tree node. It can have any of the types in @a bithenge_node_type_t. */
typedef struct bithenge_node_t {
	/** @privatesection */
	bithenge_node_type_t type;
	unsigned int refs;
	union {
		/** @privatesection */
		const struct bithenge_internal_node_ops_t *internal_ops;
		bool boolean_value;
		bithenge_int_t integer_value;
		struct {
			/** @privatesection */
			const char *ptr;
			bool needs_free;
		} string_value;
		const struct bithenge_random_access_blob_ops_t *blob_ops;
	};
} bithenge_node_t;

/** A callback function used to iterate over a node's children. It takes
 * ownership of a reference to both the key and the value.
 * @memberof bithenge_node_t
 * @param key The key.
 * @param value The value.
 * @param data Data provided to @a bithenge_node_t::bithenge_node_for_each.
 * @return EOK on success or an error code from errno.h. */
typedef errno_t (*bithenge_for_each_func_t)(bithenge_node_t *key, bithenge_node_t *value, void *data);

/** Operations providing access to an internal node. */
typedef struct bithenge_internal_node_ops_t {
	/** @copydoc bithenge_node_t::bithenge_node_for_each */
	errno_t (*for_each)(bithenge_node_t *self, bithenge_for_each_func_t func, void *data);
	/** @copydoc bithenge_node_t::bithenge_node_get */
	errno_t (*get)(bithenge_node_t *self, bithenge_node_t *key,
	    bithenge_node_t **out);
	/** Destroys the internal node.
	 * @param self The node to destroy. */
	void (*destroy)(bithenge_node_t *self);
} bithenge_internal_node_ops_t;

/** Find the type of a node.
 * @memberof bithenge_node_t
 * @param node The node.
 * @return The type of the node. */
static inline bithenge_node_type_t bithenge_node_type(const bithenge_node_t *node)
{
	return node->type;
}

/** Increment a node's reference count.
 * @memberof bithenge_node_t
 * @param node The node to reference. */
static inline void bithenge_node_inc_ref(bithenge_node_t *node)
{
	assert(node);
	node->refs++;
}

/** @memberof bithenge_node_t */
void bithenge_node_dec_ref(bithenge_node_t *node);

/** Iterate over a node's children.
 * @memberof bithenge_node_t
 * @param self The internal node to iterate over.
 * @param func The callback function.
 * @param data Data to provide to the callback function.
 * @return EOK on success or an error code from errno.h. */
static inline errno_t bithenge_node_for_each(bithenge_node_t *self,
    bithenge_for_each_func_t func, void *data)
{
	assert(self->type == BITHENGE_NODE_INTERNAL);
	return self->internal_ops->for_each(self, func, data);
}

/** @memberof bithenge_node_t */
errno_t bithenge_node_get(bithenge_node_t *, bithenge_node_t *,
    bithenge_node_t **);

/** Get the value of a boolean node.
 * @memberof bithenge_node_t
 * @param self The boolean node.
 * @return The node's value. */
static inline bool bithenge_boolean_node_value(bithenge_node_t *self)
{
	assert(self->type == BITHENGE_NODE_BOOLEAN);
	return self->boolean_value;
}

/** Get the value of an integer node.
 * @memberof bithenge_node_t
 * @param self The integer node.
 * @return The node's value. */
static inline bithenge_int_t bithenge_integer_node_value(bithenge_node_t *self)
{
	assert(self->type == BITHENGE_NODE_INTEGER);
	return self->integer_value;
}

/** Get the value of an string node.
 * @memberof bithenge_node_t
 * @param self The string node.
 * @return The node's value. */
static inline const char *bithenge_string_node_value(bithenge_node_t *self)
{
	assert(self->type == BITHENGE_NODE_STRING);
	return self->string_value.ptr;
}

/** @memberof bithenge_node_t */
errno_t bithenge_init_internal_node(bithenge_node_t *,
    const bithenge_internal_node_ops_t *);
/** @memberof bithenge_node_t */
errno_t bithenge_new_empty_internal_node(bithenge_node_t **);
/** @memberof bithenge_node_t */
errno_t bithenge_new_simple_internal_node(bithenge_node_t **, bithenge_node_t **,
    bithenge_int_t, bool needs_free);
/** @memberof bithenge_node_t */
errno_t bithenge_new_boolean_node(bithenge_node_t **, bool);
/** @memberof bithenge_node_t */
errno_t bithenge_new_integer_node(bithenge_node_t **, bithenge_int_t);
/** @memberof bithenge_node_t */
errno_t bithenge_new_string_node(bithenge_node_t **, const char *, bool);
/** @memberof bithenge_node_t */
errno_t bithenge_node_equal(bool *, bithenge_node_t *, bithenge_node_t *);

#endif

/** @}
 */
