From 67627078d235b60a76ec6e5144790cf9d7f3ce39 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 16 Jul 2020 11:50:27 -0400 Subject: [PATCH] maple_tree: Start using b_node->b_end in mas_split Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 49 +++++++++++++++--------------------------------- 1 file changed, 15 insertions(+), 34 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 5fc0ef6d9915..8470e46bfa56 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2209,7 +2209,6 @@ static inline int mas_split(struct ma_state *mas, * into the highest common ancestor necessary to be modified (which may * be a new root). */ - //list[i++] = mas->node; while (height++ <= mas->full_cnt) { struct maple_node *l, *r; enum maple_type type = mte_node_type(mas->node); @@ -2231,27 +2230,18 @@ static inline int mas_split(struct ma_state *mas, */ ancestor = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), type); - for (j = 0; j < mt_slots[type]; j++) { - if (!b_node->pivot[j]) - break; - mte_set_rcu_slot(ancestor, j, b_node->slot[j]); - if (j < mt_pivots[type]) - mte_set_pivot(ancestor, j, - b_node->pivot[j]); - if (mt_is_alloc(mas->tree)) { - mte_set_gap(ancestor, j, - b_node->gap[j]); - } - } - // Set the parent for the children. + // Set the parents mte_set_parent(l_mas.node, ancestor, mas_get_slot(&l_mas)); mte_set_parent(r_mas.node, ancestor, mas_get_slot(&r_mas)); mte_to_node(ancestor)->parent = mas_mn(mas)->parent; + // New root requires a new height. if (mas->full_cnt >= mas->tree->ma_height) mas->tree->ma_height++; - continue; + l_mas.node = ancestor; + mab_mas_cp(b_node, 0, mt_slots[type] - 1, &l_mas, 0); + break; } b_node->min = mas->min; @@ -2272,10 +2262,8 @@ static inline int mas_split(struct ma_state *mas, mte_set_pivot(r_mas.node, 0, r_mas.max); mab_mas_cp(b_node, j, b_node->b_end, &r_mas, 0); - mas_set_slot(&l_mas, mte_parent_slot(mas->node)); r_mas.min = l_mas.max + 1; - // In the case of empty. mas_set_slot(&r_mas, mas_get_slot(&l_mas) + 1); } else { @@ -2314,7 +2302,7 @@ static inline int mas_split(struct ma_state *mas, } } - j = 0; + b_node->b_end = 0; memset(b_node, 0, sizeof(struct maple_big_node)); if (mte_is_root(mas->node)) cp = false; @@ -2327,26 +2315,19 @@ static inline int mas_split(struct ma_state *mas, } if (cp && mas_get_slot(&l_mas)) - j = mas_mab_cp(mas, 0, mas_get_slot(&l_mas) - 1, - b_node, 0); - - split = j; - b_node->slot[j] = l_mas.node; - b_node->pivot[j] = l_mas.max; - mas_set_slot(&l_mas, j); - if (mt_is_alloc(mas->tree)) { - b_node->gap[j] = mas_find_gap(&l_mas); - b_node->gap[j + 1] = mas_find_gap(&r_mas); - } - b_node->slot[++j] = r_mas.node; - b_node->pivot[j] = r_mas.max; - mas_set_slot(&r_mas, j); + b_node->b_end = mas_mab_cp(mas, 0, + mas_get_slot(&l_mas) - 1, b_node, 0); + + split = b_node->b_end; + mab_set_b_end(b_node, &l_mas, l_mas.node); + mas_set_slot(&r_mas, b_node->b_end); + mab_set_b_end(b_node, &r_mas, r_mas.node); mas_dup_state(&orig_l_mas, &l_mas); mas_dup_state(&orig_r_mas, &r_mas); if (cp) - j = mas_mab_cp(mas, split + 1, + b_node->b_end = mas_mab_cp(mas, split + 1, mt_slot_count(mas->node) - 1, b_node, - j + 1); + b_node->b_end); } // Set the original node as dead -- 2.50.1