From c2c6b893aa8e0cadead94d6e1780c941e87628ec Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 16 Jul 2020 11:59:40 -0400 Subject: [PATCH] maple_tree: Code cleanup, mostly in split Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 42 +++++++++++++++++++----------------------- 1 file changed, 19 insertions(+), 23 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 8470e46bfa56..ad8c319d84f1 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1748,6 +1748,12 @@ mas_ascend_free(struct ma_state *l_mas, struct ma_state *r_mas, if (left != right) mat_add(free, right); } + +static inline struct maple_enode +*mas_b_node_ma_node(struct ma_state *mas, struct maple_big_node *b_node) +{ + return mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), b_node->type); +} /* Private * mas_mab_to_node() - Set up right and middle nodes * @@ -1770,7 +1776,7 @@ static inline unsigned char mas_mab_to_node(struct ma_state *mas, unsigned char split = 0; unsigned char slot_cnt = mt_slots[b_node->type]; - *left = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), b_node->type); + *left = mas_b_node_ma_node(mas, b_node); *right = NULL; *middle = NULL; *mid_split = 0; @@ -1779,13 +1785,11 @@ static inline unsigned char mas_mab_to_node(struct ma_state *mas, split = b_node->b_end; } else { split = mab_calc_split(b_node, mid_split); - *right = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), - b_node->type); + *right = mas_b_node_ma_node(mas, b_node); } if (*mid_split) - *middle = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), - b_node->type); + *middle = mas_b_node_ma_node(mas, b_node); return split; @@ -2210,26 +2214,24 @@ static inline int mas_split(struct ma_state *mas, * be a new root). */ while (height++ <= mas->full_cnt) { - struct maple_node *l, *r; - enum maple_type type = mte_node_type(mas->node); unsigned char mid_split; unsigned char slot_cnt = mt_slot_count(mas->node); /* should be full. */ bool cp = true; + b_node->type = mte_node_type(mas->node); if (height > mas->full_cnt) { // The last node to be created. if (mte_is_root(mas->node)) { if (mt_is_alloc(mas->tree)) - type = maple_arange_64; + b_node->type = maple_arange_64; else - type = maple_range_64; + b_node->type = maple_range_64; mas->depth = height; } /* Only a single node is used here, could be root. * Big_node should just fit in a single node. */ - ancestor = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), - type); + ancestor = mas_b_node_ma_node(mas, b_node); // Set the parents mte_set_parent(l_mas.node, ancestor, mas_get_slot(&l_mas)); @@ -2240,19 +2242,16 @@ static inline int mas_split(struct ma_state *mas, if (mas->full_cnt >= mas->tree->ma_height) mas->tree->ma_height++; l_mas.node = ancestor; - mab_mas_cp(b_node, 0, mt_slots[type] - 1, &l_mas, 0); + mab_mas_cp(b_node, 0, mt_slots[b_node->type] - 1, + &l_mas, 0); break; } b_node->min = mas->min; - b_node->type = type; - l = ma_mnode_ptr(mas_next_alloc(mas)); - r = ma_mnode_ptr(mas_next_alloc(mas)); - mas_dup_state(&l_mas, mas); mas_dup_state(&r_mas, mas); - l_mas.node = mt_mk_node(l, type); - r_mas.node = mt_mk_node(r, type); + l_mas.node = mas_b_node_ma_node(mas, b_node); + r_mas.node = mas_b_node_ma_node(mas, b_node); if (mte_is_leaf(mas->node)) { split = mab_calc_split(b_node, &mid_split); if (split < slot_cnt) @@ -2268,14 +2267,11 @@ 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. */ - /* internal node split - cut in half for now. */ split = slot_cnt / 2; j = mab_mas_cp(b_node, 0, split, &l_mas, 0); @@ -2304,9 +2300,9 @@ static inline int mas_split(struct ma_state *mas, b_node->b_end = 0; memset(b_node, 0, sizeof(struct maple_big_node)); - if (mte_is_root(mas->node)) + if (mte_is_root(mas->node)) { cp = false; - else { + } else { struct maple_enode *old = mas->node; mas_ascend(mas); -- 2.50.1