Make the stack dynamic

3 files changed, 16 insertions, 7 deletions

diff --git a/map.c b/map.c
index f26d4b1..4303003 100644
--- a/map.c
+++ b/map.c
@@ -158,6 +158,7 @@ Map rbt_maze_map(size_t width, size_t height, unsigned int seed) {
     } while (ps_peek(ps).x != beginning_cell.x || ps_peek(ps).y != beginning_cell.y) ;
 
     visited_free(visited, height);
+    ps_free(ps);
     return map;
 }
 
diff --git a/stack.c b/stack.c
index d719cb3..8b4c478 100644
--- a/stack.c
+++ b/stack.c
@@ -6,12 +6,17 @@
 
 PositionStack ps_new(void) {
     PositionStack ps;
+    ps.capacity = STACK_INITIAL_CAPACITY;
+    ps.arr = malloc(sizeof(Position) * ps.capacity);
     ps.top = 0;
     return ps;
 }
 
 int ps_push(PositionStack *ps, Position pos) {
-    if (ps->top >= STACK_SIZE) return -1; /* FIXME: do a dynamic stack */
+    if (ps->top >= ps->capacity) {
+        ps->capacity *= STACK_SIZE_COEFFICIENT;
+        if ((ps->arr = realloc(ps->arr, sizeof(Position) * ps->capacity)) == NULL) return -1;
+    }
     ps->arr[ps->top] = pos;
     ps->top += 1;
     return 0;
@@ -28,3 +33,6 @@ Position ps_peek(PositionStack ps) {
     return ps.arr[ps.top - 1];
 }
 
+void ps_free(PositionStack ps) {
+    free(ps.arr);
+}
diff --git a/stack.h b/stack.h
index 68fdb78..2105c7c 100644
--- a/stack.h
+++ b/stack.h
@@ -4,20 +4,20 @@
 #include <stddef.h>
 #include "structs.h"
 
-/* So, the implementation of the stack is array-based, for hyperspeed.
- * For bigger maps we have to increase the STACK_SIZE, but it should
- * work fine most of the time. I guess */
-#define STACK_SIZE 4096
+#define STACK_INITIAL_CAPACITY 4096
+#define STACK_SIZE_COEFFICIENT 2
 
 struct PositionStack_s {
-    Position arr[STACK_SIZE]; /* The array with all the values */
+    Position *arr; /* The array with all the values */
+    size_t capacity;
     size_t top; /* Shows where the top of the stack is */
 };
 typedef struct PositionStack_s PositionStack;
 
 PositionStack ps_new(void); /* Returns an empty position stack */
-int ps_push(PositionStack *ps, Position pos); /* Returns -1 if overflow */
+int ps_push(PositionStack *ps, Position pos); /* Returns -1 if failed to realloc() */
 Position ps_pop(PositionStack *ps);
 Position ps_peek(PositionStack ps);
+void ps_free(PositionStack ps);
 
 #endif /* STACK_H_ */