From 077663b3378e3740bbb2a1e556be527e64c546e7 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 16 Jul 2020 21:54:36 -0400 Subject: [PATCH] maple_tree: wip, try the maple_subtree_state for smaller functions Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 207 ++++++++++++++++++++++++----------------------- 1 file changed, 105 insertions(+), 102 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 9cfaae1c6809..3164b7f4bf5e 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1747,6 +1747,94 @@ static inline void mast_consume(struct maple_subtree_state *mast) mat_add(mast->destroy, mas_get_rcu_slot(mast->orig_r, slot)); } +static inline bool mast_rebalance_from_siblings(struct maple_subtree_state *mast) +{ + unsigned char end; + struct maple_enode *left = mast->orig_l->node; + struct maple_enode *right = mast->orig_r->node; + + 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); + mat_add(mast->free, right); + if (right == left) + mast->orig_l->node = mast->orig_r->node; + mast->orig_r->last = mast->orig_r->max; + return true; + } + if (mas_prev_sibling(mast->orig_l)) { + end = mas_data_end(mast->orig_l); + // shift mast->bn by prev size + 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); + mat_add(mast->free, left); + if (right == left) + 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; + mas_set_slot(mast->l, mas_get_slot(mast->l) + end + 1); + return true; + } + return false; +} + +static inline void mas_prev_node(struct ma_state *mas, unsigned long limit); +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; + struct maple_enode *left = mast->orig_l->node; + struct maple_enode *right = mast->orig_r->node; + + mas_set_slot(mast->orig_r, + mte_parent_slot(mast->orig_r->node)); + 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); + mast->orig_r->last = mast->orig_r->max; + mat_add(mast->free, right); + if (right == left) + mast->orig_l->node = mast->orig_r->node; + return true; + } + // Put left into right. + mas_dup_state(mast->orig_r, mast->orig_l); + mas_dup_state(mast->r, mast->l); + // Use prev for left. + mas_prev_node(mast->orig_l, 0); + if (mas_is_none(mast->orig_l)) { + // This is going to be a new root of + // only what is in mast->bn + mas_dup_state(mast->orig_l, mast->orig_r); + mast->bn->b_end--; + return false; + } + + mat_add(mast->free, left); + if (right == left) + mast->orig_r->node = mast->orig_l->node; + + mas_set_slot(mast->orig_l, 0); + mast->orig_l->index = mast->orig_l->min; + end = mas_data_end(mast->orig_l); + // 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; + mas_set_slot(mast->l, mas_get_slot(mast->l) + end + 1); + return true; +} + static inline void mas_ascend_free(struct ma_state *l_mas, struct ma_state *r_mas, struct ma_topiary *free) @@ -1894,9 +1982,6 @@ static inline void mas_wmb_replace(struct ma_state *mas, * * Returns the number of elements in b_node during the last loop. */ -static inline void mas_prev_node(struct ma_state *mas, unsigned long limit); -static inline unsigned long mas_next_node(struct ma_state *mas, - unsigned long max); static inline int mas_combine_separate(struct ma_state *mas, struct maple_subtree_state *mast, unsigned char count) { @@ -1908,7 +1993,6 @@ static inline int mas_combine_separate(struct ma_state *mas, MA_STATE(l_mas, mas->tree, mas->index, mas->index); MA_STATE(r_mas, mas->tree, mas->index, mas->index); MA_STATE(m_mas, mas->tree, mas->index, mas->index); - MA_TOPIARY(free, mas->tree); MA_TOPIARY(destroy, mas->tree); @@ -1929,6 +2013,7 @@ static inline int mas_combine_separate(struct ma_state *mas, &mid_split); /* Set parents from previous run */ + slot = mas_get_slot(&l_mas); mas_separate_set_parent(&l_mas, left, right, &slot, split); mas_separate_set_parent(&m_mas, left, right, &slot, split); mas_separate_set_parent(&r_mas, left, right, &slot, split); @@ -1937,19 +2022,18 @@ static inline int mas_combine_separate(struct ma_state *mas, l_mas.node = left; m_mas.node = middle; r_mas.node = right; - l_mas.min = mast->orig_l->min; mab_mas_cp(mast->bn, 0, split, &l_mas, 0); l_mas.max = mast->bn->pivot[split]; r_mas.max = l_mas.max; - if (middle) { mab_mas_cp(mast->bn, 1 + split, mid_split, &m_mas, 0); m_mas.min = mast->bn->pivot[split] + 1; m_mas.max = mast->bn->pivot[mid_split]; split = mid_split; } + if (right) { mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, &r_mas, 0); r_mas.min = mast->bn->pivot[split] + 1; @@ -1985,9 +2069,9 @@ static inline int mas_combine_separate(struct ma_state *mas, mast_consume(mast); } while (!mte_is_root(mast->orig_l->node)); } - mat_add(&free, mast->orig_l->node); + mat_add(mast->free, mast->orig_l->node); mas_dup_state(mast->orig_l, &l_mas); - goto done; + goto new_root; } mas_ascend_free(mast->orig_l, mast->orig_r, &free); @@ -2016,114 +2100,33 @@ 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); + mast->bn->b_end = mas_mab_cp(mast->orig_l, 0, + l_slot - 1, mast->bn, 0); - slot = mast->bn->b_end; + mas_set_slot(&l_mas, mast->bn->b_end); mab_set_b_end(mast->bn, &l_mas, left); mab_set_b_end(mast->bn, &m_mas, middle); mab_set_b_end(mast->bn, &r_mas, right); // 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, r_slot + 1, - r_end, mast->bn, mast->bn->b_end); + 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); mast->orig_l->last = mast->orig_l->max; - if (mast->bn->b_end > mt_min_slot_cnt(mast->orig_l->node)) continue; - // Attempt to balance from this parent - if (mast->bn->b_end - 1 < mt_min_slot_cnt(mast->orig_l->node)) { - unsigned char end; - struct maple_enode *left = mast->orig_l->node; - struct maple_enode *right = mast->orig_r->node; - 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); - mat_add(&free, right); - if (right == left) - mast->orig_l->node = mast->orig_r->node; - mast->orig_r->last = mast->orig_r->max; - if (!count) - count++; - } else if (mas_prev_sibling(mast->orig_l)) { - end = mas_data_end(mast->orig_l); - // shift mast->bn by prev size - mab_shift_right(mast->bn, end + 1, - (mt_is_alloc(mas->tree) ? true : false)); - // copy in prev. - mas_mab_cp(mast->orig_l, 0, end, mast->bn, 0); - mat_add(&free, left); - if (right == left) - mast->orig_r->node = mast->orig_l->node; - l_mas.min = mast->orig_l->min; - mast->orig_l->index = mast->orig_l->min; - mast->bn->b_end += end + 1; - slot += end + 1; - if (!count) - count++; - } - } - - // Ensure there is enough data for the next iteration. - if (mast->bn->b_end - 1 < mt_min_slot_cnt(mast->orig_l->node)) { - unsigned char end; - struct maple_enode *left = mast->orig_l->node; - struct maple_enode *right = mast->orig_r->node; - - mas_set_slot(mast->orig_r, - mte_parent_slot(mast->orig_r->node)); - mas_next_node(mast->orig_r, ULONG_MAX); - if (!mas_is_none(mast->orig_r)) { - // Add r_mas.node to clean_list. - // r_mas is now at the next node.. - 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); - mast->orig_r->last = mast->orig_r->max; - mat_add(&free, right); - if (right == left) - mast->orig_l->node = mast->orig_r->node; - } else { - // Put left into right. - mas_dup_state(mast->orig_r, mast->orig_l); - mas_dup_state(&r_mas, &l_mas); - r_slot = l_slot; - // Use prev for left. - mas_prev_node(mast->orig_l, 0); - if (mas_is_none(mast->orig_l)) { - // This is going to be a new root of - // only what is in mast->bn - mas_dup_state(mast->orig_l, mast->orig_r); - mast->bn->b_end--; - break; - } - mat_add(&free, left); - if (right == left) - mast->orig_r->node = mast->orig_l->node; - - mas_set_slot(mast->orig_l, 0); - mast->orig_l->index = mast->orig_l->min; - l_slot = 0; - end = mas_data_end(mast->orig_l); - // shift mast->bn by prev size - mab_shift_right(mast->bn, end + 1, - (mt_is_alloc(mas->tree) ? true : false)); - // copy in prev. - mas_mab_cp(mast->orig_l, 0, end, mast->bn, 0); - l_mas.min = mast->orig_l->min; - slot += end + 1; - mast->bn->b_end += end + 1; - } - if (!count) - count++; - } + // Ensure there is enough data for the next loop. + if (!mast_rebalance_from_siblings(mast)) + if (!mast_rebalance_from_cousins(mast)) + break; + if (!count) + count++; } l_mas.node = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), @@ -2149,7 +2152,7 @@ static inline int mas_combine_separate(struct ma_state *mas, mas_dup_state(mast->orig_l, &l_mas); mas->depth = mast->orig_l->depth; -done: +new_root: mte_set_node_dead(mas->node); // Set up mas for insertion. mas_dup_state(mas, mast->orig_l); -- 2.50.1