From defc4c3216e9f3b48a2ab17c8f3690cba72ccae9 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 3 Mar 2020 08:19:30 -0500 Subject: [PATCH] maple_tree: Clean up mas_data_end interface. Some places don't care about coalesce and the last pivot, so provide a cleaner way to get just the end to clean up that code. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 64 ++++++++++++++++++++++-------------------------- 1 file changed, 29 insertions(+), 35 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 637a74e9bb14..c60d3c968372 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1173,7 +1173,7 @@ done: * last pivot to @last_piv, sets @coalesce to the number of slots that can be * removed by coalescing. */ -static inline unsigned char mas_data_end(const struct ma_state *mas, +static inline unsigned char _mas_data_end(const struct ma_state *mas, const enum maple_type type, unsigned long *last_piv, unsigned char *coalesce) { @@ -1231,6 +1231,13 @@ static inline unsigned char mas_data_end(const struct ma_state *mas, return slot; } +static inline unsigned char mas_data_end(const struct ma_state *mas) +{ + unsigned long l; + unsigned char c; + + return _mas_data_end(mas, mte_node_type(mas->node), &l, &c); +} /** Private * ma_hard_data - return the number of slots required to store what is * currently in this node. @@ -1277,7 +1284,7 @@ static inline unsigned char mas_append_entry(struct ma_state *mas, void *entry) if (!mas_get_rcu_slot(mas, 0) && !mte_get_pivot(mas->node, 0)) dst_slot = 0; // empty node. else if (dst_slot > mt_slot_count(mas->node)) { // Should not happen. - dst_slot = mas_data_end(mas, mte_node_type(mas->node), + dst_slot = _mas_data_end(mas, mte_node_type(mas->node), &wr_pivot, &coalesce); // slot not set. } else if (dst_slot) wr_pivot = mas_get_safe_pivot(mas, dst_slot - 1); @@ -1558,10 +1565,7 @@ static inline unsigned char mas_append_split(struct ma_state *dst1, unsigned char slot, void *entry, bool active) { unsigned char split = mas_append_calc_split(src, active); - unsigned long wr_pivot; - unsigned char coalesce; - unsigned char data_end = mas_data_end(src, mte_node_type(src->node), - &wr_pivot, &coalesce); + unsigned char data_end = mas_data_end(src); bool add_entry = mte_is_leaf(src->node); mas_set_slot(dst1, slot); @@ -1600,9 +1604,7 @@ static inline unsigned char mas_dense_calc_split(struct ma_state *mas, enum maple_type type = mte_node_type(mas->node); unsigned long pivot_cnt = mt_pivots[type]; unsigned long half = mt_slots[type] / 2; - unsigned long last_pivot; - unsigned char coalesce; - unsigned char data_end = mas_data_end(mas, type, &last_pivot, &coalesce); + unsigned char data_end = mas_data_end(mas); if (mte_is_root(mas->node)) { i = half; @@ -2064,7 +2066,7 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot, mas_ascend(&parent); old_parent = parent.node; ptype = mas_parent_enum(mas, mas->node); - p_end = mas_data_end(&parent, ptype, &last_pivot, &coalesce); + p_end = _mas_data_end(&parent, ptype, &last_pivot, &coalesce); if (p_end - coalesce >= mt_slots[ptype] - 1) { /* Must split the parent */ mas_dup_state(mas, &parent); @@ -2081,7 +2083,7 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot, mas_set_slot(&parent, p_slot); } ptype = mas_parent_enum(mas, mas->node); - p_end = mas_data_end(&parent, ptype, &last_pivot, &coalesce); + p_end = mas_data_end(&parent); mas_dup_state(mas, &parent); mas_set_slot(mas, p_slot); mas_descend(mas); @@ -2212,8 +2214,7 @@ static inline void mas_may_move_gap(struct ma_state *mas) mas_dup_state(&next, mas); mas_dup_state(&curr, mas); - end = mas_data_end(&curr, mte_node_type(curr.node), &last_piv, - &coalesce); + end = mas_data_end(&curr); if (end != slot) { mas_prev(&curr, 0); if (curr.node == mas->node) // prev value not in prev node. @@ -2223,7 +2224,7 @@ static inline void mas_may_move_gap(struct ma_state *mas) if (mas_is_none(&curr)) return; - end = mas_data_end(&curr, mte_node_type(curr.node), &last_piv, + end = _mas_data_end(&curr, mte_node_type(curr.node), &last_piv, &coalesce); entry = mas_get_rcu_slot(&curr, end); if (entry && !xa_is_deleted(entry)) @@ -2384,10 +2385,7 @@ static inline int __mas_add(struct ma_state *mas, void *entry, enum maple_type mas_type = mte_node_type(mas->node); struct maple_node space; struct maple_node *mn = NULL; - unsigned long wr_pivot = mas->min - 1; - unsigned char coalesce; - unsigned char data_end = mas_data_end(mas, mas_type, &wr_pivot, - &coalesce); + unsigned char data_end = mas_data_end(mas); unsigned char slot = mas_get_slot(mas); unsigned char end_slot = slot; unsigned long src_max = mas->max; @@ -2645,7 +2643,7 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, // Bug if we are adding an entry to a non-leaf node. MT_BUG_ON(mas->tree, !ma_is_leaf(this_type)); - old_end = mas_data_end(mas, this_type, &last_piv, &coalesce); + old_end = _mas_data_end(mas, this_type, &last_piv, &coalesce); if (slot > slot_cnt) // search returned MAPLE_NODE_SLOTS slot = old_end + 1; @@ -2913,7 +2911,7 @@ walk_down: if (mte_is_leaf(mas->node)) goto done; - slot = mas_data_end(mas, mte_node_type(mas->node), &mas->max, + slot = _mas_data_end(mas, mte_node_type(mas->node), &mas->max, &coalesce); } while (1); @@ -2990,8 +2988,8 @@ restart_prev_node: level--; mas->node = mn; - slot = mas_data_end(mas, mte_node_type(mn), &last_pivot, - &coalesce) + 1; + slot = _mas_data_end(mas, mte_node_type(mn), + &last_pivot, &coalesce) + 1; } while (slot-- > 0); ascend: @@ -3381,7 +3379,7 @@ static inline void mas_coalesce_root(struct ma_state *mas) unsigned long piv; unsigned long min, max; unsigned char coalesce, hard_data; - unsigned char end = mas_data_end(mas, this_type, &piv, &coalesce); + unsigned char end = _mas_data_end(mas, this_type, &piv, &coalesce); MA_STATE(old_mas, mas->tree, mas->index, mas->last); @@ -3543,7 +3541,7 @@ start: mas_dup_state(&p_mas, mas); mas_ascend(&p_mas); p_slot = mte_parent_slot(mas->node); - l_end_slot = mas_data_end(mas, l_type, &l_end_piv, &l_coalesce); + l_end_slot = _mas_data_end(mas, l_type, &l_end_piv, &l_coalesce); if (!try_anyways && (ma_hard_data(l_end_slot, l_coalesce) >= mt_min_slots[l_type])) goto done; // Everything's perfectly all right now. @@ -3578,8 +3576,8 @@ start: } mas_descend(&r_mas); r_type = mte_node_type(r_mas.node); - r_end_slot = mas_data_end(&r_mas, r_type, &r_end_piv, - &r_coalesce); + r_end_slot = _mas_data_end(&r_mas, r_type, &r_end_piv, + &r_coalesce); if (r_end_slot - r_coalesce + l_end_slot - l_coalesce + 2 < mt_slots[l_type]) { // Force a rebalance/coalesce of these nodes @@ -3593,7 +3591,7 @@ start: // We have a left and a right, check if they can be coalesced. r_type = mte_node_type(r_mas.node); // not for racing. - r_end_slot = mas_data_end(&r_mas, r_type, &r_end_piv, &r_coalesce); + r_end_slot = _mas_data_end(&r_mas, r_type, &r_end_piv, &r_coalesce); // end_slot values don't count slot 0, so add one. total_slots = l_end_slot + 1 - l_coalesce; @@ -3826,7 +3824,7 @@ next: mas->max = max; if (!mt_is_empty(next)) { mas->node = next; - i = mas_data_end(mas, mte_node_type(next), &max, + i = _mas_data_end(mas, mte_node_type(next), &max, &coalesce); } else { goto ascend; @@ -4357,8 +4355,6 @@ error: */ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) { - unsigned long piv; - unsigned char coalesce; unsigned int slot_cnt = 0; long node_cnt = 0, leaves= 1; struct maple_enode *last = NULL; @@ -4389,8 +4385,7 @@ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) goto skip_r_count; } slot_cnt -= mas_get_slot(&r_mas); - slot_cnt += mas_data_end(&r_mas, mte_node_type(r_mas.node), &piv, - &coalesce); + slot_cnt += mas_data_end(&r_mas); // Count the nodes to the right. mas_set_slot(&r_mas, mte_parent_slot(r_mas.node)); @@ -4417,8 +4412,7 @@ static inline bool mas_rewind_node(struct ma_state *mas); static inline void mas_rev_awalk(struct ma_state *mas, unsigned long size) { struct maple_enode *last = NULL; - unsigned long last_piv; - unsigned char slot, coalesce; + unsigned char slot; mas_start(mas); if (mas_is_none(mas)) { @@ -4431,7 +4425,7 @@ static inline void mas_rev_awalk(struct ma_state *mas, unsigned long size) if (mas_is_err(mas)) return; - slot = mas_data_end(mas, mte_node_type(mas->node), &last_piv, &coalesce); + slot = mas_data_end(mas); mas_set_slot(mas, slot); -- 2.50.1