1 files changed, 134 insertions, 0 deletions
diff --git a/list.h b/list.h
new file mode 100644
index 0000000..a2453b6
--- /dev/null
+++ b/list.h
@@ -0,0 +1,134 @@
+#ifndef ALGDS_LIST_H_
+#define ALGDS_LIST_H_
+
+#include <stdlib.h>
+
+#include "type_alias.h"
+
+
+#define LIST_DEF(T) \
+    struct T##List_node { \
+        T val; \
+        struct T##List_node *prev; \
+        struct T##List_node *next; \
+    }; \
+    typedef struct T##List_node T##ListNode; \
+    typedef T##ListNode *T##ListIter; \
+    typedef struct { \
+        T##ListNode *vhead; \
+        T##ListNode *vtail; \
+        size_t len; \
+    } T##List; \
+    void T##List_init(T##List *self); \
+    void T##List_free(T##List *self); \
+    void T##List_move(T##List *self); \
+    T##ListIter T##List_insert_before(T##List *self, T##ListIter iter, T val); \
+    T##ListIter T##List_insert_after(T##List *self, T##ListIter iter, T val); \
+    void T##List_remove(T##List *self, T##ListIter iter); \
+    T##ListIter T##List_begin(T##List *self); \
+    T##ListIter T##List_last(T##List *self); \
+    T##ListIter T##List_end(T##List *self); \
+    T##ListIter T##List_next(T##ListIter iter); \
+    T##ListIter T##List_prev(T##ListIter iter); \
+    size_t T##List_len(T##List *self); \
+    T##ListIter T##List_push_back(T##List *self, T val); \
+    T##ListIter T##List_push_front(T##List *self, T val); \
+    void T##List_pop_back(T##List *self); \
+    void T##List_pop_front(T##List *self); \
+
+LIST_DEF(Int);
+
+#define LIST_IMPL(T) \
+    void T##List_init(T##List *self) { \
+        self->vhead = malloc(sizeof(T##ListNode)); \
+        self->vtail = malloc(sizeof(T##ListNode)); \
+        self->vhead->next = self->vtail; \
+        self->vhead->prev = NULL; \
+        self->vtail->next = NULL; \
+        self->vtail->prev = self->vhead; \
+        self->len = 0; \
+    } \
+    void T##List_free(T##List *self) { \
+        T##ListIter cur = self->vhead; \
+        while (cur != NULL) { \
+            T##ListIter next = cur->next; \
+            free(cur); \
+            cur = next; \
+        } \
+    } \
+    void T##List_move(T##List *self) { \
+        T##List dup; \
+        dup.vhead = self->vhead; \
+        dup.vtail = self->vtail; \
+        dup.len = self->len; \
+        self->vhead = NULL; \
+        self->vtail = NULL; \
+        self->len = 0; \
+    } \
+    T##ListIter T##List_insert_before(T##List *self, T##ListIter iter, T val) { \
+        if (iter->prev == NULL) return NULL; \
+        T##ListIter newnode = malloc(sizeof(T##ListNode)); \
+        newnode->prev = iter->prev; \
+        newnode->next = iter; \
+        newnode->val = val; \
+        iter->prev->next = newnode; \
+        iter->prev = newnode; \
+        self->len++; \
+        return newnode; \
+    } \
+    T##ListIter T##List_insert_after(T##List *self, T##ListIter iter, T val) { \
+        if (iter->next == NULL) return NULL; \
+        T##ListIter newnode = malloc(sizeof(T##ListNode)); \
+        newnode->next = iter->next; \
+        newnode->prev= iter; \
+        newnode->val = val; \
+        iter->next->prev= newnode; \
+        iter->next = newnode; \
+        self->len++; \
+        return newnode; \
+    } \
+    void T##List_remove(T##List *self, T##ListIter iter) { \
+        if (iter->prev == NULL || iter->next == NULL) return; \
+        iter->prev->next = iter->next; \
+        iter->next->prev = iter->prev; \
+        free(iter); \
+        self->len--; \
+    } \
+    T##ListIter T##List_begin(T##List *self) { \
+        return self->vhead->next; \
+    } \
+    T##ListIter T##List_last(T##List *self) { \
+        if (self->vtail->prev == self->vhead) return NULL; \
+        return self->vtail->prev; \
+    } \
+    T##ListIter T##List_end(T##List *self) { \
+        return self->vtail; \
+    } \
+    T##ListIter T##List_next(T##ListIter iter) { \
+        if (iter == NULL) return NULL; \
+        return iter->next; \
+    } \
+    T##ListIter T##List_prev(T##ListIter iter) { \
+        if (iter == NULL) return NULL; \
+        if (iter->prev == NULL) return NULL; \
+        if (iter->prev->prev == NULL) return NULL; \
+        return iter->prev; \
+    } \
+    size_t T##List_len(T##List *self) { \
+        return self->len; \
+    } \
+    T##ListIter T##List_push_back(T##List *self, T val) { \
+        return T##List_insert_before(self, self->vtail, val); \
+    } \
+    T##ListIter T##List_push_front(T##List *self, T val) { \
+        return T##List_insert_after(self, self->vhead, val); \
+    } \
+    void T##List_pop_back(T##List *self) { \
+        T##List_remove(self, self->vtail->prev); \
+    } \
+    void T##List_pop_front(T##List *self) { \
+        T##List_remove(self, self->vhead->next); \
+    } \
+
+#endif
+