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
|
# Memory Pool
---
## Object Definitions
```c
#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_HEADER(STRUCT); STRUCT *next;
typdef struct _kpl_alloc_tree_obj {
KPL_ALLOC_TREE_HEADER(struct _kpl_alloc_tree_obj);
} kpl_alloc_tree_obj;
typedef struct kpl_alloc {
_Atomic size_t bytes_allocated;
kpl_mutex mutex;
kpl_alloc_obj *pool[KPL_ALLOC_POOL_SIZE]
} kpl_alloc;
#define KPL_SLAB_HEADER(STRUCT) STRCUT *prev
typdef strcut _kpl_slab_obj {
KPL_SLAB_HEADER(strcut _kpl_slab_obj);
} kpl_slab_obj;
#define KPL_SLAB_LIST_HEADER(STRCUT) STRCUT *prev, *next
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; uin32_t tree_weight : KPL_TREE_WEIGHT
typdef strcut _kpl_slab_tree_obj {
KPL_SLAB_TREE_HEADER(struct _kpl_slab_tree_obj);
} kpl_slab_tree_obj;
typdef struct _kpl_slab_bucket {
struct _kpl_slab_bucket *next;
uint8_t byte_obj_array[];
} kpl_slab_bucket;
typedef struct _kpl_slab {
uint16_t obj_count, obj_index;
uint32_t obj_size;
kpl_slab_obj *pool;
kpl_slab_bucket *bucket;
kpl_mutex mutex;
} kpl_slab;
```
# Alloc
All allocated objects size must be aligned to the power of two
## Pooling
Each bucket in the `kpl_alloc.pool` represents two to the power of the bucket index
# Slab
## 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;
}
```
|
