From 96ecf29e8be977f51f351308ef2c7c492bb829aa Mon Sep 17 00:00:00 2001 From: Ethan Werner Date: Tue, 9 Jun 2026 01:17:41 +0400 Subject: refactor --- include/stack.h | 213 +++++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 179 insertions(+), 34 deletions(-) (limited to 'include/stack.h') diff --git a/include/stack.h b/include/stack.h index 7e0f711..659b013 100644 --- a/include/stack.h +++ b/include/stack.h @@ -1,84 +1,229 @@ +// stack.h — Generic dynamic stack +// +// Thread safety: Not thread-safe. External synchronization required. +// Memory safety: Double-free and use-after-free protected via NULL reset. +// Empty stack: pop/peek on empty stack returns zero-initialized value. +// Use stack_pop_ok / stack_peek_ok for error detection. + #ifndef STACK_H #define STACK_H -#include "./type.h" -#include -#include -#include -#include -#include +/* USER-DEFINED (define before including): + * typedef stack_value_t; + */ + +#include "type.h" typedef struct stack { stack_value_t *data; - stack_value_t *head; - uint_t size; - uint_t capacity; + u64 size; + u64 capacity; } stack_t; void stack_init(stack_t *); -stack_t *stack_from_array(stack_value_t *, uint_t); -void stack_push(stack_t *, stack_value_t); +void stack_free(stack_t *); +void stack_from_array(stack_t *, stack_value_t *, u64); +int stack_push(stack_t *, stack_value_t); stack_value_t stack_pop(stack_t *); -stack_value_t stack_peek(stack_t *); +int stack_pop_ok(stack_t *, stack_value_t *); +stack_value_t stack_peek(const stack_t *); +int stack_peek_ok(const stack_t *, stack_value_t *); +int stack_empty(const stack_t *); +void stack_clear(stack_t *); #endif #ifdef STACK_IMPLEMENTATION +#ifndef STACK_IMPLEMENTED +#define STACK_IMPLEMENTED -const stack_value_t ZERO = 0; +#include +#include +#include + +static stack_value_t const ZERO = {0}; /* Requires stack_value_t to be an aggregate type. For scalar types (double, int, pointer), {0} zero-initializes the entire value. For struct types, C99 guarantees remaining members are zero-initialized. */ + +// stack_init() +// +// Initialize or reset a stack. If stack->capacity is 0, defaults to 16. +// Frees any existing data buffer before allocating new one. void stack_init(stack_t *stack) { + if (!stack) + return; + if (stack->data != NULL) { + free(stack->data); + stack->data = NULL; + } if (stack->capacity == 0) { stack->capacity = 16; } - + if (stack->capacity > SIZE_MAX / sizeof(stack_value_t)) { + stack->capacity = 0; + stack->size = 0; + stack->data = NULL; + return; + } stack->size = 0; stack->data = calloc(stack->capacity, sizeof(stack_value_t)); - stack->head = stack->data; + if (!stack->data) + stack->capacity = 0; } -stack_t *stack_from_array(stack_value_t *array, uint_t size) { - stack_t *stack = calloc(1, sizeof(stack_t)); - +// stack_from_array() +// +// Initialize a stack from an existing array. Allocates exact capacity. + +void stack_from_array(stack_t *stack, stack_value_t *array, u64 size) { + if (!stack || !array || size == 0) + return; + if (size > SIZE_MAX / sizeof(stack_value_t)) + return; + if (stack->data) + free(stack->data); stack->size = size; stack->capacity = size; - stack->data = calloc(size, sizeof(stack_value_t)); + stack->data = calloc((size_t)size, sizeof(stack_value_t)); + if (!stack->data) { + stack->size = 0; + stack->capacity = 0; + stack->data = NULL; + return; + } memcpy(stack->data, array, sizeof(stack_value_t) * size); - stack->head = stack->data; - - return stack; } -void stack_push(stack_t *stack, stack_value_t x) { +// stack_push() +// +// Push a value onto the stack. Automatically doubles capacity if full. +// +// return - 1 on success, 0 on failure + +int stack_push(stack_t *stack, stack_value_t x) { + if (!stack || !stack->data) + return 0; if (stack->size == stack->capacity) { + if (stack->capacity > UINT64_MAX / 2) + return 0; stack->capacity *= 2; - stack->data = realloc(stack->data, sizeof(stack_value_t) * stack->capacity); - stack->head = &(stack->data[stack->size - 1]); + if (stack->capacity > SIZE_MAX / sizeof(stack_value_t)) { + stack->capacity /= 2; + return 0; + } + void *tmp = realloc(stack->data, sizeof(stack_value_t) * stack->capacity); + if (!tmp) { + stack->capacity /= 2; + return 0; + } + stack->data = tmp; } - *stack->head = x; - stack->head++; + stack->data[stack->size] = x; stack->size++; + return 1; } +// stack_pop() +// +// Remove and return the top element. Returns zero-initialized value on +// empty stack — use stack_pop_ok for error detection. + stack_value_t stack_pop(stack_t *stack) { - if (stack->size == 0) { + if (!stack || !stack->data || stack->size == 0) { return ZERO; } - stack_value_t x = stack->head[-1]; stack->size--; - stack->head--; + stack_value_t x = stack->data[stack->size]; + stack->data[stack->size] = ZERO; return x; } -stack_value_t stack_peek(stack_t *stack) { - if (stack->size == 0) { +// stack_pop_ok() +// +// Same as stack_pop, but writes result to *out and returns status code. +// +// return - 1 on success, 0 on empty stack or invalid args + +int stack_pop_ok(stack_t *stack, stack_value_t *out) { + if (!stack || !stack->data || !out || stack->size == 0) { + return 0; + } + + stack->size--; + *out = stack->data[stack->size]; + stack->data[stack->size] = ZERO; + + return 1; +} + +// stack_peek() +// +// Return the top element without removing it. Returns zero on empty stack +// — use stack_peek_ok for error detection. + +stack_value_t stack_peek(const stack_t *stack) { + if (!stack || !stack->data || stack->size == 0) { return ZERO; } - return stack->head[-1]; + return stack->data[stack->size - 1]; +} + +// stack_peek_ok() +// +// Same as stack_peek, but writes result to *out and returns status code. +// +// return - 1 on success, 0 on empty stack or invalid args + +int stack_peek_ok(const stack_t *stack, stack_value_t *out) { + if (!stack || !stack->data || !out || stack->size == 0) { + return 0; + } + + *out = stack->data[stack->size - 1]; + return 1; +} + +// stack_empty() +// +// Check if the stack is empty. +// +// return - 1 if empty, 0 otherwise + +int stack_empty(const stack_t *stack) { + if (!stack) + return 1; + return stack->size == 0; +} + +// stack_clear() +// +// Reset the stack to empty, zeroing all allocated slots + +void stack_clear(stack_t *stack) { + if (!stack || !stack->data) + return; + if (stack->capacity > SIZE_MAX / sizeof(stack_value_t)) + return; + for (u64 i = 0; i < stack->capacity; i++) + stack->data[i] = ZERO; + stack->size = 0; +} + +// stack_free() +// +// Release the stack's data buffer and reset all fields + +void stack_free(stack_t *stack) { + if (stack) { + free(stack->data); + stack->data = NULL; + stack->size = 0; + stack->capacity = 0; + } } -#endif \ No newline at end of file +#endif /* STACK_IMPLEMENTED */ +#endif /* STACK_IMPLEMENTATION */ \ No newline at end of file -- cgit v1.3.1