diff options
author | noodle <shawtynoodle@gmail.com> | 2023-07-10 15:40:08 +0300 |
---|---|---|
committer | noodle <shawtynoodle@gmail.com> | 2023-07-10 15:40:08 +0300 |
commit | b7ac144cd2d242791938b51569effb7a1378a332 (patch) | |
tree | 0db39dc6d72a96697707c662c32f4dcdb99372b7 /stack.c | |
parent | 35eacac40f265aad47bf25d10f3ecd3670b79b2f (diff) |
Add files
Diffstat (limited to 'stack.c')
-rw-r--r-- | stack.c | 179 |
1 files changed, 179 insertions, 0 deletions
@@ -0,0 +1,179 @@ +#include <assert.h> +#include <stdlib.h> // for malloc() and free() +#include "stack.h" + +/* node of a doubly-linked list */ +struct Node { + struct Node *next, *prev; + void *data; +}; + +/* + * stack implemented using a doubly-linked list to allow traversal from the top + * or the bottom + */ +struct Stack { + struct Node *top, *bottom; + size_t size; +}; + +/* node_new: create a new doubly-linked list node */ +static struct Node * +node_new(void) +{ + struct Node *node = malloc(sizeof *node); + if (node == NULL) { + return NULL; + } + node->next = node->prev = node->data = NULL; + return node; +} + +/* node_free: free a doubly-linked list node */ +static void +node_free(struct Node *node) +{ + assert(node != NULL); + free(node); +} + +/* stack_new: create a new empty stack */ +struct Stack * +stack_new(void) +{ + struct Stack *stack = malloc(sizeof *stack); + if (stack == NULL) { + return NULL; + } + stack->top = stack->bottom = NULL; + stack->size = 0; + return stack; +} + +/* + * stack_delete: free memory used by the stack and it's nodes. But don't free + * any data pointed to by the stack nodes + * good for stacks that don't store pointers to dynamically allocated buffers + */ +void +stack_delete(struct Stack *stack) +{ + assert(stack != NULL); + for (struct Node *node = stack->top, *next_node; + node != NULL; node = next_node) + { + next_node = node->next; + node_free(node); + } + free(stack); +} + +/* + * stack_free: free memory used by the stack, it's nodes, and the data stored + * inside each node + * good for stacks that store pointers to dynamically allocated buffers + */ +void +stack_free(struct Stack *stack, void (*free_data)(void *)) +{ + assert(stack != NULL); + assert(free_data != NULL); + + for (struct Node *node = stack->top, *next_node; + node != NULL; node = next_node) + { + next_node = node->next; + free_data(node->data); + node_free(node); + } + free(stack); +} + +/* push_stack: push a new node of value 'data' to top of 'stack' */ +void * +stack_push(struct Stack *stack, void *data) +{ + assert(stack != NULL); + assert(data != NULL); + + // create a new node with passed 'data' + struct Node *newtop; + if ((newtop = node_new()) == NULL) { + return NULL; + } + newtop->data = data; + + // push node to stack + if (stack->top == NULL) { + // first node in stack + stack->top = stack->bottom = newtop; + } else { + // link new top and old top + newtop->next = stack->top; + stack->top->prev = newtop; + // put new node at top of stack + stack->top = newtop; + } + stack->size++; + return newtop; +} + +/* stack_pop: pop data value of top node of 'stack' */ +void * +stack_pop(struct Stack *stack) +{ + assert(stack != NULL); + struct Node *oldtop = stack->top, + *newtop = stack->top->next; + void *data = oldtop->data; + + // remove reference to old top and free it + newtop->prev = NULL; + node_free(oldtop); + // set new stack top and size + stack->top = newtop; + stack->size--; + return data; +} + +/* stack_size: accessor for size of stack */ +size_t +stack_size(struct Stack *stack) +{ + assert(stack != NULL); + return stack->size; +} + +/* + * stack_iter: loop over 'stack' nodes from top to bottom, running 'apply' on + * each node + */ +void * +stack_iter(struct Stack *stack, void *(*apply)(void *)) +{ + assert(stack != NULL); + assert(apply != NULL); + for (struct Node *node = stack->top; node != NULL; node = node->next) { + if (apply(node->data) == NULL) { + return NULL; + } + } + return stack; +} + +/* + * stack_iter: loop over 'stack' nodes from bottom to top, running 'apply' on + * each node + */ +void * +stack_iter_reverse(struct Stack *stack, void *(*apply)(void *)) +{ + assert(stack != NULL); + assert(apply != NULL); + for (struct Node *node = stack->bottom; node != NULL; node = node->prev) { + if (apply(node->data) == NULL) { + return NULL; + } + } + return stack; +} |