From 88ea6a3b987c285db8eb7aa876f00553f553bf10 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 16 Jul 2020 22:09:28 -0400 Subject: [PATCH] maple_tree: Attempt to reduce split function size Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 49 +++++++++++++++--------------------------------- 1 file changed, 15 insertions(+), 34 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 3164b7f4bf5e..2cf44fdb3c68 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1915,7 +1915,7 @@ static inline void mab_set_b_end(struct maple_big_node *b_node, } /* Private - * mas_combine_set_parent() - combine_separate helper function. Sets the parent + * mas_set_split_parent() - combine_separate helper function. Sets the parent * of @mas->node to either @left or @right, depending on @slot and @split * * @mas - the maple state with the node that needs a parent @@ -1924,11 +1924,10 @@ static inline void mab_set_b_end(struct maple_big_node *b_node, * @slot - the slot the mas->node was placed * @split - the split location between @left and @right */ -static inline void mas_separate_set_parent(struct ma_state *mas, - struct maple_enode *left, - struct maple_enode *right, - unsigned char *slot, - unsigned char split) +static inline void mas_set_split_parent(struct ma_state *mas, + struct maple_enode *left, + struct maple_enode *right, + unsigned char *slot, unsigned char split) { if (!mas->node) return; @@ -1936,7 +1935,7 @@ static inline void mas_separate_set_parent(struct ma_state *mas, if ((*slot) <= split) mte_set_parent(mas->node, left, *slot); else - mte_set_parent(mas->node, right, (*slot) - split); + mte_set_parent(mas->node, right, (*slot) - split - 1); (*slot)++; } @@ -1986,7 +1985,7 @@ 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 slot = 0, l_slot = 0, r_slot = 0; + unsigned char slot = 0, l_slot = 0; struct maple_enode *left = NULL, *middle = NULL, *right = NULL; unsigned long range_min, range_max; @@ -2014,9 +2013,9 @@ static inline int mas_combine_separate(struct ma_state *mas, /* 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); + mas_set_split_parent(&l_mas, left, right, &slot, split); + mas_set_split_parent(&m_mas, left, right, &slot, split); + mas_set_split_parent(&r_mas, left, right, &slot, split); /* Copy data from mast->bn to new nodes */ l_mas.node = left; @@ -2090,7 +2089,6 @@ static inline int mas_combine_separate(struct ma_state *mas, &range_min, &range_max)) { mas_set_slot(mast->orig_r, r_end + 1); } - r_slot = mas_get_slot(mast->orig_r); /* Set up the left side of things */ mas_set_slot(mast->orig_l, 0); mast->orig_l->index = l_mas.min; @@ -2287,11 +2285,7 @@ static inline int mas_split(struct ma_state *mas, mas_set_slot(&r_mas, mas_get_slot(&l_mas) + 1); } else { unsigned char p_slot; - /* TODO: Check rebalancing to avoid continuing walking - * up if there is space in a neighbour. - * TODO: Use the same splitting as leaves, using height - * to figure if there is enough room below. - */ + /* Note, look into shifting data left or right */ /* internal node split - cut in half for now. */ split = slot_cnt / 2; j = mab_mas_cp(b_node, 0, split, &l_mas, 0); @@ -2299,23 +2293,10 @@ static inline int mas_split(struct ma_state *mas, r_mas.min = l_mas.max + 1; mab_mas_cp(b_node, j, slot_cnt, &r_mas, 0); p_slot = mas_get_slot(&orig_l_mas); - if (p_slot <= split) { // prev left side is on left. - mte_set_parent(orig_l_mas.node, l_mas.node, - p_slot); - } - else { - mte_set_parent(orig_l_mas.node, r_mas.node, - p_slot - split - 1); - } - - p_slot = mas_get_slot(&orig_r_mas); - if (p_slot <= split) {// prev right side is on left. - mte_set_parent(orig_r_mas.node, l_mas.node, - p_slot); - } else { - mte_set_parent(orig_r_mas.node, r_mas.node, - p_slot - split - 1); - } + mas_set_split_parent(&orig_l_mas, l_mas.node, + r_mas.node, &p_slot, split); + mas_set_split_parent(&orig_r_mas, l_mas.node, + r_mas.node, &p_slot, split); } b_node->b_end = 0; -- 2.50.1