source: mainline/uspace/lib/bithenge/tree.h@ 3a7356dc

/*
 * 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 <sys/types.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;

typedef struct bithenge_node_t {
        /** @privatesection */
        bithenge_node_type_t type;
        unsigned int refs;
        union {
                const struct bithenge_internal_node_ops_t *internal_ops;
                bool boolean_value;
                bithenge_int_t integer_value;
                struct {
                        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 int (*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 */
        int (*for_each)(bithenge_node_t *self, bithenge_for_each_func_t func, void *data);
        /** @copydoc bithenge_node_t::bithenge_node_get */
        int (*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++;
}

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 int 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);
}

int 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;
}

int bithenge_init_internal_node(bithenge_node_t *,
    const bithenge_internal_node_ops_t *);
int bithenge_new_empty_internal_node(bithenge_node_t **);
int bithenge_new_simple_internal_node(bithenge_node_t **, bithenge_node_t **,
    bithenge_int_t, bool needs_free);
int bithenge_new_boolean_node(bithenge_node_t **, bool);
int bithenge_new_integer_node(bithenge_node_t **, bithenge_int_t);
int bithenge_new_string_node(bithenge_node_t **, const char *, bool);
bool bithenge_node_equal(bithenge_node_t *, bithenge_node_t *);

#endif

/** @}
 */