diff options
Diffstat (limited to 'lab04')
| -rw-r--r-- | lab04/Makefile | 23 | ||||
| -rw-r--r-- | lab04/README.md | 47 | ||||
| -rw-r--r-- | lab04/container_of.h | 49 | ||||
| -rw-r--r-- | lab04/expression.h | 319 | ||||
| -rw-r--r-- | lab04/list.h | 370 | ||||
| -rw-r--r-- | lab04/main.c | 9 | ||||
| -rw-r--r-- | lab04/polynomial.h | 876 | ||||
| -rw-r--r-- | lab04/stack.h | 219 | ||||
| -rw-r--r-- | lab04/tests/Makefile | 18 | ||||
| -rw-r--r-- | lab04/tests/test.c | 497 | ||||
| -rw-r--r-- | lab04/tui.c | 190 | ||||
| -rw-r--r-- | lab04/tui.h | 38 | ||||
| -rw-r--r-- | lab04/ui.c | 1543 | ||||
| -rw-r--r-- | lab04/ui.h | 9 | ||||
| -rw-r--r-- | lab04/vec.h | 1183 |
15 files changed, 5390 insertions, 0 deletions
diff --git a/lab04/Makefile b/lab04/Makefile new file mode 100644 index 0000000..dc9f8ab --- /dev/null +++ b/lab04/Makefile @@ -0,0 +1,23 @@ +CC ?= gcc +CFLAGS ?= -std=gnu11 -Wall -Wextra -O2 +LDLIBS ?= -lm + +TARGET := calculator +SOURCES := main.c ui.c tui.c +OBJECTS := $(SOURCES:.c=.o) + +.PHONY: all clean test + +all: $(TARGET) + +test: + $(MAKE) -C tests run + +$(TARGET): $(OBJECTS) + $(CC) $(CFLAGS) $(OBJECTS) $(LDLIBS) -o $@ + +%.o: %.c + $(CC) $(CFLAGS) -c $< -o $@ + +clean: + rm -f $(TARGET) $(OBJECTS) diff --git a/lab04/README.md b/lab04/README.md new file mode 100644 index 0000000..c2b753b --- /dev/null +++ b/lab04/README.md @@ -0,0 +1,47 @@ +# 数据结构实验 04 + +## 功能简介 + +本项目使用 GNU C11 实现一个简单的终端计算器，包含： + +- 线性表的添加、插入、删除、修改、查找和遍历； +- 向量加法、减法和夹角余弦计算； +- 顺序表多项式的加减、乘法和求导； +- 链表多项式的加减、乘法和求导。 +- 四则运算表达式求值。 + +底层实现使用自定义的 `vec` 动态数组和循环双向链表。 + +## 编译说明 + +在项目根目录执行： + +```sh +make +``` + +默认使用 GNU C11 标准编译，生成可执行文件 `calculator`。 + +编译参数包括 `-std=gnu11 -Wall -Wextra -O2`，链接时使用数学库 `-lm`。 + +清理编译文件： + +```sh +make clean +``` + +## 使用说明 + +运行程序： + +```sh +./calculator +``` + +在主菜单中选择线性表、向量、顺序表多项式，链表多项式或者四则运算表达式功能。菜单支持方向键或 `j`/`k` 移动，按 Enter 确认，按 `Esc` 或 `q` 返回或退出。 + +运行测试： + +```sh +make test +``` diff --git a/lab04/container_of.h b/lab04/container_of.h new file mode 100644 index 0000000..bffe7b7 --- /dev/null +++ b/lab04/container_of.h @@ -0,0 +1,49 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/** + * @file container_of.h + * @brief Provides type-aware container and member offset macros. + */ +#ifndef _CONTAINER_OF_H +#define _CONTAINER_OF_H + +#include <stddef.h> + +/** @brief Checks whether two expressions have compatible types. */ +#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) + +/** @brief Computes a member offset using the compiler builtin. */ +#undef offsetof +#define offsetof(TYPE, MEMBER) __builtin_offsetof(TYPE, MEMBER) + +/** @brief Obtains the type of a member of a structure type. */ +#define typeof_member(T, m) typeof(((T*)0)->m) + +/** + * @brief Converts a pointer to a structure member to its containing object. + * @param ptr A pointer to the member. + * @param type The type of the containing structure. + * @param member The member name within `type`. + * + * The macro performs a compile-time type compatibility check before applying + * the member offset. + */ +#define container_of(ptr, type, member) ({ \ + _Static_assert(__same_type(*(ptr), typeof_member(type, member)) || \ + __same_type(*(ptr), void), \ + "pointer type mismatch in container_of()"); \ + (type *)((void *)(ptr) - offsetof(type, member)); }) + + +/** + * @brief Converts a member pointer while preserving its const qualification. + * @param ptr A pointer to the member. + * @param type The type of the containing structure. + * @param member The member name within `type`. + */ +#define container_of_const(ptr, type, member) \ + _Generic(ptr, \ + const typeof(*(ptr)) *: ((const type *)container_of(ptr, type, member)),\ + default: ((type *)container_of(ptr, type, member)) \ + ) + +#endif /* _CONTAINER_OF_H */ diff --git a/lab04/expression.h b/lab04/expression.h new file mode 100644 index 0000000..f0e2847 --- /dev/null +++ b/lab04/expression.h @@ -0,0 +1,319 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +#ifndef EXPRESSION_H +#define EXPRESSION_H + +#include <ctype.h> +#include <errno.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdlib.h> +#include <string.h> + +#include "stack.h" + +#define EXPRESSION_NAME_MAX 64 + +enum expression_error_code { + EXPRESSION_OK, + EXPRESSION_SYNTAX_ERROR, + EXPRESSION_PAREN_ERROR, + EXPRESSION_UNKNOWN_VARIABLE, + EXPRESSION_UNSET_VARIABLE, + EXPRESSION_DIVISION_BY_ZERO, +}; + +struct expression_error { + enum expression_error_code code; + size_t position; +}; + +struct expression_variable { + char name[EXPRESSION_NAME_MAX]; + double value; + bool assigned; +}; + +struct expression_context { + struct vec variables; +}; + +static inline void expression_init(struct expression_context *ctx) +{ + vec_init(&ctx->variables, struct expression_variable); +} + +static inline void expression_destroy(struct expression_context *ctx) +{ + vec_destroy(&ctx->variables); +} + +static inline void expression_error(struct expression_error *error, + enum expression_error_code code, + size_t position) +{ + if (error) { + error->code = code; + error->position = position; + } +} + +static inline bool expression_name_start(unsigned char c) +{ + return isalpha(c) || c == '_'; +} + +static inline bool expression_name_char(unsigned char c) +{ + return isalnum(c) || c == '_'; +} + +static inline struct expression_variable * +expression_variable(struct expression_context *ctx, const char *name) +{ + for (size_t i = 0; i < ctx->variables.size; ++i) { + struct expression_variable *v = vec_at(&ctx->variables, i); + if (strcmp(v->name, name) == 0) { + return v; + } + } + return NULL; +} + +static inline bool expression_set_variable(struct expression_context *ctx, + const char *name, + double value) +{ + if (!expression_name_start((unsigned char)name[0]) || + strlen(name) >= EXPRESSION_NAME_MAX) return false; + for (const unsigned char *p = (const unsigned char *)name + 1; *p; ++p) { + if (!expression_name_char(*p)) { + return false; + } + } + struct expression_variable *v = expression_variable(ctx, name); + if (!v) { + struct expression_variable item = { .value = value, .assigned = true }; + strcpy(item.name, name); + if (!vec_push_back(&ctx->variables, &item)) { + return false; + } + } else { + v->value = value; + v->assigned = true; + } + return true; +} + +static inline bool expression_collect_variables(struct expression_context *ctx, + const char *text, + struct expression_error *error) +{ + vec_clear(&ctx->variables); + for (size_t i = 0; text[i];) { + unsigned char c = (unsigned char)text[i]; + if (isspace(c)) { + ++i; + } else if (expression_name_start(c)) { + size_t start = i++; + while (expression_name_char((unsigned char)text[i])) { + ++i; + } + size_t length = i - start; + if (length >= EXPRESSION_NAME_MAX) { + expression_error(error, EXPRESSION_SYNTAX_ERROR, start); + return false; + } + char name[EXPRESSION_NAME_MAX]; + memcpy(name, text + start, length); + name[length] = '\0'; + if (!expression_variable(ctx, name)) { + struct expression_variable item = { .assigned = false }; + strcpy(item.name, name); + if (!vec_push_back(&ctx->variables, &item)) { + expression_error(error, EXPRESSION_SYNTAX_ERROR, start); + return false; + } + } + } else if (isdigit(c) || c == '.' || c == '+' || c == '-' || + c == '*' || c == '/' || c == '(' || c == ')') { + ++i; + } else { + expression_error(error, EXPRESSION_SYNTAX_ERROR, i); + return false; + } + } + expression_error(error, EXPRESSION_OK, 0); + return true; +} + +/** @brief An operator and its byte offset in the expression. */ +struct expression_operator { + char symbol; + size_t position; +}; + +/** @brief Returns precedence; `p` and `n` denote unary plus and minus. */ +static inline int expression_precedence(char symbol) +{ + switch (symbol) { + case 'p': case 'n': return 3; + case '*': case '/': return 2; + case '+': case '-': return 1; + default: return 0; + } +} + +/** @brief Applies the top operator to the value stack. */ +static inline bool expression_apply(stack *values, stack *operators, + struct expression_error *error) +{ + struct expression_operator op = *stack_top_as(operators, struct expression_operator); + stack_pop(operators); + bool unary = op.symbol == 'p' || op.symbol == 'n'; + if (stack_size(values) < (unary ? 1u : 2u)) { + expression_error(error, EXPRESSION_SYNTAX_ERROR, op.position); + return false; + } + if (unary) { + if (op.symbol == 'n') *stack_top_as(values, double) *= -1; + return true; + } + double rhs = *stack_top_as(values, double); + stack_pop(values); + double *lhs = stack_top_as(values, double); + switch (op.symbol) { + case '+': *lhs += rhs; break; + case '-': *lhs -= rhs; break; + case '*': *lhs *= rhs; break; + case '/': + if (rhs == 0.0) { + expression_error(error, EXPRESSION_DIVISION_BY_ZERO, op.position); + return false; + } + *lhs /= rhs; + break; + } + return true; +} + +/** + * @brief Evaluates an expression using value and operator stacks. + * @param ctx The variable table used for name lookup. + * @param text The null-terminated expression. + * @param result Receives the value on success; unchanged on failure. + * @param error Receives the error code and byte offset, or may be null. + * @return `true` on success; otherwise `false`. + * @pre `ctx` is initialized; `text` and `result` are valid pointers. + */ +static inline bool expression_eval(const struct expression_context *ctx, + const char *text, + double *result, + struct expression_error *error) +{ + STACK(values, double); + STACK(operators, struct expression_operator); + bool expect_operand = true; + bool success = false; + size_t position = 0; + + while (text[position]) { + unsigned char c = (unsigned char)text[position]; + if (isspace(c)) { + ++position; + continue; + } + if (isdigit(c) || c == '.' || expression_name_start(c)) { + if (!expect_operand) goto syntax_error; + double value; + if (expression_name_start(c)) { + size_t start = position++; + while (expression_name_char((unsigned char)text[position])) ++position; + size_t length = position - start; + if (length >= EXPRESSION_NAME_MAX) { + position = start; + goto syntax_error; + } + const struct expression_variable *variable = NULL; + for (size_t i = 0; i < ctx->variables.size; ++i) { + const struct expression_variable *v = vec_at_const(&ctx->variables, i); + if (strlen(v->name) == length && + strncmp(v->name, text + start, length) == 0) { + variable = v; + break; + } + } + if (!variable || !variable->assigned) { + expression_error(error, variable ? EXPRESSION_UNSET_VARIABLE + : EXPRESSION_UNKNOWN_VARIABLE, start); + goto done; + } + value = variable->value; + } else { + char *end; + errno = 0; + value = strtod(text + position, &end); + if (end == text + position || errno == ERANGE) goto syntax_error; + position = (size_t)(end - text); + } + if (!stack_push(&values, &value)) goto syntax_error; + expect_operand = false; + continue; + } + struct expression_operator op = { .symbol = (char)c, .position = position }; + if (c == '(') { + if (!expect_operand) goto syntax_error; + } else if (c == ')') { + if (expect_operand) goto syntax_error; + while (!stack_empty(&operators) && + stack_top_as(&operators, struct expression_operator)->symbol != '(') { + if (!expression_apply(&values, &operators, error)) goto done; + } + if (stack_empty(&operators)) goto paren_error; + stack_pop(&operators); + ++position; + continue; + } else if (c == '+' || c == '-' || c == '*' || c == '/') { + if (expect_operand) { + if (c != '+' && c != '-') goto syntax_error; + op.symbol = c == '+' ? 'p' : 'n'; + } else { + while (!stack_empty(&operators) && + expression_precedence(stack_top_as(&operators, + struct expression_operator)->symbol) >= expression_precedence(op.symbol)) { + if (!expression_apply(&values, &operators, error)) goto done; + } + } + } else { + goto syntax_error; + } + if (!stack_push(&operators, &op)) goto syntax_error; + expect_operand = true; + ++position; + } + if (expect_operand) goto syntax_error; + while (!stack_empty(&operators)) { + struct expression_operator op = *stack_top_as(&operators, struct expression_operator); + if (op.symbol == '(') { + position = op.position; + goto paren_error; + } + if (!expression_apply(&values, &operators, error)) goto done; + } + if (stack_size(&values) != 1) goto syntax_error; + *result = *stack_top_as(&values, double); + expression_error(error, EXPRESSION_OK, 0); + success = true; + goto done; + +syntax_error: + expression_error(error, EXPRESSION_SYNTAX_ERROR, position); + goto done; +paren_error: + expression_error(error, EXPRESSION_PAREN_ERROR, position); +done: + stack_destroy(&values); + stack_destroy(&operators); + return success; +} + +#endif /* EXPRESSION_H */ diff --git a/lab04/list.h b/lab04/list.h new file mode 100644 index 0000000..7d4ca23 --- /dev/null +++ b/lab04/list.h @@ -0,0 +1,370 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +/** + * @file list.h + * @brief Intrusive circular doubly linked list primitives. + * + * A list node is embedded in the structure that owns it. The list head is + * represented by a sentinel `struct list_head` whose links point to itself + * when the list is empty. + */ +#ifndef LIST_H +#define LIST_H + +#include <stddef.h> +#include <stdbool.h> +#include <assert.h> + +#include "container_of.h" + +/** + * @brief A node in an intrusive circular doubly linked list. + */ +struct list_head { + struct list_head *next; + struct list_head *prev; +}; + +/** @brief Poison value written to a deleted node's `next` link. */ +#define LIST_POISON1 ((void *) 0x100) + +/** @brief Poison value written to a deleted node's `prev` link. */ +#define LIST_POISON2 ((void *) 0x122) + +/** + * @brief Circular doubly linked list implementation. + * + * Some internal functions are useful when manipulating whole lists because + * the neighboring nodes are already known. + */ + +/** @brief Initializes a list head initializer. */ +#define LIST_HEAD_INIT(name) { &(name), &(name) } + +/** + * @brief Declares and initializes an empty list head. + * @param name The list head variable name. + */ +#define LIST_HEAD(name) \ + struct list_head name = LIST_HEAD_INIT(name) + +/** + * @brief Initializes a list node or list head. + * + * The node is made self-linked. When used as a list head, this represents + * an empty list. + * + * @param list The node or list head to initialize. + * @post `list->next == list`. + * @post `list->prev == list`. + */ +static inline void INIT_LIST_HEAD(struct list_head *list) +{ + list->next = list; + list->prev = list; +} + +/** + * @internal + * @brief Links a node between two known adjacent nodes. + */ +static inline void __list_add(struct list_head *node, + struct list_head *prev, + struct list_head *next) +{ + next->prev = node; + node->next = next; + node->prev = prev; + prev->next = node; +} + +/** + * @brief Inserts a node immediately after a list node. + * + * This operation is suitable for stack-like insertion. + * + * @param node The node to insert. + * @param head The node after which `node` is inserted. + * @pre `node` is not currently linked into a list. + */ +static inline void list_add(struct list_head *node, + struct list_head *head) +{ + __list_add(node, head, head->next); +} + +/** + * @brief Inserts a node immediately before a list node. + * + * This operation is suitable for queue-like insertion when `head` is the + * list sentinel. + * + * @param node The node to insert. + * @param head The node before which `node` is inserted. + * @pre `node` is not currently linked into a list. + */ +static inline void list_add_tail(struct list_head *node, + struct list_head *head) +{ + __list_add(node, head->prev, head); +} + +/** + * @internal + * @brief Unlinks the range between two known adjacent nodes. + */ +static inline void __list_del(struct list_head *prev, + struct list_head *next) +{ + next->prev = prev; + prev->next = next; +} + +/** + * @internal + * @brief Unlinks a node using its stored neighboring links. + */ +static inline void __list_del_entry(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); +} + +/** + * @brief Removes a node from its list. + * + * After this operation, the node's links contain poison values and must not + * be used for list traversal. + * + * @param entry The node to remove. + * @pre `entry` belongs to a valid list. + */ +static inline void list_del(struct list_head *entry) +{ + __list_del_entry(entry); + entry->next = LIST_POISON1; + entry->prev = LIST_POISON2; +} + +/** + * @brief Replaces one list node with another. + * + * The replacement node takes the position of the old node. + * + * @param old The node to replace. + * @param new The replacement node. + * @pre `old` belongs to a valid list. + * @pre `new` is not currently linked into a list. + */ +static inline void list_replace(struct list_head *old, + struct list_head *new) +{ + new->next = old->next; + new->next->prev = new; + new->prev = old->prev; + new->prev->next = new; +} + +/** + * @brief Replaces one node and reinitializes the old node. + * + * @param old The node to replace. + * @param new The replacement node. + * @pre `old` belongs to a valid list. + * @pre `new` is not currently linked into a list. + * @post `old` is a self-linked standalone node. + */ +static inline void list_replace_init(struct list_head *old, + struct list_head *new) +{ + list_replace(old, new); + INIT_LIST_HEAD(old); +} + +/** + * @brief Removes a node from its list and inserts it after `head`. + * + * @param list The node to move. + * @param head The node that precedes the moved node. + * @pre `list` belongs to a valid list. + */ +static inline void list_move(struct list_head *list, struct list_head *head) +{ + __list_del_entry(list); + list_add(list, head); +} + +/** + * @brief Removes a node from its list and inserts it before `head`. + * + * @param list The node to move. + * @param head The node that follows the moved node. + * @pre `list` belongs to a valid list. + */ +static inline void list_move_tail(struct list_head *list, + struct list_head *head) +{ + __list_del_entry(list); + list_add_tail(list, head); +} + +/** + * @brief Tests whether a node is the first entry in a list. + * + * @param list The node to test. + * @param head The list head. + * @return Nonzero if `list` is the first entry; zero otherwise. + */ +static inline int list_is_first(const struct list_head *list, const struct list_head *head) +{ + return list->prev == head; +} + +/** + * @brief Tests whether a node is the last entry in a list. + * + * @param list The node to test. + * @param head The list head. + * @return Nonzero if `list` is the last entry; zero otherwise. + */ +static inline int list_is_last(const struct list_head *list, const struct list_head *head) +{ + return list->next == head; +} + +/** + * @brief Tests whether a node is the list head. + * + * @param list The node to test. + * @param head The list head. + * @return Nonzero if `list == head`; zero otherwise. + */ +static inline int list_is_head(const struct list_head *list, const struct list_head *head) +{ + return list == head; +} + +/** + * @brief Tests whether a list is empty. + * + * @param head The list head. + * @return Nonzero if the list contains no entries; zero otherwise. + */ +static inline int list_empty(const struct list_head *head) +{ + return head->next == head; +} + +/** + * @brief Returns the containing structure for a list node. + * + * @param ptr A pointer to the embedded `struct list_head`. + * @param type The containing structure type. + * @param member The embedded list member. + * @return A pointer to the containing structure. + */ +#define list_entry(ptr, type, member) \ + container_of(ptr, type, member) + +/** + * @brief Returns the first containing structure in a list. + * + * @param ptr The list head. + * @param type The containing structure type. + * @param member The embedded list member. + * @pre The list is not empty. + */ +#define list_first_entry(ptr, type, member) \ + list_entry((ptr)->next, type, member) + +/** + * @brief Returns the last containing structure in a list. + * + * @param ptr The list head. + * @param type The containing structure type. + * @param member The embedded list member. + * @pre The list is not empty. + */ +#define list_last_entry(ptr, type, member) \ + list_entry((ptr)->prev, type, member) + +/** + * @brief Returns the containing structure following the current node. + * + * @param pos The typed cursor. + * @param member The embedded list member. + * @return The next containing structure. + */ +#define list_next_entry(pos, member) \ + list_entry((pos)->member.next, typeof(*(pos)), member) + +/** + * @brief Returns the containing structure preceding the current node. + * + * @param pos The typed cursor. + * @param member The embedded list member. + * @return The previous containing structure. + */ +#define list_prev_entry(pos, member) \ + list_entry((pos)->member.prev, typeof(*(pos)), member) + +/** + * @brief Tests whether a typed cursor refers to the list head. + * + * @param pos The typed cursor. + * @param head The list head. + * @param member The embedded list member. + * @return Nonzero if `pos` refers to `head`; zero otherwise. + */ +#define list_entry_is_head(pos, head, member) \ + (&pos->member == (head)) + +/** + * @brief Iterates over containing structures in forward order. + * + * Example: + * @code + * struct item *pos; + * list_for_each_entry(pos, &head, link) { + * use_item(pos); + * } + * @endcode + * + * @param pos The typed loop cursor. + * @param head The list head. + * @param member The embedded list member. + */ +#define list_for_each_entry(pos, head, member) \ + for (pos = list_first_entry(head, typeof(*pos), member); \ + !list_entry_is_head(pos, head, member); \ + pos = list_next_entry(pos, member)) + +/** + * @brief Iterates over containing structures in reverse order. + * + * @param pos The typed loop cursor. + * @param head The list head. + * @param member The embedded list member. + */ +#define list_for_each_entry_reverse(pos, head, member) \ + for (pos = list_last_entry(head, typeof(*pos), member); \ + !list_entry_is_head(pos, head, member); \ + pos = list_prev_entry(pos, member)) + +/** + * @brief Iterates over containing structures while allowing removal. + * + * The additional cursor stores the next entry before the loop body runs, so + * the current entry may be removed safely from the list. + * + * @param pos The typed loop cursor. + * @param n The temporary typed cursor. + * @param head The list head. + * @param member The embedded list member. + */ +#define list_for_each_entry_safe(pos, n, head, member) \ + for (pos = list_first_entry(head, typeof(*pos), member), \ + n = list_next_entry(pos, member); \ + !list_entry_is_head(pos, head, member); \ + pos = n, n = list_next_entry(n, member)) + +#endif /* LIST_H */ diff --git a/lab04/main.c b/lab04/main.c new file mode 100644 index 0000000..3b51f82 --- /dev/null +++ b/lab04/main.c @@ -0,0 +1,9 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +#include "ui.h" + +int main(void) +{ + return ui_run(); +} diff --git a/lab04/polynomial.h b/lab04/polynomial.h new file mode 100644 index 0000000..a270211 --- /dev/null +++ b/lab04/polynomial.h @@ -0,0 +1,876 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +#ifndef POLYNOMIAL_H +#define POLYNOMIAL_H + +#include <stddef.h> +#include <stdbool.h> +#include <limits.h> +#include <math.h> +#include <stdlib.h> + +#include "vec.h" +#include "list.h" + +/* + * Polynomial term: + * + * coef * x^exp + * + * exp >= 0 + */ +struct poly_term { + double coef; + unsigned int exp; +}; + +/* + * ============================================================ + * Sequential representation + * ============================================================ + * + * Terms are stored in descending order of exponent: + * + * 5x^4 + 3x^2 - 7 + * + * [ {5,4}, {3,2}, {-7,0} ] + * + * Invariants: + * + * terms.elem_size == sizeof(struct poly_term) + * terms are ordered by exp descending + * duplicate exponents do not exist + * zero-coefficient terms do not exist + */ + +struct poly_vec { + struct vec terms; +}; + +/* + * ============================================================ + * Linked representation + * ============================================================ + */ + +struct poly_node { + struct poly_term term; + struct list_head link; +}; + +struct poly_list { + struct list_head head; + size_t size; +}; + +/* + * ============================================================ + * Initialization / destruction + * ============================================================ + */ + +static inline void poly_vec_init(struct poly_vec *poly) +{ + vec_init(&poly->terms, struct poly_term); +} + +static inline void poly_vec_clear(struct poly_vec *poly) +{ + vec_clear(&poly->terms); +} + +static inline void poly_vec_destroy(struct poly_vec *poly) +{ + vec_destroy(&poly->terms); +} + +static inline void poly_list_init(struct poly_list *poly) +{ + INIT_LIST_HEAD(&poly->head); + poly->size = 0; +} + +static inline void poly_list_clear(struct poly_list *poly) +{ + struct list_head *pos = poly->head.next; + + while (pos != &poly->head) { + struct list_head *next = pos->next; + struct poly_node *node = list_entry(pos, struct poly_node, link); + list_del(pos); + free(node); + pos = next; + } + + INIT_LIST_HEAD(&poly->head); + poly->size = 0; +} + +static inline void poly_list_destroy(struct poly_list *poly) +{ + poly_list_clear(poly); +} + +static inline void __poly_vec_replace(struct poly_vec *dst, + struct poly_vec *src) +{ + struct vec old = dst->terms; + dst->terms = src->terms; + src->terms = old; + vec_destroy(&src->terms); +} + +static inline void __poly_list_replace(struct poly_list *dst, + struct poly_list *src) +{ + poly_list_clear(dst); + if (src->size == 0) { + return; + } + + dst->head.next = src->head.next; + dst->head.prev = src->head.prev; + dst->head.next->prev = &dst->head; + dst->head.prev->next = &dst->head; + dst->size = src->size; + + INIT_LIST_HEAD(&src->head); + src->size = 0; +} + +/* + * ============================================================ + * Basic properties + * ============================================================ + */ + +static inline bool poly_vec_empty(const struct poly_vec *poly) +{ + return vec_empty(&poly->terms); +} + +static inline size_t poly_vec_size(const struct poly_vec *poly) +{ + return vec_size(&poly->terms); +} + + +static inline bool poly_list_empty(const struct poly_list *poly) +{ + return list_empty(&poly->head); +} + +static inline size_t poly_list_size(const struct poly_list *poly) +{ + return poly->size; +} + +/* + * ============================================================ + * Term access + * ============================================================ + * + * Sequential representation supports indexed access. + */ + +static inline struct poly_term * +poly_vec_at(struct poly_vec *poly, size_t index) +{ + return vec_at(&poly->terms, index); +} + +static inline const struct poly_term * +poly_vec_at_const(const struct poly_vec *poly, size_t index) +{ + return vec_at_const(&poly->terms, index); +} + + +/* + * ============================================================ + * Term modification + * ============================================================ + * + * poly_*_set_term(): + * + * Sets the coefficient for x^exp. + * + * Existing exponent: + * replace coefficient + * + * Missing exponent: + * insert at the proper position + * + * coef == 0: + * remove that exponent + * + * + * poly_*_add_term(): + * + * Adds coef*x^exp to the polynomial. + * + * Existing exponent: + * old_coef += coef + * + * Result coefficient == 0: + * remove that term + * + * These two operations preserve all polynomial invariants. + */ + +static inline size_t __poly_vec_find(const struct poly_vec *poly, + unsigned int exp, + bool *found) +{ + size_t i; + + for (i = 0; i < vec_size(&poly->terms); ++i) { + const struct poly_term *term = vec_at_const(&poly->terms, i); + if (term->exp == exp) { + *found = true; + return i; + } + if (term->exp < exp) { + break; + } + } + + *found = false; + return i; +} + +static inline bool poly_vec_remove_term(struct poly_vec *poly, + unsigned int exp); + +static inline bool poly_vec_set_term(struct poly_vec *poly, + double coef, + unsigned int exp) +{ + if (coef == 0.0) { + poly_vec_remove_term(poly, exp); + return true; + } + + bool found; + size_t index = __poly_vec_find(poly, exp, &found); + if (found) { + poly_vec_at(poly, index)->coef = coef; + return true; + } + + struct poly_term term = { .coef = coef, .exp = exp }; + return vec_insert(&poly->terms, index, &term); +} + +static inline bool poly_vec_add_term(struct poly_vec *poly, + double coef, + unsigned int exp) +{ + if (coef == 0.0) { + return true; + } + + bool found; + size_t index = __poly_vec_find(poly, exp, &found); + if (found) { + struct poly_term *term = poly_vec_at(poly, index); + double result = term->coef + coef; + if (result == 0.0) { + vec_erase(&poly->terms, index); + } else { + term->coef = result; + } + return true; + } + + struct poly_term term = { .coef = coef, .exp = exp }; + return vec_insert(&poly->terms, index, &term); +} + +static inline bool poly_vec_remove_term(struct poly_vec *poly, + unsigned int exp) +{ + bool found; + size_t index = __poly_vec_find(poly, exp, &found); + if (!found) { + return false; + } + + vec_erase(&poly->terms, index); + return true; +} + +static inline bool poly_vec_get_term(const struct poly_vec *poly, + unsigned int exp, + double *coef) +{ + bool found; + size_t index = __poly_vec_find(poly, exp, &found); + if (!found) { + return false; + } + + *coef = poly_vec_at_const(poly, index)->coef; + return true; +} + +static inline bool poly_list_remove_term(struct poly_list *poly, + unsigned int exp); + +static inline bool poly_list_set_term(struct poly_list *poly, + double coef, + unsigned int exp) +{ + if (coef == 0.0) { + poly_list_remove_term(poly, exp); + return true; + } + + struct list_head *pos = poly->head.next; + while (pos != &poly->head) { + struct poly_node *node = list_entry(pos, struct poly_node, link); + if (node->term.exp == exp) { + node->term.coef = coef; + return true; + } + if (node->term.exp < exp) { + break; + } + pos = pos->next; + } + + struct poly_node *node = malloc(sizeof(*node)); + if (!node) { + return false; + } + node->term.coef = coef; + node->term.exp = exp; + __list_add(&node->link, pos->prev, pos); + ++poly->size; + return true; +} + +static inline bool poly_list_add_term(struct poly_list *poly, + double coef, + unsigned int exp) +{ + if (coef == 0.0) { + return true; + } + + struct list_head *pos = poly->head.next; + while (pos != &poly->head) { + struct poly_node *node = list_entry(pos, struct poly_node, link); + if (node->term.exp == exp) { + double result = node->term.coef + coef; + if (result == 0.0) { + list_del(pos); + free(node); + --poly->size; + } else { + node->term.coef = result; + } + return true; + } + if (node->term.exp < exp) { + break; + } + pos = pos->next; + } + + struct poly_node *node = malloc(sizeof(*node)); + if (!node) { + return false; + } + node->term.coef = coef; + node->term.exp = exp; + __list_add(&node->link, pos->prev, pos); + ++poly->size; + return true; +} + +static inline bool poly_list_remove_term(struct poly_list *poly, + unsigned int exp) +{ + struct list_head *pos = poly->head.next; + while (pos != &poly->head) { + struct poly_node *node = list_entry(pos, struct poly_node, link); + if (node->term.exp == exp) { + list_del(pos); + free(node); + --poly->size; + return true; + } + if (node->term.exp < exp) { + return false; + } + pos = pos->next; + } + return false; +} + +static inline bool poly_list_get_term(const struct poly_list *poly, + unsigned int exp, + double *coef) +{ + const struct list_head *pos = poly->head.next; + while (pos != &poly->head) { + const struct poly_node *node = + list_entry(pos, const struct poly_node, link); + if (node->term.exp == exp) { + *coef = node->term.coef; + return true; + } + if (node->term.exp < exp) { + return false; + } + pos = pos->next; + } + return false; +} + + +/* + * ============================================================ + * Copy / conversion + * ============================================================ + */ + +static inline bool poly_vec_copy(struct poly_vec *dst, + const struct poly_vec *src) +{ + struct poly_vec tmp; + poly_vec_init(&tmp); + + if (!vec_append(&tmp.terms, src->terms.data, src->terms.size)) { + poly_vec_destroy(&tmp); + return false; + } + + __poly_vec_replace(dst, &tmp); + return true; +} + +static inline bool poly_list_copy(struct poly_list *dst, + const struct poly_list *src) +{ + struct poly_list tmp; + poly_list_init(&tmp); + + const struct list_head *pos = src->head.next; + while (pos != &src->head) { + const struct poly_node *node = + list_entry(pos, const struct poly_node, link); + if (!poly_list_set_term(&tmp, node->term.coef, node->term.exp)) { + poly_list_destroy(&tmp); + return false; + } + pos = pos->next; + } + + __poly_list_replace(dst, &tmp); + return true; +} + + +/* + * Conversion between the two representations. + */ +static inline bool poly_vec_from_list(struct poly_vec *dst, + const struct poly_list *src) +{ + struct poly_vec tmp; + poly_vec_init(&tmp); + + const struct list_head *pos = src->head.next; + while (pos != &src->head) { + const struct poly_node *node = + list_entry(pos, const struct poly_node, link); + if (!poly_vec_add_term(&tmp, node->term.coef, node->term.exp)) { + poly_vec_destroy(&tmp); + return false; + } + pos = pos->next; + } + + __poly_vec_replace(dst, &tmp); + return true; +} + +static inline bool poly_list_from_vec(struct poly_list *dst, + const struct poly_vec *src) +{ + struct poly_list tmp; + poly_list_init(&tmp); + + for (size_t i = 0; i < src->terms.size; ++i) { + const struct poly_term *term = + vec_at_const(&src->terms, i); + if (!poly_list_add_term(&tmp, term->coef, term->exp)) { + poly_list_destroy(&tmp); + return false; + } + } + + __poly_list_replace(dst, &tmp); + return true; +} + + +/* + * ============================================================ + * Arithmetic + * ============================================================ + * + * dst may alias lhs or rhs unless otherwise documented. + */ + +static inline bool __poly_vec_add_scaled(struct poly_vec *dst, + const struct poly_vec *src, + double scale) +{ + for (size_t i = 0; i < src->terms.size; ++i) { + const struct poly_term *term = + vec_at_const(&src->terms, i); + if (!poly_vec_add_term(dst, term->coef * scale, term->exp)) { + return false; + } + } + return true; +} + +static inline bool __poly_list_add_scaled(struct poly_list *dst, + const struct poly_list *src, + double scale) +{ + const struct list_head *pos = src->head.next; + while (pos != &src->head) { + const struct poly_node *node = + list_entry(pos, const struct poly_node, link); + if (!poly_list_add_term(dst, node->term.coef * scale, + node->term.exp)) { + return false; + } + pos = pos->next; + } + return true; +} + +static inline bool poly_vec_add(struct poly_vec *dst, + const struct poly_vec *lhs, + const struct poly_vec *rhs) +{ + struct poly_vec tmp; + poly_vec_init(&tmp); + if (!__poly_vec_add_scaled(&tmp, lhs, 1.0) || + !__poly_vec_add_scaled(&tmp, rhs, 1.0)) { + poly_vec_destroy(&tmp); + return false; + } + __poly_vec_replace(dst, &tmp); + return true; +} + +static inline bool poly_vec_sub(struct poly_vec *dst, + const struct poly_vec *lhs, + const struct poly_vec *rhs) +{ + struct poly_vec tmp; + poly_vec_init(&tmp); + if (!__poly_vec_add_scaled(&tmp, lhs, 1.0) || + !__poly_vec_add_scaled(&tmp, rhs, -1.0)) { + poly_vec_destroy(&tmp); + return false; + } + __poly_vec_replace(dst, &tmp); + return true; +} + +static inline bool poly_list_add(struct poly_list *dst, + const struct poly_list *lhs, + const struct poly_list *rhs) +{ + struct poly_list tmp; + poly_list_init(&tmp); + if (!__poly_list_add_scaled(&tmp, lhs, 1.0) || + !__poly_list_add_scaled(&tmp, rhs, 1.0)) { + poly_list_destroy(&tmp); + return false; + } + __poly_list_replace(dst, &tmp); + return true; +} + +static inline bool poly_list_sub(struct poly_list *dst, + const struct poly_list *lhs, + const struct poly_list *rhs) +{ + struct poly_list tmp; + poly_list_init(&tmp); + if (!__poly_list_add_scaled(&tmp, lhs, 1.0) || + !__poly_list_add_scaled(&tmp, rhs, -1.0)) { + poly_list_destroy(&tmp); + return false; + } + __poly_list_replace(dst, &tmp); + return true; +} + + +/* + * ============================================================ + * Extended operations + * ============================================================ + */ + +static inline bool poly_vec_mul(struct poly_vec *dst, + const struct poly_vec *lhs, + const struct poly_vec *rhs) +{ + struct poly_vec tmp; + poly_vec_init(&tmp); + + for (size_t i = 0; i < lhs->terms.size; ++i) { + const struct poly_term *left = + vec_at_const(&lhs->terms, i); + for (size_t j = 0; j < rhs->terms.size; ++j) { + const struct poly_term *right = + vec_at_const(&rhs->terms, j); + if (left->exp > UINT_MAX - right->exp || + !poly_vec_add_term(&tmp, + left->coef * right->coef, + left->exp + right->exp)) { + poly_vec_destroy(&tmp); + return false; + } + } + } + + __poly_vec_replace(dst, &tmp); + return true; +} + +static inline bool poly_list_mul(struct poly_list *dst, + const struct poly_list *lhs, + const struct poly_list *rhs) +{ + struct poly_list tmp; + poly_list_init(&tmp); + + const struct list_head *left_pos = lhs->head.next; + while (left_pos != &lhs->head) { + const struct poly_node *left = + list_entry(left_pos, const struct poly_node, link); + const struct list_head *right_pos = rhs->head.next; + while (right_pos != &rhs->head) { + const struct poly_node *right = + list_entry(right_pos, const struct poly_node, link); + if (left->term.exp > UINT_MAX - right->term.exp || + !poly_list_add_term(&tmp, + left->term.coef * right->term.coef, + left->term.exp + right->term.exp)) { + poly_list_destroy(&tmp); + return false; + } + right_pos = right_pos->next; + } + left_pos = left_pos->next; + } + + __poly_list_replace(dst, &tmp); + return true; +} + + +/* + * Differentiate polynomial 'order' times. + * + * order == 0: + * dst = src + */ +static inline bool poly_vec_derivative(struct poly_vec *dst, + const struct poly_vec *src, + unsigned int order) +{ + struct poly_vec tmp; + poly_vec_init(&tmp); + + for (size_t i = 0; i < src->terms.size; ++i) { + const struct poly_term *term = + vec_at_const(&src->terms, i); + if (term->exp < order) { + continue; + } + + double coef = term->coef; + unsigned int exp = term->exp; + for (unsigned int j = 0; j < order; ++j) { + coef *= exp; + --exp; + } + if (!poly_vec_add_term(&tmp, coef, exp)) { + poly_vec_destroy(&tmp); + return false; + } + } + + __poly_vec_replace(dst, &tmp); + return true; +} + +static inline bool poly_list_derivative(struct poly_list *dst, + const struct poly_list *src, + unsigned int order) +{ + struct poly_list tmp; + poly_list_init(&tmp); + + const struct list_head *pos = src->head.next; + while (pos != &src->head) { + const struct poly_node *node = + list_entry(pos, const struct poly_node, link); + if (node->term.exp >= order) { + double coef = node->term.coef; + unsigned int exp = node->term.exp; + for (unsigned int i = 0; i < order; ++i) { + coef *= exp; + --exp; + } + if (!poly_list_add_term(&tmp, coef, exp)) { + poly_list_destroy(&tmp); + return false; + } + } + pos = pos->next; + } + + __poly_list_replace(dst, &tmp); + return true; +} + + +/* + * ============================================================ + * Evaluation + * ============================================================ + */ + +static inline double poly_vec_eval(const struct poly_vec *poly, double x) +{ + double result = 0.0; + + for (size_t i = 0; i < poly->terms.size; ++i) { + const struct poly_term *term = + vec_at_const(&poly->terms, i); + result += term->coef * pow(x, term->exp); + } + return result; +} + +static inline double poly_list_eval(const struct poly_list *poly, double x) +{ + double result = 0.0; + const struct list_head *pos = poly->head.next; + + while (pos != &poly->head) { + const struct poly_node *node = + list_entry(pos, const struct poly_node, link); + result += node->term.coef * pow(x, node->term.exp); + pos = pos->next; + } + return result; +} + + +/* + * ============================================================ + * Comparison + * ============================================================ + * + * eps controls floating-point coefficient comparison. + */ + +static inline bool poly_vec_equal(const struct poly_vec *lhs, + const struct poly_vec *rhs, + double eps) +{ + if (lhs->terms.size != rhs->terms.size) { + return false; + } + + for (size_t i = 0; i < lhs->terms.size; ++i) { + const struct poly_term *left = + vec_at_const(&lhs->terms, i); + const struct poly_term *right = + vec_at_const(&rhs->terms, i); + if (left->exp != right->exp || + !(fabs(left->coef - right->coef) <= eps)) { + return false; + } + } + return true; +} + +static inline bool poly_list_equal(const struct poly_list *lhs, + const struct poly_list *rhs, + double eps) +{ + if (lhs->size != rhs->size) { + return false; + } + + const struct list_head *left_pos = lhs->head.next; + const struct list_head *right_pos = rhs->head.next; + while (left_pos != &lhs->head) { + const struct poly_node *left = + list_entry(left_pos, const struct poly_node, link); + const struct poly_node *right = + list_entry(right_pos, const struct poly_node, link); + if (left->term.exp != right->term.exp || + !(fabs(left->term.coef - right->term.coef) <= eps)) { + return false; + } + left_pos = left_pos->next; + right_pos = right_pos->next; + } + return true; +} + + +/* + * ============================================================ + * Iteration: sequential representation + * ============================================================ + */ + +#define poly_vec_for_each(term, poly) \ + for (size_t __poly_i = 0; \ + __poly_i < poly_vec_size(poly) && \ + (((term) = poly_vec_at((poly), __poly_i)), true); \ + ++__poly_i) + +#define poly_vec_for_each_const(term, poly) \ + for (size_t __poly_i = 0; \ + __poly_i < poly_vec_size(poly) && \ + (((term) = poly_vec_at_const((poly), __poly_i)), true); \ + ++__poly_i) + + +/* + * ============================================================ + * Iteration: linked representation + * ============================================================ + */ + +#define poly_list_for_each(node, poly) \ + list_for_each_entry((node), &(poly)->head, link) + +#define poly_list_for_each_reverse(node, poly) \ + list_for_each_entry_reverse((node), &(poly)->head, link) + +#define poly_list_for_each_safe(node, next, poly) \ + list_for_each_entry_safe((node), (next), &(poly)->head, link) + + +#endif /* POLYNOMIAL_H */ diff --git a/lab04/stack.h b/lab04/stack.h new file mode 100644 index 0000000..06e4d67 --- /dev/null +++ b/lab04/stack.h @@ -0,0 +1,219 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +#ifndef STACK_H +#define STACK_H + +/** + * @file stack.h + * @brief LIFO stack primitives backed by a dynamically sized vector. + * + * A stack stores elements by value and uses the last vector element as its + * top. The element size is fixed when the stack is initialized. + */ + +#include "vec.h" + +/** + * @brief A generic last-in, first-out stack. + */ +typedef struct stack { + /** @brief Contiguous storage for the stack elements. */ + vec container; +} stack; + +/** @name Initialization */ +/** @{ */ + +/** + * @brief Produces an initializer for an empty stack of the given type. + * @param type The element type. + * @return An initializer for a `stack` object. + */ +#define STACK_INIT(type) { \ + .container = VEC_INIT(type), \ +} + +/** + * @brief Declares and initializes an empty stack. + * @param name The stack variable name. + * @param type The element type. + */ +#define STACK(name, type) \ + stack name = STACK_INIT(type) + +/** + * @brief Initializes an existing stack for elements of `type`. + * @param s A pointer to the stack. + * @param type The element type. + * @post `s` is empty and its element size is `sizeof(type)`. + */ +#define stack_init(s, type) \ + vec_init(&(s)->container, type) + +/** + * @brief Destroys a stack and releases its allocated storage. + * @param s A pointer to the stack. + * @pre `s` points to a stack initialized by `STACK` or `stack_init`. + */ +static inline void stack_destroy(stack *s) +{ + vec_destroy(&s->container); +} + +/** @} */ + +/** @name Basic properties */ +/** @{ */ + +/** + * @brief Returns the number of elements in the stack. + * @param s A pointer to the stack. + * @return The number of elements in the stack. + * @pre `s` points to an initialized stack. + */ +static inline size_t stack_size(const stack *s) +{ + return vec_size(&s->container); +} + +/** + * @brief Tests whether the stack is empty. + * @param s A pointer to the stack. + * @return `true` when the stack contains no elements; otherwise `false`. + * @pre `s` points to an initialized stack. + */ +static inline bool stack_empty(const stack *s) +{ + return vec_empty(&s->container); +} + +/** + * @brief Removes all elements without releasing the allocated capacity. + * @param s A pointer to the stack. + * @post The stack is empty and its allocated capacity is unchanged. + * @pre `s` points to an initialized stack. + */ +static inline void stack_clear(stack *s) +{ + vec_clear(&s->container); +} + +/** + * @brief Exchanges the contents of two stacks. + * @param a A pointer to the first stack. + * @param b A pointer to the second stack. + * @pre Both stacks are initialized with the same element size. + */ +static inline void stack_swap(stack *a, stack *b) +{ + vec_swap(&a->container, &b->container); +} + +/** @} */ + +/** @name Top element */ +/** @{ */ + +/** + * @brief Returns a writable pointer to the top element. + * @param s A pointer to the stack. + * @return A pointer to the top element. + * @pre `s` points to an initialized stack containing at least one element. + */ +static inline void *stack_top(stack *s) +{ + return vec_back(&s->container); +} + +/** + * @brief Returns a read-only pointer to the top element. + * @param s A pointer to the stack. + * @return A pointer to the top element. + * @pre `s` points to an initialized stack containing at least one element. + */ +static inline const void *stack_top_const(const stack *s) +{ + return vec_back_const(&s->container); +} + +/** @} */ + +/** @name Insertion and erasure */ +/** @{ */ + +/** + * @brief Pushes one raw element onto the stack. + * @param s A pointer to the stack. + * @param value A pointer to the element to copy. + * @return `true` on success; `false` for invalid input or allocation failure. + * @pre `s` points to an initialized stack. + */ +static inline bool stack_push(stack *s, const void *value) +{ + return vec_push_back(&s->container, value); +} + +/** + * @brief Pushes a typed value after checking its size. + * @param s A pointer to the stack. + * @param value The value to copy onto the stack. + * @pre `s` points to an initialized stack whose element type is `typeof(value)`. + */ +#define stack_push_value(s, value) ({ \ + typeof(value) __stack_tmp = (value); \ + assert(sizeof(__stack_tmp) == \ + (s)->container.elem_size); \ + stack_push((s), &__stack_tmp); \ +}) + +/** + * @brief Removes the top element, if one exists. + * @param s A pointer to the stack. + * + * Like `std::stack::pop`, this function does not return the removed value. + * @pre `s` points to an initialized stack. + */ +static inline void stack_pop(stack *s) +{ + vec_pop_back(&s->container); +} + +/** + * @brief Removes the top element and copies it to `out`. + * @param s A pointer to the stack. + * @param out A pointer receiving the removed element. + * @return `true` on success; `false` when the stack is empty or invalid. + * @pre `s` points to an initialized stack. + */ +static inline bool stack_pop_copy(stack *s, void *out) +{ + return vec_pop_back_copy(&s->container, out); +} + +/** @} */ + +/** @name Typed access helpers */ +/** @{ */ + +/** + * @brief Returns the top element converted to a writable typed pointer. + * @param s A pointer to the stack. + * @param type The element type. + * @pre `s` points to an initialized, non-empty stack. + */ +#define stack_top_as(s, type) \ + ((type *)stack_top((s))) + +/** + * @brief Returns the top element converted to a read-only typed pointer. + * @param s A pointer to the stack. + * @param type The element type. + * @pre `s` points to an initialized, non-empty stack. + */ +#define stack_top_as_const(s, type) \ + ((const type *)stack_top_const((s))) + +/** @} */ + +#endif /* STACK_H */ diff --git a/lab04/tests/Makefile b/lab04/tests/Makefile new file mode 100644 index 0000000..5724f6f --- /dev/null +++ b/lab04/tests/Makefile @@ -0,0 +1,18 @@ +CC ?= gcc +CFLAGS ?= -std=gnu11 -Wall -Wextra -Werror -O2 +LDLIBS ?= -lm + +TARGET := test_runner + +.PHONY: all run clean + +all: $(TARGET) + +$(TARGET): test.c ../container_of.h ../list.h ../vec.h ../polynomial.h ../expression.h ../stack.h + $(CC) $(CFLAGS) -I.. test.c $(LDLIBS) -o $@ + +run: $(TARGET) + ./$(TARGET) + +clean: + rm -f $(TARGET) diff --git a/lab04/tests/test.c b/lab04/tests/test.c new file mode 100644 index 0000000..c10b130 --- /dev/null +++ b/lab04/tests/test.c @@ -0,0 +1,497 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +#include "container_of.h" +#include "expression.h" +#include "list.h" +#include "polynomial.h" +#include "vec.h" + +#include <math.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> + +#define CHECK(condition) \ + do { \ + if (!(condition)) { \ + fprintf(stderr, " failed: %s:%d: %s\n", \ + __FILE__, __LINE__, #condition); \ + return false; \ + } \ + } while (0) + +static int compare_int(const void *lhs, const void *rhs) +{ + int left = *(const int *)lhs; + int right = *(const int *)rhs; + return (left > right) - (left < right); +} + +static bool test_vec_lifecycle_and_access(void) +{ + struct vec vector; + vec_init(&vector, int); + CHECK(vec_empty(&vector)); + CHECK(vec_elem_size(&vector) == sizeof(int)); + + int values[] = { 10, 20, 30 }; + for (size_t i = 0; i < sizeof(values) / sizeof(values[0]); ++i) { + CHECK(vec_push_back(&vector, &values[i])); + } + CHECK(vec_size(&vector) == 3); + CHECK(vec_capacity(&vector) >= 3); + CHECK(*(int *)vec_front(&vector) == 10); + CHECK(*(int *)vec_back(&vector) == 30); + CHECK(*(int *)vec_at_checked(&vector, 1) == 20); + CHECK(vec_at_checked(&vector, 3) == NULL); + + vec_destroy(&vector); + CHECK(vector.data == NULL); + CHECK(vector.size == 0); + CHECK(vector.capacity == 0); + CHECK(vector.elem_size == 0); + return true; +} + +static bool test_vec_insert_erase_and_assign(void) +{ + struct vec vector; + vec_init(&vector, int); + int initial[] = { 1, 3 }; + CHECK(vec_append(&vector, initial, 2)); + + int two = 2; + CHECK(vec_insert(&vector, 1, &two)); + int tail[] = { 4, 5 }; + CHECK(vec_insert_range(&vector, vector.size, tail, 2)); + CHECK(vector.size == 5); + CHECK(*(int *)vec_at(&vector, 0) == 1); + CHECK(*(int *)vec_at(&vector, 4) == 5); + + vec_erase(&vector, 1); + CHECK(*(int *)vec_at(&vector, 1) == 3); + vec_erase_n(&vector, 1, 2); + CHECK(vector.size == 2); + CHECK(*(int *)vec_at(&vector, 0) == 1); + CHECK(*(int *)vec_at(&vector, 1) == 5); + + int replacement[] = { 7, 8, 9 }; + CHECK(vec_assign_range(&vector, replacement, 3)); + CHECK(vector.size == 3); + int repeated = 4; + CHECK(vec_assign_n(&vector, 2, &repeated)); + CHECK(vector.size == 2); + CHECK(*(int *)vec_at(&vector, 0) == 4); + CHECK(*(int *)vec_at(&vector, 1) == 4); + + vec_destroy(&vector); + return true; +} + +static bool test_vec_resize_capacity_and_swap(void) +{ + struct vec vector; + vec_init(&vector, int); + CHECK(vec_reserve(&vector, 16)); + CHECK(vector.capacity >= 16); + CHECK(vec_resize_zero(&vector, 4)); + for (size_t i = 0; i < vector.size; ++i) { + CHECK(*(int *)vec_at(&vector, i) == 0); + } + + int value = 11; + CHECK(vec_assign_n(&vector, 1, &value)); + CHECK(vec_resize(&vector, 4)); + CHECK(*(int *)vec_at(&vector, 0) == 11); + CHECK(vec_resize(&vector, 1)); + CHECK(vec_shrink_to_fit(&vector)); + CHECK(vector.capacity == vector.size); + + struct vec other; + vec_init(&other, int); + int other_value = 22; + CHECK(vec_push_back(&other, &other_value)); + vec_swap(&vector, &other); + CHECK(*(int *)vec_front(&vector) == 22); + CHECK(*(int *)vec_front(&other) == 11); + CHECK(!vec_reserve(&vector, SIZE_MAX)); + + vec_destroy(&vector); + vec_destroy(&other); + return true; +} + +static bool test_vec_iterators_and_comparison(void) +{ + struct vec vector; + vec_init(&vector, int); + int values[] = { 1, 2, 3 }; + CHECK(vec_append(&vector, values, 3)); + + int *begin = vec_begin_as(&vector, int); + int *end = vec_end_as(&vector, int); + CHECK(vec_iter_distance(begin, end) == 3); + CHECK(vec_iter_distance((int *)NULL, (int *)NULL) == 0); + CHECK(*begin == 1); + CHECK(*(end - 1) == 3); + + struct vec_reverse_iterator reverse = vec_rbegin(&vector); + struct vec_reverse_iterator reverse_end = vec_rend(&vector); + CHECK(vec_reverse_distance(reverse, reverse_end) == 3); + CHECK(*(int *)vec_reverse_deref(reverse) == 3); + vec_reverse_next(&reverse); + CHECK(*(int *)vec_reverse_deref(reverse) == 2); + vec_reverse_next(&reverse); + CHECK(*(int *)vec_reverse_deref(reverse) == 1); + + struct vec same; + vec_init(&same, int); + CHECK(vec_append(&same, values, 3)); + CHECK(vec_equal(&vector, &same, compare_int)); + CHECK(vec_compare(&vector, &same, compare_int) == 0); + vec_pop_back(&same); + CHECK(vec_compare(&same, &vector, compare_int) < 0); + + vec_destroy(&vector); + vec_destroy(&same); + return true; +} + +struct list_test_item { + int value; + struct list_head link; +}; + +static bool test_list_and_container_of(void) +{ + LIST_HEAD(head); + struct list_test_item first = { .value = 1 }; + struct list_test_item second = { .value = 2 }; + struct list_test_item third = { .value = 3 }; + INIT_LIST_HEAD(&first.link); + INIT_LIST_HEAD(&second.link); + INIT_LIST_HEAD(&third.link); + + list_add(&first.link, &head); + list_add_tail(&second.link, &head); + list_add_tail(&third.link, &head); + CHECK(!list_empty(&head)); + CHECK(list_is_first(&first.link, &head)); + CHECK(list_is_last(&third.link, &head)); + CHECK(list_entry(head.next, struct list_test_item, link)->value == 1); + CHECK(list_entry(head.prev, struct list_test_item, link)->value == 3); + + struct list_test_item *cursor; + int expected = 1; + list_for_each_entry(cursor, &head, link) { + CHECK(cursor->value == expected); + ++expected; + } + list_move_tail(&first.link, &head); + CHECK(list_entry(head.prev, struct list_test_item, link)->value == 1); + list_del(&second.link); + CHECK(list_entry(head.next, struct list_test_item, link)->value == 3); + CHECK(list_entry_is_head(list_entry(head.next, struct list_test_item, link), + &head, link) == false); + return true; +} + +static bool test_poly_vec_normalization(void) +{ + struct poly_vec poly; + poly_vec_init(&poly); + CHECK(poly_vec_add_term(&poly, 3.0, 2)); + CHECK(poly_vec_add_term(&poly, 1.0, 5)); + CHECK(poly_vec_add_term(&poly, 2.0, 2)); + CHECK(poly_vec_size(&poly) == 2); + CHECK(poly_vec_at_const(&poly, 0)->exp == 5); + CHECK(poly_vec_at_const(&poly, 0)->coef == 1.0); + CHECK(poly_vec_at_const(&poly, 1)->exp == 2); + CHECK(poly_vec_at_const(&poly, 1)->coef == 5.0); + CHECK(poly_vec_set_term(&poly, 0.0, 5)); + CHECK(!poly_vec_get_term(&poly, 5, &(double){ 0.0 })); + CHECK(poly_vec_remove_term(&poly, 2)); + CHECK(poly_vec_empty(&poly)); + poly_vec_destroy(&poly); + return true; +} + +static bool test_poly_vec_add_sub_and_alias(void) +{ + struct poly_vec a; + struct poly_vec b; + struct poly_vec result; + poly_vec_init(&a); + poly_vec_init(&b); + poly_vec_init(&result); + CHECK(poly_vec_add_term(&a, 3.0, 2)); + CHECK(poly_vec_add_term(&a, 2.0, 1)); + CHECK(poly_vec_add_term(&a, 1.0, 0)); + CHECK(poly_vec_add_term(&b, 1.0, 2)); + CHECK(poly_vec_add_term(&b, -2.0, 1)); + CHECK(poly_vec_add_term(&b, 4.0, 0)); + + CHECK(poly_vec_add(&result, &a, &b)); + CHECK(poly_vec_equal(&result, &b, 0.0) == false); + CHECK(poly_vec_get_term(&result, 2, &(double){ 0.0 })); + CHECK(result.terms.size == 2); + CHECK(poly_vec_at_const(&result, 0)->coef == 4.0); + CHECK(poly_vec_at_const(&result, 1)->exp == 0); + CHECK(poly_vec_at_const(&result, 1)->coef == 5.0); + + CHECK(poly_vec_sub(&result, &a, &b)); + CHECK(poly_vec_at_const(&result, 0)->coef == 2.0); + CHECK(poly_vec_at_const(&result, 1)->coef == 4.0); + CHECK(poly_vec_at_const(&result, 2)->coef == -3.0); + + CHECK(poly_vec_add(&a, &a, &b)); + CHECK(a.terms.size == 2); + CHECK(poly_vec_at_const(&a, 0)->coef == 4.0); + CHECK(poly_vec_at_const(&a, 1)->coef == 5.0); + + poly_vec_destroy(&a); + poly_vec_destroy(&b); + poly_vec_destroy(&result); + return true; +} + +static bool test_poly_vec_mul_derivative_and_eval(void) +{ + struct poly_vec x_plus_one; + struct poly_vec x_minus_one; + struct poly_vec result; + struct poly_vec derivative; + poly_vec_init(&x_plus_one); + poly_vec_init(&x_minus_one); + poly_vec_init(&result); + poly_vec_init(&derivative); + CHECK(poly_vec_add_term(&x_plus_one, 1.0, 1)); + CHECK(poly_vec_add_term(&x_plus_one, 1.0, 0)); + CHECK(poly_vec_add_term(&x_minus_one, 1.0, 1)); + CHECK(poly_vec_add_term(&x_minus_one, -1.0, 0)); + CHECK(poly_vec_mul(&result, &x_plus_one, &x_minus_one)); + CHECK(result.terms.size == 2); + CHECK(poly_vec_at_const(&result, 0)->exp == 2); + CHECK(poly_vec_at_const(&result, 0)->coef == 1.0); + CHECK(poly_vec_at_const(&result, 1)->exp == 0); + CHECK(poly_vec_at_const(&result, 1)->coef == -1.0); + CHECK(poly_vec_derivative(&derivative, &result, 1)); + CHECK(derivative.terms.size == 1); + CHECK(poly_vec_at_const(&derivative, 0)->coef == 2.0); + CHECK(poly_vec_eval(&result, 3.0) == 8.0); + + poly_vec_destroy(&x_plus_one); + poly_vec_destroy(&x_minus_one); + poly_vec_destroy(&result); + poly_vec_destroy(&derivative); + return true; +} + +static bool test_poly_list_normalization_and_conversion(void) +{ + struct poly_list list; + struct poly_vec vector; + struct poly_list copy; + poly_list_init(&list); + poly_vec_init(&vector); + poly_list_init(©); + CHECK(poly_list_add_term(&list, 2.0, 1)); + CHECK(poly_list_add_term(&list, 5.0, 4)); + CHECK(poly_list_add_term(&list, 3.0, 1)); + CHECK(poly_list_size(&list) == 2); + CHECK(poly_list_get_term(&list, 1, &(double){ 0.0 })); + CHECK(list_entry(list.head.next, struct poly_node, link)->term.exp == 4); + CHECK(poly_vec_from_list(&vector, &list)); + CHECK(poly_vec_size(&vector) == 2); + CHECK(poly_vec_at_const(&vector, 0)->exp == 4); + CHECK(poly_vec_at_const(&vector, 1)->coef == 5.0); + CHECK(poly_list_from_vec(©, &vector)); + CHECK(poly_list_equal(&list, ©, 0.0)); + CHECK(poly_list_remove_term(&list, 4)); + CHECK(poly_list_size(&list) == 1); + + poly_list_destroy(&list); + poly_vec_destroy(&vector); + poly_list_destroy(©); + return true; +} + +static bool test_poly_list_arithmetic_and_alias(void) +{ + struct poly_list a; + struct poly_list b; + struct poly_list result; + struct poly_list derivative; + poly_list_init(&a); + poly_list_init(&b); + poly_list_init(&result); + poly_list_init(&derivative); + CHECK(poly_list_add_term(&a, 3.0, 2)); + CHECK(poly_list_add_term(&a, 1.0, 0)); + CHECK(poly_list_add_term(&b, 1.0, 2)); + CHECK(poly_list_add_term(&b, -1.0, 0)); + CHECK(poly_list_add(&result, &a, &b)); + double coefficient; + CHECK(poly_list_get_term(&result, 2, &coefficient)); + CHECK(coefficient == 4.0); + CHECK(!poly_list_get_term(&result, 0, &coefficient)); + CHECK(poly_list_sub(&result, &a, &b)); + CHECK(poly_list_get_term(&result, 0, &coefficient)); + CHECK(coefficient == 2.0); + CHECK(poly_list_derivative(&derivative, &a, 1)); + CHECK(poly_list_get_term(&derivative, 1, &coefficient)); + CHECK(coefficient == 6.0); + CHECK(poly_list_eval(&a, 2.0) == 13.0); + CHECK(poly_list_add(&a, &a, &b)); + CHECK(poly_list_get_term(&a, 2, &coefficient)); + CHECK(coefficient == 4.0); + + poly_list_destroy(&a); + poly_list_destroy(&b); + poly_list_destroy(&result); + poly_list_destroy(&derivative); + return true; +} + +static bool test_expression_nested_precedence_and_variables(void) +{ + struct expression_context context; + struct expression_error error; + double result; + expression_init(&context); + CHECK(expression_collect_variables(&context, + "-(A + 2.5) * (B - (-C + 4)) / 2", &error)); + CHECK(context.variables.size == 3); + CHECK(expression_set_variable(&context, "A", 3.0)); + CHECK(expression_set_variable(&context, "B", 10.0)); + CHECK(expression_set_variable(&context, "C", 2.0)); + CHECK(expression_eval(&context, + "-(A + 2.5) * (B - (-C + 4)) / 2", &result, &error)); + CHECK(fabs(result + 22.0) < 1e-12); + expression_destroy(&context); + return true; +} + +static bool test_expression_variable_dedup_and_update(void) +{ + struct expression_context context; + struct expression_error error; + double result; + expression_init(&context); + CHECK(expression_collect_variables(&context, + "A1 + A1 * B2 - (B2 / 2) + C", &error)); + CHECK(context.variables.size == 3); + CHECK(expression_set_variable(&context, "A1", 4.0)); + CHECK(expression_set_variable(&context, "B2", 6.0)); + CHECK(expression_set_variable(&context, "C", 1.0)); + CHECK(expression_eval(&context, + "A1 + A1 * B2 - (B2 / 2) + C", &result, &error)); + CHECK(fabs(result - 26.0) < 1e-12); + CHECK(expression_set_variable(&context, "B2", 10.0)); + CHECK(expression_eval(&context, + "A1 + A1 * B2 - (B2 / 2) + C", &result, &error)); + CHECK(result == 40.0); + expression_destroy(&context); + return true; +} + +static bool test_expression_unary_and_decimal_values(void) +{ + struct expression_context context; + struct expression_error error; + double result; + expression_init(&context); + CHECK(expression_collect_variables(&context, + "--5 + -(+2.5) * (3 - -1) + .5", &error)); + CHECK(expression_eval(&context, + "--5 + -(+2.5) * (3 - -1) + .5", &result, &error)); + CHECK(fabs(result + 4.5) < 1e-12); + expression_destroy(&context); + return true; +} + +static bool test_expression_deep_parentheses_and_associativity(void) +{ + struct expression_context context; + struct expression_error error; + double result; + expression_init(&context); + CHECK(expression_collect_variables(&context, + "1 - 2 - 3 + 4 * (5 + (6 - (7 - 8)))", &error)); + CHECK(expression_eval(&context, + "1 - 2 - 3 + 4 * (5 + (6 - (7 - 8)))", &result, &error)); + CHECK(fabs(result - 44.0) < 1e-12); + expression_destroy(&context); + return true; +} + +static bool test_expression_error_paths(void) +{ + struct expression_context context; + struct expression_error error; + double result; + expression_init(&context); + CHECK(expression_collect_variables(&context, "X + 1", &error)); + CHECK(!expression_eval(&context, "X + 1", &result, &error)); + CHECK(error.code == EXPRESSION_UNSET_VARIABLE); + CHECK(expression_set_variable(&context, "X", 2.0)); + CHECK(!expression_eval(&context, "X / (3 - 3)", &result, &error)); + CHECK(error.code == EXPRESSION_DIVISION_BY_ZERO); + CHECK(!expression_eval(&context, "X + (2 * 3", &result, &error)); + CHECK(error.code == EXPRESSION_PAREN_ERROR); + CHECK(!expression_collect_variables(&context, "X @ 2", &error)); + CHECK(error.code == EXPRESSION_SYNTAX_ERROR); + expression_destroy(&context); + return true; +} + +struct test_case { + const char *name; + bool (*function)(void); +}; + +int main(void) +{ + const struct test_case tests[] = { + { "vec lifecycle and access", test_vec_lifecycle_and_access }, + { "vec insert, erase and assign", test_vec_insert_erase_and_assign }, + { "vec resize, capacity and swap", test_vec_resize_capacity_and_swap }, + { "vec iterators and comparison", test_vec_iterators_and_comparison }, + { "list and container_of", test_list_and_container_of }, + { "poly_vec normalization", test_poly_vec_normalization }, + { "poly_vec add, sub and alias", test_poly_vec_add_sub_and_alias }, + { "poly_vec multiply, derivative and eval", + test_poly_vec_mul_derivative_and_eval }, + { "poly_list normalization and conversion", + test_poly_list_normalization_and_conversion }, + { "poly_list arithmetic and alias", + test_poly_list_arithmetic_and_alias }, + { "expression nested precedence and variables", + test_expression_nested_precedence_and_variables }, + { "expression variable dedup and update", + test_expression_variable_dedup_and_update }, + { "expression unary and decimal values", + test_expression_unary_and_decimal_values }, + { "expression deep parentheses and associativity", + test_expression_deep_parentheses_and_associativity }, + { "expression error paths", test_expression_error_paths }, + }; + size_t failures = 0; + + for (size_t i = 0; i < sizeof(tests) / sizeof(tests[0]); ++i) { + printf("[%zu/%zu] %s\n", i + 1, + sizeof(tests) / sizeof(tests[0]), tests[i].name); + if (tests[i].function()) { + puts(" passed"); + } else { + ++failures; + puts(" failed"); + } + } + printf("\n%zu/%zu tests passed\n", + sizeof(tests) / sizeof(tests[0]) - failures, + sizeof(tests) / sizeof(tests[0])); + return failures == 0 ? EXIT_SUCCESS : EXIT_FAILURE; +} diff --git a/lab04/tui.c b/lab04/tui.c new file mode 100644 index 0000000..d5abdd2 --- /dev/null +++ b/lab04/tui.c @@ -0,0 +1,190 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +#include "tui.h" + +#include <poll.h> +#include <stdarg.h> +#include <stdio.h> +#include <termios.h> +#include <unistd.h> + +struct tui_state { + struct termios saved_termios; + bool termios_saved; + bool raw_mode; + bool alternate_screen; +}; + +static struct tui_state tui_state; + +static int tui_read_byte(void) +{ + unsigned char byte; + ssize_t count = read(STDIN_FILENO, &byte, sizeof(byte)); + + return count == (ssize_t)sizeof(byte) ? byte : -1; +} + +bool tui_init(void) +{ + if (tcgetattr(STDIN_FILENO, &tui_state.saved_termios) < 0) { + return false; + } + tui_state.termios_saved = true; + + struct termios raw = tui_state.saved_termios; + cfmakeraw(&raw); + + raw.c_oflag |= OPOST | ONLCR; + + if (tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw) < 0) { + tui_state.termios_saved = false; + return false; + } + tui_state.raw_mode = true; + + /* DEC private mode 1049: 切换到备用屏幕缓冲区 */ + fputs("\033[?1049h\033[H\033[?25l", stdout); + fflush(stdout); + tui_state.alternate_screen = true; + return true; +} + +void tui_shutdown(void) +{ + if (tui_state.alternate_screen) { + tui_show_cursor(); + fputs("\033[?1049l", stdout); + fflush(stdout); + tui_state.alternate_screen = false; + } + + if (tui_state.raw_mode && tui_state.termios_saved) { + tcsetattr(STDIN_FILENO, TCSAFLUSH, &tui_state.saved_termios); + tui_state.raw_mode = false; + } +} + +void tui_clear(void) +{ + fputs("\033[2J\033[H", stdout); +} + +void tui_hide_cursor(void) +{ + fputs("\033[?25l", stdout); +} + +void tui_show_cursor(void) +{ + fputs("\033[?25h", stdout); +} + +void tui_printf(const char *format, ...) +{ + va_list arguments; + + va_start(arguments, format); + vprintf(format, arguments); + va_end(arguments); +} + +struct tui_event tui_read_key(void) +{ + int character = tui_read_byte(); + if (character < 0) { + return (struct tui_event){ .kind = TUI_KEY_ESCAPE }; + } + + if (character == '\033') { + struct pollfd input = { + .fd = STDIN_FILENO, + .events = POLLIN, + }; + if (poll(&input, 1, 25) <= 0) { + return (struct tui_event){ .kind = TUI_KEY_ESCAPE }; + } + + int sequence = tui_read_byte(); + if (sequence == '[') { + int code = tui_read_byte(); + switch (code) { + case 'A': + return (struct tui_event){ .kind = TUI_KEY_UP }; + case 'B': + return (struct tui_event){ .kind = TUI_KEY_DOWN }; + case 'C': + return (struct tui_event){ .kind = TUI_KEY_RIGHT }; + case 'D': + return (struct tui_event){ .kind = TUI_KEY_LEFT }; + default: + break; + } + } + return (struct tui_event){ .kind = TUI_KEY_ESCAPE }; + } + + if (character == '\r' || character == '\n') { + return (struct tui_event){ .kind = TUI_KEY_ENTER }; + } + if (character == '\b' || character == 127) { + return (struct tui_event){ .kind = TUI_KEY_BACKSPACE }; + } + return (struct tui_event){ + .kind = TUI_KEY_CHARACTER, + .character = character, + }; +} + +bool tui_read_line(const char *prompt, char *buffer, size_t capacity) +{ + size_t length = 0; + + if (capacity == 0) { + return false; + } + tui_show_cursor(); + buffer[0] = '\0'; + if (prompt && *prompt) { + tui_printf("%s", prompt); + } + fflush(stdout); + + for (;;) { + struct tui_event event = tui_read_key(); + if (event.kind == TUI_KEY_ENTER) { + fputc('\n', stdout); + tui_hide_cursor(); + return true; + } + if (event.kind == TUI_KEY_ESCAPE) { + fputc('\n', stdout); + tui_hide_cursor(); + return false; + } + if (event.kind == TUI_KEY_BACKSPACE) { + if (length > 0) { + buffer[--length] = '\0'; + fputs("\b \b", stdout); + fflush(stdout); + } + continue; + } + if (event.kind == TUI_KEY_CHARACTER && + event.character >= 32 && event.character != 127 && + length + 1 < capacity) { + buffer[length++] = (char)event.character; + buffer[length] = '\0'; + fputc(event.character, stdout); + fflush(stdout); + } + } +} + +void tui_wait(void) +{ + fputs("\n\n按任意键返回...", stdout); + fflush(stdout); + (void)tui_read_key(); +} diff --git a/lab04/tui.h b/lab04/tui.h new file mode 100644 index 0000000..e28e698 --- /dev/null +++ b/lab04/tui.h @@ -0,0 +1,38 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +#ifndef TUI_H +#define TUI_H + +#include <stdbool.h> +#include <stddef.h> + +enum tui_key_kind { + TUI_KEY_CHARACTER, + TUI_KEY_UP, + TUI_KEY_DOWN, + TUI_KEY_LEFT, + TUI_KEY_RIGHT, + TUI_KEY_ENTER, + TUI_KEY_ESCAPE, + TUI_KEY_BACKSPACE, +}; + +struct tui_event { + enum tui_key_kind kind; + int character; +}; + +bool tui_init(void); +void tui_shutdown(void); + +void tui_clear(void); +void tui_hide_cursor(void); +void tui_show_cursor(void); +void tui_printf(const char *format, ...); + +struct tui_event tui_read_key(void); +bool tui_read_line(const char *prompt, char *buffer, size_t capacity); +void tui_wait(void); + +#endif /* TUI_H */ diff --git a/lab04/ui.c b/lab04/ui.c new file mode 100644 index 0000000..a6f6b1d --- /dev/null +++ b/lab04/ui.c @@ -0,0 +1,1543 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +#include "ui.h" + +#include "polynomial.h" +#include "expression.h" +#include "tui.h" + +#include <ctype.h> +#include <errno.h> +#include <inttypes.h> +#include <limits.h> +#include <math.h> +#include <stdarg.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/ioctl.h> +#include <unistd.h> + +#define STYLE_RESET "\033[0m" +#define STYLE_BOLD "\033[1m" +#define STYLE_DIM "\033[2m" +#define STYLE_SELECTED "\033[7;1m" +#define COLOR_CYAN "\033[1;36m" +#define COLOR_GREEN "\033[1;32m" +#define COLOR_RED "\033[1;31m" +#define COLOR_YELLOW "\033[1;33m" + +enum ui_vector_result_kind { + UI_VECTOR_RESULT_NONE, + UI_VECTOR_RESULT_VALUE, + UI_VECTOR_RESULT_COSINE, +}; + +struct ui_state { + struct vec linear; + + struct vec vector_a; + struct vec vector_b; + struct vec vector_result; + enum ui_vector_result_kind vector_result_kind; + double vector_cosine; + + struct poly_vec poly_vec_a; + struct poly_vec poly_vec_b; + struct poly_vec poly_vec_result; + bool poly_vec_result_valid; + + struct poly_list poly_list_a; + struct poly_list poly_list_b; + struct poly_list poly_list_result; + bool poly_list_result_valid; + + struct expression_context expression; + char expression_text[256]; + double expression_result; + bool expression_result_valid; + + char status[256]; +}; + +static void ui_set_status(struct ui_state *state, const char *format, ...) +{ + va_list arguments; + + va_start(arguments, format); + vsnprintf(state->status, sizeof(state->status), format, arguments); + va_end(arguments); +} + +static void ui_clear_status(struct ui_state *state) +{ + state->status[0] = '\0'; +} + +/* 计算 UTF-8 字符串在终端中的实际显示列宽（中文字符占 2 列） */ +static size_t ui_str_display_width(const char *str) +{ + size_t width = 0; + while (*str) { + unsigned char c = (unsigned char)*str; + if (c < 0x80) { + width += 1; + str += 1; + } else if ((c & 0xE0) == 0xC0) { + width += 1; + str += 2; + } else if ((c & 0xF0) == 0xE0) { + width += 2; + str += 3; + } else if ((c & 0xF8) == 0xF0) { + width += 2; + str += 4; + } else { + str += 1; + } + } + return width; +} + +static int ui_terminal_width(void) +{ + struct winsize size; + if (ioctl(STDOUT_FILENO, TIOCGWINSZ, &size) == 0 && size.ws_col > 0) { + return size.ws_col; + } + return 50; +} + +static void ui_print_rule(char character) +{ + int width = ui_terminal_width(); + for (int i = 0; i < width; ++i) { + putchar(character); + } + putchar('\n'); +} + +static void ui_print_centered(const char *text, int width) +{ + size_t disp_w = ui_str_display_width(text); + int pad = (width > (int)disp_w) ? (width - (int)disp_w) / 2 : 0; + for (int i = 0; i < pad; ++i) { + putchar(' '); + } + printf("%s\n", text); +} + +static void ui_print_header(const char *title) +{ + int width = ui_terminal_width(); + printf(COLOR_CYAN); + ui_print_rule('='); + printf(STYLE_BOLD); + ui_print_centered(title, width); + printf(STYLE_RESET); + printf(COLOR_CYAN); + ui_print_rule('='); + printf(STYLE_RESET "\n"); +} + +static void ui_print_status(const struct ui_state *state) +{ + if (state->status[0] != '\0') { + printf("\n" STYLE_DIM); + ui_print_rule('-'); + printf(STYLE_RESET); + if (strncmp(state->status, "错误", 6) == 0) { + printf(COLOR_RED " [!] %s" STYLE_RESET "\n", state->status); + } else if (strncmp(state->status, "已取消", 9) == 0) { + printf(COLOR_YELLOW " [*] %s" STYLE_RESET "\n", state->status); + } else { + printf(COLOR_GREEN " [√] %s" STYLE_RESET "\n", state->status); + } + } +} + +static void ui_print_footer(const char *text) +{ + printf("\n" STYLE_DIM); + ui_print_rule('-'); + printf(STYLE_RESET); + printf(STYLE_DIM " %s" STYLE_RESET "\n", text); +} + +static void ui_print_menu(const char *const *items, + size_t count, + size_t selected, + const char *zero_item) +{ + for (size_t i = 0; i < count; ++i) { + if (i == selected) { + printf(STYLE_SELECTED " > %zu. %s " STYLE_RESET "\n", i + 1, items[i]); + } else { + printf(" %zu. %s\n", i + 1, items[i]); + } + } + if (selected == count) { + printf(STYLE_SELECTED " > 0. %s " STYLE_RESET "\n", zero_item); + } else { + printf(STYLE_DIM " 0. %s" STYLE_RESET "\n", zero_item); + } +} + +static int ui_menu_input(size_t *selected, size_t count) +{ + size_t total = count + 1; + struct tui_event event = tui_read_key(); + + if (event.kind == TUI_KEY_UP) { + *selected = *selected == 0 ? total - 1 : *selected - 1; + return -2; + } + if (event.kind == TUI_KEY_DOWN) { + *selected = (*selected + 1) % total; + return -2; + } + if (event.kind == TUI_KEY_CHARACTER && + (event.character == 'k' || event.character == 'K')) { + *selected = *selected == 0 ? total - 1 : *selected - 1; + return -2; + } + if (event.kind == TUI_KEY_CHARACTER && + (event.character == 'j' || event.character == 'J')) { + *selected = (*selected + 1) % total; + return -2; + } + if (event.kind == TUI_KEY_ENTER) { + if (*selected == count) { + return -1; + } + return (int)*selected; + } + if (event.kind == TUI_KEY_ESCAPE || + (event.kind == TUI_KEY_CHARACTER && + (event.character == 'q' || event.character == 'Q' || + event.character == '0'))) { + return -1; + } + if (event.kind == TUI_KEY_CHARACTER && + event.character >= '1' && + event.character <= '0' + (int)count) { + return event.character - '1'; + } + return -2; +} + +static void ui_print_vec_int(const struct vec *vector) +{ + printf("["); + for (size_t i = 0; i < vector->size; ++i) { + if (i != 0) { + printf(", "); + } + printf("%d", *(const int *)vec_at_const(vector, i)); + } + printf("]"); +} + +static void ui_print_vec_double(const struct vec *vector) +{ + printf("["); + for (size_t i = 0; i < vector->size; ++i) { + if (i != 0) { + printf(", "); + } + printf("%g", *(const double *)vec_at_const(vector, i)); + } + printf("]"); +} + +static void ui_print_poly_term(double coefficient, + unsigned int exponent, + bool *first) +{ + double magnitude = fabs(coefficient); + + if (*first) { + if (coefficient < 0.0) { + printf("-"); + } + *first = false; + } else { + printf(coefficient < 0.0 ? " - " : " + "); + } + + if (exponent == 0) { + printf("%g", magnitude); + return; + } + if (magnitude != 1.0) { + printf("%g", magnitude); + } + printf("x"); + if (exponent != 1) { + printf("^%u", exponent); + } +} + +static void ui_print_poly_vec(const struct poly_vec *poly) +{ + bool first = true; + + for (size_t i = 0; i < poly->terms.size; ++i) { + const struct poly_term *term = vec_at_const(&poly->terms, i); + ui_print_poly_term(term->coef, term->exp, &first); + } + if (first) { + printf("0"); + } +} + +static void ui_print_poly_list(const struct poly_list *poly) +{ + bool first = true; + const struct list_head *position = poly->head.next; + + while (position != &poly->head) { + const struct poly_node *node = + list_entry(position, const struct poly_node, link); + ui_print_poly_term(node->term.coef, node->term.exp, &first); + position = position->next; + } + if (first) { + printf("0"); + } +} + +static const char *ui_skip_space(const char *text) +{ + while (isspace((unsigned char)*text)) { + ++text; + } + return text; +} + +static bool ui_parse_int(const char *text, int *value) +{ + char *end; + const char *start = ui_skip_space(text); + + errno = 0; + long parsed = strtol(start, &end, 10); + if (start == end || errno == ERANGE || parsed < INT_MIN || + parsed > INT_MAX || *ui_skip_space(end) != '\0') { + return false; + } + *value = (int)parsed; + return true; +} + +static bool ui_parse_size(const char *text, size_t *value) +{ + char *end; + const char *start = ui_skip_space(text); + + if (*start == '-') { + return false; + } + errno = 0; + uintmax_t parsed = strtoumax(start, &end, 10); + if (start == end || errno == ERANGE || parsed > SIZE_MAX || + *ui_skip_space(end) != '\0') { + return false; + } + *value = (size_t)parsed; + return true; +} + +static bool ui_parse_unsigned(const char *text, unsigned int *value) +{ + char *end; + const char *start = ui_skip_space(text); + + if (*start == '-') { + return false; + } + errno = 0; + uintmax_t parsed = strtoumax(start, &end, 10); + if (start == end || errno == ERANGE || parsed > UINT_MAX || + *ui_skip_space(end) != '\0') { + return false; + } + *value = (unsigned int)parsed; + return true; +} + +static bool ui_parse_vector(const char *text, struct vec *destination) +{ + struct vec temporary; + vec_init(&temporary, double); + const char *position = text; + + for (;;) { + char *end; + position = ui_skip_space(position); + if (*position == '\0') { + break; + } + + errno = 0; + double value = strtod(position, &end); + if (position == end || errno == ERANGE || + !vec_push_back(&temporary, &value)) { + vec_destroy(&temporary); + return false; + } + position = end; + } + + if (temporary.size == 0) { + vec_destroy(&temporary); + return false; + } + vec_swap(destination, &temporary); + vec_destroy(&temporary); + return true; +} + +static bool ui_parse_poly_vec(const char *text, struct poly_vec *destination) +{ + struct poly_vec temporary; + poly_vec_init(&temporary); + const char *position = text; + size_t term_count = 0; + + for (;;) { + char *end; + position = ui_skip_space(position); + if (*position == '\0') { + break; + } + + errno = 0; + double coefficient = strtod(position, &end); + if (position == end || errno == ERANGE) { + poly_vec_destroy(&temporary); + return false; + } + position = ui_skip_space(end); + + if (*position == '-') { + poly_vec_destroy(&temporary); + return false; + } + errno = 0; + uintmax_t exponent = strtoumax(position, &end, 10); + if (position == end || errno == ERANGE || exponent > UINT_MAX) { + poly_vec_destroy(&temporary); + return false; + } + if (!poly_vec_add_term(&temporary, coefficient, + (unsigned int)exponent)) { + poly_vec_destroy(&temporary); + return false; + } + ++term_count; + position = end; + } + + if (term_count == 0) { + poly_vec_destroy(&temporary); + return false; + } + vec_swap(&destination->terms, &temporary.terms); + poly_vec_destroy(&temporary); + return true; +} + +static bool ui_parse_poly_list(const char *text, struct poly_list *destination) +{ + struct poly_list temporary; + poly_list_init(&temporary); + const char *position = text; + size_t term_count = 0; + + for (;;) { + char *end; + position = ui_skip_space(position); + if (*position == '\0') { + break; + } + + errno = 0; + double coefficient = strtod(position, &end); + if (position == end || errno == ERANGE) { + poly_list_destroy(&temporary); + return false; + } + position = ui_skip_space(end); + + if (*position == '-') { + poly_list_destroy(&temporary); + return false; + } + errno = 0; + uintmax_t exponent = strtoumax(position, &end, 10); + if (position == end || errno == ERANGE || exponent > UINT_MAX) { + poly_list_destroy(&temporary); + return false; + } + if (!poly_list_add_term(&temporary, coefficient, + (unsigned int)exponent)) { + poly_list_destroy(&temporary); + return false; + } + ++term_count; + position = end; + } + + if (term_count == 0) { + poly_list_destroy(&temporary); + return false; + } + __poly_list_replace(destination, &temporary); + return true; +} + +/* 原位输入框：保留界面上下文数据 */ +static bool ui_prompt_inline(const char *title, + const char *description, + char *buffer, + size_t capacity) +{ + printf("\n" COLOR_YELLOW "┌── %s" STYLE_RESET "\n", title); + if (description != NULL && *description != '\0') { + printf(COLOR_YELLOW "│ " STYLE_RESET "%s\n", description); + } + printf(COLOR_YELLOW "└─> " STYLE_RESET); + fflush(stdout); + return tui_read_line("", buffer, capacity); +} + +static bool ui_confirm(const char *title, const char *question) +{ + char input[16]; + + if (!ui_prompt_inline(title, question, input, sizeof(input))) { + return false; + } + return input[0] == 'y' || input[0] == 'Y'; +} + +static bool ui_state_init(struct ui_state *state) +{ + memset(state, 0, sizeof(*state)); + vec_init(&state->linear, int); + vec_init(&state->vector_a, double); + vec_init(&state->vector_b, double); + vec_init(&state->vector_result, double); + poly_vec_init(&state->poly_vec_a); + poly_vec_init(&state->poly_vec_b); + poly_vec_init(&state->poly_vec_result); + poly_list_init(&state->poly_list_a); + poly_list_init(&state->poly_list_b); + poly_list_init(&state->poly_list_result); + expression_init(&state->expression); + + int linear_values[] = { 10, 20, 30, 40 }; + double vector_a_values[] = { 1.0, 2.0, 3.0 }; + double vector_b_values[] = { 4.0, 5.0, 6.0 }; + for (size_t i = 0; i < sizeof(linear_values) / sizeof(linear_values[0]); + ++i) { + if (!vec_push_back(&state->linear, &linear_values[i])) { + return false; + } + } + for (size_t i = 0; i < sizeof(vector_a_values) / sizeof(vector_a_values[0]); + ++i) { + if (!vec_push_back(&state->vector_a, &vector_a_values[i]) || + !vec_push_back(&state->vector_b, &vector_b_values[i])) { + return false; + } + } + + if (!poly_vec_add_term(&state->poly_vec_a, 5.0, 4) || + !poly_vec_add_term(&state->poly_vec_a, 3.0, 2) || + !poly_vec_add_term(&state->poly_vec_a, 1.0, 0) || + !poly_vec_add_term(&state->poly_vec_b, 2.0, 3) || + !poly_vec_add_term(&state->poly_vec_b, -3.0, 2) || + !poly_vec_add_term(&state->poly_vec_b, 7.0, 0) || + !poly_list_add_term(&state->poly_list_a, 5.0, 4) || + !poly_list_add_term(&state->poly_list_a, 3.0, 2) || + !poly_list_add_term(&state->poly_list_a, 1.0, 0) || + !poly_list_add_term(&state->poly_list_b, 2.0, 3) || + !poly_list_add_term(&state->poly_list_b, -3.0, 2) || + !poly_list_add_term(&state->poly_list_b, 7.0, 0)) { + return false; + } + return true; +} + +static void ui_state_destroy(struct ui_state *state) +{ + vec_destroy(&state->linear); + vec_destroy(&state->vector_a); + vec_destroy(&state->vector_b); + vec_destroy(&state->vector_result); + poly_vec_destroy(&state->poly_vec_a); + poly_vec_destroy(&state->poly_vec_b); + poly_vec_destroy(&state->poly_vec_result); + poly_list_destroy(&state->poly_list_a); + poly_list_destroy(&state->poly_list_b); + poly_list_destroy(&state->poly_list_result); + expression_destroy(&state->expression); +} + +static void ui_draw_linear(const struct ui_state *state, size_t selected) +{ + static const char *const items[] = { + "尾部添加", + "指定位置插入", + "删除元素", + "修改元素", + "查找元素", + "遍历线性表", + "清空线性表", + "查看内部状态", + }; + + tui_clear(); + ui_print_header("线性表操作"); + printf(COLOR_CYAN "当前线性表: " STYLE_BOLD); + ui_print_vec_int(&state->linear); + printf(STYLE_RESET "\n" STYLE_DIM "size = %zu capacity = %zu" STYLE_RESET "\n\n", + state->linear.size, state->linear.capacity); + + ui_print_menu(items, sizeof(items) / sizeof(items[0]), selected, "返回"); + ui_print_status(state); + ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q/Esc 返回"); + fflush(stdout); +} + +static bool ui_read_int_value(const char *title, + const char *description, + int *value, + struct ui_state *state) +{ + char input[128]; + + if (!ui_prompt_inline(title, description, input, sizeof(input))) { + ui_set_status(state, "已取消"); + return false; + } + if (!ui_parse_int(input, value)) { + ui_set_status(state, "错误：输入格式无效"); + return false; + } + return true; +} + +static bool ui_read_size_value(const char *title, + const char *description, + size_t *value, + struct ui_state *state) +{ + char input[128]; + + if (!ui_prompt_inline(title, description, input, sizeof(input))) { + ui_set_status(state, "已取消"); + return false; + } + if (!ui_parse_size(input, value)) { + ui_set_status(state, "错误：输入格式无效"); + return false; + } + return true; +} + +static void ui_linear_append(struct ui_state *state) +{ + int value; + + if (!ui_read_int_value("尾部添加", "元素值：", &value, state)) { + return; + } + if (!vec_push_back(&state->linear, &value)) { + ui_set_status(state, "错误：内存分配失败"); + return; + } + ui_set_status(state, "已添加元素 %d", value); +} + +static void ui_linear_insert(struct ui_state *state) +{ + size_t index; + int value; + + if (!ui_read_size_value("指定位置插入", "插入位置：", &index, state) || + !ui_read_int_value("指定位置插入", "元素值：", &value, state)) { + return; + } + if (index > state->linear.size) { + ui_set_status(state, "错误：插入位置超出范围"); + return; + } + if (!vec_insert(&state->linear, index, &value)) { + ui_set_status(state, "错误：内存分配失败"); + return; + } + ui_set_status(state, "已在位置 %zu 插入 %d", index, value); +} + +static void ui_linear_erase(struct ui_state *state) +{ + size_t index; + + if (!ui_read_size_value("删除元素", "删除位置：", &index, state)) { + return; + } + if (index >= state->linear.size) { + ui_set_status(state, "错误：删除位置超出范围"); + return; + } + vec_erase(&state->linear, index); + ui_set_status(state, "已删除位置 %zu 的元素", index); +} + +static void ui_linear_modify(struct ui_state *state) +{ + size_t index; + int value; + + if (!ui_read_size_value("修改元素", "修改位置：", &index, state) || + !ui_read_int_value("修改元素", "新元素值：", &value, state)) { + return; + } + int *element = vec_at_checked(&state->linear, index); + if (element == NULL) { + ui_set_status(state, "错误：修改位置超出范围"); + return; + } + *element = value; + ui_set_status(state, "已修改位置 %zu", index); +} + +static void ui_linear_find(struct ui_state *state) +{ + int value; + + if (!ui_read_int_value("查找元素", "查找值：", &value, state)) { + return; + } + for (size_t i = 0; i < state->linear.size; ++i) { + if (*(const int *)vec_at_const(&state->linear, i) == value) { + ui_set_status(state, "元素 %d 位于位置 %zu", value, i); + return; + } + } + ui_set_status(state, "未找到元素 %d", value); +} + +static void ui_linear_traverse(const struct ui_state *state) +{ + tui_clear(); + ui_print_header("遍历线性表"); + printf("当前线性表："); + ui_print_vec_int(&state->linear); + printf("\n"); + tui_wait(); +} + +static void ui_linear_clear(struct ui_state *state) +{ + if (!ui_confirm("清空线性表", "确定清空当前线性表？ [y/N]")) { + ui_set_status(state, "已取消"); + return; + } + vec_clear(&state->linear); + ui_set_status(state, "已清空线性表"); +} + +static void ui_linear_state(const struct ui_state *state) +{ + tui_clear(); + ui_print_header("线性表内部状态"); + printf("size = %zu\n", state->linear.size); + printf("capacity = %zu\n", state->linear.capacity); + printf("elem_size = %zu\n\n", state->linear.elem_size); + printf("下标 元素\n"); + printf("────────────────────────\n"); + for (size_t i = 0; i < state->linear.size; ++i) { + printf("%-11zu %d\n", i, + *(const int *)vec_at_const(&state->linear, i)); + } + tui_wait(); +} + +static void ui_linear_action(struct ui_state *state, int choice) +{ + ui_clear_status(state); + switch (choice) { + case 0: + ui_linear_append(state); + break; + case 1: + ui_linear_insert(state); + break; + case 2: + ui_linear_erase(state); + break; + case 3: + ui_linear_modify(state); + break; + case 4: + ui_linear_find(state); + break; + case 5: + ui_linear_traverse(state); + break; + case 6: + ui_linear_clear(state); + break; + case 7: + ui_linear_state(state); + break; + default: + break; + } +} + +static void ui_linear_page(struct ui_state *state) +{ + size_t selected = 0; + + for (;;) { + ui_draw_linear(state, selected); + int choice = ui_menu_input(&selected, 8); + if (choice == -1) { + return; + } + if (choice >= 0) { + ui_linear_action(state, choice); + } + } +} + +static void ui_draw_vector(const struct ui_state *state, size_t selected) +{ + static const char *const items[] = { + "输入向量 A", + "输入向量 B", + "A + B", + "A - B", + "计算夹角余弦", + }; + + tui_clear(); + ui_print_header("向量运算"); + printf(COLOR_CYAN "A = " STYLE_BOLD); + ui_print_vec_double(&state->vector_a); + printf(STYLE_RESET "\n" COLOR_CYAN "B = " STYLE_BOLD); + ui_print_vec_double(&state->vector_b); + printf(STYLE_RESET "\n\n"); + + ui_print_menu(items, sizeof(items) / sizeof(items[0]), selected, "返回"); + + if (state->vector_result_kind == UI_VECTOR_RESULT_VALUE) { + printf("\n" COLOR_GREEN "结果：" STYLE_BOLD); + ui_print_vec_double(&state->vector_result); + printf(STYLE_RESET "\n"); + } else if (state->vector_result_kind == UI_VECTOR_RESULT_COSINE) { + printf("\n" COLOR_GREEN "cos(A, B) = %.6f" STYLE_RESET "\n", state->vector_cosine); + } + + ui_print_status(state); + ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q/Esc 返回"); + fflush(stdout); +} + +static void ui_vector_input(struct vec *destination, + const char *name, + struct ui_state *state) +{ + char input[512]; + char description[128]; + + snprintf(description, sizeof(description), + "请输入各分量，以空格分隔（向量 %s）：", name); + if (!ui_prompt_inline(name, description, input, sizeof(input))) { + ui_set_status(state, "已取消"); + return; + } + if (!ui_parse_vector(input, destination)) { + ui_set_status(state, "错误：向量输入格式无效"); + return; + } + state->vector_result_kind = UI_VECTOR_RESULT_NONE; + ui_set_status(state, "已更新向量 %s", name); +} + +static void ui_vector_binary(struct ui_state *state, bool subtract) +{ + if (state->vector_a.size != state->vector_b.size) { + ui_set_status(state, "错误：两个向量维度不同"); + return; + } + + struct vec temporary; + vec_init(&temporary, double); + for (size_t i = 0; i < state->vector_a.size; ++i) { + double left = *(const double *)vec_at_const(&state->vector_a, i); + double right = *(const double *)vec_at_const(&state->vector_b, i); + double value = subtract ? left - right : left + right; + if (!vec_push_back(&temporary, &value)) { + vec_destroy(&temporary); + ui_set_status(state, "错误：内存分配失败"); + return; + } + } + vec_swap(&state->vector_result, &temporary); + vec_destroy(&temporary); + state->vector_result_kind = UI_VECTOR_RESULT_VALUE; + ui_set_status(state, "已计算 A %c B", subtract ? '-' : '+'); +} + +static void ui_vector_cosine(struct ui_state *state) +{ + if (state->vector_a.size != state->vector_b.size) { + ui_set_status(state, "错误：两个向量维度不同"); + return; + } + + double dot = 0.0; + double norm_a = 0.0; + double norm_b = 0.0; + for (size_t i = 0; i < state->vector_a.size; ++i) { + double left = *(const double *)vec_at_const(&state->vector_a, i); + double right = *(const double *)vec_at_const(&state->vector_b, i); + dot += left * right; + norm_a += left * left; + norm_b += right * right; + } + if (norm_a == 0.0 || norm_b == 0.0) { + ui_set_status(state, "错误：零向量无法计算夹角余弦"); + return; + } + state->vector_cosine = dot / (sqrt(norm_a) * sqrt(norm_b)); + state->vector_result_kind = UI_VECTOR_RESULT_COSINE; + ui_set_status(state, "已计算夹角余弦"); +} + +static void ui_vector_action(struct ui_state *state, int choice) +{ + ui_clear_status(state); + switch (choice) { + case 0: + ui_vector_input(&state->vector_a, "输入向量 A", state); + break; + case 1: + ui_vector_input(&state->vector_b, "输入向量 B", state); + break; + case 2: + ui_vector_binary(state, false); + break; + case 3: + ui_vector_binary(state, true); + break; + case 4: + ui_vector_cosine(state); + break; + default: + break; + } +} + +static void ui_vector_page(struct ui_state *state) +{ + size_t selected = 0; + + for (;;) { + ui_draw_vector(state, selected); + int choice = ui_menu_input(&selected, 5); + if (choice == -1) { + return; + } + if (choice >= 0) { + ui_vector_action(state, choice); + } + } +} + +static void ui_draw_poly_vec(const struct ui_state *state, size_t selected) +{ + static const char *const items[] = { + "输入多项式 A", + "输入多项式 B", + "A + B", + "A - B", + "A × B", + "多项式求导", + "查看存储结构", + }; + + tui_clear(); + ui_print_header("顺序表多项式"); + printf(COLOR_CYAN "A(x) = " STYLE_BOLD); + ui_print_poly_vec(&state->poly_vec_a); + printf(STYLE_RESET "\n" COLOR_CYAN "B(x) = " STYLE_BOLD); + ui_print_poly_vec(&state->poly_vec_b); + printf(STYLE_RESET "\n\n"); + + ui_print_menu(items, sizeof(items) / sizeof(items[0]), selected, "返回"); + + if (state->poly_vec_result_valid) { + printf("\n" COLOR_GREEN "结果：" STYLE_BOLD); + ui_print_poly_vec(&state->poly_vec_result); + printf(STYLE_RESET "\n"); + } + + ui_print_status(state); + ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q/Esc 返回"); + fflush(stdout); +} + +static void ui_poly_vec_input(struct poly_vec *destination, + const char *name, + struct ui_state *state) +{ + char input[512]; + char description[256]; + + snprintf(description, sizeof(description), + "输入格式：系数 指数；多个项用空格分隔\n例如：5 4 3 2 1 0\n输入多项式 %s：", + name); + if (!ui_prompt_inline("输入多项式", description, input, sizeof(input))) { + ui_set_status(state, "已取消"); + return; + } + if (!ui_parse_poly_vec(input, destination)) { + ui_set_status(state, "错误：输入格式无效，应输入“系数 指数”对"); + return; + } + state->poly_vec_result_valid = false; + ui_set_status(state, "已更新多项式 %s", name); +} + +static void ui_poly_vec_binary(struct ui_state *state, char operation) +{ + bool success; + + switch (operation) { + case '+': + success = poly_vec_add(&state->poly_vec_result, + &state->poly_vec_a, &state->poly_vec_b); + break; + case '-': + success = poly_vec_sub(&state->poly_vec_result, + &state->poly_vec_a, &state->poly_vec_b); + break; + default: + success = poly_vec_mul(&state->poly_vec_result, + &state->poly_vec_a, &state->poly_vec_b); + break; + } + if (!success) { + ui_set_status(state, "错误：多项式运算失败"); + return; + } + state->poly_vec_result_valid = true; + ui_set_status(state, "已计算 A %c B", operation); +} + +static void ui_poly_vec_derivative(struct ui_state *state) +{ + char input[128]; + unsigned int which; + unsigned int order; + const struct poly_vec *source; + + if (!ui_prompt_inline("多项式求导", "选择多项式（1=A，2=B）：", + input, sizeof(input))) { + ui_set_status(state, "已取消"); + return; + } + if (!ui_parse_unsigned(input, &which) || (which != 1 && which != 2)) { + ui_set_status(state, "错误：多项式选择无效"); + return; + } + if (!ui_prompt_inline("多项式求导", "输入求导阶数：", + input, sizeof(input))) { + ui_set_status(state, "已取消"); + return; + } + if (!ui_parse_unsigned(input, &order)) { + ui_set_status(state, "错误：求导阶数无效"); + return; + } + source = which == 1 ? &state->poly_vec_a : &state->poly_vec_b; + if (!poly_vec_derivative(&state->poly_vec_result, source, order)) { + ui_set_status(state, "错误：多项式求导失败"); + return; + } + state->poly_vec_result_valid = true; + ui_set_status(state, "已完成多项式求导"); +} + +static void ui_poly_vec_storage(const struct ui_state *state) +{ + tui_clear(); + ui_print_header("顺序表存储结构"); + printf("A(x) = "); + ui_print_poly_vec(&state->poly_vec_a); + printf("\nsize = %zu capacity = %zu\n", + state->poly_vec_a.terms.size, + state->poly_vec_a.terms.capacity); + printf("下标 系数 指数\n"); + printf("─────────────────────────────\n"); + for (size_t i = 0; i < state->poly_vec_a.terms.size; ++i) { + const struct poly_term *term = + vec_at_const(&state->poly_vec_a.terms, i); + printf("%-12zu %-12.6g %u\n", i, term->coef, term->exp); + } + printf("\nB(x) = "); + ui_print_poly_vec(&state->poly_vec_b); + printf("\nsize = %zu capacity = %zu\n", + state->poly_vec_b.terms.size, + state->poly_vec_b.terms.capacity); + tui_wait(); +} + +static void ui_poly_vec_action(struct ui_state *state, int choice) +{ + ui_clear_status(state); + switch (choice) { + case 0: + ui_poly_vec_input(&state->poly_vec_a, "A", state); + break; + case 1: + ui_poly_vec_input(&state->poly_vec_b, "B", state); + break; + case 2: + ui_poly_vec_binary(state, '+'); + break; + case 3: + ui_poly_vec_binary(state, '-'); + break; + case 4: + ui_poly_vec_binary(state, '*'); + break; + case 5: + ui_poly_vec_derivative(state); + break; + case 6: + ui_poly_vec_storage(state); + break; + default: + break; + } +} + +static void ui_poly_vec_page(struct ui_state *state) +{ + size_t selected = 0; + + for (;;) { + ui_draw_poly_vec(state, selected); + int choice = ui_menu_input(&selected, 7); + if (choice == -1) { + return; + } + if (choice >= 0) { + ui_poly_vec_action(state, choice); + } + } +} + +static void ui_draw_poly_list(const struct ui_state *state, size_t selected) +{ + static const char *const items[] = { + "输入多项式 A", + "输入多项式 B", + "A + B", + "A - B", + "A × B", + "多项式求导", + "查看链表结构", + }; + + tui_clear(); + ui_print_header("链表多项式"); + printf(COLOR_CYAN "A(x) = " STYLE_BOLD); + ui_print_poly_list(&state->poly_list_a); + printf(STYLE_RESET "\n" COLOR_CYAN "B(x) = " STYLE_BOLD); + ui_print_poly_list(&state->poly_list_b); + printf(STYLE_RESET "\n\n"); + + ui_print_menu(items, sizeof(items) / sizeof(items[0]), selected, "返回"); + + if (state->poly_list_result_valid) { + printf("\n" COLOR_GREEN "结果：" STYLE_BOLD); + ui_print_poly_list(&state->poly_list_result); + printf(STYLE_RESET "\n"); + } + + ui_print_status(state); + ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q/Esc 返回"); + fflush(stdout); +} + +static void ui_poly_list_input(struct poly_list *destination, + const char *name, + struct ui_state *state) +{ + char input[512]; + char description[256]; + + snprintf(description, sizeof(description), + "输入格式：系数 指数；多个项用空格分隔\n例如：5 4 3 2 1 0\n输入多项式 %s：", + name); + if (!ui_prompt_inline("输入多项式", description, input, sizeof(input))) { + ui_set_status(state, "已取消"); + return; + } + if (!ui_parse_poly_list(input, destination)) { + ui_set_status(state, "错误：输入格式无效，应输入“系数 指数”对"); + return; + } + state->poly_list_result_valid = false; + ui_set_status(state, "已更新多项式 %s", name); +} + +static void ui_poly_list_binary(struct ui_state *state, char operation) +{ + bool success; + + switch (operation) { + case '+': + success = poly_list_add(&state->poly_list_result, + &state->poly_list_a, &state->poly_list_b); + break; + case '-': + success = poly_list_sub(&state->poly_list_result, + &state->poly_list_a, &state->poly_list_b); + break; + default: + success = poly_list_mul(&state->poly_list_result, + &state->poly_list_a, &state->poly_list_b); + break; + } + if (!success) { + ui_set_status(state, "错误：多项式运算失败"); + return; + } + state->poly_list_result_valid = true; + ui_set_status(state, "已计算 A %c B", operation); +} + +static void ui_poly_list_derivative(struct ui_state *state) +{ + char input[128]; + unsigned int which; + unsigned int order; + const struct poly_list *source; + + if (!ui_prompt_inline("多项式求导", "选择多项式（1=A，2=B）：", + input, sizeof(input))) { + ui_set_status(state, "已取消"); + return; + } + if (!ui_parse_unsigned(input, &which) || (which != 1 && which != 2)) { + ui_set_status(state, "错误：多项式选择无效"); + return; + } + if (!ui_prompt_inline("多项式求导", "输入求导阶数：", + input, sizeof(input))) { + ui_set_status(state, "已取消"); + return; + } + if (!ui_parse_unsigned(input, &order)) { + ui_set_status(state, "错误：求导阶数无效"); + return; + } + source = which == 1 ? &state->poly_list_a : &state->poly_list_b; + if (!poly_list_derivative(&state->poly_list_result, source, order)) { + ui_set_status(state, "错误：多项式求导失败"); + return; + } + state->poly_list_result_valid = true; + ui_set_status(state, "已完成多项式求导"); +} + +static void ui_poly_list_storage(const struct ui_state *state) +{ + tui_clear(); + ui_print_header("链表存储结构"); + printf("A(x) = "); + ui_print_poly_list(&state->poly_list_a); + printf("\n节点数：%zu\n\n", state->poly_list_a.size); + printf("HEAD"); + const struct list_head *position = state->poly_list_a.head.next; + while (position != &state->poly_list_a.head) { + const struct poly_node *node = + list_entry(position, const struct poly_node, link); + printf(" <-> [ %g, %u ]", node->term.coef, node->term.exp); + position = position->next; + } + printf(" <-> HEAD\n"); + printf("\n每个节点：[ coef | exp | link ]\n"); + printf("\nB(x) = "); + ui_print_poly_list(&state->poly_list_b); + printf("\n节点数：%zu\n", state->poly_list_b.size); + tui_wait(); +} + +static void ui_poly_list_action(struct ui_state *state, int choice) +{ + ui_clear_status(state); + switch (choice) { + case 0: + ui_poly_list_input(&state->poly_list_a, "A", state); + break; + case 1: + ui_poly_list_input(&state->poly_list_b, "B", state); + break; + case 2: + ui_poly_list_binary(state, '+'); + break; + case 3: + ui_poly_list_binary(state, '-'); + break; + case 4: + ui_poly_list_binary(state, '*'); + break; + case 5: + ui_poly_list_derivative(state); + break; + case 6: + ui_poly_list_storage(state); + break; + default: + break; + } +} + +static void ui_poly_list_page(struct ui_state *state) +{ + size_t selected = 0; + + for (;;) { + ui_draw_poly_list(state, selected); + int choice = ui_menu_input(&selected, 7); + if (choice == -1) { + return; + } + if (choice >= 0) { + ui_poly_list_action(state, choice); + } + } +} + +static const char *ui_expression_error_text(enum expression_error_code code) +{ + switch (code) { + case EXPRESSION_SYNTAX_ERROR: return "表达式语法错误"; + case EXPRESSION_PAREN_ERROR: return "括号不匹配"; + case EXPRESSION_UNKNOWN_VARIABLE: return "变量不存在"; + case EXPRESSION_UNSET_VARIABLE: return "变量尚未赋值"; + case EXPRESSION_DIVISION_BY_ZERO: return "除数不能为零"; + default: return "表达式错误"; + } +} + +static void ui_draw_expression(const struct ui_state *state, size_t selected) +{ + static const char *const items[] = { + "输入新表达式", + "修改变量值", + "计算表达式", + }; + + tui_clear(); + ui_print_header("表达式计算"); + printf(COLOR_CYAN "当前表达式：" STYLE_RESET "\n %s\n\n", + state->expression_text[0] ? state->expression_text : "（未输入）"); + printf(COLOR_CYAN "变量表：" STYLE_RESET "\n"); + if (state->expression.variables.size == 0) { + printf(" （无变量）\n"); + } + for (size_t i = 0; i < state->expression.variables.size; ++i) { + const struct expression_variable *v = + vec_at_const(&state->expression.variables, i); + if (v->assigned) printf(" %s = %g\n", v->name, v->value); + else printf(" %s = （未赋值）\n", v->name); + } + printf("\n" COLOR_CYAN "计算结果：" STYLE_RESET "\n"); + if (state->expression_result_valid) printf(" %g\n", state->expression_result); + else printf(" （未计算）\n"); + ui_print_menu(items, 3, selected, "返回"); + ui_print_status(state); + ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q/Esc 返回"); + fflush(stdout); +} + +static void ui_expression_input(struct ui_state *state) +{ + char input[sizeof(state->expression_text)]; + if (!ui_prompt_inline("输入新表达式", "例如：3+4*X2-2*(20-5*2)", + input, sizeof(input))) return; + struct expression_error error; + if (!expression_collect_variables(&state->expression, input, &error)) { + ui_set_status(state, "错误：%s（位置 %zu）", + ui_expression_error_text(error.code), error.position); + return; + } + strcpy(state->expression_text, input); + state->expression_result_valid = false; + ui_set_status(state, "已更新表达式"); +} + +static void ui_expression_set_variable(struct ui_state *state) +{ + char name[EXPRESSION_NAME_MAX]; + char input[64]; + if (state->expression.variables.size == 0) { + ui_set_status(state, "当前表达式没有变量"); + return; + } + if (!ui_prompt_inline("修改变量值", "输入变量名：", name, sizeof(name))) return; + struct expression_variable *variable = expression_variable(&state->expression, name); + if (!variable) { + ui_set_status(state, "错误：变量不存在"); + return; + } + if (!ui_prompt_inline("修改变量值", "输入新值：", input, sizeof(input))) return; + char *end; + errno = 0; + double value = strtod(input, &end); + if (end == input || errno == ERANGE || *ui_skip_space(end) != '\0') { + ui_set_status(state, "错误：数值格式无效"); + return; + } + variable->value = value; + variable->assigned = true; + state->expression_result_valid = false; + ui_set_status(state, "已更新变量 %s", name); +} + +static void ui_expression_calculate(struct ui_state *state) +{ + if (state->expression_text[0] == '\0') { + ui_set_status(state, "错误：请先输入表达式"); + return; + } + struct expression_error error; + if (!expression_eval(&state->expression, state->expression_text, + &state->expression_result, &error)) { + state->expression_result_valid = false; + ui_set_status(state, "错误：%s（位置 %zu）", + ui_expression_error_text(error.code), error.position); + return; + } + state->expression_result_valid = true; + ui_set_status(state, "计算完成"); +} + +static void ui_expression_action(struct ui_state *state, int choice) +{ + switch (choice) { + case 0: + ui_expression_input(state); + break; + case 1: + ui_expression_set_variable(state); + break; + case 2: + ui_expression_calculate(state); + break; + default: + break; + } +} + +static void ui_expression_page(struct ui_state *state) +{ + size_t selected = 0; + for (;;) { + ui_draw_expression(state, selected); + int choice = ui_menu_input(&selected, 3); + if (choice == -1) { + return; + } + if (choice >= 0) { + ui_expression_action(state, choice); + } + } +} + +static void ui_draw_main(const struct ui_state *state, size_t selected) +{ + static const char *const items[] = { + "线性表操作", + "向量运算", + "顺序表多项式", + "链表多项式", + "表达式计算", + }; + + (void)state; + tui_clear(); + printf(COLOR_CYAN); + ui_print_rule('='); + printf(STYLE_BOLD); + ui_print_centered("简单计算器", ui_terminal_width()); + printf(STYLE_RESET); + printf(COLOR_CYAN); + ui_print_rule('='); + printf(STYLE_RESET "\n"); + ui_print_menu(items, sizeof(items) / sizeof(items[0]), selected, "退出"); + ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q 退出"); + fflush(stdout); +} + +int ui_run(void) +{ + struct ui_state state; + + if (!ui_state_init(&state)) { + ui_state_destroy(&state); + fputs("初始化数据失败\n", stderr); + return 1; + } + if (!tui_init()) { + ui_state_destroy(&state); + fputs("无法初始化终端交互\n", stderr); + return 1; + } + + size_t selected = 0; + for (;;) { + ui_draw_main(&state, selected); + int choice = ui_menu_input(&selected, 5); + if (choice == -1) { + break; + } + switch (choice) { + case 0: + ui_linear_page(&state); + break; + case 1: + ui_vector_page(&state); + break; + case 2: + ui_poly_vec_page(&state); + break; + case 3: + ui_poly_list_page(&state); + break; + case 4: + ui_expression_page(&state); + break; + default: + break; + } + } + + tui_shutdown(); + ui_state_destroy(&state); + return 0; +} diff --git a/lab04/ui.h b/lab04/ui.h new file mode 100644 index 0000000..d7e2c9b --- /dev/null +++ b/lab04/ui.h @@ -0,0 +1,9 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +#ifndef UI_H +#define UI_H + +int ui_run(void); + +#endif /* LAB02_UI_H */ diff --git a/lab04/vec.h b/lab04/vec.h new file mode 100644 index 0000000..d62df76 --- /dev/null +++ b/lab04/vec.h @@ -0,0 +1,1183 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +/** + * @file vec.h + * @brief A dynamically sized contiguous sequence with byte-based storage. + * + * `struct vec` stores the element size rather than a type. The caller is + * responsible for using the type associated with the initialized element size. + */ +#ifndef VEC_H +#define VEC_H + +#include <stddef.h> +#include <stdbool.h> +#include <assert.h> +#include <stdlib.h> +#include <stdint.h> +#include <string.h> + +/** + * @brief A dynamically sized contiguous sequence. + * + * `data` points to storage for at most `capacity` elements. The first + * `size` positions contain valid elements. + */ +typedef struct vec { + void *data; + size_t size; + size_t capacity; + size_t elem_size; +} vec; + +/** + * @brief Compares two elements. + * + * @return A value less than, equal to, or greater than zero when the left + * element is less than, equal to, or greater than the right element. + */ +typedef int (*vec_compare_fn)(const void *lhs, const void *rhs); + +/** @name Initialization */ +/** @{ */ + +/** + * @brief Produces an initializer for an empty vector of the given element type. + * @param type The element type. + */ +#define VEC_INIT(type) { \ + .data = NULL, \ + .size = 0, \ + .capacity = 0, \ + .elem_size = sizeof(type), \ +} + +/** + * @brief Declares and initializes a vector for the given element type. + * @param name The vector variable name. + * @param type The element type. + */ +#define VEC(name, type) \ + struct vec name = VEC_INIT(type) + +/** + * @brief Initializes an existing vector. + * @param v A pointer to the vector. + * @param type The element type. + */ +#define vec_init(v, type) \ + (*(v) = (struct vec)VEC_INIT(type)) + +/** @} */ + +/** @name Basic properties */ +/** @{ */ + +/** @brief Returns the number of valid elements in the vector. */ +static inline size_t vec_size(const struct vec *v) +{ + return v->size; +} + +/** @brief Returns the current storage capacity of the vector. */ +static inline size_t vec_capacity(const struct vec *v) +{ + return v->capacity; +} + +/** @brief Returns the size of one element in bytes. */ +static inline size_t vec_elem_size(const struct vec *v) +{ + return v->elem_size; +} + +/** + * @brief Returns the maximum number of elements representable at this element size. + */ +static inline size_t vec_max_size(const struct vec *v) +{ + return SIZE_MAX / v->elem_size; +} + +/** @brief Tests whether the vector is empty. */ +static inline int vec_empty(const struct vec *v) +{ + return v->size == 0; +} + +/** @} */ + +/** @name Lifetime and capacity */ +/** @{ */ + +/** + * @brief Removes all valid elements from the vector. + * + * The operation does not release the allocated capacity. + */ +static inline void vec_clear(struct vec *v) +{ + v->size = 0; +} + +/** + * @brief Destroys the vector and releases its storage. + */ +static inline void vec_destroy(struct vec *v) +{ + free(v->data); + + v->data = NULL; + v->size = 0; + v->capacity = 0; + v->elem_size = 0; +} + +/** + * @brief Ensures that the vector has at least the requested capacity. + * @param v A pointer to the vector. + * @param capacity The minimum requested number of elements. + * @return `true` on success; `false` on overflow or allocation failure. + */ +static inline bool vec_reserve(struct vec *v, size_t capacity) +{ + if (!v || v->elem_size == 0) { + return false; + } + // 当前容量已满足需求，直接返回成功 + if (capacity <= v->capacity) { + return true; + } + // 乘法溢出检查 (capacity * elem_size > SIZE_MAX) + if (capacity > SIZE_MAX / v->elem_size) { + return false; + } + + size_t new_bytes = capacity * v->elem_size; + void *new_data = realloc(v->data, new_bytes); + if (!new_data) { + return false; // 分配失败，原 v->data 依然有效 + } + + v->data = new_data; + v->capacity = capacity; + return true; +} + +/** + * @brief Changes the number of valid elements in the vector. + * + * Elements added by growing the vector are uninitialized. + * + * @param v A pointer to the vector. + * @param size The new number of elements. + * @return `true` on success; `false` on allocation failure. + */ +static inline bool vec_resize(struct vec *v, size_t size) +{ + if (!v) { + return false; + } + + if (size > v->capacity) { + if (!vec_reserve(v, size)) { + return false; + } + } + v->size = size; + return true; +} + +/** + * @brief Changes the vector size and clears newly added bytes. + * + * Clearing bytes does not guarantee a type-specific zero value; it only + * guarantees that the corresponding storage bytes are zero. + */ +static inline bool vec_resize_zero(struct vec *v, size_t size) +{ + if (!v) { + return false; + } + size_t old_size = v->size; + + if (size > old_size) { + if (size > v->capacity) { + if (!vec_reserve(v, size)) { + return false; + } + } + /* 这里使用 memset 清零字节，不保证所有元素类型都得到 + * 该类型语义上的零值。 */ + char *start = (char *)v->data + (old_size * v->elem_size); + size_t zero_bytes = (size - old_size) * v->elem_size; + memset(start, 0, zero_bytes); + } + + v->size = size; + return true; +} + +/** + * @brief Attempts to reduce the capacity to the current size. + * @return `true` on success; `false` if reallocation fails. + */ +static inline bool vec_shrink_to_fit(struct vec *v) +{ + if (!v || v->elem_size == 0) { + return false; + } + // 已经完全贴合，无需缩容 + if (v->capacity == v->size) { + return true; + } + + // 当 size == 0 时，彻底归还堆内存 + if (v->size == 0) { + free(v->data); + v->data = NULL; + v->capacity = 0; + return true; + } + + // 缩容至刚好容纳 size 个元素 + size_t bytes = v->size * v->elem_size; + void *new_data = realloc(v->data, bytes); + if (!new_data) { + return false; // 极少数情况下缩容可能失败，保持原样 + } + + v->data = new_data; + v->capacity = v->size; + return true; +} + +/** @} */ + +/** @name Raw element access */ +/** @{ */ + +/** @brief Returns a writable pointer to the vector storage. */ +static inline void *vec_data(struct vec *v) +{ + return v->data; +} + +/** @brief Returns a read-only pointer to the vector storage. */ +static inline const void *vec_data_const(const struct vec *v) +{ + return v->data; +} + +/** + * @brief Tests two vectors for equality using a comparison function. + */ +static inline bool vec_equal(const struct vec *a, + const struct vec *b, + vec_compare_fn compare) +{ + if (a->elem_size != b->elem_size || a->size != b->size) { + return false; + } + + for (size_t i = 0; i < a->size; ++i) { + const void *lhs = (const unsigned char *)a->data + + i * a->elem_size; + const void *rhs = (const unsigned char *)b->data + + i * b->elem_size; + if (compare(lhs, rhs) != 0) { + return false; + } + } + return true; +} + +/** + * @brief Compares two vectors lexicographically. + * @return -1, 0, or 1 when the left vector is less than, equal to, or + * greater than the right vector. + */ +static inline int vec_compare(const struct vec *a, + const struct vec *b, + vec_compare_fn compare) +{ + size_t common_size = a->size < b->size ? a->size : b->size; + + for (size_t i = 0; i < common_size; ++i) { + const void *lhs = (const unsigned char *)a->data + + i * a->elem_size; + const void *rhs = (const unsigned char *)b->data + + i * b->elem_size; + int result = compare(lhs, rhs); + if (result < 0) { + return -1; + } + if (result > 0) { + return 1; + } + } + + if (a->size < b->size) { + return -1; + } + if (a->size > b->size) { + return 1; + } + return 0; +} + +/** + * @brief Returns a writable pointer to the element at `index`. + * @pre `index < v->size`. + */ +static inline void *vec_at(struct vec *v, size_t index) +{ + assert(index < v->size); + + return (unsigned char *)v->data + + index * v->elem_size; +} + +/** + * @brief Returns a read-only pointer to the element at `index`. + * @pre `index < v->size`. + */ +static inline const void *vec_at_const(const struct vec *v, + size_t index) +{ + assert(index < v->size); + + return (const unsigned char *)v->data + + index * v->elem_size; +} + +/** + * @brief Returns a writable pointer to the element at `index`, or `NULL` + * when `index` is out of range. + */ +static inline void *vec_at_checked(struct vec *v, size_t index) +{ + if (index >= v->size) { + return NULL; + } + + return (unsigned char *)v->data + + index * v->elem_size; +} + +/** + * @brief Returns a read-only pointer to the element at `index`, or `NULL` + * when `index` is out of range. + */ +static inline const void *vec_at_checked_const(const struct vec *v, + size_t index) +{ + if (index >= v->size) { + return NULL; + } + + return (const unsigned char *)v->data + + index * v->elem_size; +} + +/** + * @brief Returns a writable pointer to the first element. + * @pre The vector is not empty. + */ +static inline void *vec_front(struct vec *v) +{ + assert(v->size); + return v->data; +} + +/** + * @brief Returns a read-only pointer to the first element. + * @pre The vector is not empty. + */ +static inline const void *vec_front_const(const struct vec *v) +{ + assert(v->size); + return v->data; +} + +/** + * @brief Returns a writable pointer to the last element. + * @pre The vector is not empty. + */ +static inline void *vec_back(struct vec *v) +{ + assert(v->size); + return vec_at(v, v->size - 1); +} + +/** + * @brief Returns a read-only pointer to the last element. + * @pre The vector is not empty. + */ +static inline const void *vec_back_const(const struct vec *v) +{ + assert(v->size); + return vec_at_const(v, v->size - 1); +} + +/** @} */ + +/** @name Typed access macros */ +/** @{ */ + +/** @brief Converts the storage pointer to a writable pointer of `type`. */ +#define vec_data_as(v, type) \ + ((type *)vec_data(v)) + +/** @brief Converts the storage pointer to a read-only pointer of `type`. */ +#define vec_data_as_const(v, type) \ + ((const type *)vec_data_const(v)) + +/** @brief Accesses the writable element at `i` as `type`. */ +#define vec_at_as(v, type, i) \ + (*(type *)vec_at((v), (i))) + +/** @brief Accesses the read-only element at `i` as `type`. */ +#define vec_at_as_const(v, type, i) \ + (*(const type *)vec_at_const((v), (i))) + +/** @brief Accesses the first element as a writable `type`. */ +#define vec_front_as(v, type) \ + (*(type *)vec_front(v)) + +/** @brief Accesses the first element as a read-only `type`. */ +#define vec_front_as_const(v, type) \ + (*(const type *)vec_front_const(v)) + +/** @brief Accesses the last element as a writable `type`. */ +#define vec_back_as(v, type) \ + (*(type *)vec_back(v)) + +/** @brief Accesses the last element as a read-only `type`. */ +#define vec_back_as_const(v, type) \ + (*(const type *)vec_back_const(v)) + +/** @} */ + +/** @name Raw element insertion */ +/** @{ */ + +/* 内部辅助函数：按 2 倍几何级数扩容，确保至少容纳 needed 个元素 */ +static inline bool __vec_grow_to(struct vec *v, size_t needed) +{ + size_t max_elements = SIZE_MAX / v->elem_size; + if (needed > max_elements) { + return false; + } + if (needed <= v->capacity) { + return true; + } + // 初始默认给 8 个元素容量，之后每次翻倍 + size_t new_cap = v->capacity ? v->capacity : 8; + if (new_cap > max_elements) { + new_cap = max_elements; + } + while (new_cap < needed) { + // 防止翻倍超过最大元素数量 + if (new_cap > max_elements / 2) { + new_cap = max_elements; + break; + } + new_cap *= 2; + } + return vec_reserve(v, new_cap); +} + +/** + * @brief Reserves an uninitialized slot at the end of the vector. + * @return A pointer to the new slot, or `NULL` on failure. + */ +static inline void *vec_emplace_back(struct vec *v) +{ + if (!v || v->elem_size == 0) { + return NULL; + } + size_t max_elements = SIZE_MAX / v->elem_size; + if (v->size >= max_elements) { + return NULL; + } + size_t needed = v->size + 1; + /* Grow the storage when the current capacity is exhausted. */ + if (v->size >= v->capacity) { + if (!__vec_grow_to(v, needed)) { + return NULL; + } + } + void *slot = (char *)v->data + (v->size * v->elem_size); + v->size++; + return slot; +} + +static inline size_t __vec_source_index(const struct vec *v, + const void *elem) +{ + if (!v || !v->data || !elem || v->elem_size == 0) { + return SIZE_MAX; + } + + uintptr_t base = (uintptr_t)v->data; + uintptr_t address = (uintptr_t)elem; + if (address < base) { + return SIZE_MAX; + } + + uintptr_t offset = address - base; + if (offset % v->elem_size != 0) { + return SIZE_MAX; + } + + size_t index = (size_t)(offset / v->elem_size); + return index < v->size ? index : SIZE_MAX; +} + +/** + * @brief Appends one raw element to the vector. + * @param v A pointer to the vector. + * @param elem A pointer to the element to copy. + * @return `true` on success; `false` on invalid input or allocation failure. + */ +static inline bool vec_push_back(struct vec *v, + const void *elem) +{ + if (!elem) { + return false; + } + size_t source_index = __vec_source_index(v, elem); + void *slot = vec_emplace_back(v); + if (!slot) { + return false; + } + const void *source = source_index == SIZE_MAX + ? elem + : (const unsigned char *)v->data + + source_index * v->elem_size; + memcpy(slot, source, v->elem_size); + return true; +} + +/** + * @brief Reserves an uninitialized slot at `index`. + * @param v A pointer to the vector. + * @param index The insertion index in the range `[0, size]`. + * @return A pointer to the new slot, or `NULL` on failure. + */ +static inline void *vec_emplace(struct vec *v, + size_t index) +{ + if (!v || v->elem_size == 0 || index > v->size) { + return NULL; + } + size_t max_elements = SIZE_MAX / v->elem_size; + if (v->size >= max_elements) { + return NULL; + } + size_t needed = v->size + 1; + if (v->size >= v->capacity) { + if (!__vec_grow_to(v, needed)) { + return NULL; + } + } + char *slot = (char *)v->data + (index * v->elem_size); + + /* Shift the suffix when insertion is not at the end. */ + if (index < v->size) { + memmove(slot + v->elem_size, slot, (v->size - index) * v->elem_size); + } + + v->size++; + return (void *)slot; + +} + +/** + * @brief Inserts one raw element at `index`. + * @param v A pointer to the vector. + * @param index The insertion index in the range `[0, size]`. + * @param elem A pointer to the element to copy. + * @return `true` on success; `false` on invalid input or allocation failure. + */ +static inline bool vec_insert(struct vec *v, + size_t index, + const void *elem) +{ + if (!elem) { + return false; + } + size_t source_index = __vec_source_index(v, elem); + void *slot = vec_emplace(v, index); + if (!slot) { + return false; + } + if (source_index != SIZE_MAX && source_index >= index) { + source_index++; + } + const void *source = source_index == SIZE_MAX + ? elem + : (const unsigned char *)v->data + + source_index * v->elem_size; + memcpy(slot, source, v->elem_size); + return true; +} + +/** + * @brief Inserts a range of raw elements at `index`. + * + * The source range must not refer to the vector's storage. + * + * @param v A pointer to the vector. + * @param index The insertion index in the range `[0, size]`. + * @param src The source range. + * @param count The number of elements to insert. + * @return `true` on success; `false` on invalid input or allocation failure. + */ +static inline bool vec_insert_range(struct vec *v, + size_t index, + const void *src, + size_t count) +{ + /* 前置条件：src 不得指向当前 vector 的存储区， + * 这与 std::vector::insert(position, first, last) 一致。 */ + if (!v || v->elem_size == 0 || index > v->size) { + return false; + } + if (count == 0) { + return true; /* Inserting zero elements succeeds. */ + } + if (!src) { + return false; + } + /* Check for overflow in size + count. */ + if (count > SIZE_MAX - v->size) { + return false; + } + + size_t needed = v->size + count; + if (needed > v->capacity) { + if (!__vec_grow_to(v, needed)) { + return false; + } + } + + char *dest = (char *)v->data + (index * v->elem_size); + + /* Shift the suffix when insertion is not at the end. */ + if (index < v->size) { + memmove(dest + (count * v->elem_size), dest, (v->size - index) * v->elem_size); + } + + /* Copy the source range into the newly opened gap. */ + memcpy(dest, src, count * v->elem_size); + v->size += count; + return true; +} + +/** + * @brief Replaces the vector with `count` copies of one raw element. + * @param v A pointer to the vector. + * @param count The resulting number of elements. + * @param value A pointer to the value to copy. + * @return `true` on success; `false` on invalid input or allocation failure. + */ +static inline bool vec_assign_n(struct vec *v, + size_t count, + const void *value) +{ + if (!v || v->elem_size == 0) { + return false; + } + if (count == 0) { + v->size = 0; + return true; + } + if (!value || count > vec_max_size(v)) { + return false; + } + + size_t source_index = __vec_source_index(v, value); + if (count > v->capacity && !vec_reserve(v, count)) { + return false; + } + + const void *source = source_index == SIZE_MAX + ? value + : (const unsigned char *)v->data + + source_index * v->elem_size; + for (size_t i = 0; i < count; ++i) { + void *dest = (unsigned char *)v->data + i * v->elem_size; + memmove(dest, source, v->elem_size); + } + v->size = count; + return true; +} + +/** + * @brief Replaces the vector with a range of raw elements. + * + * The source range must not refer to the vector's storage. + * + * @param v A pointer to the vector. + * @param src The source range. + * @param count The number of elements to assign. + * @return `true` on success; `false` on invalid input or allocation failure. + */ +static inline bool vec_assign_range(struct vec *v, + const void *src, + size_t count) +{ + /* 前置条件：src 不得指向当前 vector 的存储区。 */ + if (!v || v->elem_size == 0) { + return false; + } + if (count == 0) { + v->size = 0; + return true; + } + if (!src || count > vec_max_size(v)) { + return false; + } + if (count > v->capacity && !vec_reserve(v, count)) { + return false; + } + + memmove(v->data, src, count * v->elem_size); + v->size = count; + return true; +} + +/** + * @brief Appends a range of raw elements to the vector. + * + * The source range must not refer to the vector's storage. + * + * @param v A pointer to the vector. + * @param src The source range. + * @param count The number of elements to append. + * @return `true` on success; `false` on invalid input or allocation failure. + */ +static inline bool vec_append(struct vec *v, + const void *src, + size_t count) +{ + /* The source must not refer to the vector's storage. */ + if (!v) { + return false; + } + /* Reuse vec_insert_range() at the current end position. */ + return vec_insert_range(v, v->size, src, count); +} + + +/** @} */ + +/** @name Value insertion wrappers */ +/** @{ */ + +/** @brief Appends a typed value after checking its size. */ +#define vec_push(v, value) ({ \ + typeof(value) __vec_tmp = (value); \ + assert(sizeof(__vec_tmp) == \ + (v)->elem_size); \ + vec_push_back((v), &__vec_tmp); \ +}) + +/** @brief Inserts a typed value after checking its size. */ +#define vec_insert_value(v, index, value) ({ \ + typeof(value) __vec_tmp = (value); \ + assert(sizeof(__vec_tmp) == \ + (v)->elem_size); \ + vec_insert((v), (index), &__vec_tmp); \ +}) + +/** @brief Reserves a typed slot at the end of the vector. */ +#define vec_emplace_back_as(v, type) \ + ((type *)vec_emplace_back(v)) + +/** @brief Reserves a typed slot at the specified index. */ +#define vec_emplace_as(v, type, index) \ + ((type *)vec_emplace((v), (index))) + + +/** @} */ + +/** @name Erasure */ +/** @{ */ + +/** @brief Removes the last element, if one exists. */ +static inline void vec_pop_back(struct vec *v) +{ + if (!v || v->size == 0) { + return; + } + v->size--; +} + +/** + * @brief Removes the last element and copies it to `out`. + * @return `true` on success; `false` when the vector is empty or `out` is null. + */ +static inline bool vec_pop_back_copy(struct vec *v, + void *out) +{ + if (!v || !out || v->size == 0) { + return false; + } + v->size--; + const char *last_elem = (const char *)v->data + (v->size * v->elem_size); + memcpy(out, last_elem, v->elem_size); + return true; +} + +/** + * @brief Removes up to `count` elements starting at `index`. + */ +static inline void vec_erase_n(struct vec *v, + size_t index, + size_t count) +{ + if (!v || index >= v->size || count == 0) { + return; + } + + /* Limit the count without allowing index + count to overflow. */ + if (count > v->size - index) { + count = v->size - index; + } + + size_t trailing_elems = v->size - (index + count); + if (trailing_elems > 0) { + char *dest = (char *)v->data + (index * v->elem_size); + const char *src = (const char *)v->data + ((index + count) * v->elem_size); + /* The source and destination overlap, so use memmove. */ + memmove(dest, src, trailing_elems * v->elem_size); + } + + v->size -= count; +} + +/** @brief Removes the element at `index`, if it exists. */ +static inline void vec_erase(struct vec *v, + size_t index) +{ + vec_erase_n(v, index, 1); +} + +/** + * @brief Removes the half-open range `[first, last)`. + * @return A pointer to the element now at `first`, or the end pointer. + */ +static inline void *vec_erase_range(struct vec *v, + size_t first, + size_t last) +{ + if (!v || first > last || last > v->size) { + return NULL; + } + + vec_erase_n(v, first, last - first); + if (first == v->size) { + if (!v->data) { + return NULL; + } + return (unsigned char *)v->data + v->size * v->elem_size; + } + return (unsigned char *)v->data + first * v->elem_size; +} + +/** @brief Exchanges the contents of two vectors. */ +static inline void vec_swap(struct vec *a, struct vec *b) +{ + struct vec tmp = *a; + *a = *b; + *b = tmp; +} + + +/** + * @brief Removes an element by replacing it with the last element. + * + * The order of the remaining elements is not preserved. + */ +static inline void vec_swap_erase(struct vec *v, + size_t index) +{ + if (!v || index >= v->size) { + return; + } + + size_t last_idx = v->size - 1; + /* Move the last element over the erased element when necessary. */ + if (index < last_idx) { + char *dest = (char *)v->data + (index * v->elem_size); + const char *src = (const char *)v->data + (last_idx * v->elem_size); + memcpy(dest, src, v->elem_size); + } + + v->size--; +} + +/** @} */ + +/** @name Forward iterators */ +/** @{ */ + +/** @brief Returns a writable iterator to the first element. */ +static inline void *vec_begin(struct vec *v) +{ + return v->data; +} + +/** @brief Returns a read-only iterator to the first element. */ +static inline const void *vec_cbegin(const struct vec *v) +{ + return v->data; +} + +/** @brief Returns a writable iterator past the last element. */ +static inline void *vec_end(struct vec *v) +{ + if (!v->data) + return NULL; + + return (unsigned char *)v->data + + v->size * v->elem_size; +} + +/** @brief Returns a read-only iterator past the last element. */ +static inline const void *vec_cend(const struct vec *v) +{ + if (!v->data) + return NULL; + + return (const unsigned char *)v->data + + v->size * v->elem_size; +} + +/** @brief Returns the first element as a typed writable iterator. */ +#define vec_begin_as(v, type) \ + ((type *)vec_begin(v)) + +/** @brief Returns the end as a typed writable iterator. */ +#define vec_end_as(v, type) \ + ((type *)vec_end(v)) + +/** @brief Returns the first element as a typed read-only iterator. */ +#define vec_cbegin_as(v, type) \ + ((const type *)vec_cbegin(v)) + +/** @brief Returns the end as a typed read-only iterator. */ +#define vec_cend_as(v, type) \ + ((const type *)vec_cend(v)) + + +/** @} */ + +/** @name Iterator helpers */ +/** @{ */ + +/** @brief Advances a pointer iterator by one element. */ +#define vec_iter_next(it) \ + (++(it)) + +/** @brief Moves a pointer iterator back by one element. */ +#define vec_iter_prev(it) \ + (--(it)) + +/** + * @brief Returns the distance between two pointer iterators. + * + * Equal iterators, including two null pointers, have distance zero. + */ +#define vec_iter_distance(first, last) ({ \ + __auto_type __vec_first = (first); \ + __auto_type __vec_last = (last); \ + __vec_first == __vec_last \ + ? 0 \ + : __vec_last - __vec_first; \ +}) + +/** + * @brief A reverse iterator over mutable vector storage. + */ +struct vec_reverse_iterator { + void *data; + size_t size; + size_t elem_size; + size_t offset; +}; + +/** + * @brief A reverse iterator over read-only vector storage. + */ +struct vec_const_reverse_iterator { + const void *data; + size_t size; + size_t elem_size; + size_t offset; +}; + +/** @brief Returns a reverse iterator to the last element. */ +static inline struct vec_reverse_iterator vec_rbegin(struct vec *v) +{ + return (struct vec_reverse_iterator){ + .data = v->data, + .size = v->size, + .elem_size = v->elem_size, + .offset = 0, + }; +} + +/** @brief Returns a reverse iterator past the first element. */ +static inline struct vec_reverse_iterator vec_rend(struct vec *v) +{ + return (struct vec_reverse_iterator){ + .data = v->data, + .size = v->size, + .elem_size = v->elem_size, + .offset = v->size, + }; +} + +/** @brief Returns a read-only reverse iterator to the last element. */ +static inline struct vec_const_reverse_iterator +vec_crbegin(const struct vec *v) +{ + return (struct vec_const_reverse_iterator){ + .data = v->data, + .size = v->size, + .elem_size = v->elem_size, + .offset = 0, + }; +} + +/** @brief Returns a read-only reverse iterator past the first element. */ +static inline struct vec_const_reverse_iterator +vec_crend(const struct vec *v) +{ + return (struct vec_const_reverse_iterator){ + .data = v->data, + .size = v->size, + .elem_size = v->elem_size, + .offset = v->size, + }; +} + +/** @brief Dereferences a mutable reverse iterator. */ +static inline void *vec_reverse_deref(struct vec_reverse_iterator it) +{ + return (unsigned char *)it.data + + (it.size - it.offset - 1) * it.elem_size; +} + +/** @brief Dereferences a read-only reverse iterator. */ +static inline const void * +vec_reverse_deref_const(struct vec_const_reverse_iterator it) +{ + return (const unsigned char *)it.data + + (it.size - it.offset - 1) * it.elem_size; +} + +/** @brief Advances a mutable reverse iterator. */ +static inline void vec_reverse_next(struct vec_reverse_iterator *it) +{ + ++it->offset; +} + +/** @brief Advances a read-only reverse iterator. */ +static inline void +vec_reverse_next_const(struct vec_const_reverse_iterator *it) +{ + ++it->offset; +} + +/** @brief Moves a mutable reverse iterator backwards. */ +static inline void vec_reverse_prev(struct vec_reverse_iterator *it) +{ + --it->offset; +} + +/** @brief Moves a read-only reverse iterator backwards. */ +static inline void +vec_reverse_prev_const(struct vec_const_reverse_iterator *it) +{ + --it->offset; +} + +/** @brief Compares two mutable reverse iterators. */ +static inline bool vec_reverse_equal(struct vec_reverse_iterator lhs, + struct vec_reverse_iterator rhs) +{ + return lhs.data == rhs.data && lhs.offset == rhs.offset; +} + +/** @brief Compares two read-only reverse iterators. */ +static inline bool +vec_reverse_equal_const(struct vec_const_reverse_iterator lhs, + struct vec_const_reverse_iterator rhs) +{ + return lhs.data == rhs.data && lhs.offset == rhs.offset; +} + +/** @brief Returns the distance between mutable reverse iterators. */ +static inline ptrdiff_t +vec_reverse_distance(struct vec_reverse_iterator first, + struct vec_reverse_iterator last) +{ + return (ptrdiff_t)last.offset - (ptrdiff_t)first.offset; +} + +/** @brief Returns the distance between read-only reverse iterators. */ +static inline ptrdiff_t +vec_reverse_distance_const(struct vec_const_reverse_iterator first, + struct vec_const_reverse_iterator last) +{ + return (ptrdiff_t)last.offset - (ptrdiff_t)first.offset; +} + + +/** @} */ + +/** @name Traversal */ +/** @{ */ + +/** + * @brief Iterates over mutable vector elements. + * + * Example: + * @code + * int *it; + * vec_for_each(it, &v, int) + * printf("%d\\n", *it); + * @endcode + */ + +#define vec_for_each(pos, v, type) \ + for ((pos) = vec_begin_as((v), type); \ + (pos) != vec_end_as((v), type); \ + ++(pos)) + +/** @brief Iterates over read-only vector elements. */ +#define vec_for_each_const(pos, v, type) \ + for ((pos) = vec_cbegin_as((v), type); \ + (pos) != vec_cend_as((v), type); \ + ++(pos)) + +/** + * @brief Iterates over vector indexes in ascending order. + */ + +#define vec_for_each_index(i, v) \ + for (size_t i = 0; i < (v)->size; ++i) + +/** @brief Iterates over vector indexes in descending order. */ +#define vec_for_each_index_reverse(i, v) \ + for (size_t i = (v)->size; i-- > 0; ) + +/** @} */ + +#endif /* VEC_H */ |