Merge branch 'christmas' into HEAD

7 files changed, 664 insertions, 104 deletions

diff --git a/include/shared/array_list.h b/include/shared/array_list.h
new file mode 100644
index 0000000..8b942ad
--- /dev/null
+++ b/include/shared/array_list.h
@@ -0,0 +1,105 @@
+#ifndef SHARED_ARRAY_LIST_H_
+#define SHARED_ARRAY_LIST_H_
+
+#include "kern/common.h"
+#include "kern/mem.h"
+
+#define ALLOC kalloc
+#define FREE kfree
+
+#define array_list_t(type) array_list_##type##_t
+#define array_list_new(type) array_list_##type##_new
+#define array_list_length(type) array_list_##type##_length
+#define array_list_reserve(type) array_list_##type##_reserve
+#define array_list_add(type) array_list_##type##_add
+#define array_list_remove(type) array_list_##type##remove
+#define array_list_ref(type) array_list_##type##_get
+#define array_list_free(type) array_list_##type##_free
+
+#define array_list_foreach(ar, val)            \
+  typeof((ar)->elements[0]) val;               \
+  if ((ar)->size > 0) val = (ar)->elements[0]; \
+  for (size_t _idx_ = 0; _idx_ < (ar)->size;   \
+       val = (++_idx_) >= (ar)->size ? val : (ar)->elements[_idx_])
+
+#define ARRAY_LIST_DECL(type)                                                \
+  typedef struct {                                                           \
+    size_t reserved;                                                         \
+    size_t size;                                                             \
+    type* elements;                                                          \
+  } array_list_t(type);                                                      \
+  size_t array_list_length(type)(const array_list_t(type)*);                 \
+  array_list_t(type) * array_list_new(type)();                               \
+  bool array_list_reserve(type)(array_list_t(type)*, size_t len);            \
+  bool array_list_add(type)(array_list_t(type)*, type val);                  \
+  bool array_list_remove(type)(array_list_t(type)*, size_t idx, type * out); \
+  type* array_list_ref(type)(array_list_t(type)*, size_t idx);               \
+  void array_list_free(type)(array_list_t(type)*);
+
+#define ARRAY_LIST_IMPL(type)                                            \
+  array_list_t(type) * array_list_new(type)()                            \
+  {                                                                      \
+    array_list_t(type)* ret = ALLOC(sizeof(array_list_t(type)));         \
+    ret->size = 0;                                                       \
+    ret->reserved = 0;                                                   \
+    ret->elements = NULL;                                                \
+    return ret;                                                          \
+  }                                                                      \
+  size_t array_list_length(type)(const array_list_t(type) * lst)         \
+  {                                                                      \
+    return lst->size;                                                    \
+  }                                                                      \
+  bool array_list_reserve(type)(array_list_t(type) * lst, size_t newlen) \
+  {                                                                      \
+    if (lst->reserved < newlen) {                                        \
+      type* new_arr = ALLOC(sizeof(type) * newlen);                      \
+      if (!new_arr) {                                                    \
+        return 0;                                                        \
+      }                                                                  \
+      for (size_t i = 0; i < lst->size; ++i) {                           \
+        new_arr[i] = lst->elements[i];                                   \
+      }                                                                  \
+      FREE(lst->elements);                                               \
+      lst->elements = new_arr;                                           \
+      lst->reserved = newlen;                                            \
+    }                                                                    \
+    return 1;                                                            \
+  }                                                                      \
+  bool array_list_add(type)(array_list_t(type) * lst, type v)            \
+  {                                                                      \
+    if (lst->size == lst->reserved) {                                    \
+      if (!array_list_reserve(type)(                                     \
+              lst, lst->reserved == 0 ? 4 : lst->reserved * 2)) {        \
+        return 0;                                                        \
+      }                                                                  \
+    }                                                                    \
+    lst->elements[lst->size++] = v;                                      \
+    return 1;                                                            \
+  }                                                                      \
+  bool array_list_remove(type)(                                          \
+      array_list_t(type) * lst, size_t idx, type * out)                  \
+  {                                                                      \
+    if (idx >= lst->size) {                                              \
+      return 0;                                                          \
+    }                                                                    \
+    if (out) *out = lst->elements[idx];                                  \
+    for (size_t i = idx; i < lst->size - 1; ++i) {                       \
+      lst->elements[i] = lst->elements[i + 1];                           \
+    }                                                                    \
+    lst->size--;                                                         \
+    return 1;                                                            \
+  }                                                                      \
+  type* array_list_ref(type)(array_list_t(type) * lst, size_t idx)       \
+  {                                                                      \
+    if (idx >= lst->size) {                                              \
+      return NULL;                                                       \
+    }                                                                    \
+    return &lst->elements[idx];                                          \
+  }                                                                      \
+  void array_list_free(type)(array_list_t(type) * lst)                   \
+  {                                                                      \
+    FREE(lst->elements);                                                 \
+    FREE(lst);                                                           \
+  }
+
+#endif /* SHARED_ARRAY_LIST_H_ */
diff --git a/include/shared/avl_tree.h b/include/shared/avl_tree.h
new file mode 100644
index 0000000..2b174d3
--- /dev/null
+++ b/include/shared/avl_tree.h
@@ -0,0 +1,270 @@
+#ifndef _SHARED_AVL_TREE_H_
+#define _SHARED_AVL_TREE_H_
+
+#define ALLOC kalloc
+#define FREE kfree
+
+#include <assert.h>
+#include <stdio.h>
+
+#include "kern/common.h"
+#include "kern/mem.h"
+#include "shared/stdmacro.h"
+
+#define get_height(n) ((n) == NULL ? 0 : (n)->height)
+#define max(a, b) ((a) < (b) ? (b) : (a))
+#define reset_height(node) \
+  (node)->height =         \
+      (max(get_height((node)->right), get_height((node)->left)) + 1)
+
+#define avl_tree_t(T) CONCAT(avl_tree__, T)
+#define avl_tree_node_t(T) CONCAT(avl_tree_node__, T)
+
+#define avl_tree_new(T) CONCAT(avl_tree_new__, T)
+#define avl_tree_free(T) CONCAT(avl_tree_free__, T)
+#define avl_tree_size(T) CONCAT(avl_tree_size__, T)
+#define avl_tree_insert(T) CONCAT(avl_tree_insert__, T)
+#define avl_tree_find(T) CONCAT(avl_tree_find__, T)
+#define avl_tree_erase(T) CONCAT(avl_tree_erase__, T)
+#define avl_tree_height(T) CONCAT(avl_tree_height__, T)
+
+#define null_dtor(a)
+
+#define AVL_TREE_DECL(T)                                    \
+  typedef struct CONCAT(AVL_TREE_NODE_, T) {                \
+    T value;                                                \
+    size_t height;                                          \
+    struct CONCAT(AVL_TREE_NODE_, T) * left;                \
+    struct CONCAT(AVL_TREE_NODE_, T) * right;               \
+  } avl_tree_node_t(T);                                     \
+                                                            \
+  typedef struct {                                          \
+    avl_tree_node_t(T) * root;                              \
+  } avl_tree_t(T);                                          \
+                                                            \
+  size_t avl_tree_height(T)(avl_tree_t(T) * tree);          \
+  avl_tree_t(T) * avl_tree_new(T)();                        \
+  void avl_tree_free(T)(avl_tree_t(T) * tree);              \
+  size_t avl_tree_size(T)(const avl_tree_t(T) * avl_tree);  \
+  T* avl_tree_insert(T)(avl_tree_t(T) * avl_tree, T value); \
+  T* avl_tree_find(T)(const avl_tree_t(T)*, T val);         \
+  bool avl_tree_erase(T)(avl_tree_t(T) * tree, T val, T * out);
+
+#define AVL_TREE_IMPL(T, CMP, DTOR)                                            \
+  avl_tree_t(T) * avl_tree_new(T)()                                            \
+  {                                                                            \
+    avl_tree_t(T)* ret = ALLOC(sizeof(avl_tree_t(T)));                         \
+    ret->root = NULL;                                                          \
+    return ret;                                                                \
+  }                                                                            \
+  static void CONCAT(avl_loose_free__, T)(avl_tree_node_t(T) * node)           \
+  {                                                                            \
+    if (!node) return;                                                         \
+    CONCAT(avl_loose_free__, T)(node->right);                                  \
+    CONCAT(avl_loose_free__, T)(node->left);                                   \
+    DTOR(node->value);                                                         \
+    FREE(node);                                                                \
+  }                                                                            \
+  void avl_tree_free(T)(avl_tree_t(T) * tree)                                  \
+  {                                                                            \
+    CONCAT(avl_loose_free__, T)(tree->root);                                   \
+    FREE(tree);                                                                \
+  }                                                                            \
+  static inline size_t CONCAT(                                                 \
+      loose_size__, T)(const avl_tree_node_t(T) * node)                        \
+  {                                                                            \
+    if (!node) return 0;                                                       \
+    return 1 + CONCAT(loose_size__, T)(node->left) +                           \
+           CONCAT(loose_size__, T)(node->right);                               \
+  }                                                                            \
+  size_t avl_tree_size(T)(const avl_tree_t(T) * tree)                          \
+  {                                                                            \
+    return CONCAT(loose_size__, T)(tree->root);                                \
+  }                                                                            \
+  static int CONCAT(balance_factor, T)(avl_tree_node_t(T) * node)              \
+  {                                                                            \
+    return get_height(node->left) - get_height(node->right);                   \
+  }                                                                            \
+  static avl_tree_node_t(T) * CONCAT(ll_rotate, T)(avl_tree_node_t(T) * node)  \
+  {                                                                            \
+    avl_tree_node_t(T)* child = node->left;                                    \
+    node->left = child->right;                                                 \
+    reset_height(node);                                                        \
+    child->right = node;                                                       \
+    reset_height(child);                                                       \
+    return child;                                                              \
+  }                                                                            \
+  static avl_tree_node_t(T) * CONCAT(rr_rotate, T)(avl_tree_node_t(T) * node)  \
+  {                                                                            \
+    avl_tree_node_t(T)* child = node->right;                                   \
+    node->right = child->left;                                                 \
+    reset_height(node);                                                        \
+    child->left = node;                                                        \
+    reset_height(child);                                                       \
+    return child;                                                              \
+  }                                                                            \
+  static avl_tree_node_t(T) * CONCAT(rl_rotate, T)(avl_tree_node_t(T) * node)  \
+  {                                                                            \
+    avl_tree_node_t(T)* child = node->right;                                   \
+    node->right = CONCAT(ll_rotate, T)(child);                                 \
+    reset_height(node);                                                        \
+    return CONCAT(rr_rotate, T)(node);                                         \
+  }                                                                            \
+  static avl_tree_node_t(T) * CONCAT(lr_rotate, T)(avl_tree_node_t(T) * node)  \
+  {                                                                            \
+    avl_tree_node_t(T)* child = node->left;                                    \
+    node->left = CONCAT(rr_rotate, T)(child);                                  \
+    reset_height(node);                                                        \
+    return CONCAT(ll_rotate, T)(node);                                         \
+  }                                                                            \
+  static avl_tree_node_t(T) *                                                  \
+      CONCAT(avl_tree_balance_, T)(avl_tree_node_t(T) * node)                  \
+  {                                                                            \
+    int d = CONCAT(balance_factor, T)(node);                                   \
+    if (d > 1) {                                                               \
+      if (CONCAT(balance_factor, T)(node->left) > 0) {                         \
+        return CONCAT(ll_rotate, T)(node);                                     \
+      } else {                                                                 \
+        return CONCAT(lr_rotate, T)(node);                                     \
+      }                                                                        \
+    } else if (d < -1) {                                                       \
+      if (CONCAT(balance_factor, T)(node->right) > 0) {                        \
+        return CONCAT(rl_rotate, T)(node);                                     \
+      } else {                                                                 \
+        return CONCAT(rr_rotate, T)(node);                                     \
+      }                                                                        \
+    }                                                                          \
+                                                                               \
+    return node;                                                               \
+  }                                                                            \
+  static avl_tree_node_t(T) *                                                  \
+      CONCAT(avl_tree_loose_insert_, T)(                                       \
+          avl_tree_node_t(T) * node, T value, T * *ptr_out)                    \
+  {                                                                            \
+    if (!node) {                                                               \
+      node = ALLOC(sizeof(avl_tree_node_t(T)));                                \
+      assert(node);                                                            \
+      node->left = NULL;                                                       \
+      node->right = NULL;                                                      \
+      node->value = value;                                                     \
+      node->height = 1;                                                        \
+      *ptr_out = &node->value;                                                 \
+    } else {                                                                   \
+      typeof(CMP(node->value, value)) cmp = CMP(node->value, value);           \
+      if (cmp < 0) {                                                           \
+        node->left =                                                           \
+            CONCAT(avl_tree_loose_insert_, T)(node->left, value, ptr_out);     \
+        reset_height(node);                                                    \
+        node = CONCAT(avl_tree_balance_, T)(node);                             \
+      } else if (cmp > 0) {                                                    \
+        node->right =                                                          \
+            CONCAT(avl_tree_loose_insert_, T)(node->right, value, ptr_out);    \
+        reset_height(node);                                                    \
+        node = CONCAT(avl_tree_balance_, T)(node);                             \
+      }                                                                        \
+    }                                                                          \
+    return node;                                                               \
+  }                                                                            \
+  T* avl_tree_insert(T)(avl_tree_t(T) * tree, T value)                         \
+  {                                                                            \
+    T* ret;                                                                    \
+    tree->root = CONCAT(avl_tree_loose_insert_, T)(tree->root, value, &ret);   \
+    return ret;                                                                \
+  }                                                                            \
+  size_t avl_tree_height(T)(avl_tree_t(T) * tree)                              \
+  {                                                                            \
+    if (!tree) return 0;                                                       \
+    return get_height(tree->root);                                             \
+  }                                                                            \
+  static T* CONCAT(loose_avl_tree_find, T)(avl_tree_node_t(T) * node, T value) \
+  {                                                                            \
+    if (!node) return NULL;                                                    \
+                                                                               \
+    typeof(CMP(node->value, value)) cmp = CMP(node->value, value);             \
+    if (cmp > 0) {                                                             \
+      return CONCAT(loose_avl_tree_find, T)(node->right, value);               \
+    } else if (cmp < 0) {                                                      \
+      return CONCAT(loose_avl_tree_find, T)(node->left, value);                \
+    }                                                                          \
+    return &node->value;                                                       \
+  }                                                                            \
+  T* avl_tree_find(T)(const avl_tree_t(T) * tree, T val)                       \
+  {                                                                            \
+    if (!tree) return NULL;                                                    \
+    return CONCAT(loose_avl_tree_find, T)(tree->root, val);                    \
+  }                                                                            \
+  static avl_tree_node_t(T) *                                                  \
+      CONCAT(pluck_left, T)(avl_tree_node_t(T) * node, T * into)               \
+  {                                                                            \
+    if (node->left) {                                                          \
+      node->left = CONCAT(pluck_left, T)(node->left, into);                    \
+      reset_height(node);                                                      \
+      return CONCAT(avl_tree_balance_, T)(node);                               \
+    } else {                                                                   \
+      *into = node->value;                                                     \
+      FREE(node);                                                              \
+      return node->right;                                                       \
+    }                                                                          \
+  }                                                                            \
+  static avl_tree_node_t(T) *                                                  \
+      CONCAT(pluck_right, T)(avl_tree_node_t(T) * node, T * into)              \
+  {                                                                            \
+    if (node->right) {                                                         \
+      node->right = CONCAT(pluck_right, T)(node->right, into);                 \
+      reset_height(node);                                                      \
+      return CONCAT(avl_tree_balance_, T)(node);                               \
+    } else {                                                                   \
+      *into = node->value;                                                     \
+      FREE(node);                                                              \
+      return node->left;                                                       \
+    }                                                                          \
+  }                                                                            \
+  avl_tree_node_t(T) *                                                         \
+      CONCAT(loose_avl_tree_erase, T)(                                         \
+          avl_tree_node_t(T) * node, T value, bool* out, T* erased)            \
+  {                                                                            \
+    if (!node) {                                                               \
+      *out = 0;                                                                \
+      return NULL;                                                             \
+    }                                                                          \
+    typeof(CMP(node->value, value)) cmp = CMP(node->value, value);             \
+    if (cmp == 0) {                                                            \
+      if (erased) *erased = node->value;                                       \
+      *out = 1;                                                                \
+      if (!node->right && !node->left) {                                       \
+        FREE(node);                                                            \
+        return NULL;                                                           \
+      }                                                                        \
+      if (get_height(node->right) > get_height(node->left)) {                  \
+        node->right = CONCAT(pluck_left, T)(node->right, &node->value);        \
+        reset_height(node);                                                    \
+        node = CONCAT(avl_tree_balance_, T)(node);                             \
+        return node;                                                           \
+      }                                                                        \
+      node->left = CONCAT(pluck_right, T)(node->left, &node->value);           \
+      reset_height(node);                                                      \
+      node = CONCAT(avl_tree_balance_, T)(node);                               \
+      return node;                                                             \
+    } else if (cmp < 0) {                                                      \
+      node->left =                                                             \
+          CONCAT(loose_avl_tree_erase, T)(node->left, value, out, erased);     \
+      reset_height(node);                                                      \
+      node = CONCAT(avl_tree_balance_, T)(node);                               \
+    } else {                                                                   \
+      node->right =                                                            \
+          CONCAT(loose_avl_tree_erase, T)(node->right, value, out, erased);    \
+      reset_height(node);                                                      \
+      node = CONCAT(avl_tree_balance_, T)(node);                               \
+    }                                                                          \
+    return node;                                                               \
+  }                                                                            \
+  bool avl_tree_erase(T)(avl_tree_t(T) * tree, T val, T * erased)              \
+  {                                                                            \
+    if (!tree) return 0;                                                       \
+    bool out;                                                                  \
+    tree->root =                                                               \
+        CONCAT(loose_avl_tree_erase, T)(tree->root, val, &out, erased);        \
+    return out;                                                                \
+  }
+
+#endif /* _SHARED_AVL_TREE_H_ */
diff --git a/include/shared/avl_tree.h.gch b/include/shared/avl_tree.h.gch
new file mode 100644
index 0000000..78fc043
--- /dev/null
+++ b/include/shared/avl_tree.h.gch
diff --git a/include/shared/linked_list.h b/include/shared/linked_list.h
index 3f8e075..ec72377 100644
--- a/include/shared/linked_list.h
+++ b/include/shared/linked_list.h
@@ -1,15 +1,21 @@
 #ifndef SHARED_LINKED_LIST_H_
 #define SHARED_LINKED_LIST_H_
 
-#define linked_list_t(type) linked_list_##type##_t
-#define linked_list_node_t(type) linked_list_node_##type##_t
-#define linked_list_push_back(type) linked_list_push_back_##type
-#define linked_list_push_front(type) linked_list_push_front_##type
-#define linked_list_pop_front(type) linked_list_pop_front_##type
-#define linked_list_pop_back(type) linked_list_pop_back_##type
-#define linked_list_front(type) linked_list_front_##type
-#define linked_list_back(type) linked_list_back_##type
-#define linked_list_length(type) linked_list_length_##type
+#include "kern/common.h"
+
+#define linked_list_t(T) linked_list___##T##___t
+#define linked_list_node_t(T) linked_list_node___##T##___t
+#define linked_list_itr_t(T) linked_list_node_itr___##T##___t
+#define linked_list_push_back(T) linked_list_push_back___##T
+#define linked_list_push_front(T) linked_list_push_front___##T
+#define linked_list_pop_front(T) linked_list_pop_front___##T
+#define linked_list_pop_back(T) linked_list_pop_back___##T
+#define linked_list_front(T) linked_list_front___##T
+#define linked_list_back(T) linked_list_back___##T
+#define linked_list_length(T) linked_list_length___##T
+#define linked_list_find_match(T) linked_list_find_match___##T
+#define linked_list_remove_first_match(T) linked_list_remove_first_match___##T
+#define linked_list_remove(T) linked_list_remove___##T
 
 #define LINKED_LIST_INIT \
   {                      \
@@ -24,108 +30,171 @@
 
 #define NO_ATTRIBUTE
 
-#define LINKED_LIST_DECL(type) LINKED_LIST_INTERNAL_DECL(type, NO_ATTRIBUTE)
+#define LINKED_LIST_DECL(T) LINKED_LIST_INTERNAL_DECL(T, NO_ATTRIBUTE)
 
-#define LINKED_LIST_STATIC_DECL(type) LINKED_LIST_INTERNAL_DECL(type, static)
+#define LINKED_LIST_STATIC_DECL(T) LINKED_LIST_INTERNAL_DECL(T, static inline)
 
-#define LINKED_LIST_INTERNAL_DECL(type, attr)                                  \
-  typedef struct LINKED_LIST_NODE_##type {                                     \
-    type value;                                                                \
-    struct LINKED_LIST_NODE_##type* next;                                      \
-  } linked_list_node_t(type);                                                  \
+#define LINKED_LIST_INTERNAL_DECL(T, attr)                                     \
+  typedef struct LINKED_LIST_NODE_##T {                                        \
+    T value;                                                                   \
+    struct LINKED_LIST_NODE_##T* next;                                         \
+  } linked_list_node_t(T);                                                     \
+                                                                               \
+  typedef struct {                                                             \
+    linked_list_node_t(T) * prev;                                              \
+    linked_list_node_t(T) * cur;                                               \
+  } linked_list_itr_t(T);                                                      \
                                                                                \
   typedef struct {                                                             \
-    linked_list_node_t(type) * head;                                           \
-  } linked_list_t(type);                                                       \
+    linked_list_node_t(T) * head;                                              \
+  } linked_list_t(T);                                                          \
                                                                                \
-  attr void linked_list_push_back(type)(linked_list_t(type) * ll, type value); \
-  attr void linked_list_push_front(type)(                                      \
-      linked_list_t(type) * ll, type value);                                   \
-  attr void linked_list_pop_back(type)(linked_list_t(type) * ll);              \
-  attr void linked_list_pop_front(type)(linked_list_t(type) * ll);             \
-  attr type* linked_list_front(type)(linked_list_t(type) * ll);                \
-  attr type* linked_list_back(type)(linked_list_t(type) * ll);
+  attr void linked_list_push_back(T)(linked_list_t(T) * ll, T value);          \
+  attr void linked_list_push_front(T)(linked_list_t(T) * ll, T value);         \
+  attr void linked_list_pop_back(T)(linked_list_t(T) * ll);                    \
+  attr void linked_list_pop_front(T)(linked_list_t(T) * ll);                   \
+  attr size_t linked_list_length(T)(const linked_list_t(T) * ll);              \
+  attr T* linked_list_front(T)(const linked_list_t(T) * ll);                   \
+  attr bool linked_list_find_match(T)(                                         \
+      const linked_list_t(T) * ll,                                             \
+      linked_list_itr_t(T) * itr_out,                                          \
+      bool (*match)(T, void*),                                                 \
+      void* closure);                                                          \
+  attr bool linked_list_remove_first_match(T)(                                 \
+      linked_list_t(T) * ll, T * out, bool (*match)(T, void*), void* closure); \
+  attr T* linked_list_back(T)(const linked_list_t(T) * ll);
 
-#define LINKED_LIST_IMPL(type) LINKED_LIST_INTERNAL_IMPL(type, NO_ATTRIBUTE)
+#define LINKED_LIST_IMPL(T) LINKED_LIST_INTERNAL_IMPL(T, NO_ATTRIBUTE)
 
-#define LINKED_LIST_STATIC_IMPL(type) LINKED_LIST_INTERNAL_IMPL(type, static)
+#define LINKED_LIST_STATIC_IMPL(T) LINKED_LIST_INTERNAL_IMPL(T, static inline)
 
-#define LINKED_LIST_INTERNAL_IMPL(type, attr)                                  \
-  attr void linked_list_push_back(type)(linked_list_t(type) * ll, type value)  \
-  {                                                                            \
-    if (!ll->head) {                                                           \
-      ll->head = kalloc(sizeof(linked_list_node_t(type)));                     \
-      ll->head->value = value;                                                 \
-      ll->head->next = NULL;                                                   \
-    } else {                                                                   \
-      linked_list_node_t(type)* c = ll->head;                                  \
-      while (c->next) c = c->next;                                             \
-      c->next = kalloc(sizeof(linked_list_node_t(type)));                      \
-      c->next->next = NULL;                                                    \
-      c->next->value = value;                                                  \
-    }                                                                          \
-  }                                                                            \
-  attr void linked_list_push_front(type)(linked_list_t(type) * ll, type value) \
-  {                                                                            \
-    if (!ll->head) {                                                           \
-      ll->head = kalloc(sizeof(linked_list_node_t(type)));                     \
-      ll->head->value = value;                                                 \
-      ll->head->next = NULL;                                                   \
-    } else {                                                                   \
-      linked_list_node_t(type)* node =                                         \
-          kalloc(sizeof(linked_list_node_t(type)));                            \
-      node->next = ll->head;                                                   \
-      node->value = value;                                                     \
-      ll->head = node;                                                         \
-    }                                                                          \
-  }                                                                            \
-  attr void linked_list_pop_back(type)(linked_list_t(type) * ll)               \
-  {                                                                            \
-    if (!ll->head) {                                                           \
-      return;                                                                  \
-    }                                                                          \
-    if (!ll->head->next) {                                                     \
-      kfree(ll->head);                                                         \
-      ll->head = NULL;                                                         \
-      return;                                                                  \
-    }                                                                          \
-    linked_list_node_t(type)* c = ll->head;                                    \
-    while (c->next->next) c = c->next;                                         \
-    kfree(c->next);                                                            \
-    c->next = NULL;                                                            \
-    return;                                                                    \
-  }                                                                            \
-  attr void linked_list_pop_front(type)(linked_list_t(type) * ll)              \
-  {                                                                            \
-    if (!ll->head) {                                                           \
-      return;                                                                  \
-    }                                                                          \
-    linked_list_node_t(type)* node = ll->head;                                 \
-    ll->head = node->next;                                                     \
-    kfree(node);                                                               \
-  }                                                                            \
-  attr type* linked_list_front(type)(linked_list_t(type) * ll)                 \
-  {                                                                            \
-    if (!ll->head) {                                                           \
-      return NULL;                                                             \
-    }                                                                          \
-    return &ll->head->value;                                                   \
-  }                                                                            \
-  attr type* linked_list_back(type)(linked_list_t(type) * ll)                  \
-  {                                                                            \
-    if (!ll->head) {                                                           \
-      return NULL;                                                             \
-    }                                                                          \
-    linked_list_node_t(type)* cur = ll->head;                                  \
-    while (cur->next) cur = cur->next;                                         \
-    return &cur->value;                                                        \
-  }                                                                            \
-  attr size_t linked_list_length(type)(linked_list_t(type) * ll)               \
-  {                                                                            \
-    linked_list_node_t(type) * cur;                                            \
-    size_t ret = 0;                                                            \
-    for (cur = ll->head; cur; cur = cur->next) ++ret;                          \
-    return ret;                                                                \
-  }
+#define PRAGMA(x) _Pragma(#x)
+#define LINKED_LIST_INTERNAL_IMPL(T, attr)                                    \
+  _Pragma("GCC diagnostic push")                                              \
+      _Pragma("GCC diagnostic ignored \"-Wunused-function\"")                 \
+          attr void linked_list_push_back(T)(linked_list_t(T) * ll, T value)  \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      ll->head = kalloc(sizeof(linked_list_node_t(T)));                       \
+      ll->head->value = value;                                                \
+      ll->head->next = NULL;                                                  \
+    } else {                                                                  \
+      linked_list_node_t(T)* c = ll->head;                                    \
+      while (c->next) c = c->next;                                            \
+      c->next = kalloc(sizeof(linked_list_node_t(T)));                        \
+      c->next->next = NULL;                                                   \
+      c->next->value = value;                                                 \
+    }                                                                         \
+  }                                                                           \
+  attr void linked_list_push_front(T)(linked_list_t(T) * ll, T value)         \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      ll->head = kalloc(sizeof(linked_list_node_t(T)));                       \
+      ll->head->value = value;                                                \
+      ll->head->next = NULL;                                                  \
+    } else {                                                                  \
+      linked_list_node_t(T)* node = kalloc(sizeof(linked_list_node_t(T)));    \
+      node->next = ll->head;                                                  \
+      node->value = value;                                                    \
+      ll->head = node;                                                        \
+    }                                                                         \
+  }                                                                           \
+  attr void linked_list_pop_back(T)(linked_list_t(T) * ll)                    \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      return;                                                                 \
+    }                                                                         \
+    if (!ll->head->next) {                                                    \
+      kfree(ll->head);                                                        \
+      ll->head = NULL;                                                        \
+      return;                                                                 \
+    }                                                                         \
+    linked_list_node_t(T)* c = ll->head;                                      \
+    while (c->next->next) c = c->next;                                        \
+    kfree(c->next);                                                           \
+    c->next = NULL;                                                           \
+    return;                                                                   \
+  }                                                                           \
+  attr void linked_list_pop_front(T)(linked_list_t(T) * ll)                   \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      return;                                                                 \
+    }                                                                         \
+    linked_list_node_t(T)* node = ll->head;                                   \
+    ll->head = node->next;                                                    \
+    kfree(node);                                                              \
+  }                                                                           \
+  attr T* linked_list_front(T)(const linked_list_t(T) * ll)                   \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      return NULL;                                                            \
+    }                                                                         \
+    return &ll->head->value;                                                  \
+  }                                                                           \
+  attr T* linked_list_back(T)(const linked_list_t(T) * ll)                    \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      return NULL;                                                            \
+    }                                                                         \
+    linked_list_node_t(T)* cur = ll->head;                                    \
+    while (cur->next) cur = cur->next;                                        \
+    return &cur->value;                                                       \
+  }                                                                           \
+  attr size_t linked_list_length(T)(const linked_list_t(T) * ll)              \
+  {                                                                           \
+    linked_list_node_t(T) * cur;                                              \
+    size_t ret = 0;                                                           \
+    for (cur = ll->head; cur; cur = cur->next) ++ret;                         \
+    return ret;                                                               \
+  }                                                                           \
+  attr bool linked_list_find_match(T)(                                        \
+      const linked_list_t(T) * ll,                                            \
+      linked_list_itr_t(T) * itr_out,                                         \
+      bool (*match)(T, void*),                                                \
+      void* closure)                                                          \
+  {                                                                           \
+    linked_list_node_t(T)* prev = NULL;                                       \
+    linked_list_node_t(T)* cur = NULL;                                        \
+    if (!ll || !ll->head) {                                                   \
+      return 0;                                                               \
+    }                                                                         \
+    for (cur = ll->head; cur != NULL; cur = (prev = cur)->next) {             \
+      if (match(cur->value, closure)) {                                       \
+        itr_out->prev = prev;                                                 \
+        itr_out->cur = cur;                                                   \
+        return 1;                                                             \
+      }                                                                       \
+    }                                                                         \
+    return 0;                                                                 \
+  }                                                                           \
+  attr bool linked_list_remove_first_match(T)(                                \
+      linked_list_t(T) * ll, T * out, bool (*match)(T, void*), void* closure) \
+  {                                                                           \
+    linked_list_itr_t(T) ctx;                                                 \
+    if (!linked_list_find_match(T)(ll, &ctx, match, closure)) {               \
+      return 0;                                                               \
+    }                                                                         \
+    if (out) *out = ctx.cur->value;                                           \
+    if (!ctx.prev) {                                                          \
+      ll->head = ctx.cur->next;                                               \
+    } else {                                                                  \
+      ctx.prev->next = ctx.cur->next;                                         \
+    }                                                                         \
+    kfree(ctx.cur);                                                           \
+    return 1;                                                                 \
+  }                                                                           \
+  int memcmp(const void* s1, const void* s2, size_t n);                       \
+  static inline bool linked_list___##T##___eq(T elem, void* other)            \
+  {                                                                           \
+    return memcmp(&elem, other, sizeof(T)) == 0;                              \
+  }                                                                           \
+  attr bool linked_list_remove(T)(linked_list_t(T) * ll, T val)               \
+  {                                                                           \
+    bool (*fn)(T, void*) = &linked_list___##T##___eq;                         \
+    bool ret = 0;                                                             \
+    while (linked_list_remove_first_match(T)(ll, NULL, fn, &val)) ret = 1;    \
+    return ret;                                                                 \
+  }                                                                           \
+  _Pragma("GCC diagnostic pop")
 
 #endif /* SHARED_LINKED_LIST_H_ */
diff --git a/include/shared/map.h b/include/shared/map.h
new file mode 100644
index 0000000..c9ee6b9
--- /dev/null
+++ b/include/shared/map.h
@@ -0,0 +1,90 @@
+#ifndef _SHARED_MAP_H_
+#define _SHARED_MAP_H_
+
+#include "shared/avl_tree.h"
+#include "shared/stdmacro.h"
+
+#define MAP_PASTE_KV(K, V) CONCAT(CONCAT(K, ___), V)
+#define map_entry_t(K, V) CONCAT(map_entry_t__, MAP_PASTE_KV(K, V))
+#define map_t(K, V) CONCAT(map_t__, MAP_PASTE_KV(K, V))
+
+#define map_new(K, V) CONCAT(map_new__, MAP_PASTE_KV(K, V))
+#define map_free(K, V) CONCAT(map_free__, MAP_PASTE_KV(K, V))
+#define map_put(K, V) CONCAT(map_put__, MAP_PASTE_KV(K, V))
+#define map_get(K, V) CONCAT(map_get__, MAP_PASTE_KV(K, V))
+#define map_erase(K, V) CONCAT(map_erase__, MAP_PASTE_KV(K, V))
+#define _map_compare_(K, V) CONCAT(_map_compare__, MAP_PASTE_KV(K, V))
+#define _map_dtor_(K, V) CONCAT(_map_dtor__, MAP_PASTE_KV(K, V))
+
+#define MAP_DECL(K, V)                                 \
+  typedef struct {                                     \
+    K key;                                             \
+    V value;                                           \
+  } map_entry_t(K, V);                                 \
+  AVL_TREE_DECL(map_entry_t(K, V));                    \
+  typedef struct {                                     \
+    avl_tree_t(map_entry_t(K, V)) * tree;              \
+  } map_t(K, V);                                       \
+  map_t(K, V) * map_new(K, V)();                       \
+  void map_free(K, V)(map_t(K, V) * map);              \
+  V* map_get(K, V)(map_t(K, V) * map, K key);          \
+  V* map_put(K, V)(map_t(K, V) * map, K key, V value); \
+  bool map_erase(K, V)(map_t(K, V) * map, K key, V * out);
+
+#define MAP_IMPL(K, V, CMP, DTOR)                                              \
+  static inline int _map_compare_(K, V)(                                       \
+      map_entry_t(K, V) e1, map_entry_t(K, V) e2)                              \
+  {                                                                            \
+    return CMP(e1.key, e2.key);                                                \
+  }                                                                            \
+  static inline void _map_dtor_(K, V)(map_entry_t(K, V) e1)                    \
+  {                                                                            \
+    DTOR(e1.value);                                                            \
+  }                                                                            \
+  AVL_TREE_IMPL(map_entry_t(K, V), _map_compare_(K, V), _map_dtor_(K, V))      \
+  map_t(K, V) * map_new(K, V)()                                                \
+  {                                                                            \
+    map_t(K, V)* ret = ALLOC(sizeof(map_t(K, V)));                             \
+    ret->tree = avl_tree_new(map_entry_t(K, V))();                             \
+    return ret;                                                                \
+  }                                                                            \
+  void map_free(K, V)(map_t(K, V) * map) { \
+    avl_tree_free(map_entry_t(K, V))(map->tree); \
+    FREE(map); \
+  }\
+  V* map_get(K, V)(map_t(K, V) * map, K key)                                   \
+  {                                                                            \
+    map_entry_t(K, V) key_;                                                    \
+    key_.key = key;                                                            \
+    map_entry_t(K, V)* entry =                                                 \
+        avl_tree_find(map_entry_t(K, V))(map->tree, key_);                     \
+                                                                               \
+    if (!entry) {                                                              \
+      return NULL;                                                             \
+    }                                                                          \
+                                                                               \
+    return &entry->value;                                                      \
+  }                                                                            \
+  V* map_put(K, V)(map_t(K, V) * map, K key, V val)                            \
+  {                                                                            \
+    map_entry_t(K, V) entry;                                                   \
+    entry.key = key;                                                           \
+    entry.value = val;                                                         \
+    map_entry_t(K, V)* ref =                                                   \
+        avl_tree_insert(map_entry_t(K, V))(map->tree, entry);                  \
+    return &ref->value;                                                        \
+  }                                                                            \
+  bool map_erase(K, V)(map_t(K, V) * map, K key, V * out)                      \
+  {                                                                            \
+    map_entry_t(K, V) key_;                                                    \
+    key_.key = key;                                                            \
+                                                                               \
+    map_entry_t(K, V) entry_out;                                               \
+    bool ret = avl_tree_erase(map_entry_t(K, V))(map->tree, key_, &entry_out); \
+    if (ret) {                                                                 \
+      *out = entry_out.value;                                                  \
+    }                                                                          \
+    return ret;                                                                \
+  }
+
+#endif /* _SHARED_MAP_H_ */
diff --git a/include/shared/math.h b/include/shared/math.h
new file mode 100644
index 0000000..6aec0e7
--- /dev/null
+++ b/include/shared/math.h
@@ -0,0 +1,19 @@
+#ifndef _SHARED_MATH_H_
+#define _SHARED_MATH_H_
+
+#include "kern/common.h"
+
+/* Returns round(sin(2πn / 256) * 127.5 + 127.5). */
+uint8_t byte_sin(uint8_t n);
+
+static inline uint8_t byte_scale(uint8_t n, uint8_t sc) {
+  return n * sc / 255;
+}
+
+#define min(a, b) (a) < (b) ? (a) : (b)
+#define max(a, b) (a) > (b) ? (a) : (b)
+
+/* returns (in / 256)^n * 256. */
+uint8_t amp(uint8_t in, uint8_t n);
+
+#endif /* _SHARED_MATH_H_ */
diff --git a/include/shared/stdmacro.h b/include/shared/stdmacro.h
new file mode 100644
index 0000000..6010982
--- /dev/null
+++ b/include/shared/stdmacro.h
@@ -0,0 +1,7 @@
+#ifndef _SHARED_STDMACRO_H_
+#define _SHARED_STDMACRO_H_
+
+#define CONCAT_(a, b) a ## b
+#define CONCAT(a, b) CONCAT_(a, b)
+
+#endif /* _SHARED_STDMACRO_H_ */