A pattern for applying a map function to a dag in C without using malloc.

map_dag.c

#include <stdio.h>
#include <zconf.h>
#include <stdlib.h>
#include <assert.h>

typedef struct IntNode {
    int leaf;
    int value;
    int numChildren;
    struct IntNode **children;
} IntNode;

typedef struct CharNode {
    int leaf;
    char value;
    int numChildren;
    struct CharNode **children;
} CharNode;

typedef struct Link {
    const IntNode *input;
    CharNode **output;
    struct Link *next;
} Link;

void mapIntToChar(const IntNode *inputRoot, void done(CharNode *)) {
    CharNode *outputRoot = NULL;
    Link link0 = {
            .input = inputRoot,
            .output = &outputRoot,
            .next = NULL,
    };
    Link *head, *current, *tail;
    head = current = tail = &link0;

    while (current != NULL) {
        // head <= current <= tail <= NULL
        const IntNode *input = current->input;
        CharNode **output = current->output;
        current = current->next;
        if (current == NULL) {
            tail = NULL;
        }

        *output = alloca(sizeof(CharNode));
        (*output)->value = (char) (input->value + 'a');
        if (input->leaf) {
            (*output)->leaf = 1;
        } else {
            (*output)->leaf = 0;
            int numChildren = input->numChildren;
            assert(numChildren >= 0);
            (*output)->numChildren = numChildren;
            (*output)->children = alloca(sizeof(CharNode *) * numChildren);

            for (int i = 0; i < numChildren; ++i) {
                const IntNode *childInput = input->children[i];
                CharNode **childOutput = (*output)->children + i;

                // head <= current <= tail <= NULL
                Link *link;
                if (head == current) {
                    link = alloca(sizeof(Link));
                } else {
                    link = head;
                    head = head->next;
                }
                if (tail != NULL) {
                    tail->next = link;
                }
                tail = link;
                if (current == NULL) {
                    current = tail;
                }
                if (head == NULL) {
                    head = current;
                }
                tail->input = childInput;
                tail->output = childOutput;
                tail->next = NULL;
            }
        }
    }
    done(outputRoot);
}

void printIntNode(IntNode *node, int indent) {
    if (node == NULL) {
        return;
    }
    printf("%*s%d\n", indent, "", node->value);
    if (!node->leaf) {
        for (int i = 0; i < node->numChildren; ++i) {
            printIntNode(node->children[i], indent + 2);
        }
    }
}

void printCharNode(CharNode *node, int indent) {
    if (node == NULL) {
        return;
    }
    printf("%*c\n", indent + 1, node->value);
    if (!node->leaf) {
        for (int i = 0; i < node->numChildren; ++i) {
            printCharNode(node->children[i], indent + 2);
        }
    }
}

#define INT_LEAF(i) \
    IntNode leaf ## i; \
    leaf ## i.leaf = 1;\
    leaf ## i.value = i;

#define INT_NODE(i, ...) \
    IntNode *children ## i[] = { __VA_ARGS__ };\
    IntNode node ## i;   \
    node ## i.value = i;                     \
    node ## i.leaf = 0;\
    node ## i.numChildren = sizeof(children ## i) / sizeof(IntNode *); \
    node ## i.children = children ## i;

void callback(CharNode *root) {
    printf("done!\n");
    printCharNode(root, 0);
}

int main() {
    INT_LEAF(0)
    INT_LEAF(1)
    INT_LEAF(2)
    INT_LEAF(3)
    INT_LEAF(4)
    INT_LEAF(5)
    INT_LEAF(6)
    INT_LEAF(7)
    INT_NODE(8, &leaf0, &leaf1)
    INT_NODE(9, &leaf2, &leaf3)
    INT_NODE(10, &leaf4, &leaf5)
    INT_NODE(11, &leaf6, &leaf7)
    INT_NODE(12, &node8, &node9)
    INT_NODE(13, &node10, &node11)
    INT_NODE(14, &node12, &node13)
    printIntNode(&node14, 0);
    mapIntToChar(&node14, callback);
}