Lines Matching refs:varea
22 static void _print_varea(rt_varea_t varea, int depth) in _print_varea() argument
26 printf("%p ", varea->start); in _print_varea()
30 rt_varea_t lchild = VAREA_ENTRY(varea->node.node.avl_left); in _print_varea()
31 rt_varea_t rchild = VAREA_ENTRY(varea->node.node.avl_right); in _print_varea()
46 rt_varea_t varea = VAREA_ENTRY(aspace->tree.tree.root_node); in _print_tree() local
47 if (!varea) in _print_tree()
51 _print_varea(varea, i); in _print_tree()
58 static int _is_bst(rt_varea_t varea) in _is_bst() argument
60 rt_varea_t lchild = VAREA_ENTRY(varea->node.node.avl_left); in _is_bst()
61 rt_varea_t rchild = VAREA_ENTRY(varea->node.node.avl_right); in _is_bst()
64 RT_ASSERT(lchild->node.node.parent == &varea->node.node); in _is_bst()
65 RT_ASSERT(varea->start > lchild->start); in _is_bst()
69 RT_ASSERT(rchild->node.node.parent == &varea->node.node); in _is_bst()
70 if (varea->start >= rchild->start) in _is_bst()
79 static int _is_balanced(rt_varea_t varea) in _is_balanced() argument
81 if (!varea) in _is_balanced()
86 rt_varea_t lchild = VAREA_ENTRY(varea->node.node.avl_left); in _is_balanced()
87 rt_varea_t rchild = VAREA_ENTRY(varea->node.node.avl_right); in _is_balanced()
108 static int _check_asc_before(rt_varea_t varea, void *arg) in _check_asc_before() argument
110 if (varea->start >= _start && (!_boundary || varea->start >= _boundary) && _is_bst(varea)) in _check_asc_before()
112 _buf[_count] = varea; in _check_asc_before()
113 _start = varea->start; in _check_asc_before()
114 _boundary = varea->start + varea->size; in _check_asc_before()
125 static int _check_asc_before_rev(rt_varea_t varea, void *arg) in _check_asc_before_rev() argument
128 RT_ASSERT(varea == _buf[_count]); in _check_asc_before_rev()
132 static int _check_asc_after(rt_varea_t varea, void *arg) in _check_asc_after() argument
135 if (!_is_bst(varea)) in _check_asc_after()
140 if (varea == _buf[_count]) in _check_asc_after()
146 else if (add_elem && add_elem == varea) in _check_asc_after()
150 else if (!add_elem && varea == _buf[_count + 1]) in _check_asc_after()
161 add_elem->start, varea->start, _count, _buf[_count]); in _check_asc_after()
167 static int _aspace_traversal(rt_aspace_t aspace, int (*fn)(rt_varea_t varea, void *arg), void *arg) in _aspace_traversal() argument
169 rt_varea_t varea = ASPACE_VAREA_FIRST(aspace); in _aspace_traversal() local
170 while (varea) in _aspace_traversal()
172 fn(varea, arg); in _aspace_traversal()
173 varea = ASPACE_VAREA_NEXT(varea); in _aspace_traversal()
179 static int _aspace_traversal_reverse(rt_aspace_t aspace, int (*fn)(rt_varea_t varea, void *arg), vo… in _aspace_traversal_reverse() argument
181 rt_varea_t varea = ASPACE_VAREA_LAST(aspace); in _aspace_traversal_reverse() local
182 while (varea) in _aspace_traversal_reverse()
184 fn(varea, arg); in _aspace_traversal_reverse()
185 varea = ASPACE_VAREA_PREV(varea); in _aspace_traversal_reverse()
191 static int _check_bst_before(struct rt_aspace *aspace, struct rt_varea *varea) in _check_bst_before() argument
204 _aspace_traversal(aspace, _check_asc_before, varea); in _check_bst_before()
206 _aspace_traversal_reverse(aspace, _check_asc_before_rev, varea); in _check_bst_before()
212 static int _check_bst_after(struct rt_aspace *aspace, struct rt_varea *varea, int isdel) in _check_bst_after() argument
224 _aspace_traversal(aspace, _check_asc_after, isdel ? NULL : varea); in _check_bst_after()
367 rt_varea_t varea = VAREA_ENTRY(node); in search() local
368 int cmp = compare(range.start, range.end, varea->start, in search()
369 varea->start + varea->size - 1); in search()
381 return varea; in search()
402 rt_varea_t varea = VAREA_ENTRY(node); in _aspace_bst_search_exceed() local
403 void *va_s = varea->start; in _aspace_bst_search_exceed()
412 closest = varea; in _aspace_bst_search_exceed()
422 return varea; in _aspace_bst_search_exceed()
442 void _aspace_bst_insert(struct rt_aspace *aspace, struct rt_varea *varea) in _aspace_bst_insert() argument
447 rt_ubase_t key = (rt_ubase_t)varea->start; in _aspace_bst_insert()
464 _check_bst_before(aspace, varea); in _aspace_bst_insert()
465 util_avl_link(&varea->node.node, current, next); in _aspace_bst_insert()
467 _check_bst_after(aspace, varea, 0); in _aspace_bst_insert()
471 void _aspace_bst_remove(struct rt_aspace *aspace, struct rt_varea *varea) in _aspace_bst_remove() argument
473 struct util_avl_struct *node = &varea->node.node; in _aspace_bst_remove()
474 _check_bst_before(aspace, varea); in _aspace_bst_remove()
476 _check_bst_after(aspace, varea, 1); in _aspace_bst_remove()
517 struct rt_varea *varea; in insert_test() local
518 varea = &_varea_buf[i]; in insert_test()
519 varea->start = (void *)(uintptr_t)dataset[i]; in insert_test()
520 varea->size = 1; in insert_test()
521 _aspace_bst_insert(&aspace, varea); in insert_test()
530 struct rt_varea *varea; in search_test() local
531 varea = _aspace_bst_search(&aspace, start); in search_test()
532 assert(varea); in search_test()
533 assert(varea->start == start); in search_test()
542 struct rt_varea *varea; in delete_test() local
543 varea = _aspace_bst_search(&aspace, start); in delete_test()
544 _aspace_bst_remove(&aspace, varea); in delete_test()