aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorErik Liodden <[email protected]>2017-11-05 15:49:40 +0100
committerErik Liodden <[email protected]>2017-11-15 15:59:55 +0100
commit1c8c71eac2abc91c582652156d1be0401dd3be17 (patch)
treec3deeb561d4b56363c31b4ffc36344632ed7d4aa
parentbc8c1f71b027bebafe98deddbdc7d2b98b12c253 (diff)
downloadalgdat-1c8c71eac2abc91c582652156d1be0401dd3be17.tar.gz
add basic stack functionality
generic stack. the stack_destroy funcion must be extended to free memory the elements points to.
-rw-r--r--include/list.h16
-rw-r--r--src/misc/list.c50
2 files changed, 66 insertions, 0 deletions
diff --git a/include/list.h b/include/list.h
index 2881f4c..a97b9b0 100644
--- a/include/list.h
+++ b/include/list.h
@@ -8,6 +8,22 @@
#ifndef LIST_H
#define LIST_H
+/****************************************************************************
+ * Stack *
+ ****************************************************************************/
+
+struct stack {
+ void *elems;
+ size_t elem_size;
+ int log_length;
+ int alloc_length;
+};
+
+void stack_init(struct stack *s, size_t elem_size);
+void stack_destroy(struct stack *s);
+void stack_push(struct stack *s, void *elem_addr);
+void stack_pop(struct stack *s, void *elem_addr);
+
/* linked lists */
struct llist {
struct llist_node *head;
diff --git a/src/misc/list.c b/src/misc/list.c
index 4164812..56f4ee2 100644
--- a/src/misc/list.c
+++ b/src/misc/list.c
@@ -7,8 +7,58 @@
#include <stdlib.h>
#include <stdio.h>
+#include <assert.h>
+#include <string.h>
#include "list.h"
+
+
+/****************************************************************************
+ * Stack *
+ ****************************************************************************/
+
+static void grow_stack(struct stack *s)
+{
+ s->alloc_length *= 2;
+ s->elems = realloc(s->elems, s->alloc_length * s->elem_size);
+ assert(s->elems != NULL);
+}
+
+void stack_init(struct stack *s, size_t elem_size)
+{
+ s->elem_size = elem_size;
+ s->log_length = 0;
+ s->alloc_length = 4;
+ s->elems = malloc(s->alloc_length * elem_size);
+ assert(s->elems != NULL);
+}
+
+void stack_destroy(struct stack *s)
+{
+ free(s);
+}
+
+void stack_push(struct stack *s, void *elem_addr)
+{
+ if (s->log_length == s->alloc_length)
+ grow_stack(s);
+ void *target = (char *)s->elems + (s->log_length * s->elem_size);
+ memcpy(target, elem_addr, s->elem_size);
+ s->log_length++;
+}
+
+void stack_pop(struct stack *s, void *elem_addr)
+{
+ assert(s->log_length > 0);
+ s->log_length--;
+ void *source = (char *)s->elems + (s->log_length * s->elem_size);
+ memcpy(elem_addr, source, s->elem_size);
+}
+
+
+
+
+
static struct llist_node *create_node(void *data)
{
struct llist_node *node = malloc(sizeof(*node));