first commit

20 files changed, 1619 insertions, 0 deletions

diff --git a/lib/README.md b/lib/README.md
new file mode 100644
index 0000000..7c4c97b
--- /dev/null
+++ b/lib/README.md
@@ -0,0 +1,4 @@
+# stdlib for sll
+
+Use the [scrubs](https://nathanreiner.xyz/git/scrubs) tool to read its
+documentation.
diff --git a/lib/avl_tree/avl_tree.c b/lib/avl_tree/avl_tree.c
new file mode 100644
index 0000000..db3e44e
--- /dev/null
+++ b/lib/avl_tree/avl_tree.c
@@ -0,0 +1,463 @@
+#include "avl_tree.h"
+#include "../malloc/malloc.h"
+
+avl_tree_node_t *__new_avl_tree_node(avl_tree_node_t *parent, void *value);
+void            __free_avl_tree_node(avl_tree_t *tree, avl_tree_node_t *node);
+void            __avl_tree_rebalance(avl_tree_node_t *node);
+
+/** DOC
+ * @type function
+ * @name new_avl_tree
+ *
+ * @param  u8(*compare)(void*, void*)
+ * @return avl_tree_t*
+ *
+ * @description
+ * Creates a new empty AVL-Tree.
+ */
+avl_tree_t *new_avl_tree(i8(*compare)(void*, void*), u8 free_value)
+{
+	avl_tree_t *tree = malloc(sizeof(avl_tree_t));
+	tree->root = 0;
+	tree->size = 0;
+	tree->compare = compare;
+	tree->free_value = free_value;
+	
+	return tree;
+}
+
+
+/** DOC
+ * @type function
+ * @name free_avl_tree
+ *
+ * @param avl_tree_t *tree
+ *
+ * @description
+ * Frees a given `avl_tree_t`.
+ */
+void free_avl_tree(avl_tree_t *tree)
+{
+	if (tree->root)
+		__free_avl_tree_node(tree, tree->root);
+	
+	free(tree);
+}
+
+
+/** DOC
+ * @type function
+ * @name avl_tree_search
+ *
+ * @param  avl_tree_t *tree
+ * @param  void       *value
+ * @return void*
+ *
+ * @description
+ * Searches the value returns it when found.
+ * Returns `0` if node was not found.
+ */
+void *avl_tree_search(avl_tree_t *tree, void *value)
+{
+	if (!tree->root)
+		return 0;
+
+	avl_tree_node_t *current = tree->root;
+	u8 factor = tree->compare(current->value, value);
+
+	while (current->left || current->right) {
+		factor = tree->compare(current->value, value);
+
+		switch (factor) {
+			case (u8)1: current = current->right; break;
+			case (u8)0: return current->value; break;
+			case (u8)-1: current = current->left; break;
+		}
+	}
+
+	factor = tree->compare(current->value, value);
+	if (!factor)
+		return current->value;
+
+	return 0;
+}
+
+
+/** DOC
+ * @type function
+ * @name avl_tree_insert
+ *
+ * @param avl_tree_t *tree
+ * @param void       *value
+ *
+ * @description
+ * Inserts `value` into `tree`.
+ * If `value` is equal to a node according to `tree->compare`
+ * the `value` of the node is overwritten by `value`.
+ */
+void avl_tree_insert(avl_tree_t *tree, void *value)
+{
+	avl_tree_node_t *current = tree->root;
+	avl_tree_node_t *last    = current;
+	u8 factor                = 0;
+
+	if (current)
+		factor = tree->compare(current->value, value);
+
+	while (current && (current->left || current->right)) {
+		factor = tree->compare(current->value, value);
+		current->balance_factor += factor;
+		last = current;
+
+		switch (factor) {
+			case (u8)1:  current = current->right;            break;
+			case (u8)0:
+			             free(current->value);
+			             current->value = value;
+			             current = 0;
+			             break;
+			case (u8)-1: current = current->left;             break;
+		}
+	}
+
+	if (factor) {
+		++tree->size;
+		current = __new_avl_tree_node(last, value);
+
+		switch (factor) {
+			case (u8)1:  last->right = current; break;
+			case (u8)-1: last->left  = current; break;
+		}
+	} else if (!last) {
+		++tree->size;
+		current = __new_avl_tree_node(0, value);
+		tree->root = current;
+	}
+
+	if (factor || !last)
+		__avl_tree_rebalance(current);
+	else {
+			while (current->parent) {
+				current = current->parent;
+				current->balance_factor -= tree->compare(current->value, value);
+			}
+		}
+}
+
+
+/* DOC
+ * @type function
+ * @name avl_tree_remove
+ *
+ * @param avl_tree_t *tree
+ * @param void       *value
+ *
+ * @description
+ * Removes `value` from tree if exists.
+ */
+void avl_tree_remove(avl_tree_t *tree, void *value)
+{
+	avl_tree_node_t *current = tree->root;
+	avl_tree_node_t *last    = current;
+	u8 factor                = 0;
+
+	if (current)
+		factor = tree->compare(current->value, value);
+
+	while (current && (current->left || current->right)) {
+		factor = tree->compare(current->value, value);
+		current->balance_factor -= factor;
+		last = current;
+
+		switch (factor) {
+			case (u8)1:  current = current->right; break;
+			case (u8)0:  current = 0;   break;
+			case (u8)-1: current = current->left;  break;
+		}
+	}
+
+	if (!factor) {
+		--tree->size;
+		
+		avl_tree_node_t *next;
+		avl_tree_node_t *parent;
+
+		if (last->right) {
+			next = last->right;
+
+			while (next->left)
+				next = next->left;
+
+			next->parent->left = next->right;
+			if (next->right)
+				next->right->parent = next->parent;
+
+			next->left = last->left;
+			if (last->left)
+				last->left->parent = next;
+
+		} else if (last->left) {
+			next = last->left;
+
+			while (next->right)
+				next = next->right;
+
+			next->parent->right = next->left;
+			if (next->left)
+				next->left->parent = next->parent;
+
+			next->right = last->right;
+			if (last->right)
+				last->right->parent = next;
+		}
+
+		next->parent = last->parent;
+
+		if (last->parent) {
+			if (last->parent->left == last)
+				last->parent->left = next;
+			else
+				last->parent->right = next;
+		}
+
+		last->right = 0;
+		last->left = 0;
+
+		__free_avl_tree_node(tree, last);
+
+		__avl_tree_rebalance(parent);
+	} else {
+		while (current->parent) {
+			current = current->parent;
+			current->balance_factor += tree->compare(current->value, value);
+		}
+	}
+}
+
+
+/** DOC
+ * @type function
+ * @name __new_avl_tree_node
+ *
+ * @param  avl_tree_node_t *parent
+ * @param  void            *value
+ * @return avl_tree_node_t*
+ *
+ * @description
+ * Creates a new `avl_tree_node_t`
+ */
+avl_tree_node_t *__new_avl_tree_node(avl_tree_node_t *parent, void *value)
+{
+	avl_tree_node_t *node = malloc(sizeof(avl_tree_node_t));
+	node->left           = 0;
+	node->right          = 0;
+	node->balance_factor = 0;
+	node->parent         = parent;
+	node->value          = value;
+
+	return node;
+}
+
+
+/** DOC
+ * @type function
+ * @name __free_avl_tree_node
+ *
+ * @param avl_tree_node_t *node
+ *
+ * @description
+ * Frees a `avl_tree_node_t` recurlively.
+ */
+void __free_avl_tree_node(avl_tree_t *tree, avl_tree_node_t *node)
+{
+	if (node) {
+		if (node->left)
+			__free_avl_tree_node(tree, node->left);
+		if (node->right)
+			__free_avl_tree_node(tree, node->right);
+
+		if (tree->free_value)
+			free(node->value);
+		free(node);
+	}
+}
+
+
+/** DOC
+ * @type function
+ * @name __avl_tree_rebalance
+ *
+ * @param avl_tree_node_t *node
+ *
+ * @description
+ * Rebalances the tree from the `node` upwards.
+ */
+void __avl_tree_rebalance(avl_tree_node_t *node)
+{
+	while (node) {
+		if (node->balance_factor == 2) {
+			avl_tree_node_t *parent = node->parent;
+			avl_tree_node_t *right  = node->right;
+
+			if (parent->left == node)
+				parent->left =  right;
+			else
+				parent->right = right;
+
+			right->parent = parent;
+
+			node->right = right->left;
+			right->left = node;
+
+			node->balance_factor = 0;
+			right->balance_factor = 0;
+		} else if (node->balance_factor == -2) {
+			avl_tree_node_t *parent = node->parent;
+			avl_tree_node_t *left= node->left;
+
+			if (parent->left == node)
+				parent->left =  left;
+			else
+				parent->right = left;
+
+			left->parent = parent;
+
+			node->left = left->right;
+			left->right = node;
+
+			node->balance_factor = 0;
+			left->balance_factor = 0;
+		}
+
+		node = node->parent;
+	}
+}
+
+/** DOC
+ * @type function
+ * @name <type>_compare
+ *
+ * @param  void *a
+ * @param  void *b
+ * @return i8
+ *
+ * @description
+ * This functions compare `u8 - u64` and `i8 - i64` values
+ * for the generic avl_tree implementation. In this way
+ * the avl_tree can hold any type.
+ *
+ * A compare function returns the following values:
+ *                  `-1 <=> a < b`
+ *                   `0 <=> a = b`
+ *                   `1 <=> a > b`
+ */
+i8 u8_compare(void *a, void *b)
+{
+	u8 x = *((u8*)a);
+	u8 y = *((u8*)b);
+
+	if (x < y)
+		return -1;
+	else if (x == y)
+		return 0;
+	else
+		return 1;
+}
+
+
+i8 i8_compare(void *a, void *b)
+{
+	i8 x = *((i8*)a);
+	i8 y = *((i8*)b);
+
+	if (x < y)
+		return -1;
+	else if (x == y)
+		return 0;
+	else
+		return 1;
+}
+
+
+i8 u16_compare(void *a, void *b)
+{
+	u16 x = *((u16*)a);
+	u16 y = *((u16*)b);
+
+	if (x < y)
+		return -1;
+	else if (x == y)
+		return 0;
+	else
+		return 1;
+}
+
+
+i8 i16_compare(void *a, void *b)
+{
+	i16 x = *((i16*)a);
+	i16 y = *((i16*)b);
+
+	if (x < y)
+		return -1;
+	else if (x == y)
+		return 0;
+	else
+		return 1;
+}
+
+
+i8 u32_compare(void *a, void *b)
+{
+	u32 x = *((u32*)a);
+	u32 y = *((u32*)b);
+
+	if (x < y)
+		return -1;
+	else if (x == y)
+		return 0;
+	else
+		return 1;
+}
+
+
+i8 i32_compare(void *a, void *b)
+{
+	i32 x = *((i32*)a);
+	i32 y = *((i32*)b);
+
+	if (x < y)
+		return -1;
+	else if (x == y)
+		return 0;
+	else
+		return 1;
+}
+
+
+i8 u64_compare(void *a, void *b)
+{
+	u64 x = *((u64*)a);
+	u64 y = *((u64*)b);
+
+	if (x < y)
+		return -1;
+	else if (x == y)
+		return 0;
+	else
+		return 1;
+}
+
+
+i8 i64_compare(void *a, void *b)
+{
+	i64 x = *((i64*)a);
+	i64 y = *((i64*)b);
+
+	if (x < y)
+		return -1;
+	else if (x == y)
+		return 0;
+	else
+		return 1;
+}
diff --git a/lib/avl_tree/avl_tree.h b/lib/avl_tree/avl_tree.h
new file mode 100644
index 0000000..2f0563a
--- /dev/null
+++ b/lib/avl_tree/avl_tree.h
@@ -0,0 +1,52 @@
+#ifndef AVL_TREE_H
+#define AVL_TREE_H
+
+#include "../sys/sizes.h"
+
+typedef struct avl_tree_node_t__ {
+	i8                       balance_factor;
+	struct avl_tree_node_t__ *parent;
+	struct avl_tree_node_t__ *left;
+	struct avl_tree_node_t__ *right;
+	void                     *value;
+} avl_tree_node_t;
+
+/** DOC
+ * @type typename
+ * @name avl_tree_t
+ *
+ * @member avl_tree_node_t *root
+ * @member u64             size
+ * @member u8(*compare)(void*, void*)
+ *
+ * @description
+ * This type describes the head of an `avl_tree_t`
+ * It contains its `size` and holds its `root`.
+ * Additionally it holds the `compare` function
+ * which is used for having a custom order of elements.
+ * To use the normal order for an `avl_tree_t` just holding
+ * integers use the `<type>_compare` functions given by this header.
+ */
+typedef struct {
+	avl_tree_node_t *root;
+	u64 size;
+	i8(*compare)(void*, void*);
+	u8 free_value;
+} avl_tree_t;
+
+avl_tree_t *new_avl_tree(i8(*compare)(void*, void*), u8 free_value);
+void       free_avl_tree(avl_tree_t *tree);
+void       *avl_tree_search(avl_tree_t *tree, void *value);
+void       avl_tree_insert(avl_tree_t *tree, void *value);
+void       avl_tree_remove(avl_tree_t *tree, void *value);
+
+i8 u8_compare(void*, void*);
+i8 i8_compare(void*, void*);
+i8 u16_compare(void*, void*);
+i8 i16_compare(void*, void*);
+i8 u32_compare(void*, void*);
+i8 i32_compare(void*, void*);
+i8 u64_compare(void*, void*);
+i8 i64_compare(void*, void*);
+
+#endif
diff --git a/lib/cstr/cstr.c b/lib/cstr/cstr.c
new file mode 100644
index 0000000..fcb91f4
--- /dev/null
+++ b/lib/cstr/cstr.c
@@ -0,0 +1,353 @@
+#include "cstr.h"
+
+/** DOC
+ * @type function
+ * @name string_length
+ *
+ * @param  char *str
+ * @return u64
+ *
+ * @description
+ * Computes the length of an `ASCII` cstr.
+ */
+u64 cstr_length(const char *str)
+{
+	const char *p = str;
+	while (*p) ++p;
+	return p - str;
+}
+
+
+/** DOC
+ * @type function
+ * @name cstr_compare
+ *
+ * @param  const char *a
+ * @param  const char *b
+ * @return u8
+ *
+ * @description
+ * Compares two strings.
+ * Returns 1 if a has a higher alphabethical value.
+ * Returns -1 if a has a lower alphabethical value.
+ * Returns 0 if strings are equal.
+ */
+i8 cstr_compare(const char *a, const char *b)
+{
+	while (*a && *b) {
+		if (*a < *b)
+			return -1;
+		if (*a > *b)
+			return 1;
+
+		++a;
+		++b;
+	}
+
+	if (*a < *b)
+		return -1;
+	if (*a > *b)
+		return 1;
+
+	return 0;
+}
+
+
+/** DOC
+ * @type function
+ * @name cstr_split
+ *
+ * @param  char *cstr
+ * @param  char split
+ * @return u64
+ *
+ * @description
+ * Splits a string on every `split` char.
+ * Returns the number of splits.
+ * ``WARNING`` This function does replace all `split` char with `0`.
+ *             The old string does not exist after calling this function.
+ */
+u64 cstr_split(char *cstr, char split)
+{
+	u64 splits = 1;
+
+	while (*cstr) {
+		if (*cstr == split) {
+			*cstr = 0;
+			++splits;
+		}
+
+		++cstr;
+	}
+
+	return splits;
+}
+
+
+/** DOC
+ * @type function
+ * @name next_split
+ * 
+ * @param  const char *previous;
+ * @return const char*
+ *
+ * @description
+ * Returns the next split of a `split list` created by `cstr_split`.
+ */
+const char *next_split(const char *previous)
+{
+	while (*previous) ++previous;
+	return previous + 1;
+}
+
+
+/** DOC
+ * @type function
+ * @name strip_front
+ *
+ * @param  char *cstr
+ * @param  char strip
+ * @return u64
+ *
+ * @description
+ * Remove `strip` from front.
+ */
+u64 strip_front(char *cstr, char strip)
+{
+	char *front = cstr;
+
+	while (*front && *front == strip) ++front;
+
+	while (*front) {
+		*cstr = *front;
+		++cstr;
+		++front;
+	}
+
+	while (*cstr) {
+		*cstr = 0;
+		++cstr;
+	}
+
+	return front - cstr;
+}
+
+
+/** DOC
+ * @type function
+ * @name strip_back
+ *
+ * @param  char *cstr
+ * @param  char stip
+ * @return u64
+ *
+ * @description
+ * Removes `strip` char from back of the cstr.
+ */
+u64 strip_back(char *cstr, char strip)
+{
+	u64 diff = 0;
+
+	while (*cstr) ++cstr;
+	--cstr;
+
+	while (*cstr == strip) {
+		*cstr = 0;
+		++diff;
+	}
+
+	return diff;
+}
+
+/** DOC
+ * @type function
+ * @name strip_cstr
+ *
+ * @param  char *cstr
+ * @param  char strip
+ * @return u64
+ *
+ * @description
+ * Strips `strip` char from start and end of the string.
+ */
+u64 strip_cstr(char *cstr, char strip)
+{
+	return strip_front(cstr, strip) + strip_back(cstr, strip);
+}
+
+/* DOC
+ * @type function
+ * @name string_utf8_length
+ *
+ * @param  char *str
+ * @return u64
+ *
+ * @description
+ * Computes the length of a `UTF-8` cstr.
+ */
+u64 cstr_utf8_length(const char * str)
+{
+	const char *p = str;
+	u64 length = 0;
+	int a = 0;
+
+	while (*p) {
+		next_utf8(&p);
+		++length;
+	}
+
+	return length;
+}
+
+
+/** DOC
+ * @type function
+ * @name next_utf8
+ *
+ * @param  char **c
+ * @return u8
+ *
+ * @description
+ * Set `c` to the next `UTF-8` char.
+ * Returns the difference relative to `ASCII` chars.
+ */
+u8 next_utf8(const char **c)
+{
+	int a;
+
+	switch (**c & 0xf0) {
+		case 0xf0: a = 4; break;
+		case 0xe0: a = 3; break;
+		case 0xc0: a = 2; break;
+		default:   a = 1; break;
+	}
+
+	*c += a;
+	return a;
+}
+
+/** DOC
+ * @type function
+ * @name previous_utf8
+ *
+ * @param  char **c
+ * @return u8
+ *
+ * @description
+ * Set `c` to the previous `UTF-8` char.
+ * Returns the difference relative to `ASCII` chars.
+ */
+u8 previous_utf8(const char **c)
+{
+	int a = 1;
+	--(*c);
+
+	while ((**c & 0xc0) == 0x80) {
+		--(*c);
+		++a;
+	}
+
+	return a;
+}
+
+/** DOC
+ * @type function
+ * @name u64_to_cstr
+ *
+ * @param u64  n
+ * @param char *cstr
+ * @param u64  length
+ *
+ * @description
+ * Writes the string representation of `n` to the `cstr`.
+ */
+void u64_to_cstr(u64 n, char *cstr, u64 length)
+{
+	char *p = cstr + length - 1;
+	u64 d;
+	int i = 0;
+
+	for (;n && i < length; ++i) {
+		*(p--) = (n % 10) + '0';
+		n /= 10;
+	}
+
+	d = p - cstr;
+
+	for (i = 0; i < length - d; ++i)
+		cstr[i] = cstr[i + d];
+}
+
+/** DOC
+ * @type function
+ * @name i64_to_cstr
+ *
+ * @param i64  n
+ * @param char *cstr
+ * @param u64  length
+ *
+ * @description
+ * Writes the string representation of `n` to the `cstr`.
+ */
+void i64_to_cstr(i64 n, char *cstr, u64 length)
+{
+	if (n < 0) {
+		*cstr = '-';
+		n = -n;
+		u64_to_cstr((u64)n, cstr + 1, length - 1);
+	} else {
+		u64_to_cstr((u64)n, cstr, length);
+	}
+}
+
+/** DOC
+ * @type function
+ * @name cstr_to_u64
+ *
+ * @param  const char *cstr
+ * @return u64
+ *
+ * @description
+ * Parses an `u64` to cstr.
+ */
+u64 cstr_to_u64(const char *cstr)
+{
+	u64 n = 0;
+	u64 e = 1;
+	const char *p = cstr;
+
+	while (*p) {
+		if ((const unsigned char)(*p - '0') > 9)
+			return 0;
+		++p;
+	}
+
+	--p;
+
+	while (p >= cstr) {
+		n += (*p - '0') * e;
+		e *= 10;
+		--p;
+	}
+
+	return n;
+}
+
+
+/** DOC
+ * @type function
+ * @name cstr_to_i64
+ */
+i64 cstr_to_i64(const char *cstr)
+{
+	i64 n = 0;
+
+	if (*cstr == '-') {
+		n = (i64)cstr_to_u64(cstr + 1);
+		n = -n;
+	} else {
+		n = (i64)cstr_to_u64(cstr);
+	}
+
+	return n;
+}
diff --git a/lib/cstr/cstr.h b/lib/cstr/cstr.h
new file mode 100644
index 0000000..80dc359
--- /dev/null
+++ b/lib/cstr/cstr.h
@@ -0,0 +1,23 @@
+#ifndef CSTR_H
+#define CSTR_H
+
+#include "../sys/sizes.h"
+
+u64        cstr_length(const char *);
+i8         cstr_compare(const char *a, const char *b);
+u64        cstr_split(char *cstr, char split);
+const char *next_split(const char *previous);
+u64        strip_front(char *cstr, char strip);
+u64        strip_back(char *cstr, char strip);
+u64        strip_cstr(char *cstr, char strip);
+
+u64 cstr_utf8_length(const char *);
+u8  next_utf8(const char **);
+u8  previous_utf8(const char **);
+
+void u64_to_cstr(u64 n, char *cstr, u64 length);
+void i64_to_cstr(i64 n, char *cstr, u64 length);
+u64  cstr_to_u64(const char *cstr);
+i64  cstr_to_i64(const char *cstr);
+
+#endif
diff --git a/lib/malloc/malloc.c b/lib/malloc/malloc.c
new file mode 100644
index 0000000..a0e9ebf
--- /dev/null
+++ b/lib/malloc/malloc.c
@@ -0,0 +1,187 @@
+#include "malloc.h"
+
+#include "../sys/brk.h"
+
+/** DOC
+ * @type typename
+ * @name segment_t
+ *
+ * @member void      *ptr
+ * @member u64       size
+ * @member u8        free
+ * @member segment_t *next
+ *
+ * @description
+ * A segment is a meta block for an allocated area.
+ * It contains the pointer `(void *ptr)` for the memory location
+ * its size and if its free `(u8 free)`. 
+ * The segment_t is a single linked list node because of that
+ * it also holds a `(segment_t *next)` pointer to the next segment.
+ */
+typedef struct __segment_t {
+	void                *ptr;
+	u64                 size;
+	u8                  free;
+	struct __segment_t  *next;
+} segment_t;
+
+
+/** DOC
+ * @type instance
+ * @name mbrk
+ *
+ * @member u64       initial
+ * @member u64       current
+ * @member segment_t *first
+ * @member segment_t *last
+ *
+ * @description
+ * The mbrk instance holds the current brk `(see [man 2 brk])`
+ * and the first and last element of the segement list.
+ */
+struct __break {
+	u64        initial;
+	u64        current;
+	segment_t  *first;
+	segment_t  *last;
+} mbrk = {
+	.initial = 0,
+	.current = 0,
+	.first = 0,
+	.last = 0
+};
+
+
+void  __initialize_memory();
+segment_t *__find_free_segment(u64 size);
+segment_t *__allocate_new(u64 size);
+
+
+/** DOC
+ * @type function
+ * @name malloc
+ *
+ * @param  u64 size
+ * @return void*
+ *
+ * @description
+ * Allocates memory. If there is no space left requests new space.
+ */
+void* malloc(u64 size)
+{
+	segment_t *seg;
+
+	if (!mbrk.initial)
+		__initialize_memory();
+	
+	seg = __find_free_segment(size);
+
+	if (!seg)
+		seg = __allocate_new(size);
+
+	seg->free = 0;
+	return seg->ptr;
+}
+
+
+/** DOC
+ * @type function
+ * @name free
+ *
+ * @param  void *ptr
+ * @return void
+ *
+ * @description
+ * Frees the memory allocated by `malloc`.
+ *
+ * ``IMPORTANT`` this function does not free the memory to be accessible
+ * for the whole system. The freed memory is only accessible for the current
+ * process and is released on exit.
+ */
+void free(void *ptr)
+{
+	segment_t * seg = mbrk.first;
+
+	for (; seg; seg = seg->next) {
+		if (ptr == seg->ptr) {
+			seg->free = 1;
+			break;
+		}
+	}
+}
+
+
+/** DOC
+ * @type function
+ * @name __initialize_memory
+ *
+ * @description
+ * Initalizes `mbrk` by calling `brk(0)`.
+ * Is only called if `mbrk.initial` is zero.
+ */
+void __initialize_memory()
+{
+	mbrk.initial = brk(0);
+	mbrk.current = mbrk.initial;
+}
+
+
+/** DOC
+ * @type function
+ * @name __find_free_segment
+ *
+ * @param  u64 size
+ * @return segment_t*
+ *
+ * @description
+ * Searches a segment with the given `size` in
+ * the segment linked-list.
+ * If there is no such segment it returns `0`
+ */
+segment_t *__find_free_segment(u64 size)
+{
+	segment_t * seg = mbrk.first;
+
+	for (; seg; seg = seg->next) {
+		if (seg->free && size == seg->size)
+			return seg;
+	}
+
+	return 0;
+}
+
+/** DOC
+ * @type function
+ * @name __allocate_new
+ *
+ * @param  u64 size
+ * @return segment_t*
+ *
+ * @description
+ * Allocates a new segement.
+ * This function is only called if no free segment with
+ * the given `size` was found. A new segment is allocated
+ * by using the `brk` syscall and adding `size + sizeof(segment_t)`
+ * new memory to the process.
+ */
+segment_t *__allocate_new(u64 size)
+{
+	u64 last = mbrk.current;
+	mbrk.current += size + sizeof(segment_t);
+	brk((void*)mbrk.current);
+
+	segment_t *seg = (segment_t*)last;
+	seg->ptr = (void*)(mbrk.current - size);
+	seg->size = size;
+	seg->free = 0;
+	seg->next = 0;
+
+	if (!mbrk.first)
+		mbrk.first = seg;
+	else
+		mbrk.last->next = seg;
+	
+	mbrk.last = seg;
+
+	return seg;
+}
diff --git a/lib/malloc/malloc.h b/lib/malloc/malloc.h
new file mode 100644
index 0000000..d4896bf
--- /dev/null
+++ b/lib/malloc/malloc.h
@@ -0,0 +1,9 @@
+#ifndef MALLOC_H
+#define MALLOC_H
+
+#include "../sys/sizes.h"
+
+void * malloc(u64 size);
+void free(void * ptr);
+
+#endif
diff --git a/lib/sys/brk.h b/lib/sys/brk.h
new file mode 100644
index 0000000..d2221a2
--- /dev/null
+++ b/lib/sys/brk.h
@@ -0,0 +1,10 @@
+#ifndef BRK_H
+#define BRK_H
+
+#include "syscalls.h"
+
+static unsigned long brk(void * addr) {
+	return syscall(BRK, addr);
+}
+
+#endif
diff --git a/lib/sys/execve.h b/lib/sys/execve.h
new file mode 100644
index 0000000..04d6dea
--- /dev/null
+++ b/lib/sys/execve.h
@@ -0,0 +1,11 @@
+#ifndef EXECVE_H
+#define EXECVE_H
+
+#include "syscalls.h"
+
+int execve(const char *pathname, char *const argv[], char *const envp[])
+{
+	return syscall(EXECVE, pathname, argv, envp);
+}
+
+#endif
diff --git a/lib/sys/mmap.h b/lib/sys/mmap.h
new file mode 100644
index 0000000..7e885c4
--- /dev/null
+++ b/lib/sys/mmap.h
@@ -0,0 +1,17 @@
+#ifndef MMAP_H
+#define MMAP_H
+#include "syscalls.h"
+
+#define PROT_READ   0x1
+#define PROT_WRITE  0x2
+#define PROT_EXEC   0x4
+#define PROT_NONE   0x0
+
+#define MAP_SHARED  0x1
+#define MAP_PRIVATE 0x2
+
+static void * mmap(void * addr, unsigned long size, int prot, int flags, int fd, int offset) {
+	return syscall(MMAP, size, prot, flags, fd, offset);
+}
+
+#endif
diff --git a/lib/sys/munmap.h b/lib/sys/munmap.h
new file mode 100644
index 0000000..4a876d6
--- /dev/null
+++ b/lib/sys/munmap.h
@@ -0,0 +1,9 @@
+#ifndef MUNMAP_H
+#define MUNMAP_H
+#include "syscall.h"
+
+static int munmap(void * addr, unsigned long size) {
+	return syscall(MUNMAP, addr, size);
+}
+
+#endif
diff --git a/lib/sys/read.h b/lib/sys/read.h
new file mode 100644
index 0000000..7dba6e7
--- /dev/null
+++ b/lib/sys/read.h
@@ -0,0 +1,9 @@
+#ifndef READ_H
+#define READ_H
+#include "syscalls.h"
+
+static int read(unsigned int fd, char * buf, unsigned long count) {
+	return syscall(READ, fd, buf, count, 0, 0);
+}
+
+#endif
diff --git a/lib/sys/reboot.h b/lib/sys/reboot.h
new file mode 100644
index 0000000..fd119c5
--- /dev/null
+++ b/lib/sys/reboot.h
@@ -0,0 +1,21 @@
+#ifndef SHUTDOWN_H
+#define SHUTDOWN_H
+
+#include "syscalls.h"
+
+#define REBOOT_HALT_SYSTEM 0xcdef0123
+#define REBOOT_HARD_RESET  0x01234567
+#define REBOOT_ENABLE_CAD  0x89abcdef
+#define REBOOT_DISABLE_CAD 0
+#define REBOOT_POWEROFF    0x4321fedc
+#define REBOOT_SUSPEND     0xd000fce2
+#define REBOOT_NEW_KERNEL  0x45584543
+
+static int reboot(int cmd) {
+	const int magic1 = 0xfee1dead;
+	const int magic2 =  537993216;
+
+	return syscall((void*)REBOOT, magic1, magic2, cmd, 0);
+}
+
+#endif
diff --git a/lib/sys/sbrk.h b/lib/sys/sbrk.h
new file mode 100644
index 0000000..25d9c6c
--- /dev/null
+++ b/lib/sys/sbrk.h
@@ -0,0 +1,10 @@
+#ifndef SBRK_H
+#define SBRK_H
+
+#include "syscalls.h"
+
+static int brk(void * addr) {
+	return syscall(BRK, addr);
+}
+
+#endif
diff --git a/lib/sys/sizes.h b/lib/sys/sizes.h
new file mode 100644
index 0000000..127d483
--- /dev/null
+++ b/lib/sys/sizes.h
@@ -0,0 +1,16 @@
+#ifndef SIZES_H
+#define SIZES_H
+
+typedef signed   char i8;
+typedef unsigned char u8;
+
+typedef signed   short int i16;
+typedef unsigned short int u16;
+
+typedef signed   int i32;
+typedef unsigned int u32;
+
+typedef signed   long int i64;
+typedef unsigned long int u64;
+
+#endif
diff --git a/lib/sys/start.S b/lib/sys/start.S
new file mode 100644
index 0000000..deafd67
--- /dev/null
+++ b/lib/sys/start.S
@@ -0,0 +1,6 @@
+.global _start
+_start:
+	call main
+	mov %rax, %rdi
+	mov $60, %rax
+	syscall
diff --git a/lib/sys/stat.h b/lib/sys/stat.h
new file mode 100644
index 0000000..02bdc48
--- /dev/null
+++ b/lib/sys/stat.h
@@ -0,0 +1,62 @@
+#ifndef STAT_H
+#define STAT_H
+
+#include "sizes.h"
+#include "time.h"
+#include "syscalls.h"
+
+#define S_IFMT     0170000
+#define S_IFSOCK   0140000
+#define S_IFLNK    0120000
+#define S_IFREG    0100000
+#define S_IFBLK    0060000
+#define S_IFDIR    0040000
+#define S_IFCHR    0020000
+#define S_IFIFO    0010000
+
+#define S_ISUID     04000
+#define S_ISGID     02000
+#define S_ISVTX     01000
+
+#define S_IRWXU     00700
+
+#define S_IRUSR     00400
+#define S_IWUSR     00200
+#define S_IXUSR     00100
+
+#define S_IRWXG     00070
+
+#define S_IRGRP     00040
+#define S_IWGRP     00020
+#define S_IXGRP     00010
+
+#define S_IRWXO     00007
+
+#define S_IROTH     00004
+#define S_IWOTH     00002
+#define S_IXOTH     00001
+
+struct stat {
+	i64 dev;
+	i64 ino;
+	u64 nlink;
+	u32 mode;
+	u32 uid;
+	u32 gid;
+	u64 rdev;
+	u64 size;
+	u64 blksize;
+	i64 blocks;
+
+	struct timespec atime;
+	struct timespec mtime;
+	struct timespec ctime;
+
+	u64 __[3];
+};
+
+static int stat(const char * filename, struct stat * statbuf) {
+	return syscall(STAT, filename, statbuf);
+}
+
+#endif
diff --git a/lib/sys/syscalls.h b/lib/sys/syscalls.h
new file mode 100644
index 0000000..03ce997
--- /dev/null
+++ b/lib/sys/syscalls.h
@@ -0,0 +1,336 @@
+#ifndef SYSCALLS_H
+#define SYSCALLS_H
+
+__asm__ (
+	"syscall:\n"
+		"endbr64\n" 
+		"mov %rdi,    %rax\n"
+		"mov %rsi,    %rdi\n"
+		"mov %rdx,    %rsi\n"
+		"mov %rcx,    %rdx\n"
+		"mov %r8,     %rcx\n"
+		"mov %r9,     %r8\n"
+		"mov 8(%rsp), %r9\n"
+		"syscall\n" 
+		"ret\n"
+);
+
+enum {
+	READ,
+	WRITE,
+	OPEN,
+	CLOSE,
+	STAT,
+	FSTAT,
+	LSTAT,
+	POLL,
+	LSEEK,
+	MMAP,
+	MPROTECT,
+	MUNMAP,
+	BRK,
+	RT_SIGACTION,
+	RT_SIGPROCMASK,
+	RT_SIGRETURN,
+	IOCTL,
+	PREAD64,
+	PWRITE64,
+	READV,
+	WRITEV,
+	ACCESS,
+	PIPE,
+	SELECT,
+	SCHED_YIELD,
+	MREMAP,
+	MSYNC,
+	MINCORE,
+	MADVISE,
+	SHMGET,
+	SHMAT,
+	SHMCTL,
+	DUP,
+	DUP2,
+	PAUSE,
+	NANOSLEEP,
+	GETITIMER,
+	ALARM,
+	SETITIMER,
+	GETPID,
+	SENDFILE,
+	SOCKET,
+	CONNECT,
+	ACCEPT,
+	SENDTO,
+	RECVFROM,
+	SENDMSG,
+	RECVMSG,
+	SHUTDOWN,
+	BIND,
+	LISTEN,
+	GETSOCKNAME,
+	GETPEERNAME,
+	SOCKETPAIR,
+	SETSOCKOPT,
+	GETSOCKOPT,
+	CLONE,
+	FORK,
+	VFORK,
+	EXECVE,
+	EXIT,
+	WAIT4,
+	KILL,
+	UNAME,
+	SEMGET,
+	SEMOP,
+	SEMCTL,
+	SHMDT,
+	MSGGET,
+	MSGSND,
+	MSGRCV,
+	MSGCTL,
+	FCNTL,
+	FLOCK,
+	FSYNC,
+	FDATASYNC,
+	TRUNCATE,
+	FTRUNCATE,
+	GETDENTS,
+	GETCWD,
+	CHDIR,
+	FCHDIR,
+	RENAME,
+	MKDIR,
+	RMDIR,
+	CREAT,
+	LINK,
+	UNLINK,
+	SYMLINK,
+	READLINK,
+	CHMOD,
+	FCHMOD,
+	CHOWN,
+	FCHOWN,
+	LCHOWN,
+	UMASK,
+	GETTIMEOFDAY,
+	GETRLIMIT,
+	GETRUSAGE,
+	SYSINFO,
+	TIMES,
+	PTRACE,
+	GETUID,
+	SYSLOG,
+	GETGID,
+	SETUID,
+	SETGID,
+	GETEUID,
+	GETEGID,
+	SETPGID,
+	GETPPID,
+	GETPGRP,
+	SETSID,
+	SETREUID,
+	SETREGID,
+	GETGROUPS,
+	SETGROUPS,
+	SETRESUID,
+	GETRESUID,
+	SETRESGID,
+	GETRESGID,
+	GETPGID,
+	SETFSUID,
+	SETFSGID,
+	GETSID,
+	CAPGET,
+	CAPSET,
+	RT_SIGPENDING,
+	RT_SIGTIMEDWAIT,
+	RT_SIGQUEUEINFO,
+	RT_SIGSUSPEND,
+	SIGALTSTACK,
+	UTIME,
+	MKNOD,
+	USELIB,
+	PERSONALITY,
+	USTAT,
+	STATFS,
+	FSTATFS,
+	SYSFS,
+	GETPRIORITY,
+	SETPRIORITY,
+	SCHED_SETPARAM,
+	SCHED_GETPARAM,
+	SCHED_SETSCHEDULER,
+	SCHED_GETSCHEDULER,
+	SCHED_GET_PRIORITY_MAX,
+	SCHED_GET_PRIORITY_MIN,
+	SCHED_RR_GET_INTERVAL,
+	MLOCK,
+	MUNLOCK,
+	MLOCKALL,
+	MUNLOCKALL,
+	VHANGUP,
+	MODIFY_LDT,
+	PIVOT_ROOT,
+	_SYSCTL,
+	PRCTL,
+	ARCH_PRCTL,
+	ADJTIMEX,
+	SETRLIMIT,
+	CHROOT,
+	SYNC,
+	ACCT,
+	SETTIMEOFDAY,
+	MOUNT,
+	UMOUNT2,
+	SWAPON,
+	SWAPOFF,
+	REBOOT,
+	SETHOSTNAME,
+	SETDOMAINNAME,
+	IOPL,
+	IOPERM,
+	CREATE_MODULE,
+	INIT_MODULE,
+	DELETE_MODULE,
+	GET_KERNEL_SYMS,
+	QUERY_MODULE,
+	QUOTACTL,
+	NFSSERVCTL,
+	GETPMSG,
+	PUTPMSG,
+	AFS_SYSCALL,
+	TUXCALL,
+	SECURITY,
+	GETTID,
+	READAHEAD,
+	SETXATTR,
+	LSETXATTR,
+	FSETXATTR,
+	GETXATTR,
+	LGETXATTR,
+	FGETXATTR,
+	LISTXATTR,
+	LLISTXATTR,
+	FLISTXATTR,
+	REMOVEXATTR,
+	LREMOVEXATTR,
+	FREMOVEXATTR,
+	TKILL,
+	TIME,
+	FUTEX,
+	SCHED_SETAFFINITY,
+	SCHED_GETAFFINITY,
+	SET_THREAD_AREA,
+	IO_SETUP,
+	IO_DESTROY,
+	IO_GETEVENTS,
+	IO_SUBMIT,
+	IO_CANCEL,
+	GET_THREAD_AREA,
+	LOOKUP_DCOOKIE,
+	EPOLL_CREATE,
+	EPOLL_CTL_OLD,
+	EPOLL_WAIT_OLD,
+	REMAP_FILE_PAGES,
+	GETDENTS64,
+	SET_TID_ADDRESS,
+	RESTART_SYSCALL,
+	SEMTIMEDOP,
+	FADVISE64,
+	TIMER_CREATE,
+	TIMER_SETTIME,
+	TIMER_GETTIME,
+	TIMER_GETOVERRUN,
+	TIMER_DELETE,
+	CLOCK_SETTIME,
+	CLOCK_GETTIME,
+	CLOCK_GETRES,
+	CLOCK_NANOSLEEP,
+	EXIT_GROUP,
+	EPOLL_WAIT,
+	EPOLL_CTL,
+	TGKILL,
+	UTIMES,
+	VSERVER,
+	MBIND,
+	SET_MEMPOLICY,
+	GET_MEMPOLICY,
+	MQ_OPEN,
+	MQ_UNLINK,
+	MQ_TIMEDSEND,
+	MQ_TIMEDRECEIVE,
+	MQ_NOTIFY,
+	MQ_GETSETATTR,
+	KEXEC_LOAD,
+	WAITID,
+	ADD_KEY,
+	REQUEST_KEY,
+	KEYCTL,
+	IOPRIO_SET,
+	IOPRIO_GET,
+	INOTIFY_INIT,
+	INOTIFY_ADD_WATCH,
+	INOTIFY_RM_WATCH,
+	MIGRATE_PAGES,
+	OPENAT,
+	MKDIRAT,
+	MKNODAT,
+	FCHOWNAT,
+	FUTIMESAT,
+	NEWFSTATAT,
+	UNLINKAT,
+	RENAMEAT,
+	LINKAT,
+	SYMLINKAT,
+	READLINKAT,
+	FCHMODAT,
+	FACCESSAT,
+	PSELECT6,
+	PPOLL,
+	UNSHARE,
+	SET_ROBUST_LIST,
+	GET_ROBUST_LIST,
+	SPLICE,
+	TEE,
+	SYNC_FILE_RANGE,
+	VMSPLICE,
+	MOVE_PAGES,
+	UTIMENSAT,
+	EPOLL_PWAIT,
+	SIGNALFD,
+	TIMERFD_CREATE,
+	EVENTFD,
+	FALLOCATE,
+	TIMERFD_SETTIME,
+	TIMERFD_GETTIME,
+	ACCEPT4,
+	SIGNALFD4,
+	EVENTFD2,
+	EPOLL_CREATE1,
+	DUP3,
+	PIPE2,
+	INOTIFY_INIT1,
+	PREADV,
+	PWRITEV,
+	RT_TGSIGQUEUEINFO,
+	PERF_EVENT_OPEN,
+	RECVMMSG,
+	FANOTIFY_INIT,
+	FANOTIFY_MARK,
+	PRLIMIT64,
+	NAME_TO_HANDLE_AT,
+	OPEN_BY_HANDLE_AT,
+	CLOCK_ADJTIME,
+	SYNCFS,
+	SENDMMSG,
+	SETNS,
+	GETCPU,
+	PROCESS_VM_READV,
+	PROCESS_VM_WRITEV,
+	KCMP,
+	FINIT_MODULE,
+};
+
+
+#endif
diff --git a/lib/sys/time.h b/lib/sys/time.h
new file mode 100644
index 0000000..920ee5c
--- /dev/null
+++ b/lib/sys/time.h
@@ -0,0 +1,11 @@
+#ifndef TIME_H
+#define TIME_H
+
+#include "sizes.h"
+
+struct timespec {
+	u64  tv_sec;
+	long tv_nsec;
+};
+
+#endif
diff --git a/lib/sys/write.h b/lib/sys/write.h
new file mode 100644
index 0000000..a705873
--- /dev/null
+++ b/lib/sys/write.h
@@ -0,0 +1,10 @@
+#ifndef WRITE_H
+#define WRITE_H
+
+#include "syscalls.h"
+
+static int write(unsigned int fd, const char * buf, unsigned long count) {
+	return syscall((void*)WRITE, (void*)fd, (void*)buf, (void*)count);
+}
+
+#endif