1 /*
2 * Copyright (c) 2006-2022, RT-Thread Development Team
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 *
6 * Change Logs:
7 * Date Author Notes
8 * 2022-11-14 WangXiaoyao the first version
9 */
10 #include <rtdef.h>
11
12 #include <avl.h>
13 #include "avl_adpt.h"
14 #include "mm_aspace.h"
15 #include "mm_private.h"
16
17 #define DBG_TAG "MM"
18 #define DBG_LVL DBG_INFO
19 #include <rtdbg.h>
20
21 /**
22 * @brief Adapter Layer for lwp AVL BST
23 */
24
_aspace_bst_init(struct rt_aspace * aspace)25 rt_err_t _aspace_bst_init(struct rt_aspace *aspace)
26 {
27 aspace->tree.tree.root_node = AVL_ROOT;
28 return RT_EOK;
29 }
30
compare_overlap(void * as,void * ae,void * bs,void * be)31 static int compare_overlap(void *as, void *ae, void *bs, void *be)
32 {
33 LOG_D("as %lx, ae %lx, bs %lx, be %lx", as, ae, bs, be);
34 int cmp;
35 if (as > be)
36 {
37 cmp = 1;
38 }
39 else if (ae < bs)
40 {
41 cmp = -1;
42 }
43 else
44 {
45 cmp = 0;
46 }
47 LOG_D("ret %d", cmp);
48 return cmp;
49 }
50
compare_exceed(void * as,void * ae,void * bs,void * be)51 static int compare_exceed(void *as, void *ae, void *bs, void *be)
52 {
53 LOG_D("as %lx, ae %lx, bs %lx, be %lx", as, ae, bs, be);
54 int cmp;
55 if (as > bs)
56 {
57 cmp = 1;
58 }
59 else if (as < bs)
60 {
61 cmp = -1;
62 }
63 else
64 {
65 cmp = 0;
66 }
67 LOG_D("ret %d", cmp);
68 return cmp;
69 }
70
search(struct util_avl_root * root,struct _mm_range range,int (* compare)(void * as,void * ae,void * bs,void * be))71 static struct rt_varea *search(struct util_avl_root *root,
72 struct _mm_range range,
73 int (*compare)(void *as, void *ae, void *bs,
74 void *be))
75 {
76 struct util_avl_struct *node = root->root_node;
77 while (node)
78 {
79 rt_varea_t varea = VAREA_ENTRY(node);
80 int cmp = compare(range.start, range.end, varea->start,
81 (char *)varea->start + varea->size - 1);
82
83 if (cmp < 0)
84 {
85 node = node->avl_left;
86 }
87 else if (cmp > 0)
88 {
89 node = node->avl_right;
90 }
91 else
92 {
93 return varea;
94 }
95 }
96 return NULL;
97 }
98
_aspace_bst_search(struct rt_aspace * aspace,void * key)99 struct rt_varea *_aspace_bst_search(struct rt_aspace *aspace, void *key)
100 {
101 struct util_avl_root *root = &aspace->tree.tree;
102 struct _mm_range range = {key, key};
103 return search(root, range, compare_overlap);
104 }
105
_aspace_bst_search_exceed(struct rt_aspace * aspace,void * start)106 rt_varea_t _aspace_bst_search_exceed(struct rt_aspace *aspace, void *start)
107 {
108 struct util_avl_root *root = &aspace->tree.tree;
109 struct util_avl_struct *node = root->root_node;
110 rt_varea_t closest = NULL;
111 ptrdiff_t min_off = PTRDIFF_MAX;
112 while (node)
113 {
114 rt_varea_t varea = VAREA_ENTRY(node);
115 void *va_s = varea->start;
116 int cmp = compare_exceed(start, start, va_s, va_s);
117
118 if (cmp < 0)
119 {
120 /* varae exceed start */
121 ptrdiff_t off = (char *)va_s - (char *)start;
122 if (off < min_off)
123 {
124 min_off = off;
125 closest = varea;
126 }
127 node = node->avl_left;
128 }
129 else if (cmp > 0)
130 {
131 /* find the next huger varea */
132 node = node->avl_right;
133 }
134 else
135 {
136 return varea;
137 }
138 }
139 return closest;
140 }
141
_aspace_bst_search_overlap(struct rt_aspace * aspace,struct _mm_range range)142 struct rt_varea *_aspace_bst_search_overlap(struct rt_aspace *aspace,
143 struct _mm_range range)
144 {
145 struct util_avl_root *root = &aspace->tree.tree;
146 return search(root, range, compare_overlap);
147 }
148
_aspace_bst_insert(struct rt_aspace * aspace,struct rt_varea * varea)149 void _aspace_bst_insert(struct rt_aspace *aspace, struct rt_varea *varea)
150 {
151 struct util_avl_root *root = &aspace->tree.tree;
152 struct util_avl_struct *current = NULL;
153 struct util_avl_struct **next = &(root->root_node);
154 rt_ubase_t key = (rt_ubase_t)varea->start;
155
156 /* Figure out where to put new node */
157 while (*next)
158 {
159 current = *next;
160 struct rt_varea *data = VAREA_ENTRY(current);
161
162 if (key < (rt_ubase_t)data->start)
163 next = &(current->avl_left);
164 else if (key > (rt_ubase_t)data->start)
165 next = &(current->avl_right);
166 else
167 return;
168 }
169
170 /* Add new node and rebalance tree. */
171 util_avl_link(&varea->node.node, current, next);
172 util_avl_rebalance(current, root);
173 return;
174 }
175
_aspace_bst_remove(struct rt_aspace * aspace,struct rt_varea * varea)176 void _aspace_bst_remove(struct rt_aspace *aspace, struct rt_varea *varea)
177 {
178 struct util_avl_struct *node = &varea->node.node;
179 util_avl_remove(node, &aspace->tree.tree);
180 }
181