summaryrefslogtreecommitdiff
path: root/stack.c
diff options
context:
space:
mode:
authornoodle <shawtynoodle@gmail.com>2023-07-10 15:40:08 +0300
committernoodle <shawtynoodle@gmail.com>2023-07-10 15:40:08 +0300
commitb7ac144cd2d242791938b51569effb7a1378a332 (patch)
tree0db39dc6d72a96697707c662c32f4dcdb99372b7 /stack.c
parent35eacac40f265aad47bf25d10f3ecd3670b79b2f (diff)
Add files
Diffstat (limited to 'stack.c')
-rw-r--r--stack.c179
1 files changed, 179 insertions, 0 deletions
diff --git a/stack.c b/stack.c
new file mode 100644
index 0000000..178ed6e
--- /dev/null
+++ b/stack.c
@@ -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;
+}