From b840ec8bc225c10d9f7eb9448dbe07702e885d23 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 16 Jul 2020 23:32:51 -0400 Subject: [PATCH] maple_tree: not much Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 30 ++++++++---------------------- 1 file changed, 8 insertions(+), 22 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 9f1ca66f9778..3151891ce66f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1877,7 +1877,7 @@ mast_ascend_free(struct maple_subtree_state *mast) } static inline struct maple_enode -*mas_b_node_ma_node(struct ma_state *mas, struct maple_big_node *b_node) +*mas_new_ma_node(struct ma_state *mas, struct maple_big_node *b_node) { return mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), b_node->type); } @@ -1903,7 +1903,7 @@ static inline unsigned char mas_mab_to_node(struct ma_state *mas, unsigned char split = 0; unsigned char slot_cnt = mt_slots[b_node->type]; - *left = mas_b_node_ma_node(mas, b_node); + *left = mas_new_ma_node(mas, b_node); *right = NULL; *middle = NULL; *mid_split = 0; @@ -1912,11 +1912,11 @@ static inline unsigned char mas_mab_to_node(struct ma_state *mas, split = b_node->b_end; } else { split = mab_calc_split(b_node, mid_split); - *right = mas_b_node_ma_node(mas, b_node); + *right = mas_new_ma_node(mas, b_node); } if (*mid_split) - *middle = mas_b_node_ma_node(mas, b_node); + *middle = mas_new_ma_node(mas, b_node); return split; @@ -2143,7 +2143,6 @@ static inline int mas_combine_separate(struct ma_state *mas, split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, &mid_split); mast_set_split_parents(mast, left, right, split); - mast_cp_to_nodes(mast, left, middle, right, split, mid_split); /* Copy data from next level in the tree to mast->bn from next iteration */ @@ -2265,26 +2264,14 @@ static inline int mas_split(struct ma_state *mas, MA_TOPIARY(mat, mas->tree); - // Allocation failures will happen early. - // TODO: Increase this by one when optimizing with a rebalance. mas_node_cnt(mas, 1 + mas->full_cnt * 2); if (mas_is_err(mas)) return 0; - /* At the start of the loop, the maple state points to the leaf that - * needs to be split. The loop walks up and splits all nodes that need - * to be split. Obviously it will overflow nodes that need to be split, - * so leaf is split into two and then placed in a maple_big_node which - * has enough space. Each iteration after that will use the - * maple_big_node data to split equally left and right until the height - * is larger than mas->full_cnt which will place the maple_big_node data - * into the highest common ancestor necessary to be modified (which may - * be a new root). - */ while (height++ <= mas->full_cnt) { unsigned char mid_split; - unsigned char slot_cnt = mt_slot_count(mas->node); /* should be full. */ + unsigned char slot_cnt = mt_slot_count(mas->node); bool cp = true; b_node->type = mte_node_type(mas->node); @@ -2300,8 +2287,7 @@ static inline int mas_split(struct ma_state *mas, /* Only a single node is used here, could be root. * Big_node should just fit in a single node. */ - ancestor = mas_b_node_ma_node(mas, b_node); - // Set the parents + ancestor = mas_new_ma_node(mas, b_node); mte_set_parent(l_mas.node, ancestor, mas_get_slot(&l_mas)); mte_set_parent(r_mas.node, ancestor, @@ -2319,8 +2305,8 @@ static inline int mas_split(struct ma_state *mas, b_node->min = mas->min; mas_dup_state(&l_mas, mas); mas_dup_state(&r_mas, mas); - l_mas.node = mas_b_node_ma_node(mas, b_node); - r_mas.node = mas_b_node_ma_node(mas, b_node); + l_mas.node = mas_new_ma_node(mas, b_node); + r_mas.node = mas_new_ma_node(mas, b_node); if (mte_is_leaf(mas->node)) { split = mab_calc_split(b_node, &mid_split); if (split < slot_cnt) -- 2.50.1