#include "expr.h" #include #include static void release_node(ex_tree *tree, ex_node *node) { ex_node *pending[256], *reverse[256]; size_t pending_size = 0, reverse_size = 0, i; if (node) pending[pending_size++] = node; while (pending_size) { ex_node *current = pending[--pending_size]; reverse[reverse_size++] = current; for (i = 0; i < current->arity; ++i) pending[pending_size++] = current->child[i]; } while (reverse_size) tree->memory.release(tree->memory.context, reverse[--reverse_size]); } ex_status ex_init(ex_tree *tree, ex_allocator memory, size_t nodes, size_t depth) { if (!tree || !memory.allocate || !memory.release || !nodes || nodes > 256 || !depth || depth > 32) return EX_ARGUMENT; tree->root = NULL; tree->memory = memory; tree->max_nodes = nodes; tree->max_depth = depth; return EX_OK; } void ex_destroy(ex_tree *tree) { if (!tree) return; release_node(tree, tree->root); tree->root = NULL; } static size_t node_count(const ex_node *node) { size_t result = 1; size_t i; if (!node) return 0; for (i = 0; i < node->arity; ++i) result += node_count(node->child[i]); return result; } static size_t node_height(const ex_node *node) { size_t height = 0; size_t i; if (!node) return 0; for (i = 0; i < node->arity; ++i) { size_t child = node_height(node->child[i]); if (child > height) height = child; } return height + 1; } size_t ex_count(const ex_tree *tree) { return tree ? node_count(tree->root) : 0; } size_t ex_height(const ex_tree *tree) { return tree ? node_height(tree->root) : 0; } static void visit_node(const ex_node *node, ex_visitor visit, void *context) { size_t i; if (!node) return; for (i = 0; i < node->arity; ++i) visit_node(node->child[i], visit, context); visit(context, node); } void ex_visit(const ex_tree *tree, ex_visitor visit, void *context) { if (tree && visit) visit_node(tree->root, visit, context); } static ex_node *copy_node(ex_tree *destination, const ex_node *source, ex_status *status) { const ex_node *originals[256]; ex_node *copies[256]; size_t take = 0, put = 1, i; ex_node *root; if (!source) return NULL; root = destination->memory.allocate(destination->memory.context, sizeof(*root)); if (!root) { *status = EX_MEMORY; return NULL; } *root = *source; root->arity = 0; memset(root->child, 0, sizeof(root->child)); originals[0] = source; copies[0] = root; while (take < put) { const ex_node *current = originals[take]; ex_node *copy = copies[take++]; for (i = 0; i < current->arity; ++i) { ex_node *child = destination->memory.allocate(destination->memory.context, sizeof(*child)); if (!child) { *status = EX_MEMORY; release_node(destination, root); return NULL; } *child = *current->child[i]; child->arity = 0; memset(child->child, 0, sizeof(child->child)); copy->child[copy->arity++] = child; originals[put] = current->child[i]; copies[put++] = child; } } return root; } ex_status ex_clone(ex_tree *destination, const ex_tree *source) { ex_node *replacement; ex_status status = EX_OK; if (!destination || !source || !destination->memory.allocate || !destination->memory.release) return EX_ARGUMENT; if (node_count(source->root) > destination->max_nodes || node_height(source->root) > destination->max_depth) return EX_LIMIT; replacement = copy_node(destination, source->root, &status); if (status != EX_OK) return status; ex_destroy(destination); destination->root = replacement; return EX_OK; } typedef struct { char text[EX_TEXT_LIMIT + 1]; size_t length; int overflow; } writer; static void append(writer *out, const char *text) { size_t length = strlen(text); if (out->length + length > EX_TEXT_LIMIT) { out->overflow = 1; return; } memcpy(out->text + out->length, text, length); out->length += length; } static const char *kind_name(ex_kind kind) { switch (kind) { case EX_ADD: return "add"; case EX_SUB: return "sub"; case EX_MUL: return "mul"; case EX_MIN: return "min"; case EX_MAX: return "max"; case EX_NEG: return "neg"; case EX_ABS: return "abs"; case EX_SUM: return "sum"; default: return ""; } } static void render_node(const ex_node *node, writer *out) { size_t i; char number[32]; if (node->kind == EX_NUMBER) { snprintf(number, sizeof(number), "%lld", (long long)node->number); append(out, number); } else if (node->kind == EX_VARIABLE) { append(out, node->name); } else { append(out, "("); append(out, kind_name(node->kind)); for (i = 0; i < node->arity; ++i) { append(out, " "); render_node(node->child[i], out); } append(out, ")"); } } ex_status ex_render(const ex_tree *tree, char *buffer, size_t capacity, size_t *needed) { writer out; if (!tree || !needed || (!buffer && capacity)) return EX_ARGUMENT; memset(&out, 0, sizeof(out)); if (tree->root) render_node(tree->root, &out); if (out.overflow) return EX_LIMIT; *needed = out.length; if (capacity <= out.length) return EX_BUFFER; memcpy(buffer, out.text, out.length); buffer[out.length] = '\0'; return EX_OK; }