/* * 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 /** @} */