1. Evan Gates
  2. tidbits

Commits

Evan Gates  committed af930d5

add circular doubly linked list in list.h, mv stack -> vector and update

  • Participants
  • Parent commits ab6c1c9
  • Branches master

Comments (0)

Files changed (2)

File types/list.h

View file
  • Ignore whitespace
+#ifndef LIST_H_
+#define LIST_H_
+
+/*
+ * NOTES
+ * Circular doubly linked list.
+ * Insert and append add before and after the given node respectively. This has
+ * the consequence that insert and append on a head will append and insert on
+ * the list as a whole, respectively.
+ */
+#define list_def(Name, Type)         \
+typedef struct Name_ Name;           \
+struct Name_{                        \
+    Type  data;                      \
+    Name *next;                      \
+    Name *prev;                      \
+};                                   \
+Name *Name##_new(Type t)             \
+{                                    \
+    Name *n = malloc(sizeof(Name));  \
+    if (!n)                          \
+        return NULL;                 \
+    n->data = t;                     \
+    n->next = n->prev = n;           \
+    return n;                        \
+}                                    \
+void Name##_del(Name *l)             \
+{                                    \
+    if (!l)                          \
+        return;                      \
+    l->next->prev = l->prev;         \
+    l->prev->next = l->next;         \
+    free(l);                         \
+}                                    \
+void Name##_del_all(Name *l)         \
+{                                    \
+    Name *p = l->next;               \
+    if (!l)                          \
+        return;                      \
+    while (p != l) {                 \
+        p = p->next;                 \
+        free(p->prev);               \
+    }                                \
+    free(p);                         \
+}                                    \
+Name *Name##_append(Name *l, Type t) \
+{                                    \
+    Name *n;                         \
+    if (!l || !(n = Name##_new(t)))  \
+        return NULL;                 \
+    n->prev = l;                     \
+    n->next = l->next;               \
+    l->next = n;                     \
+    n->next->prev = n;               \
+    return n;                        \
+}                                    \
+Name *Name##_insert(Name *l, Type t) \
+{                                    \
+    Name *n;                         \
+    if (!l || !(n = Name##_new(t)))  \
+        return NULL;                 \
+    n->next = l;                     \
+    n->prev = l->prev;               \
+    l->prev = n;                     \
+    n->prev->next = n;               \
+    return n;                        \
+}
+
+#endif

File types/vector.h

View file
  • Ignore whitespace
+#ifndef VECTOR_H_
+#define VECTOR_H_
+
+#include <stdlib.h>
+#include <assert.h>
+#include <sys/types.h>
+
+size_t size_t_min(size_t a, size_t b) { return a < b ? a : b; }
+size_t size_t_max(size_t a, size_t b) { return a > b ? a : b; }
+
+#define vector_def(Name, Type)                                       \
+typedef struct {                                                     \
+    Type  *data;                                                     \
+    size_t size;                                                     \
+    size_t capacity;                                                 \
+    size_t min_capacity;                                             \
+} Name;                                                              \
+ssize_t Name##_resize(Name *v, size_t capacity)                      \
+{                                                                    \
+    Type *t = realloc(v->data, capacity * sizeof(Type));             \
+    if (capacity && !t)                                              \
+        return -1;                                                   \
+    v->size     = size_t_min(v->size, capacity);                     \
+    v->data     = t;                                                 \
+    v->capacity = capacity;                                          \
+    return capacity;                                                 \
+}                                                                    \
+Type *Name##_push(Name *v, Type m)                                   \
+{                                                                    \
+    if (v->size == v->capacity)                                      \
+        if (Name##_resize(v, size_t_max(v->capacity * 2, 1)) < 0)    \
+            return NULL;                                             \
+    v->data[v->size] = m;                                            \
+    return v->data + v->size++;                                      \
+}                                                                    \
+Type Name##_pop(Name *v)                                             \
+{                                                                    \
+    Type t;                                                          \
+    assert(v->size > 0);                                             \
+    t = v->data[--v->size];                                          \
+    if (v->size <= v->capacity / 4 && v->capacity > v->min_capacity) \
+        Name##_resize(v, size_t_max(v->size * 2, v->min_capacity));  \
+    return t;                                                        \
+}                                                                    \
+Name *Name##_new(size_t min_capacity)                                \
+{                                                                    \
+    Name *t = malloc(sizeof(Name));                                  \
+    if (!t)                                                          \
+        return NULL;                                                 \
+    *t = (Name){ NULL, 0, 0, min_capacity };                         \
+    Name##_resize(t, min_capacity);                                  \
+    return t;                                                        \
+}                                                                    \
+void Name##_del(Name *v)                                             \
+{                                                                    \
+    free(v->data);                                                   \
+    free(v);                                                         \
+}
+
+#endif