commit c0ba285bf6e3423d552463518ecfb8dbf77f3108
Author: mjkloeckner <martin.cachari@gmail.com>
Date: Sun, 29 Jan 2023 17:24:02 -0300
first insertion: generic stack data structure
Diffstat:
| A | Makefile | | | 20 | ++++++++++++++++++++ |
| A | main.c | | | 21 | +++++++++++++++++++++ |
| A | stack.c | | | 42 | ++++++++++++++++++++++++++++++++++++++++++ |
| A | stack.h | | | 22 | ++++++++++++++++++++++ |
4 files changed, 105 insertions(+), 0 deletions(-)
diff --git a/Makefile b/Makefile
@@ -0,0 +1,20 @@
+CC := gcc
+CFLAGS := -Wall -Wshadow -pedantic -ansi -std=c99 -O3
+SRCS := $(wildcard *.c)
+OBJS := $(SRCS:.c=.o)
+
+TARGET := main
+
+.PHONY: all clean
+
+all: $(TARGET)
+
+$(TARGET): $(OBJS)
+ $(CC) $(CLIBS) $(CFLAGS) -o $@ $^
+ rm -f $(OBJS)
+
+%.o: %.c
+ $(CC) $(CLIBS) $(CFLAGS) -c $< -o $@
+
+clean:
+ rm -f $(OBJS)
diff --git a/main.c b/main.c
@@ -0,0 +1,21 @@
+#include <stdio.h>
+
+#include "stack.h"
+
+int main (void) {
+ Stack *S;
+ int x;
+
+ stack_new(&S, sizeof(int));
+
+ for(size_t i = 0; i < 100; ++i)
+ stack_push(S, &i);
+
+ while(S->len) {
+ stack_pop(S, &x);
+ printf("%5d%s", x, S->len % 10 ? " " : "\n");
+ }
+
+ stack_destroy(S);
+ return 0;
+}
diff --git a/stack.c b/stack.c
@@ -0,0 +1,42 @@
+/* Stack implementation using a vector to store the elements */
+
+#include "stack.h"
+
+#include <stdio.h>
+#include <string.h>
+
+void stack_new(Stack **S, size_t mem_width) {
+ (*S) = malloc(sizeof(Stack));
+ (*S)->vector = malloc(sizeof(Stack *) * STACK_INITIAL_ALLOC);
+ (*S)->mem_width = mem_width;
+ (*S)->mem_alloc = STACK_INITIAL_ALLOC;
+ (*S)->len = 0;
+}
+
+/* generates a copy of the element an push it into stack
+ * does not check if elem is valid type */
+void stack_push(Stack *S, const void *elem) {
+ if(S->mem_alloc == S->len)
+ S->vector = realloc(S->vector,
+ (S->mem_alloc *= STACK_GROWTH_FACTOR) * sizeof(Stack *));
+
+ S->vector[S->len] = malloc(S->mem_width);
+ memcpy(S->vector[S->len++], elem, S->mem_width);
+}
+
+void stack_peek(const Stack *S, void *data) {
+ data = S->len ? S->vector[S->len - 1] : NULL;
+}
+
+void stack_pop(Stack *S, void *data) {
+ if(S->len) {
+ memcpy(data, S->vector[--S->len], S->mem_width);
+ free(S->vector[S->len]);
+ }
+}
+
+void stack_destroy(Stack *S) {
+ free(S->vector);
+ free(S);
+}
+
diff --git a/stack.h b/stack.h
@@ -0,0 +1,22 @@
+#ifndef STACK_H_
+#define STACK_H_
+
+#include <stdlib.h>
+
+#define STACK_INITIAL_ALLOC 10
+#define STACK_GROWTH_FACTOR 2
+
+typedef struct Stack Stack;
+
+struct Stack {
+ void **vector;
+ size_t len, mem_alloc, mem_width;
+};
+
+void stack_new(Stack **S, size_t mem_width);
+void stack_push(Stack *S, const void *elem);
+void stack_peek(const Stack *S, void *data);
+void stack_pop(Stack *S, void *data);
+void stack_destroy(Stack *S);
+
+#endif
