# Namespace

---

## Object Definitions

```c
typedef struct _kpl_export {
    size_t tree_weight;
    struct _kpl_export *tree_left, *tree_right;
    kpl_type_ptr type;
} kpl_export;

typedef struct _kpl_namespace_native {
    size_t tree_weight;
    struct _kpl_namespace_native *tree_left, *tree_right;
    const char *name;
    kpl_export *export_tree;
} kpl_namespace_native;

static kpl_namespace_native *namespace_native_tree;

typedef struct _kpl_namespace_module {
    size_t tree_weight;
    struct _kpl_namespace_module *tree_left, *tree_right;
    kpl_buffer *module_string, *module_name;
    kpl_export *export_tree;
    kpl_mutex export_mutex;
    kpl_type_ptr ast;
} kpl_namespace_module;

static kpl_namespace_module *namespace_module_tree;

kpl_mutex namespace_modul_tree_mutex;

static kpl_namespace_module 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

The exports are stored under a tree for both the native and namespace objects

# Registering

## Native

TODO C code for exposing native code

## Module/String/REPL

### Main

Begin life cycle and [Register](../lifecycle/register.md)

### Scan ``import`

Add a [Register](../lifecycle/register.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`

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`

1. Add find namespace task to the `namespace_module_mutex`, the namespace not existing is an error
2. Add a get export task to the namespaces `export_mutex`
3. The `export_mutex` will not start processing it's queue until the namespace notifies that it's and unlocks its `export_mutex`
4. The importer will get a copy of the read only `export_tree`

# AVL Tree Storage and Lookup

## 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;
}
```