From 5b361a3b7135c541d1359e9e2e4668b2d031234c Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 15 Feb 2019 15:43:48 -0500 Subject: [PATCH] maple_tree: Efficiencies Remove unneeded code. Fix splitting from the back of a node. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 58 ++++++++++++------------------------------------ 1 file changed, 14 insertions(+), 44 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 13f0c38344d6..935fae1f07e0 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -500,20 +500,9 @@ static inline void ma_update_rcu_slot(const struct maple_node *mn, break; } } -static void mas_update_limits(struct ma_state *ms, unsigned char slot, +static inline void mas_update_limits(struct ma_state *ms, unsigned char slot, enum maple_type type) { - if (slot >= MAPLE_NODE_SLOTS) - return; - - if (mas_is_start(ms)) - return; - - if (ma_is_root(ms->node)) { - ms->max = mt_max[type]; - ms->min = 0; - } - if (slot > 0) ms->min = _ma_get_pivot(ms->node, slot - 1, type); @@ -646,27 +635,18 @@ static inline struct maple_node *mas_node_cnt(struct ma_state *ms, int count) static inline void *mas_start(struct ma_state *mas) { - void *entry; - - if (mas_is_err(mas)) - return NULL; - if (mas->node == MAS_START) { - entry = mas->tree->ma_root; - if (!xa_is_node(entry)) { + if (!xa_is_node(mas->tree->ma_root)) { if (mas->index > 0) return NULL; mas->node = MAS_ROOT; ma_set_slot(mas, MAPLE_NODE_SLOTS); + return NULL; } else { - entry = mt_safe_root(entry); + return mt_safe_root(mas->tree->ma_root); } - - } else { - entry = mas->node; } - - return entry; + return mas->node; } static inline unsigned char ma_data_end(const struct maple_node *mn, @@ -692,8 +672,8 @@ static inline unsigned char ma_data_end(const struct maple_node *mn, static inline unsigned char ma_calc_split(struct ma_state *mas, struct maple_node **left, struct maple_node **right) { - unsigned char i, j; - unsigned long min = mas->min; + char i, j; + unsigned long min = mas->max; unsigned long max = min; enum maple_type type = mt_node_type(mas->node); unsigned long pivot_cnt = mt_pivots[type]; @@ -726,13 +706,16 @@ static inline unsigned char ma_calc_split(struct ma_state *mas, else max = mas->max; - for (j = data_end - 1; j >= 0; j--) { + j = data_end; + do { + j--; min = ma_get_pivot(mas->node, j); if ((max - min) > 15) { j++; break; } - } + } while (j > 0); + if (data_end - j >= 4) { *left = mt_mk_node(*left, type); *right = mt_mk_node(*right, maple_dense); @@ -1334,7 +1317,6 @@ linear_node: ma_set_slot(mas, i); return ret; } - static inline bool mas_traverse(struct ma_state *mas, enum maple_type type) { unsigned char slot = ma_get_slot(mas); @@ -1390,18 +1372,14 @@ static inline void ma_insert(struct ma_state *mas, void *entry) mas_coalesce(mas); if (mas_is_err(mas)) - goto error; + return; /* Do the insert */ _ma_insert(mas, entry, slot); - if (mas_is_err(mas)) - goto error; - return; exists: mas_set_err(mas, -EEXIST); -error: return; } @@ -1430,17 +1408,11 @@ void *mas_walk(struct ma_state *mas) return NULL; } - /* Outside this nodes range, it doesn't exist. */ - if (mas->min > mas->index || - mas->max < mas->index) - return NULL; // FIXME: Retry? - leaf = _mas_walk(mas); slot = ma_get_slot(mas); if (leaf == true && slot != MAPLE_NODE_SLOTS) entry = ma_get_rcu_slot(mas->node, slot); - ma_set_slot(mas, 0); return entry; } @@ -1486,9 +1458,7 @@ int ma_erase(struct ma_state *mas) } mas_coalesce(mas); - if (mas_is_err(mas)) - goto error; -error: + /* Error may be returned, but it will be passed through anyways */ return cnt; } -- 2.50.1