ntnode.h

Go to the documentation of this file.

 
#ifndef ECU_NTNODE_H_
#define ECU_NTNODE_H_
 
/*------------------------------------------------------------*/
/*------------------------- INCLUDES -------------------------*/
/*------------------------------------------------------------*/
 
/* STDLib. */
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
 
/* ECU. */
#include "ecu/dlist.h"
#include "ecu/object_id.h"
#include "ecu/utils.h"
 
/*------------------------------------------------------------*/
/*---------------------- DEFINES AND MACROS ------------------*/
/*------------------------------------------------------------*/
 
#define ECU_NTNODE_OBJ_UNUSED \
    ((void *)0)
 
#define ECU_NTNODE_DESTROY_UNUSED \
    ((void (*)(struct ecu_ntnode *, ecu_object_id_t))0)
 
#define ECU_NTNODE_GET_ENTRY(ptr_, type_, member_) \
    ECU_CONTAINER_OF(ptr_, type_, member_)
 
#define ECU_NTNODE_GET_CONST_ENTRY(ptr_, type_, member_) \
    ECU_CONST_CONTAINER_OF(ptr_, type_, member_)
 
#define ECU_NTNODE_CHILD_FOR_EACH(var_, iter_, parent_)                             \
    for (struct ecu_ntnode *var_ = ecu_ntnode_child_iterator_begin(iter_, parent_); \
         var_ != ecu_ntnode_child_iterator_end(iter_);                              \
         var_ = ecu_ntnode_child_iterator_next(iter_))
 
#define ECU_NTNODE_CONST_CHILD_FOR_EACH(var_, citer_, parent_)                              \
    for (const struct ecu_ntnode *var_ = ecu_ntnode_child_iterator_cbegin(citer_, parent_); \
         var_ != ecu_ntnode_child_iterator_cend(citer_);                                    \
         var_ = ecu_ntnode_child_iterator_cnext(citer_))
 
#define ECU_NTNODE_NEXT_SIBLING_AT_FOR_EACH(var_, iter_, start_)                       \
    for (struct ecu_ntnode *var_ = ecu_ntnode_next_sibling_iterator_at(iter_, start_); \
         var_ != ecu_ntnode_next_sibling_iterator_end(iter_);                          \
         var_ = ecu_ntnode_next_sibling_iterator_next(iter_))
 
#define ECU_NTNODE_CONST_NEXT_SIBLING_AT_FOR_EACH(var_, citer_, start_)                        \
    for (const struct ecu_ntnode *var_ = ecu_ntnode_next_sibling_iterator_cat(citer_, start_); \
         var_ != ecu_ntnode_next_sibling_iterator_cend(citer_);                                \
         var_ = ecu_ntnode_next_sibling_iterator_cnext(citer_))
 
#define ECU_NTNODE_NEXT_SIBLING_FOR_EACH(var_, iter_, start_)                             \
    for (struct ecu_ntnode *var_ = ecu_ntnode_next_sibling_iterator_begin(iter_, start_); \
         var_ != ecu_ntnode_next_sibling_iterator_end(iter_);                             \
         var_ = ecu_ntnode_next_sibling_iterator_next(iter_))
 
#define ECU_NTNODE_CONST_NEXT_SIBLING_FOR_EACH(var_, citer_, start_)                              \
    for (const struct ecu_ntnode *var_ = ecu_ntnode_next_sibling_iterator_cbegin(citer_, start_); \
         var_ != ecu_ntnode_next_sibling_iterator_cend(citer_);                                   \
         var_ = ecu_ntnode_next_sibling_iterator_cnext(citer_))
 
#define ECU_NTNODE_PARENT_AT_FOR_EACH(var_, iter_, start_)                       \
    for (struct ecu_ntnode *var_ = ecu_ntnode_parent_iterator_at(iter_, start_); \
         var_ != ecu_ntnode_parent_iterator_end(iter_);                          \
         var_ = ecu_ntnode_parent_iterator_next(iter_))
 
#define ECU_NTNODE_CONST_PARENT_AT_FOR_EACH(var_, citer_, start_)                        \
    for (const struct ecu_ntnode *var_ = ecu_ntnode_parent_iterator_cat(citer_, start_); \
         var_ != ecu_ntnode_parent_iterator_cend(citer_);                                \
         var_ = ecu_ntnode_parent_iterator_cnext(citer_))
 
#define ECU_NTNODE_PARENT_FOR_EACH(var_, iter_, start_)                             \
    for (struct ecu_ntnode *var_ = ecu_ntnode_parent_iterator_begin(iter_, start_); \
         var_ != ecu_ntnode_parent_iterator_end(iter_);                             \
         var_ = ecu_ntnode_parent_iterator_next(iter_))
 
#define ECU_NTNODE_CONST_PARENT_FOR_EACH(var_, citer_, start_)                              \
    for (const struct ecu_ntnode *var_ = ecu_ntnode_parent_iterator_cbegin(citer_, start_); \
         var_ != ecu_ntnode_parent_iterator_cend(citer_);                                   \
         var_ = ecu_ntnode_parent_iterator_cnext(citer_))
 
#define ECU_NTNODE_POSTORDER_FOR_EACH(var_, iter_, root_)                             \
    for (struct ecu_ntnode *var_ = ecu_ntnode_postorder_iterator_begin(iter_, root_); \
         var_ != ecu_ntnode_postorder_iterator_end(iter_);                            \
         var_ = ecu_ntnode_postorder_iterator_next(iter_))
 
#define ECU_NTNODE_CONST_POSTORDER_FOR_EACH(var_, citer_, root_)                              \
    for (const struct ecu_ntnode *var_ = ecu_ntnode_postorder_iterator_cbegin(citer_, root_); \
         var_ != ecu_ntnode_postorder_iterator_cend(citer_);                                  \
         var_ = ecu_ntnode_postorder_iterator_cnext(citer_))
 
#define ECU_NTNODE_PREORDER_FOR_EACH(var_, iter_, root_)                             \
    for (struct ecu_ntnode *var_ = ecu_ntnode_preorder_iterator_begin(iter_, root_); \
         var_ != ecu_ntnode_preorder_iterator_end(iter_);                            \
         var_ = ecu_ntnode_preorder_iterator_next(iter_))
 
#define ECU_NTNODE_CONST_PREORDER_FOR_EACH(var_, citer_, root_)                              \
    for (const struct ecu_ntnode *var_ = ecu_ntnode_preorder_iterator_cbegin(citer_, root_); \
         var_ != ecu_ntnode_preorder_iterator_cend(citer_);                                  \
         var_ = ecu_ntnode_preorder_iterator_cnext(citer_))
 
#define ECU_NTNODE_PREV_SIBLING_AT_FOR_EACH(var_, iter_, start_)                       \
    for (struct ecu_ntnode *var_ = ecu_ntnode_prev_sibling_iterator_at(iter_, start_); \
         var_ != ecu_ntnode_prev_sibling_iterator_end(iter_);                          \
         var_ = ecu_ntnode_prev_sibling_iterator_next(iter_))
 
#define ECU_NTNODE_CONST_PREV_SIBLING_AT_FOR_EACH(var_, citer_, start_)                        \
    for (const struct ecu_ntnode *var_ = ecu_ntnode_prev_sibling_iterator_cat(citer_, start_); \
         var_ != ecu_ntnode_prev_sibling_iterator_cend(citer_);                                \
         var_ = ecu_ntnode_prev_sibling_iterator_cnext(citer_))
 
#define ECU_NTNODE_PREV_SIBLING_FOR_EACH(var_, iter_, start_)                             \
    for (struct ecu_ntnode *var_ = ecu_ntnode_prev_sibling_iterator_begin(iter_, start_); \
         var_ != ecu_ntnode_prev_sibling_iterator_end(iter_);                             \
         var_ = ecu_ntnode_prev_sibling_iterator_next(iter_))
 
#define ECU_NTNODE_CONST_PREV_SIBLING_FOR_EACH(var_, citer_, start_)                              \
    for (const struct ecu_ntnode *var_ = ecu_ntnode_prev_sibling_iterator_cbegin(citer_, start_); \
         var_ != ecu_ntnode_prev_sibling_iterator_cend(citer_);                                   \
         var_ = ecu_ntnode_prev_sibling_iterator_cnext(citer_))
 
#define ECU_NTNODE_SIBLING_FOR_EACH(var_, iter_, start_)                             \
    for (struct ecu_ntnode *var_ = ecu_ntnode_sibling_iterator_begin(iter_, start_); \
         var_ != ecu_ntnode_sibling_iterator_end(iter_);                             \
         var_ = ecu_ntnode_sibling_iterator_next(iter_))
 
#define ECU_NTNODE_CONST_SIBLING_FOR_EACH(var_, citer_, start_)                              \
    for (const struct ecu_ntnode *var_ = ecu_ntnode_sibling_iterator_cbegin(citer_, start_); \
         var_ != ecu_ntnode_sibling_iterator_cend(citer_);                                   \
         var_ = ecu_ntnode_sibling_iterator_cnext(citer_))
 
/*------------------------------------------------------------*/
/*--------------------------- NTNODE -------------------------*/
/*------------------------------------------------------------*/
 
struct ecu_ntnode
{
    struct ecu_dnode dnode;
 
    struct ecu_dlist children;
 
    struct ecu_ntnode *parent;
 
    void (*destroy)(struct ecu_ntnode *me, ecu_object_id_t id);
};
 
/*------------------------------------------------------------*/
/*--------------------- NTNODE CHILD ITERATOR ----------------*/
/*------------------------------------------------------------*/
 
struct ecu_ntnode_child_iterator
{
    struct ecu_ntnode *current;
 
    struct ecu_ntnode *next;
};
 
struct ecu_ntnode_child_citerator
{
    const struct ecu_ntnode *current;
 
    const struct ecu_ntnode *next;
};
 
/*------------------------------------------------------------*/
/*-------------------- NTNODE PARENT ITERATOR ----------------*/
/*------------------------------------------------------------*/
 
struct ecu_ntnode_parent_iterator
{
    struct ecu_ntnode *current;
 
    struct ecu_ntnode *next;
};
 
struct ecu_ntnode_parent_citerator
{
    const struct ecu_ntnode *current;
 
    const struct ecu_ntnode *next;
};
 
/*------------------------------------------------------------*/
/*--------------- NTNODE NEXT SIBLING ITERATOR ---------------*/
/*------------------------------------------------------------*/
 
struct ecu_ntnode_next_sibling_iterator
{
    struct ecu_ntnode *current;
 
    struct ecu_ntnode *next;
};
 
struct ecu_ntnode_next_sibling_citerator
{
    const struct ecu_ntnode *current;
 
    const struct ecu_ntnode *next;
};
 
/*------------------------------------------------------------*/
/*------------------- NTNODE POSTORDER ITERATOR --------------*/
/*------------------------------------------------------------*/
 
struct ecu_ntnode_postorder_iterator
{
    struct ecu_ntnode delimiter;
 
    struct ecu_ntnode *root;
 
    struct ecu_ntnode *current;
 
    struct ecu_ntnode *next;
};
 
struct ecu_ntnode_postorder_citerator
{
    struct ecu_ntnode delimiter;
 
    const struct ecu_ntnode *root;
 
    const struct ecu_ntnode *current;
 
    const struct ecu_ntnode *next;
};
 
/*------------------------------------------------------------*/
/*------------------- NTNODE PREORDER ITERATOR ---------------*/
/*------------------------------------------------------------*/
 
struct ecu_ntnode_preorder_iterator
{
    struct ecu_ntnode delimiter;
 
    struct ecu_ntnode *root;
 
    struct ecu_ntnode *current;
};
 
struct ecu_ntnode_preorder_citerator
{
    struct ecu_ntnode delimiter;
 
    const struct ecu_ntnode *root;
 
    const struct ecu_ntnode *current;
};
 
/*------------------------------------------------------------*/
/*--------------- NTNODE PREV SIBLING ITERATOR ---------------*/
/*------------------------------------------------------------*/
 
struct ecu_ntnode_prev_sibling_iterator
{
    struct ecu_ntnode *current;
 
    struct ecu_ntnode *next;
};
 
struct ecu_ntnode_prev_sibling_citerator
{
    const struct ecu_ntnode *current;
 
    const struct ecu_ntnode *next;
};
 
/*------------------------------------------------------------*/
/*-------------------- NTNODE SIBLING ITERATOR ---------------*/
/*------------------------------------------------------------*/
 
struct ecu_ntnode_sibling_iterator
{
    struct ecu_ntnode *end;
 
    struct ecu_ntnode *current;
 
    struct ecu_ntnode *next;
};
 
struct ecu_ntnode_sibling_citerator
{
    const struct ecu_ntnode *end;
 
    const struct ecu_ntnode *current;
 
    const struct ecu_ntnode *next;
};
 
/*------------------------------------------------------------*/
/*------------------ NTNODE MEMBER FUNCTIONS -----------------*/
/*------------------------------------------------------------*/
 
#ifdef __cplusplus
extern "C" {
#endif
 
extern void ecu_ntnode_ctor(struct ecu_ntnode *me,
                            void (*destroy)(struct ecu_ntnode *me, ecu_object_id_t id),
                            ecu_object_id_t id);
 
extern void ecu_ntnode_destroy(struct ecu_ntnode *me);
extern void ecu_ntnode_clear(struct ecu_ntnode *me);
 
extern size_t ecu_ntnode_count(const struct ecu_ntnode *me);
 
extern struct ecu_ntnode *ecu_ntnode_first_child(struct ecu_ntnode *me);
 
extern const struct ecu_ntnode *ecu_ntnode_first_cchild(const struct ecu_ntnode *me);
 
extern ecu_object_id_t ecu_ntnode_id(const struct ecu_ntnode *me);
 
extern bool ecu_ntnode_in_tree(const struct ecu_ntnode *me);
 
extern void ecu_ntnode_insert_sibling_after(struct ecu_ntnode *pos, struct ecu_ntnode *sibling);
 
extern void ecu_ntnode_insert_sibling_before(struct ecu_ntnode *pos, struct ecu_ntnode *sibling);
 
extern bool ecu_ntnode_is_descendant(const struct ecu_ntnode *me);
 
extern bool ecu_ntnode_is_leaf(const struct ecu_ntnode *me);
 
extern bool ecu_ntnode_is_root(const struct ecu_ntnode *me);
 
extern struct ecu_ntnode *ecu_ntnode_last_child(struct ecu_ntnode *me);
 
extern const struct ecu_ntnode *ecu_ntnode_last_cchild(const struct ecu_ntnode *me);
 
extern struct ecu_ntnode *ecu_ntnode_lca(struct ecu_ntnode *n1, struct ecu_ntnode *n2);
 
extern const struct ecu_ntnode *ecu_ntnode_clca(const struct ecu_ntnode *n1, const struct ecu_ntnode *n2);
 
extern size_t ecu_ntnode_level(const struct ecu_ntnode *me);
 
extern struct ecu_ntnode *ecu_ntnode_next(struct ecu_ntnode *me);
 
extern const struct ecu_ntnode *ecu_ntnode_cnext(const struct ecu_ntnode *me);
 
extern struct ecu_ntnode *ecu_ntnode_parent(struct ecu_ntnode *me);
 
extern const struct ecu_ntnode *ecu_ntnode_cparent(const struct ecu_ntnode *me);
 
extern struct ecu_ntnode *ecu_ntnode_prev(struct ecu_ntnode *me);
 
extern const struct ecu_ntnode *ecu_ntnode_cprev(const struct ecu_ntnode *me);
 
extern void ecu_ntnode_push_child_back(struct ecu_ntnode *parent, struct ecu_ntnode *child);
 
extern void ecu_ntnode_push_child_front(struct ecu_ntnode *parent, struct ecu_ntnode *child);
 
extern void ecu_ntnode_remove(struct ecu_ntnode *me);
 
extern size_t ecu_ntnode_size(const struct ecu_ntnode *me);
 
extern bool ecu_ntnode_valid(const struct ecu_ntnode *me);
/*------------------------------------------------------------*/
/*------------------------ CHILD ITERATOR --------------------*/
/*------------------------------------------------------------*/
 
extern struct ecu_ntnode *ecu_ntnode_child_iterator_begin(struct ecu_ntnode_child_iterator *me,
                                                          struct ecu_ntnode *parent);
 
extern struct ecu_ntnode *ecu_ntnode_child_iterator_end(struct ecu_ntnode_child_iterator *me);
 
extern struct ecu_ntnode *ecu_ntnode_child_iterator_next(struct ecu_ntnode_child_iterator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_child_iterator_cbegin(struct ecu_ntnode_child_citerator *me,
                                                                 const struct ecu_ntnode *parent);
 
extern const struct ecu_ntnode *ecu_ntnode_child_iterator_cend(struct ecu_ntnode_child_citerator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_child_iterator_cnext(struct ecu_ntnode_child_citerator *me);
/*------------------------------------------------------------*/
/*------------------- NEXT SIBLING ITERATOR ------------------*/
/*------------------------------------------------------------*/
 
extern struct ecu_ntnode *ecu_ntnode_next_sibling_iterator_at(struct ecu_ntnode_next_sibling_iterator *me,
                                                              struct ecu_ntnode *start);
 
extern struct ecu_ntnode *ecu_ntnode_next_sibling_iterator_begin(struct ecu_ntnode_next_sibling_iterator *me,
                                                                 struct ecu_ntnode *start);
 
extern struct ecu_ntnode *ecu_ntnode_next_sibling_iterator_end(struct ecu_ntnode_next_sibling_iterator *me);
 
extern struct ecu_ntnode *ecu_ntnode_next_sibling_iterator_next(struct ecu_ntnode_next_sibling_iterator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_next_sibling_iterator_cat(struct ecu_ntnode_next_sibling_citerator *me,
                                                                     const struct ecu_ntnode *start);
 
extern const struct ecu_ntnode *ecu_ntnode_next_sibling_iterator_cbegin(struct ecu_ntnode_next_sibling_citerator *me,
                                                                        const struct ecu_ntnode *start);
 
extern const struct ecu_ntnode *ecu_ntnode_next_sibling_iterator_cend(struct ecu_ntnode_next_sibling_citerator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_next_sibling_iterator_cnext(struct ecu_ntnode_next_sibling_citerator *me);
/*------------------------------------------------------------*/
/*------------------------ PARENT ITERATOR -------------------*/
/*------------------------------------------------------------*/
 
extern struct ecu_ntnode *ecu_ntnode_parent_iterator_at(struct ecu_ntnode_parent_iterator *me,
                                                        struct ecu_ntnode *start);
 
extern struct ecu_ntnode *ecu_ntnode_parent_iterator_begin(struct ecu_ntnode_parent_iterator *me,
                                                           struct ecu_ntnode *start);
 
extern struct ecu_ntnode *ecu_ntnode_parent_iterator_end(struct ecu_ntnode_parent_iterator *me);
 
extern struct ecu_ntnode *ecu_ntnode_parent_iterator_next(struct ecu_ntnode_parent_iterator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_parent_iterator_cat(struct ecu_ntnode_parent_citerator *me,
                                                               const struct ecu_ntnode *start);
 
extern const struct ecu_ntnode *ecu_ntnode_parent_iterator_cbegin(struct ecu_ntnode_parent_citerator *me,
                                                                  const struct ecu_ntnode *start);
 
extern const struct ecu_ntnode *ecu_ntnode_parent_iterator_cend(struct ecu_ntnode_parent_citerator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_parent_iterator_cnext(struct ecu_ntnode_parent_citerator *me);
/*------------------------------------------------------------*/
/*--------------------- POSTORDER ITERATOR -------------------*/
/*------------------------------------------------------------*/
 
extern struct ecu_ntnode *ecu_ntnode_postorder_iterator_begin(struct ecu_ntnode_postorder_iterator *me,
                                                              struct ecu_ntnode *root);
 
extern struct ecu_ntnode *ecu_ntnode_postorder_iterator_end(struct ecu_ntnode_postorder_iterator *me);
 
extern struct ecu_ntnode *ecu_ntnode_postorder_iterator_next(struct ecu_ntnode_postorder_iterator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_postorder_iterator_cbegin(struct ecu_ntnode_postorder_citerator *me,
                                                                     const struct ecu_ntnode *root);
 
extern const struct ecu_ntnode *ecu_ntnode_postorder_iterator_cend(struct ecu_ntnode_postorder_citerator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_postorder_iterator_cnext(struct ecu_ntnode_postorder_citerator *me);
/*------------------------------------------------------------*/
/*----------------------- PREORDER ITERATOR ------------------*/
/*------------------------------------------------------------*/
 
extern struct ecu_ntnode *ecu_ntnode_preorder_iterator_begin(struct ecu_ntnode_preorder_iterator *me,
                                                             struct ecu_ntnode *root);
 
extern struct ecu_ntnode *ecu_ntnode_preorder_iterator_end(struct ecu_ntnode_preorder_iterator *me);
 
extern struct ecu_ntnode *ecu_ntnode_preorder_iterator_next(struct ecu_ntnode_preorder_iterator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_preorder_iterator_cbegin(struct ecu_ntnode_preorder_citerator *me,
                                                                    const struct ecu_ntnode *root);
 
extern const struct ecu_ntnode *ecu_ntnode_preorder_iterator_cend(struct ecu_ntnode_preorder_citerator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_preorder_iterator_cnext(struct ecu_ntnode_preorder_citerator *me);
/*------------------------------------------------------------*/
/*------------------- PREV SIBLING ITERATOR ------------------*/
/*------------------------------------------------------------*/
 
extern struct ecu_ntnode *ecu_ntnode_prev_sibling_iterator_at(struct ecu_ntnode_prev_sibling_iterator *me,
                                                              struct ecu_ntnode *start);
 
extern struct ecu_ntnode *ecu_ntnode_prev_sibling_iterator_begin(struct ecu_ntnode_prev_sibling_iterator *me,
                                                                 struct ecu_ntnode *start);
 
extern struct ecu_ntnode *ecu_ntnode_prev_sibling_iterator_end(struct ecu_ntnode_prev_sibling_iterator *me);
 
extern struct ecu_ntnode *ecu_ntnode_prev_sibling_iterator_next(struct ecu_ntnode_prev_sibling_iterator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_prev_sibling_iterator_cat(struct ecu_ntnode_prev_sibling_citerator *me,
                                                                     const struct ecu_ntnode *start);
 
extern const struct ecu_ntnode *ecu_ntnode_prev_sibling_iterator_cbegin(struct ecu_ntnode_prev_sibling_citerator *me,
                                                                        const struct ecu_ntnode *start);
 
extern const struct ecu_ntnode *ecu_ntnode_prev_sibling_iterator_cend(struct ecu_ntnode_prev_sibling_citerator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_prev_sibling_iterator_cnext(struct ecu_ntnode_prev_sibling_citerator *me);
/*------------------------------------------------------------*/
/*----------------------- SIBLING ITERATOR -------------------*/
/*------------------------------------------------------------*/
 
extern struct ecu_ntnode *ecu_ntnode_sibling_iterator_begin(struct ecu_ntnode_sibling_iterator *me,
                                                            struct ecu_ntnode *start);
 
extern struct ecu_ntnode *ecu_ntnode_sibling_iterator_end(struct ecu_ntnode_sibling_iterator *me);
 
extern struct ecu_ntnode *ecu_ntnode_sibling_iterator_next(struct ecu_ntnode_sibling_iterator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_sibling_iterator_cbegin(struct ecu_ntnode_sibling_citerator *me,
                                                                   const struct ecu_ntnode *start);
 
extern const struct ecu_ntnode *ecu_ntnode_sibling_iterator_cend(struct ecu_ntnode_sibling_citerator *me);
 
extern const struct ecu_ntnode *ecu_ntnode_sibling_iterator_cnext(struct ecu_ntnode_sibling_citerator *me);
#ifdef __cplusplus
}
#endif
 
#endif /* ECU_NTNODE_H_ */