From dec9e073ce04d9568768f451cfc30405f1a084d0 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 16 Jul 2020 22:32:32 -0400 Subject: [PATCH] maple_tree: mas_mab_cp sets b_end now Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 58 ++++++++++++++++++++++-------------------------- 1 file changed, 27 insertions(+), 31 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 2cf44fdb3c68..96407fdb752c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1524,9 +1524,9 @@ static inline int mab_calc_split(struct maple_big_node *b_node, /* * Note, mas_end is inclusive */ -static inline int mas_mab_cp(struct ma_state *mas, unsigned char mas_start, - unsigned char mas_end, struct maple_big_node *b_node, - unsigned char mab_start) +static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, + unsigned char mas_end, struct maple_big_node *b_node, + unsigned char mab_start) { int i, j; for (i = mas_start, j = mab_start; i <= mas_end; i++, j++) { @@ -1548,7 +1548,7 @@ static inline int mas_mab_cp(struct ma_state *mas, unsigned char mas_start, break; } } - return j; + b_node->b_end = j; } static inline int mab_mas_cp(struct maple_big_node *b_node, @@ -1626,7 +1626,8 @@ static inline unsigned char mas_store_b_node(struct ma_state *mas, unsigned long piv = mas->min; if (slot) { - b_end = mas_mab_cp(mas, 0, slot - 1, b_node, 0); + mas_mab_cp(mas, 0, slot - 1, b_node, 0); + b_end = b_node->b_end; piv = b_node->pivot[b_end - 1]; } @@ -1658,8 +1659,8 @@ static inline unsigned char mas_store_b_node(struct ma_state *mas, b_node->slot[++b_end] = NULL; b_node->pivot[b_end] = piv; } else { - b_end = mas_mab_cp(mas, slot, end + 1, b_node, ++b_end); - b_end--; + mas_mab_cp(mas, slot, end + 1, b_node, ++b_end); + b_end = b_node->b_end - 1; } } @@ -1755,8 +1756,7 @@ static inline bool mast_rebalance_from_siblings(struct maple_subtree_state *mast if (mas_next_sibling(mast->orig_r)) { end = mas_data_end(mast->orig_r); - mast->bn->b_end = mas_mab_cp(mast->orig_r, 0, end, - mast->bn, mast->bn->b_end); + mas_mab_cp(mast->orig_r, 0, end, mast->bn, mast->bn->b_end); mat_add(mast->free, right); if (right == left) mast->orig_l->node = mast->orig_r->node; @@ -1764,6 +1764,7 @@ static inline bool mast_rebalance_from_siblings(struct maple_subtree_state *mast return true; } if (mas_prev_sibling(mast->orig_l)) { + unsigned char b_end = mast->bn->b_end; end = mas_data_end(mast->orig_l); // shift mast->bn by prev size mab_shift_right(mast->bn, end + 1, @@ -1775,7 +1776,7 @@ static inline bool mast_rebalance_from_siblings(struct maple_subtree_state *mast mast->orig_r->node = mast->orig_l->node; mast->l->min = mast->orig_l->min; mast->orig_l->index = mast->orig_l->min; - mast->bn->b_end += end + 1; + mast->bn->b_end = end + 1 + b_end; mas_set_slot(mast->l, mas_get_slot(mast->l) + end + 1); return true; } @@ -1787,7 +1788,7 @@ static inline unsigned long mas_next_node(struct ma_state *mas, unsigned long max); static inline bool mast_rebalance_from_cousins(struct maple_subtree_state *mast) { - unsigned char end; + unsigned char end, b_end; struct maple_enode *left = mast->orig_l->node; struct maple_enode *right = mast->orig_r->node; @@ -1796,8 +1797,7 @@ static inline bool mast_rebalance_from_cousins(struct maple_subtree_state *mast) mas_next_node(mast->orig_r, ULONG_MAX); if (!mas_is_none(mast->orig_r)) { end = mas_data_end(mast->orig_r); - mast->bn->b_end = mas_mab_cp(mast->orig_r, 0, end, - mast->bn, mast->bn->b_end); + mas_mab_cp(mast->orig_r, 0, end, mast->bn, mast->bn->b_end); mast->orig_r->last = mast->orig_r->max; mat_add(mast->free, right); if (right == left) @@ -1824,13 +1824,14 @@ static inline bool mast_rebalance_from_cousins(struct maple_subtree_state *mast) mas_set_slot(mast->orig_l, 0); mast->orig_l->index = mast->orig_l->min; end = mas_data_end(mast->orig_l); + b_end = mast->bn->b_end; // shift mast->bn mab_shift_right(mast->bn, end + 1, (mt_is_alloc(mast->l->tree) ? true : false)); // copy in prev. mas_mab_cp(mast->orig_l, 0, end, mast->bn, 0); mast->l->min = mast->orig_l->min; - mast->bn->b_end += end + 1; + mast->bn->b_end = b_end + end + 1; mas_set_slot(mast->l, mas_get_slot(mast->l) + end + 1); return true; } @@ -2098,8 +2099,7 @@ static inline int mas_combine_separate(struct ma_state *mas, mast->bn->b_end = 0; if (l_slot) - mast->bn->b_end = mas_mab_cp(mast->orig_l, 0, - l_slot - 1, mast->bn, 0); + mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0); mas_set_slot(&l_mas, mast->bn->b_end); mab_set_b_end(mast->bn, &l_mas, left); @@ -2108,9 +2108,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) { - mast->bn->b_end = mas_mab_cp(mast->orig_r, - mas_get_slot(mast->orig_r) + 1, - r_end, mast->bn, mast->bn->b_end); + mas_mab_cp(mast->orig_r, mas_get_slot(mast->orig_r) + 1, + r_end, mast->bn, mast->bn->b_end); mast->orig_r->last = mast->orig_r->max; } mast_consume(mast); @@ -2181,18 +2180,18 @@ static inline int mas_rebalance(struct ma_state *mas, b_node->b_end++; if (mas_next_sibling(&r_mas)) { - b_node->b_end = mas_mab_cp(&r_mas, 0, mas_data_end(&r_mas), - b_node, b_node->b_end); + mas_mab_cp(&r_mas, 0, mas_data_end(&r_mas), b_node, + b_node->b_end); r_mas.last = r_mas.index = r_mas.max; } else { - unsigned char shift; + unsigned char shift, b_end = b_node->b_end; mas_prev_sibling(&l_mas); shift = mas_data_end(&l_mas) + 1; mab_shift_right(b_node, shift, (mt_is_alloc(mas->tree) ? true : false)); mas_mab_cp(&l_mas, 0, shift - 1, b_node, 0); - b_node->b_end += shift; + b_node->b_end = shift + b_end; l_mas.index = l_mas.last = l_mas.min; } @@ -2312,8 +2311,7 @@ static inline int mas_split(struct ma_state *mas, } if (cp && mas_get_slot(&l_mas)) - b_node->b_end = mas_mab_cp(mas, 0, - mas_get_slot(&l_mas) - 1, b_node, 0); + 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); @@ -2322,9 +2320,8 @@ static inline int mas_split(struct ma_state *mas, mas_dup_state(&orig_l_mas, &l_mas); mas_dup_state(&orig_r_mas, &r_mas); if (cp) - b_node->b_end = mas_mab_cp(mas, split + 1, - mt_slot_count(mas->node) - 1, b_node, - b_node->b_end); + mas_mab_cp(mas, split + 1, mt_slot_count(mas->node) - 1, + b_node, b_node->b_end); } // Set the original node as dead @@ -2752,9 +2749,8 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) // Copy l_mas and store the value in b_node. b_node.b_end = mas_store_b_node(&l_mas, &b_node, entry); // Copy r_mas into b_node. - b_node.b_end = mas_mab_cp(&r_mas, mas_get_slot(&r_mas), - mas_data_end(&r_mas), &b_node, - b_node.b_end + 1); + mas_mab_cp(&r_mas, mas_get_slot(&r_mas), mas_data_end(&r_mas), &b_node, + b_node.b_end + 1); // Stop spanning searches by searching for just index. l_mas.index = l_mas.last = mas->index; // Calc the number of iterations of combining and splitting that will -- 2.50.1