1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
# 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;
}
```
|
