aboutsummaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/arch/x86_64/arch.h2
-rw-r--r--include/kern/common.h1
-rw-r--r--include/kern/mem.h2
-rw-r--r--include/shared/avl_tree.h271
-rw-r--r--include/shared/map.h90
-rw-r--r--include/shared/stdmacro.h7
6 files changed, 372 insertions, 1 deletions
diff --git a/include/arch/x86_64/arch.h b/include/arch/x86_64/arch.h
index 1848b58..15ebd6d 100644
--- a/include/arch/x86_64/arch.h
+++ b/include/arch/x86_64/arch.h
@@ -41,6 +41,6 @@
// testing.
#define GHOST_DATA_SEGMENT_SIZE 1200
#define HEAP_START (*(((unsigned char*)SRAM1_BASE) + GHOST_DATA_SEGMENT_SIZE))
-#define HEAP_STOP (*(&HEAP_START + 16384 - GHOST_DATA_SEGMENT_SIZE))
+#define HEAP_STOP (*(&HEAP_START + 49152 - GHOST_DATA_SEGMENT_SIZE))
#endif /* ARCH_H_ */
diff --git a/include/kern/common.h b/include/kern/common.h
index 021229b..0acc9d3 100644
--- a/include/kern/common.h
+++ b/include/kern/common.h
@@ -39,6 +39,7 @@ typedef enum { ENDIANNESS_LITTLE, ENDIANNESS_BIG } endianness_t;
#define ptr2reg(ptr) ((uint32_t)(ptrdiff_t)(ptr))
typedef __IO uint32_t bits_t;
+typedef uint16_t msize_t;
#define regset(reg, mask, val) ((reg) = ((reg) & ~mask) | (val << CTZ(mask)))
diff --git a/include/kern/mem.h b/include/kern/mem.h
index 20b09bb..bc6c4e2 100644
--- a/include/kern/mem.h
+++ b/include/kern/mem.h
@@ -22,6 +22,8 @@ int debug_kalloc_assert_consistency(char* error, size_t len);
void debug_print_blocks();
+int debug_is_heap_empty();
+
#endif
diff --git a/include/shared/avl_tree.h b/include/shared/avl_tree.h
new file mode 100644
index 0000000..98151f2
--- /dev/null
+++ b/include/shared/avl_tree.h
@@ -0,0 +1,271 @@
+#ifndef _SHARED_AVL_TREE_H_
+#define _SHARED_AVL_TREE_H_
+
+#define ALLOC kalloc
+#define FREE kfree
+
+#include <assert.h>
+#include <stdio.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)
+
+typedef unsigned int bool;
+
+#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/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/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_ */
generated by cgit (git 2.34.1) at 2025-07-03 04:54:37 +0000