lib/mdb/mdb_tree.c

635 mdb_exchange_child(struct cte *first, struct cte *first_parent,
638     assert(mdb_is_child(first, first_parent));
643     else if (N(first_parent)->left == first) {
646     else if (N(first_parent)->right == first) {
650         assert(!"first is not child of first_parent");
655 mdb_exchange_nodes(struct cte *first, struct cte *first_parent,
661     mdb_exchange_child(first, first_parent, second);
662     mdb_exchange_child(second, second_parent, first);
664     tmp_node = N(first)->left;
665     N(first)->left = N(second)->left;
668     tmp_node = N(first)->right;
669     N(first)->right = N(second)->right;
672     tmp_level = N(first)->level;
673     N(first)->level = N(second)->level;
676     mdb_update_end(first);
679     assert(mdb_is_reachable(mdb_root, first));
1018 mdb_choose_surrounding(genpaddr_t address, size_t size, struct cte *first,
1021     assert(first);
1023     assert(get_type_root(C(first)->type) == get_type_root(C(second)->type));
1026     genpaddr_t fst_beg = get_address(C(first));
1028     genpaddr_t fst_end = fst_beg + get_size(C(first));
1034     if (compare_caps(C(first), C(second), true) >= 0) {
1035         return first;
1043 mdb_choose_inner(genpaddr_t address, size_t size, struct cte *first,
1046     assert(first);
1048     assert(get_type_root(C(first)->type) == get_type_root(C(second)->type));
1051     genpaddr_t fst_beg = get_address(C(first));
1053     genpaddr_t fst_end = fst_beg + get_size(C(first));
1059     if (compare_caps(C(first), C(second), true) <= 0) {
1060         return first;
1068 mdb_choose_partial(genpaddr_t address, size_t size, struct cte *first,
1071     assert(first);
1073     assert(get_type_root(C(first)->type) == get_type_root(C(second)->type));
1075     genpaddr_t fst_beg = get_address(C(first));
1079     genpaddr_t fst_end = fst_beg + get_size(C(first));
1094         return first;
1100         if (compare_caps(C(first), C(second), true) >= 0) {
1101             return first;
1317     struct cte *first, *second;
1319         first = node->left;
1322         first = node->right;
1328     if (first) {
1329         err = mdb_traverse_subtree(first, order, cb, data);