From 2228d546f16df019126e2d0cee9bc64fe7073ad2 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 12 Aug 2020 20:29:39 -0400 Subject: [PATCH] maple_tree: compress to left Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 118 +++++++++++++++++++++++------------------------ 1 file changed, 59 insertions(+), 59 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index dd1ce54fa424..06807be04e56 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2280,10 +2280,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); @@ -2442,7 +2438,8 @@ static inline bool mas_split_final_node(struct maple_subtree_state *mast, } static inline void mast_split_fill_bnode(struct maple_subtree_state *mast, - struct ma_state *mas) + struct ma_state *mas, + unsigned char skip) { bool cp = true; struct maple_enode *old = mas->node; @@ -2466,7 +2463,7 @@ static inline void mast_split_fill_bnode(struct maple_subtree_state *mast, mas_set_slot(mast->r, mast->bn->b_end); mab_set_b_end(mast->bn, mast->r, mast->r->node); if (cp) - mas_mab_cp(mas, split + 1, mt_slot_count(mas->node) - 1, + mas_mab_cp(mas, split + skip, mt_slot_count(mas->node) - 1, mast->bn, mast->bn->b_end); mast->bn->b_end--; mast->bn->type = mte_node_type(mas->node); @@ -2474,11 +2471,11 @@ static inline void mast_split_fill_bnode(struct maple_subtree_state *mast, static inline void mast_split_data(struct maple_subtree_state *mast, - struct ma_state *mas) + struct ma_state *mas, + unsigned char split) { - unsigned char p_slot, mid_split, split = 0; + unsigned char p_slot; - split = mab_calc_split(mast->bn, &mid_split); mab_mas_cp(mast->bn, 0, split, mast->l); mte_set_pivot(mast->r->node, 0, mast->r->max); mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r); @@ -2493,12 +2490,59 @@ static inline void mast_split_data(struct maple_subtree_state *mast, mast->r->node, &p_slot, split); } } + +static inline bool mas_push_left(struct ma_state *mas, + struct maple_subtree_state *mast) +{ + unsigned char slot_total = mast->bn->b_end; + unsigned char end, space, split; + + MA_STATE(tmp_mas, mas->tree, mas->index, mas->last); + mas_dup_state(&tmp_mas, mast->l); // for depth. + tmp_mas.node = mas->node; + + if (!mas_prev_sibling(&tmp_mas)) + return false; + + end = mas_data_end(&tmp_mas); + slot_total += end; + + space = 2 * mt_slot_count(mas->node) - 1; + /* -2 instead of -1 to ensure there isn't a triple split */ + if (ma_is_leaf(mast->bn->type)) + space--; + + if (mas->max == ULONG_MAX) + space--; + + if (slot_total >= space) + return false; + + /* Fill mast->bn */ + mast->bn->b_end++; + mab_shift_right(mast->bn, end + 1); + mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0); + mast->bn->b_end = slot_total + 1; + /* Switch mas to prev node */ + mat_add(mast->free, mas->node); + mas_dup_state(mas, &tmp_mas); + /* Start using mast->l for the left side. */ + tmp_mas.node = mast->l->node; + mas_dup_state(mast->l, &tmp_mas); + split = mab_no_null_split(mast->bn, mt_slots[mast->bn->type] - 1, + mt_slots[mast->bn->type]); + mast_split_data(mast, mas, split); + mast_split_fill_bnode(mast, mas, 2); + mas_split_final_node(mast, mas, mas->full_cnt + 1); + return true; +} static inline int mas_split(struct ma_state *mas, struct maple_big_node *b_node) { struct maple_subtree_state mast; int height = 0; + unsigned char mid_split, split = 0; MA_STATE(l_mas, mas->tree, mas->index, mas->last); MA_STATE(r_mas, mas->tree, mas->index, mas->last); @@ -2527,8 +2571,12 @@ static inline int mas_split(struct ma_state *mas, mas_dup_state(&r_mas, mas); l_mas.node = mas_new_ma_node(mas, b_node); r_mas.node = mas_new_ma_node(mas, b_node); - mast_split_data(&mast, mas); - mast_split_fill_bnode(&mast, mas); + if (mas_push_left(mas, &mast)) + break; + + split = mab_calc_split(mast.bn, &mid_split); + mast_split_data(&mast, mas, split); + mast_split_fill_bnode(&mast, mas, 1); mas_dup_state(&prev_l_mas, mast.l); mas_dup_state(&prev_r_mas, mast.r); } @@ -2545,51 +2593,6 @@ static inline int mas_cnt_positive(struct ma_state *mas) return mas->full_cnt * -1; return mas->full_cnt; } -static inline bool mas_fits_left(struct ma_state *mas, - struct maple_big_node *b_node) -{ - unsigned char slot_total = b_node->b_end; - unsigned char end, space; - char empty_cnt = mas_cnt_positive(mas); - struct maple_subtree_state mast; - - MA_STATE(l_mas, mas->tree, mas->index, mas->last); - mas_dup_state(&l_mas, mas); - l_mas.depth = mas->depth; - - if (!mas_prev_sibling(&l_mas)) - return false; - - end = mas_data_end(&l_mas); - slot_total += end; - - space = 2 * mt_slot_count(mas->node) - 1; - if (mas->max == ULONG_MAX) - space--; - - if (slot_total > space) - return false; - - empty_cnt++; - - mas_node_cnt(mas, 1 + empty_cnt * 2); - if (mas_is_err(mas)) - return false; - - b_node->b_end++; - mab_shift_right(b_node, end + 1); - mas_mab_cp(&l_mas, 0, end, b_node, 0); - b_node->b_end = slot_total + 2; - l_mas.index = l_mas.last = l_mas.min; - mas->index = mas->last = mas->max; - - mast.orig_l = &l_mas; - mast.orig_r = mas; - mast.bn = b_node; - - mas_spanning_rebalance(mas, &mast, empty_cnt); - return true; -} static inline int mas_commit_b_node(struct ma_state *mas, struct maple_big_node *b_node) { @@ -2602,9 +2605,6 @@ static inline int mas_commit_b_node(struct ma_state *mas, if (b_node->b_end >= mt_slot_count(mas->node)) { - if (mas_fits_left(mas, b_node)) - return 1; - if (mas_is_err(mas)) return 0; -- 2.50.1