node.h

// node.h - A node implementation.
//
// Library macros:
// - STRUCTYPES_IMPLEMENTATION: defines all of structype's implementations.
// - STRUCTYPES_DEBUG: if defined, prints error messages.

#ifndef NODE_H_
#define NODE_H_

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdarg.h>

/** A node. */
typedef struct Node {
    /** Value of the node. */
    void *value;
    /** Pointer to the parent node. */
    struct Node *parent;
    /** Array of children nodes. */
    struct Node **nodes;
    /** Number of child nodes. */
    size_t size;
} Node;

/**
 * Defines how a function should handle sorting algorithms:
 * - `NONE`: insertion order (no sort).
 * - `ASC` : ascending order.
 * - `DESC`: descending order.
 */
typedef enum {
    NONE,
    ASC,
    DESC,
} NodeSortOpts;

/**
 * Defines how nodes will be printed:
 * - indent: starting indentation.
 * - indent_step: indent increment on each level.
 * - sort: how nodes' values will be sorted. Check docs for `NodeSortOpts`.
 */
typedef struct {
    unsigned int indent;
    unsigned int indent_step;
    NodeSortOpts sort;
} NodePrintOpts;

/**
 * Creates a new `Node` with a `value`.
 *
 * Returns `NULL` when:
 * - `malloc` fails to allocate a new `Node`.
 */
Node *node_new(void *value);

/**
 * Frees `node->nodes` and `node`.
 *
 * To free the values of stack or heap allocated nodes, use `node_free_stack`
 * or `node_free`, respectively.
 *
 * Returns `false` when:
 * - `node` evaluates to false.
 */
bool node_free_struct(Node *node);

/**
 * Frees each node inside `node->nodes` (and their values) and `node->value`,
 * then calls `node_free_struct` to cleanup `node->nodes` and `node`.
 *
 * This is used to free nodes with `heap` allocated values.
 * To free nodes with `stack` allocated values, use `node_free_stack`.
 *
 * Keep in mind that if you free a node that has a parent, not removing that
 * index in the parent is a reference to a dead node.
 *
 * Returns `false` when:
 * - `node` evaluates to false.
 * - Recursion fails on `node_free`.
 * - `node_free_struct` fails.
 */
bool node_free(Node *node);

/**
 * Frees each node inside `node->nodes` (not their values), then calls
 * `node_free_struct` to cleanup `node->nodes` and `node`.
 *
 * This is used to free nodes with `stack` allocated values.
 * To free nodes with `heap` allocated values, use `node_free`.
 *
 * Keep in mind that if you free a node that has a parent, not removing that
 * index in the parent is a reference to a dead node.
 *
 * Returns `false` when:
 * - `node` evaluates to false.
 * - Recursion fails on `node_free`.
 * - `node_free_struct` fails.
 */
bool node_free_stack(Node *node);

/**
 * Creates a new `Node` with a `parent` and a `value`.
 *
 * Returns `NULL` when:
 * - `parent` evaluates to false.
 * - `node_new` fails to create `node`.
 * - `node_add_child` fails to append `node` to `parent`.
 */
Node *node_add(Node *parent, void *value);

/**
 * Appends `child` to `parent`.
 *
 * Returns `false` when:
 * - `parent` or `child` evaluate to false.
 * - `parent` points to the same reference as `child`.
 * - `realloc` for `node->nodes` fails.
 */
bool node_add_child(Node *parent, Node *child);

/**
 * Same as `node_print_deep`, but with style options.
 *
 * Nodes with `size == 0` will be printed first always.
 * `opts` changes the function's behaviour. Check docs for `NodePrintOpts`.
 *
 * Returns `false` when:
 * - `node` evaluates to false.
 * - `node->value` is `NULL`.
 * - `opts.indent_step < 1`.
 */
bool node_print(Node *node, NodePrintOpts opts);

/**
 * A "deep" print of a `Node`.
 *
 * Prints the value of `node` and recurses over each child node (and their
 * child nodes too).
 *
 * Use `node_print_shallow` to print just the immediate child nodes of `node`.
 *
 * Returns `false` when:
 * - `node` evaluates to false.
 */
bool node_print_deep(Node *node);

/**
 * A "shallow" print of a `Node`.
 *
 * Prints the value of `node` and the value of its immediate child nodes, but
 * it doesn't recurse into deeper nodes.
 *
 * Use `node_print_deep` to print deeper nodes of `node`.
 *
 * Returns `false` when:
 * - `node` evaluates to false.
 */
bool node_print_shallow(Node *node);

/**
 * Prints the values of `parent`, `value` and `size` of `node`.
 *
 * Returns `false` when:
 * - `node` evaluates to false.
 */
bool node_info(Node *node);

/**
 * Counts the total of child nodes in `node` (doesn't count `node`).
 *
 * Returns `0` when:
 * - `node` evaluates to false.
 */
size_t node_total(Node *node);

/**
 * Returns a NodePrintOpts with the defined default values:
 *
 * By defining the implementation macros, the default values are:
 * - indent: 0
 * - indent_step: 2
 * - sort: `NONE`
 */
NodePrintOpts nodeprintopts_default();

#endif // NODE_H_

// This allows the user to use an implementation in more than one file without linker errors
#if !defined(__STRUCTYPES_NODE_IMPLEMENTED) && (defined(STRUCTYPES_IMPLEMENTATION))
#define __STRUCTYPES_NODE_IMPLEMENTED

#ifdef STRUCTYPES_DEBUG
static void _node_err(const char *file, int line, const char *func, const char *fmt, ...) {
    va_list args;
    va_start(args, fmt);
    fprintf(stderr, "[%s:%d] %s: ", file, line, func);
    vfprintf(stderr, fmt, args);
    fprintf(stderr, "\n");
    va_end(args);
}
#define NODE_THROW(ret, fmt, ...) ({ _node_err(__FILE__, __LINE__, __func__, fmt, ##__VA_ARGS__); return ret; })
#else
#define NODE_THROW(ret, fmt, ...) ({ return ret; })
#endif // STRUCTYPES_DEBUG

static int _indent = 0;
static int _indent_step = 2;
static NodeSortOpts _sort;

static int _node_comp(const void *a, const void *b) {
    const Node *n1 = a;
    const Node *n2 = b;

    const char *s1 = *(const char **)n1->value;
    const char *s2 = *(const char **)n2->value;

    while (*s1 && *s2 && *s1 == *s2) s1++, s2++;

    int diff = (unsigned char)*s1 - (unsigned char)*s2;

    return (_sort == ASC) ? diff : -diff;
}

static void _print_indent(unsigned int indent, void *value) {
    printf("%*s%s\n", indent, "", (char *)value);
}

Node *node_new(void *value) {
    Node *node = malloc(sizeof(Node));
    if (!node) NODE_THROW(NULL, "malloc error on initialize root");

    node->value = value;
    node->parent = NULL;
    node->nodes = NULL;
    node->size = 0;

    return node;
}

bool node_free_struct(Node *node) {
    if (!node) NODE_THROW(false, "node evaluates to false");

    if (node->nodes) free(node->nodes);

    free(node);
    node = NULL;

    return true;
}

bool node_free(Node *node) {
    if (!node) NODE_THROW(false, "node evaluates to false");

    if (node->nodes) {
        for (size_t i = 0; i < node->size; i++) {
            if (!node_free(node->nodes[i]))
                NODE_THROW(false, "recursion error");
        }
    }

    if (node->value != NULL) free(node->value);

    return node_free_struct(node);
}

bool node_free_stack(Node *node) {
    if (!node) NODE_THROW(false, "node evaluates to false");

    if (node->nodes) {
        for (size_t i = 0; i < node->size; i++) {
            if (!node_free_stack(node->nodes[i]))
                NODE_THROW(false, "recursion error");
        }
    }

    return node_free_struct(node);
}

Node *node_add(Node *parent, void *value) {
    if (!parent) NODE_THROW(NULL, "parent evaluates to false");

    Node *node = node_new(value);
    if (!node) NODE_THROW(NULL, "malloc error on initialize root");

    if (!node_add_child(parent, node))
        NODE_THROW(NULL, "error adding node to parent");

    return node;
}

bool node_add_child(Node *parent, Node *child) {
    if (!parent) NODE_THROW(false, "parent evaluates to false");
    if (!child) NODE_THROW(false, "child evaluates to false");

    if (parent == child)
        NODE_THROW(false, "parent points to the same reference as child");

    void *tmp = realloc(parent->nodes, (parent->size + 1) * sizeof(Node *));
    if (!tmp) NODE_THROW(false, "realloc error");

    child->parent = parent;

    parent->nodes = tmp;
    parent->nodes[parent->size++] = child;

    return true;
}

bool node_print(Node *node, NodePrintOpts opts) {
    if (!node) NODE_THROW(false, "node evaluates to false");

    if (opts.indent_step < 1)
        NODE_THROW(false, "indent_step must be greater than 0");

    _print_indent(opts.indent, node->value);
    if (!node->size) return true;

    size_t sizeofNode = sizeof(void *);

    Node **zero = malloc(sizeofNode * node->size);
    if (!zero) NODE_THROW(false, "malloc error for zero");

    Node **nonZero = malloc(sizeofNode * node->size);
    if (!nonZero) {
        free(zero);
        NODE_THROW(false, "malloc error for nonZero");
    }

    size_t zeroLen = 0;
    size_t nonZeroLen = 0;

    for (size_t i = 0; i < node->size; i++) {
        if (!node->nodes[i]->size) zero[zeroLen++] = node->nodes[i];
        else nonZero[nonZeroLen++] = node->nodes[i];
    }

    if (opts.sort != NONE) {
        _sort = opts.sort;
        qsort(zero, zeroLen, sizeofNode, _node_comp);
        qsort(nonZero, nonZeroLen, sizeofNode, _node_comp);
    }

    opts.indent += opts.indent_step;

    for (size_t i = 0; i < zeroLen; i++)
        _print_indent(opts.indent, zero[i]->value);

    for (size_t i = 0; i < nonZeroLen; i++)
        if (!node_print(nonZero[i], opts)) {
            free(zero);
            free(nonZero);
            NODE_THROW(false, "recursion error");
        }

    free(zero);
    free(nonZero);

    return true;
}

bool node_print_deep(Node *node) {
    if (!node) NODE_THROW(false, "node evaluates to false");

    _print_indent(_indent, node->value);

    _indent += _indent_step;
    size_t local_indent = _indent;

    for (size_t i = 0; i < node->size; i++) {
        Node *child = node->nodes[i];

        if (child->size < 1) {
            _print_indent(_indent, child->value);
            continue;
        }

        if (!node_print_deep(child)) NODE_THROW(false, "recursion error");
        _indent = local_indent;
    }

    return true;
}

bool node_print_shallow(Node *node) {
    if (!node) NODE_THROW(false, "node evaluates to false");

    printf("%s\n", (char *)node->value);

    for (size_t i = 0; i < node->size; i++)
        _print_indent(_indent_step, node->nodes[i]->value);

    return true;
}

bool node_info(Node *node) {
    if (!node) NODE_THROW(false, "node evaluates to false");

    printf("parent: %s\n",  node->parent
        ? (char *)node->parent->value
        : "null"
    );

    printf("value:  %s\n",  (char *)node->value);
    printf("size:   %zu\n", node->size);

    return true;
}

size_t node_total(Node *node) {
    if (!node) NODE_THROW(0, "node evaluates to false");

    size_t total = node->size;

    for (size_t i = 0; i < node->size; i++)
        total += node_total(node->nodes[i]);

    return total;
}

NodePrintOpts nodeprintopts_default() {
    return (NodePrintOpts) {
        .indent      = 0,
        .indent_step = 2,
        .sort        = ASC,
    };
}

#endif // STRUCTYPES_IMPLEMENTATION