From 90e4024478b85be67386512945744db1831882ef Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 16 Jul 2020 22:51:43 -0400 Subject: [PATCH] maple_tree: Cleaner check in combine_separate Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 61 ++++++++++++++++++++++++------------------------ 1 file changed, 30 insertions(+), 31 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index c423fe7bd5c7..5f9d20c5e3e1 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1835,19 +1835,44 @@ static inline bool mast_rebalance_from_cousins(struct maple_subtree_state *mast) mas_set_slot(mast->l, mas_get_slot(mast->l) + end + 1); return true; } - +/* Private + * mast_ascend_free() - ascend orig_l and orig_r and add the child nodes to the + * free list. Set the slots to point to the correct location in the parents of + * those children. + * + * @mast - the maple subtree state. + */ static inline void mast_ascend_free(struct maple_subtree_state *mast) { struct maple_enode *left = mast->orig_l->node; struct maple_enode *right = mast->orig_r->node; + unsigned long range_min, range_max; + mas_ascend(mast->orig_l); mas_ascend(mast->orig_r); mat_add(mast->free, left); if (left != right) mat_add(mast->free, right); - mas_set_slot(mast->orig_l, 0); + mas_set_slot(mast->orig_r, 0); + mast->orig_r->index = mast->r->max; + /* last should be larger than or equal to index */ + if (mast->orig_r->last < mast->orig_r->index) + mast->orig_r->last = mast->orig_r->index; + /* The node may not contain the value so set slot to ensure all + * of the nodes contents are freed or destroyed. + */ + if (!mas_node_walk(mast->orig_r, + mte_node_type(mast->orig_r->node), + &range_min, &range_max)) { + mas_set_slot(mast->orig_r, mas_data_end(mast->orig_r) + 1); + } + /* Set up the left side of things */ + mas_set_slot(mast->orig_l, 0); + mast->orig_l->index = mast->l->min; + mas_node_walk(mast->orig_l, mte_node_type(mast->orig_l->node), + &range_min, &range_max); } static inline struct maple_enode @@ -1968,7 +1993,6 @@ static inline void mas_wmb_replace(struct ma_state *mas, static inline bool mast_new_root(struct maple_subtree_state *mast, struct ma_state *mas) { - unsigned long range_min, range_max; if (mast->l->min || mast->l->max != ULONG_MAX) return false; @@ -1984,12 +2008,6 @@ static inline bool mast_new_root(struct maple_subtree_state *mast, } else { do { mast_ascend_free(mast); - mas_node_walk(mast->orig_l, - mte_node_type(mast->orig_l->node), - &range_min, &range_max); - mas_node_walk(mast->orig_r, - mte_node_type(mast->orig_r->node), - &range_min, &range_max); mast_consume(mast); } while (!mte_is_root(mast->orig_l->node)); } @@ -2018,10 +2036,9 @@ static inline bool mast_new_root(struct maple_subtree_state *mast, static inline int mas_combine_separate(struct ma_state *mas, struct maple_subtree_state *mast, unsigned char count) { - unsigned char split, r_end, mid_split; + unsigned char split, mid_split; unsigned char slot = 0, l_slot = 0; struct maple_enode *left = NULL, *middle = NULL, *right = NULL; - unsigned long range_min, range_max; MA_STATE(l_mas, mas->tree, mas->index, mas->index); MA_STATE(r_mas, mas->tree, mas->index, mas->index); @@ -2081,24 +2098,6 @@ static inline int mas_combine_separate(struct ma_state *mas, goto new_root; mast_ascend_free(mast); - /* Set up the right side of things */ - r_end = mas_data_end(mast->orig_r); - mast->orig_r->index = r_mas.max; - /* last should be larger than or equal to index */ - if (mast->orig_r->last < mast->orig_r->index) - mast->orig_r->last = mast->orig_r->index; - /* The node may not contain the value so set slot to ensure all - * of the nodes contents are freed or destroyed. - */ - if (!mas_node_walk(mast->orig_r, - mte_node_type(mast->orig_r->node), - &range_min, &range_max)) { - mas_set_slot(mast->orig_r, r_end + 1); - } - /* Set up the left side of things */ - mast->orig_l->index = l_mas.min; - mas_node_walk(mast->orig_l, mte_node_type(mast->orig_l->node), - &range_min, &range_max); l_slot = mas_get_slot(mast->orig_l); mast->bn->b_end = 0; @@ -2113,7 +2112,8 @@ static inline int mas_combine_separate(struct ma_state *mas, // Copy anything necessary out of the right node. if (mast->bn->pivot[mast->bn->b_end - 1] < mast->orig_r->max) { mas_mab_cp(mast->orig_r, mas_get_slot(mast->orig_r) + 1, - r_end, mast->bn, mast->bn->b_end); + mas_data_end(mast->orig_r), mast->bn, + mast->bn->b_end); mast->orig_r->last = mast->orig_r->max; } mast_consume(mast); @@ -2133,7 +2133,6 @@ static inline int mas_combine_separate(struct ma_state *mas, l_mas.node = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), mte_node_type(mast->orig_l->node)); mast->orig_l->depth++; - mab_mas_cp(mast->bn, 0, mast->bn->b_end, &l_mas, 0); mte_set_parent(left, l_mas.node, slot); if (middle) -- 2.50.1