From c7c648b8eaa647a9ef447b99da9af27225fcac57 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 27 Jul 2020 19:02:13 -0400 Subject: [PATCH] maple_tree: Remove possibility of having mas->node null Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 48 +++++++++++++++--------------------------------- 1 file changed, 15 insertions(+), 33 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ee319fe06c5c..d12ad07ea628 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -312,7 +312,7 @@ static inline enum maple_type mas_parent_enum(struct ma_state *mas, return mte_parent_range_enum(parent); } -/* +/* Private * mte_set_parent() - Set the parent node and encode the slot. * * Type is encoded in the node->parent @@ -653,7 +653,7 @@ void mte_destroy_walk(struct maple_enode *mn, struct maple_tree *mtree) mte_free(mn); } -/* +/* Private * mat_add() - Add a @dead_enode to the ma_topiary of a list of dead nodes. * * Add the %dead_enode to the linked list in %mat. @@ -1766,7 +1766,7 @@ static inline struct maple_enode *mte_node_or_none(struct maple_enode *enode) return ma_enode_ptr(MAS_NONE); } -/* +/* Private * mast_topiary() - Add the portions of the tree to the removal list; either to * be freed or discarded (destroy walk). * @@ -2011,7 +2011,7 @@ static inline void mab_set_b_end(struct maple_big_node *b_node, b_node->pivot[b_node->b_end++] = mas->max; } -/* +/* Private * mas_set_split_parent() - combine_then_separate helper function. Sets the parent * of @mas->node to either @left or @right, depending on @slot and @split * @@ -2075,28 +2075,14 @@ static inline void mast_set_split_parents(struct maple_subtree_state *mast, unsigned char mid_split) { unsigned char slot; - struct maple_enode *l = left; - struct maple_enode *r = right; if (mas_is_none(mast->l)) return; - if (middle) - r = middle; - slot = mas_get_slot(mast->l); - - mte_mid_split_check(&l, &r, right, slot, &split, mid_split); - // Set left parent. - mas_set_split_parent(mast->l, l, r, &slot, split); - - mte_mid_split_check(&l, &r, right, slot, &split, mid_split); - // Set middle parent. - mas_set_split_parent(mast->m, l, r, &slot, split); - - mte_mid_split_check(&l, &r, right, slot, &split, mid_split); - // Set right parent. - mas_set_split_parent(mast->r, l, r, &slot, split); + mas_set_split_parent(mast->l, left, right, &slot, split); + mas_set_split_parent(mast->m, left, right, &slot, split); + mas_set_split_parent(mast->r, left, right, &slot, split); } static inline void mas_wmb_replace(struct ma_state *mas, struct ma_topiary *free, @@ -2222,9 +2208,10 @@ static inline void mast_setup_bnode_for_split(struct maple_subtree_state *mast) mast->bn->type = mte_node_type(mast->orig_l->node); } -/* +/* Private * - * mas_spanning_rebalance() - Rebalance across two nodes which may not be peers. + * mas_combine_then_separate() - Combine two nodes and then separate them as + * needed. * @mas: The starting maple state * @mast: The maple_subtree_state, keeps track of 4 maple states. * @count: The estimated count of iterations needed. @@ -2241,7 +2228,7 @@ static inline void mast_setup_bnode_for_split(struct maple_subtree_state *mast) * * Returns the number of elements in b_node during the last loop. */ -static inline int mas_spanning_rebalance(struct ma_state *mas, +static inline int mas_combine_then_separate(struct ma_state *mas, struct maple_subtree_state *mast, unsigned char count) { @@ -2262,12 +2249,6 @@ static inline int mas_spanning_rebalance(struct ma_state *mas, mast->destroy = &destroy; l_mas.node = r_mas.node = m_mas.node = MAS_NONE; - if (mast->orig_l->depth != mast->orig_r->depth) { - printk("Error: %d != %d\n", - mast->orig_l->depth, mast->orig_r->depth); - } - MT_BUG_ON(mas->tree, mast->orig_l->depth != mast->orig_r->depth); - mast->orig_l->depth = 0; mast_topiary(mast); while (count--) { mast_setup_bnode_for_split(mast); @@ -2341,7 +2322,7 @@ new_root: return mast->bn->b_end; } -/* +/* Private * mas_rebalance() - Rebalance a given node. * * @mas: The maple state @@ -2388,7 +2369,7 @@ static inline int mas_rebalance(struct ma_state *mas, l_mas.index = l_mas.last = l_mas.min; } - return mas_spanning_rebalance(mas, &mast, empty_cnt); + return mas_combine_then_separate(mas, &mast, empty_cnt); } static inline bool mas_split_final_node(struct maple_subtree_state *mast, @@ -2940,7 +2921,8 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) count = mas_cnt_positive(mas) + mas->tree->ma_height - mas->depth + 1; // Combine l_mas and r_mas and split them up evenly again. - return mas_spanning_rebalance(mas, &mast, count); + l_mas.depth = 0; + return mas_combine_then_separate(mas, &mast, count); } static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite) -- 2.50.1