use trees without parent nodes

4 files changed, 136 insertions, 36 deletions

diff --git a/docs/application/index.md b/docs/application/index.md
index a534225..c6153b6 100644
--- a/docs/application/index.md
+++ b/docs/application/index.md
@@ -44,11 +44,12 @@
 2.  ##### [Parse](../lifecycle/parse.md)
 3.  ##### Scan
 4.  ##### Scope
-5.  ##### Check
-6.  ##### Eval
-7.  ##### Ir
-8.  ##### Jit
-9.  ##### Exec
-10. ##### Notify
+5.  ##### Import
+6.  ##### Check
+7.  ##### Eval
+8.  ##### Ir
+9.  ##### Jit
+10. ##### Exec
+11. ##### Notify
 
 ## Shutdown
diff --git a/docs/application/memory.md b/docs/application/memory.md
index 61a59f9..a7eab83 100644
--- a/docs/application/memory.md
+++ b/docs/application/memory.md
@@ -5,20 +5,22 @@
 ## Object Definitions
 
 ```c
-#define KPL_ALLOC_HEADER(STRCUT) size_t obj_size : 56; int8_t tree_weight; STRCUT *prev
+#define KPL_ALLOC_POOL_SIZE 40
+
+#define KPL_TREE_WEIGHT 24
+
+#define KPL_ALLOC_HEADER(STRCUT) size_t obj_size : KPL_ALLOC_POOL_SIZE; uint32_t tree_weight : KPL_TREE_WEIGHT; STRCUT *prev
 
 typedef struct _kpl_alloc_obj {
     KPL_ALLOC_HEADER(_kpl_alloc_obj);
 } kpl_alloc_obj;
 
-#define KPL_ALLOC_TREE_HEADER(STRCUT) KPL_ALLOC_TREE_HEADER(STRUCT); STRUCT *next, *parent
+#define KPL_ALLOC_TREE_HEADER(STRCUT) KPL_ALLOC_HEADER(STRUCT); STRUCT *next;
 
 typdef struct _kpl_alloc_tree_obj {
     KPL_ALLOC_TREE_HEADER(struct _kpl_alloc_tree_obj);
 } kpl_alloc_tree_obj;
 
-#define KPL_ALLOC_POOL_SIZE 56
-
 typedef struct kpl_alloc {
     _Atomic size_t bytes_allocated;
     kpl_mutex mutex;
@@ -37,7 +39,7 @@ typdef strcut _kpl_slab_list_obj {
     KPL_SLAB_LIST_HEADER(strcut _kpl_slab_list_obj);
 } kpl_slab_list_obj;
 
-#define KPL_SLAB_TREE_HEADER(STRUCT) STRUCT *prev, *next, *parent; int8_t tree_weight
+#define KPL_SLAB_TREE_HEADER(STRUCT) STRUCT *prev, *next; uin32_t tree_weight : KPL_TREE_WEIGHT
 
 typdef strcut _kpl_slab_tree_obj {
     KPL_SLAB_TREE_HEADER(struct _kpl_slab_tree_obj);
@@ -60,8 +62,6 @@ All allocated objects size must be aligned to the power of two
 
 Each bucket in the `kpl_alloc.pool` represents two to the power of the bucket index
 
-# AVL Tree For Slab And Alloc
-
 # Slab
 
 Allocated by `kpl_alloc`
@@ -69,3 +69,80 @@ Allocated by `kpl_alloc`
 ## Pooling
 
 Objects for reuse are stored as a list by the `kpl_slab_obj.prev` on `kpl_slab.pool`
+
+# AVL Tree For Slab And Alloc
+
+## AVL Tree Example
+
+```c
+typedef struct _avl {
+    int val, count;
+    struct _avl *left, *right;
+} avl;
+
+
+int get_count(const avl *node) {
+    return node ? node->count : 0;
+}
+
+int get_balance(const avl *node) {
+    if (!node)
+        return 0;
+    return get_count(node->left) - get_count(node->right);
+}
+
+void right_rotate(avl **right) {
+    avl *left = (*right)->left, *left_right = left->right;
+    left->right = *right;
+    (*right)->left = left_right;
+    (*right)->count = MAX(get_count((*right)->left), get_count((*right)->right)) + 1;
+    left->count = MAX(get_count(left->left), get_count(left->right)) + 1;
+    *right = left;
+}
+
+void left_rotate(avl **left) {
+    avl *right = (*left)->right, *right_left = right->left;
+    right->left = *left;
+    (*left)->right = right_left;
+    (*left)->count = MAX(get_count((*left)->left), get_count((*left)->right)) + 1;
+    right->count = MAX(get_count(right->left), get_count(right->right)) + 1;
+    *left = right;
+}
+
+void insert(avl **parent, avl *node) {
+    if (!*parent) {
+        *parent = node;
+        return;
+    }
+    if (node->val < (*parent)->val)
+        insert(&(*parent)->left, node);
+    else
+        insert(&(*parent)->right, node);
+    (*parent)->count = MAX(get_count((*parent)->left), get_count((*parent)->right)) + 1;
+    int balance = get_balance(*parent);
+    if (balance > 1 && get_balance((*parent)->left) >= 0)
+        right_rotate(parent);
+    if (balance > 1 && get_balance((*parent)->left) > 0) {
+        left_rotate(&(*parent)->left);
+        right_rotate(parent);
+    }
+    if (balance < -1 && get_balance((*parent)->right) <= 0)
+        left_rotate(parent);
+    if (balance < -1 && get_balance((*parent)->right) > 0) {
+        right_rotate(&(*parent)->right);
+        left_rotate(parent);
+    }
+}
+
+struct TreeNode* sortedListToBST(struct ListNode* head) {
+    avl *root = NULL;
+    while (head) {
+        avl *node = calloc(1, sizeof(avl));
+        node->val = head->val;
+        node->count = 1;
+        head = head->next;
+        insert(&root, node);
+    }
+    return (struct TreeNode*) root;
+}
+```
diff --git a/docs/application/name.md b/docs/application/name.md
index 3db91dc..3c00aa0 100644
--- a/docs/application/name.md
+++ b/docs/application/name.md
@@ -11,9 +11,4 @@ typedef struct _kpl_name {
     KPL_ALLOC_TREE_HEADER(struct _kpl_name);
     char c_str[];
 } kpl_name;
-
-typedef strcut {
-    kpl_name *root;
-    kpl_mutex mutex;
-} kpl_name_tree;
 ```
diff --git a/docs/application/namespace.md b/docs/application/namespace.md
index e6809d5..b8caea7 100644
--- a/docs/application/namespace.md
+++ b/docs/application/namespace.md
@@ -6,43 +6,50 @@
 
 ```c
 typedef struct _kpl_export {
-    KPL_SLAB_TREE_HEADER(struct _kpl_export);
+    KPL_ALLOC_TREE_HEADER(struct _kpl_export);
     kpl_type_ptr type;
 } kpl_export;
 
 typedef struct _kpl_namespace_native {
     KPL_SLAB_TREE_HEADER(struct _kpl_namespace_native);
-    kpl_buffer *name;
-    kpl_export *exports;
+    const char *name;
+    kpl_export *export_tree;
 } kpl_namespace_native;
 
-static kpl_namespace_native *namespace_native_head;
+static kpl_namespace_native namespace_native_tree;
+
+typedef enum : uint8_t {
+    // ...
+} namespace_lifecycle;
 
 typedef struct _kpl_namespace_module {
     KPL_SLAB_TREE_HEADER(struct _kpl_namespace_module);
     kpl_type_ptr ast;
-    kpl_queue *parents;
+    kpl_name *name_tree;
     kpl_buffer *module_name, *module_string;
-    kpl_export *exports;
-    kpl_task *task;
-    _Atomic int32_t children;
+    kpl_export *export_tree;
+    kpl_mutex mutex;
 } kpl_namespace_module;
 
-static kpl_namespace_module *namespace_module_head;
+static kpl_namespace_module *namespace_module_tree;
+
+kpl_mutex namespace_module_mutex;
 
 typedef struct _kpl_namespace_string {
-    kpl_buffer *string;
-    kpl_task *task;
     kpl_type_ptr ast;
-    _Atomic int32_t children;
+    kpl_name *name_tree;
+    kpl_buffer *string;
+    kpl_mutex mutex;
 } kpl_namespace_string;
+
+static kpl_namespace_string namespace_string
 ```
 
 Each `NAMESPACE_IDENTIFIER` maps to `kpl_namespace_native*` or `kpl_namespace_module*` depending on flags
 
 ## Lookup and Storage
 
-The native and namespace objects are stored as a tree under `namespace_native_head` and `namespace_module_head`
+The native and namespace objects are stored as a tree
 
 The exports are stored under a tree for both the native and namespace objects
 
@@ -50,26 +57,46 @@ The exports are stored under a tree for both the native and namespace objects
 
 ## Native
 
-## Module
+TODO C code for exposing native code
+
+## Module/String/REPL
 
 ### Main
 
-### ``import`
+Begin life cycle and [Register](../lifecycle/register.md)
 
-## String/REPL
+### Scan ``import`
+
+Add a [Register](../lifecycle/regiser.md) task to `namespace_module_mutex`
 
 # Updating
 
+## Native
+
+### Native code should not be updated at runtime, doing so is undefined behavior
+
 ## Module
 
 ### ``export`
 
+Add exports directly to the namespaces `export_tree`, thread safe
+
+## String/REPL
+
+### Cannot export for String/REPL
+
 # Using
 
 ## Native
 
 ### ``use`
 
-## Module
+Since the native modules are loaded statically the `native_module_tree` becomes read only at runtime, access is thread safe
+
+## Module/String/REPL
+
+### Import ``import`
 
-### ``import`
+1. Add find namespace task to the `namespace_module_mutex`, the namespace not existing is an error
+2. Add task to the namespaces `mutex`
+3. The task will resume the importer