Added list and tree data types for better vfs

3 files changed, 422 insertions, 0 deletions

diff --git a/src/kernel/lib/data.h b/src/kernel/lib/data.h
new file mode 100644
index 0000000..356b978
--- /dev/null
+++ b/src/kernel/lib/data.h
@@ -0,0 +1,94 @@
+#ifndef MELVIX_DATA_H
+#define MELVIX_DATA_H
+
+#include <stdint.h>
+
+// LIST
+
+struct list_node {
+	struct list_node *prev;
+	struct list_node *next;
+	void *val;
+};
+
+struct list {
+	struct list_node *head;
+	struct list_node *tail;
+	uint32_t size;
+};
+
+#define foreach(t, list) for (struct list_node *t = list->head; t != NULL; t = t->next)
+
+struct list *list_create();
+
+uint32_t list_size(struct list *list);
+
+struct list_node *list_insert_front(struct list *list, void *val);
+
+void list_insert_back(struct list *list, void *val);
+
+void *list_remove_node(struct list *list, struct list_node *node);
+
+void *list_remove_front(struct list *list);
+
+void *list_remove_back(struct list *list);
+
+void list_push(struct list *list, void *val);
+
+struct list_node *list_pop(struct list *list);
+
+void list_enqueue(struct list *list, void *val);
+
+struct list_node *list_dequeue(struct list *list);
+
+void *list_peek_front(struct list *list);
+
+void *list_peek_back(struct list *list);
+
+void list_destroy(struct list *list);
+
+void listnode_destroy(struct list_node *node);
+
+int list_contain(struct list *list, void *val);
+
+struct list_node *list_get_node_by_index(struct list *list, int index);
+
+void *list_remove_by_index(struct list *list, int index);
+
+struct list *str_split(const char *str, const char *delim, uint32_t *numtokens);
+char *list_to_str(struct list *list, const char *delim);
+
+// Tree
+
+struct tree_node {
+	struct list *children;
+	void *value;
+};
+
+struct tree {
+	struct tree_node *root;
+};
+
+struct tree *tree_create();
+
+struct tree_node *treenode_create(void *value);
+
+struct tree_node *tree_insert(struct tree *tree, struct tree_node *subroot, void *value);
+
+struct tree_node *tree_find_parent(struct tree *tree, struct tree_node *remove_node,
+				   int *child_index);
+
+struct tree_node *tree_find_parent_recur(struct tree *tree, struct tree_node *remove_node,
+					 struct tree_node *subroot, int *child_index);
+
+void tree_remove(struct tree *tree, struct tree_node *remove_node);
+
+void tree2list_recur(struct tree_node *subroot, struct list *list);
+
+void tree2list(struct tree *tree, struct list *list);
+
+void tree2array(struct tree *tree, void **array, int *size);
+
+void tree2array_recur(struct tree_node *subroot, void **array, int *size);
+
+#endif
diff --git a/src/kernel/lib/data/list.c b/src/kernel/lib/data/list.c
new file mode 100644
index 0000000..3346e32
--- /dev/null
+++ b/src/kernel/lib/data/list.c
@@ -0,0 +1,225 @@
+#include <stdint.h>
+#include <stddef.h>
+#include <kernel/lib/lib.h>
+#include <kernel/lib/stdlib.h>
+#include <kernel/lib/data.h>
+#include <kernel/memory/alloc.h>
+
+struct list *list_create()
+{
+	struct list *list = kcalloc(sizeof(struct list), 1);
+	return list;
+}
+
+uint32_t list_size(struct list *list)
+{
+	if (!list)
+		return 0;
+	return list->size;
+}
+
+void *list_remove_node(struct list *list, struct list_node *node)
+{
+	void *val = node->val;
+	if (list->head == node)
+		return list_remove_front(list);
+	else if (list->tail == node)
+		return list_remove_back(list);
+	else {
+		node->next->prev = node->prev;
+		node->prev->next = node->next;
+		list->size--;
+		kfree(node);
+	}
+	return val;
+}
+struct list_node *list_insert_front(struct list *list, void *val)
+{
+	struct list_node *t = kcalloc(sizeof(struct list_node), 1);
+	list->head->prev = t;
+	t->next = list->head;
+	t->val = val;
+
+	if (!list->head)
+		list->tail = t;
+
+	list->head = t;
+	list->size++;
+	return t;
+}
+
+void list_insert_back(struct list *list, void *val)
+{
+	struct list_node *t = kcalloc(sizeof(struct list_node), 1);
+	t->prev = list->tail;
+	if (list->tail)
+		list->tail->next = t;
+	t->val = val;
+
+	if (!list->head)
+		list->head = t;
+
+	list->tail = t;
+	list->size++;
+}
+
+void *list_remove_front(struct list *list)
+{
+	if (!list->head)
+		return NULL;
+	struct list_node *t = list->head;
+	void *val = t->val;
+	list->head = t->next;
+	if (list->head)
+		list->head->prev = NULL;
+	kfree(t);
+	list->size--;
+	return val;
+}
+
+void *list_remove_back(struct list *list)
+{
+	if (!list->head)
+		return NULL;
+	struct list_node *t = list->tail;
+	void *val = t->val;
+	list->tail = t->prev;
+	if (list->tail)
+		list->tail->next = NULL;
+	kfree(t);
+	list->size--;
+	return val;
+}
+
+void list_push(struct list *list, void *val)
+{
+	list_insert_back(list, val);
+}
+
+struct list_node *list_pop(struct list *list)
+{
+	if (!list->head)
+		return NULL;
+	struct list_node *t = list->tail;
+	list->tail = t->prev;
+	if (list->tail)
+		list->tail->next = NULL;
+	list->size--;
+	return t;
+}
+
+void list_enqueue(struct list *list, void *val)
+{
+	list_insert_front(list, val);
+}
+
+struct list_node *list_dequeue(struct list *list)
+{
+	return list_pop(list);
+}
+
+void *list_peek_front(struct list *list)
+{
+	if (!list->head)
+		return NULL;
+	return list->head->val;
+}
+
+void *list_peek_back(struct list *list)
+{
+	if (!list->tail)
+		return NULL;
+	return list->tail->val;
+}
+
+
+int list_contain(struct list *list, void *val)
+{
+	int idx = 0;
+	foreach(listnode, list)
+	{
+		if (listnode->val == val)
+			return idx;
+		idx++;
+	}
+	return -1;
+}
+
+struct list_node *list_get_node_by_index(struct list *list, int index)
+{
+	if (index < 0 || index >= list_size(list))
+		return NULL;
+	int curr = 0;
+	foreach(listnode, list)
+	{
+		if (index == curr)
+			return listnode;
+		curr++;
+	}
+	return NULL;
+}
+
+void *list_remove_by_index(struct list *list, int index)
+{
+	struct list_node *node = list_get_node_by_index(list, index);
+	return list_remove_node(list, node);
+}
+
+void list_destroy(struct list *list)
+{
+	struct list_node *node = list->head;
+	while (node != NULL) {
+		struct list_node *save = node;
+		node = node->next;
+		kfree(save);
+	}
+	kfree(list);
+}
+
+void listnode_destroy(struct list_node *node)
+{
+	kfree(node);
+}
+
+// Conversion
+
+struct list *str_split(const char *str, const char *delim, uint32_t *numtokens)
+{
+	struct list *ret_list = list_create();
+	char *s = strdup(str);
+	char *token, *rest = s;
+	while ((token = strsep(&rest, delim)) != NULL) {
+		if (!strcmp(token, "."))
+			continue;
+		if (!strcmp(token, "..")) {
+			if (list_size(ret_list) > 0)
+				list_pop(ret_list);
+			continue;
+		}
+		list_push(ret_list, strdup(token));
+		if (numtokens)
+			(*numtokens)++;
+	}
+	kfree(s);
+	return ret_list;
+}
+
+char *list_to_str(struct list *list, const char *delim)
+{
+	char *ret = kmalloc(256);
+	memset(ret, 0, 256);
+	int len = 0, ret_len = 256;
+	while (list_size(list) > 0) {
+		char *temp = list_pop(list)->val;
+		int len_temp = strlen(temp);
+		if (len + len_temp + 1 + 1 > ret_len) {
+			ret_len = ret_len * 2;
+			/* ret = krealloc(ret, ret_len); */
+			ret = kmalloc(ret_len);
+			len = len + len_temp + 1;
+		}
+		strcat(ret, delim);
+		strcat(ret, temp);
+	}
+	return ret;
+}
diff --git a/src/kernel/lib/data/tree.c b/src/kernel/lib/data/tree.c
new file mode 100644
index 0000000..53233a4
--- /dev/null
+++ b/src/kernel/lib/data/tree.c
@@ -0,0 +1,103 @@
+#include <stdint.h>
+#include <kernel/lib/data.h>
+#include <kernel/memory/alloc.h>
+
+struct tree *tree_create()
+{
+	return (struct tree *)kcalloc(sizeof(struct tree), 1);
+}
+
+struct tree_node *treenode_create(void *value)
+{
+	struct tree_node *n = kcalloc(sizeof(struct tree_node), 1);
+	n->value = value;
+	n->children = list_create();
+	return n;
+}
+
+struct tree_node *tree_insert(struct tree *tree, struct tree_node *subroot, void *value)
+{
+	struct tree_node *treenode = kcalloc(sizeof(struct tree_node), 1);
+	treenode->children = list_create();
+	treenode->value = value;
+
+	if (!tree->root) {
+		tree->root = treenode;
+		return treenode;
+	}
+	list_insert_front(subroot->children, treenode);
+	return treenode;
+}
+
+struct tree_node *tree_find_parent(struct tree *tree, struct tree_node *remove_node,
+				   int *child_index)
+{
+	if (remove_node == tree->root)
+		return NULL;
+	return tree_find_parent_recur(tree, remove_node, tree->root, child_index);
+}
+
+struct tree_node *tree_find_parent_recur(struct tree *tree, struct tree_node *remove_node,
+					 struct tree_node *subroot, int *child_index)
+{
+	int idx;
+	if ((idx = list_contain(subroot->children, remove_node)) != -1) {
+		*child_index = idx;
+		return subroot;
+	}
+	foreach(child, subroot->children)
+	{
+		struct tree_node *ret =
+			tree_find_parent_recur(tree, remove_node, child->val, child_index);
+		if (ret != NULL) {
+			return ret;
+		}
+	}
+	return NULL;
+}
+
+void tree_remove(struct tree *tree, struct tree_node *remove_node)
+{
+	int child_index = -1;
+	struct tree_node *parent = tree_find_parent(tree, remove_node, &child_index);
+	if (parent != NULL) {
+		struct tree_node *freethis = list_remove_by_index(parent->children, child_index);
+		kfree(freethis);
+	}
+}
+
+void tree2list_recur(struct tree_node *subroot, struct list *list)
+{
+	if (subroot == NULL)
+		return;
+	foreach(child, subroot->children)
+	{
+		struct tree_node *curr_treenode = (struct tree_node *)child->val;
+		void *curr_val = curr_treenode->value;
+		list_insert_back(list, curr_val);
+		tree2list_recur(child->val, list);
+	}
+}
+
+void tree2list(struct tree *tree, struct list *list)
+{
+	tree2list_recur(tree->root, list);
+}
+
+void tree2array(struct tree *tree, void **array, int *size)
+{
+	tree2array_recur(tree->root, array, size);
+}
+
+void tree2array_recur(struct tree_node *subroot, void **array, int *size)
+{
+	if (subroot == NULL)
+		return;
+	void *curr_val = (void *)subroot->value;
+	array[*size] = curr_val;
+	*size = *size + 1;
+	foreach(child, subroot->children)
+	{
+		tree2array_recur(child->val, array, size);
+	}
+}