Commits

Anonymous committed ab6c1c9

add templated stack/vector in stack.h

Comments (0)

Files changed (1)

+#include <stdlib.h>
+#include <assert.h>
+#include <sys/types.h>
+
+#define MAX(a,b) ((a) > (b) ? (a) : (b))
+#define MIN(a,b) ((a) < (b) ? (a) : (b))
+
+#define stack_def(Name, Type)                             \
+typedef struct Name##_ {                                  \
+    Type  *data;                                          \
+    size_t depth;                                         \
+    size_t size;                                          \
+    size_t min_size;                                      \
+    Type   *(*push  )(struct Name##_ *, Type  );          \
+    Type    (*pop   )(struct Name##_ *);                  \
+    ssize_t (*resize)(struct Name##_ *, size_t);          \
+} Name;                                                   \
+ssize_t Name##_resize(Name *s, size_t size)               \
+{                                                         \
+    Type *t = realloc(s->data, size * sizeof(Type));      \
+    if (size && !t)                                       \
+        return -1;                                        \
+    s->depth = MIN(s->depth, size);                       \
+    s->data  = t;                                         \
+    s->size  = size;                                      \
+    return size;                                          \
+}                                                         \
+Type *Name##_push(Name *s, Type m)                        \
+{                                                         \
+    if (s->depth == s->size)                              \
+        if (s->resize(s, MAX(s->size * 2, 1)) < 0)        \
+            return NULL;                                  \
+    s->data[s->depth] = m;                                \
+    return s->data + s->depth++;                          \
+}                                                         \
+Type Name##_pop(Name *s)                                  \
+{                                                         \
+    Type t;                                               \
+    assert(s->depth > 0);                                 \
+    t = s->data[--s->depth];                              \
+    if (s->depth <= s->size / 4 && s->size > s->min_size) \
+        s->resize(s, MAX(s->depth * 2, s->min_size));     \
+    return t;                                             \
+}                                                         \
+Name Name##_new(size_t min_size)                          \
+{                                                         \
+    Name t = { NULL, 0, 0, min_size,                      \
+               Name##_push, Name##_pop, Name##_resize };  \
+    t.resize(&t, min_size);                               \
+    return t;                                             \
+}