From fd3f26b825034172b89f2452bafb39cb89d83910 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 28 Sep 2020 15:21:06 -0400 Subject: [PATCH] maple_tree: Optimize gap calcs Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 110 +++++++++++++++++++++++++---------------------- 1 file changed, 59 insertions(+), 51 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 7e415e5ef0aa..2213dfefe566 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1097,49 +1097,53 @@ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) return max_gap; } - pstart = mas->min; - for (i = 0; i < mt_slots[mt]; i++) { - pend = mas_logical_pivot(mas, pivots, i, mt); + pstart = mas->min; + for (i = 0; i < mt_slots[mt]; i++) { + pend = mas_logical_pivot(mas, pivots, i, mt); - if (slots[i]) - goto next; + if (slots[i]) + goto next; - gap = pend - pstart + 1; - if (gap > max_gap) - max_gap = gap; + gap = pend - pstart + 1; + if (gap > max_gap) + max_gap = gap; next: - if (pend >= mas->max) - break; - pstart = pend + 1; - } - return max_gap; - } + if (pend >= mas->max) + break; + pstart = pend + 1; + } + return max_gap; +} +static inline unsigned long +ma_max_gap(unsigned long *pivots, unsigned long *gaps, enum maple_type mt) +{ + unsigned char i = mt_slots[mt] - 1; + unsigned long max_gap = gaps[i--]; + do { + if (!pivots[i]) + continue; + + if (gaps[i] > max_gap) + max_gap = gaps[i]; + } while(i--); + return max_gap; +} /* * mas_max_gap() - find the largest gap in a non-leaf node and set the slot. */ static inline unsigned long mas_max_gap(struct ma_state *mas) { unsigned long *gaps, *pivots; - unsigned long max_gap; enum maple_type mt; - unsigned char i; + if (mte_is_leaf(mas->node)) + return mas_leaf_max_gap(mas); mt = mte_node_type(mas->node); gaps = ma_gaps(mas_mn(mas), mt); pivots = ma_pivots(mas_mn(mas), mt); - i = mt_slots[mt] - 1; - max_gap = gaps[i--]; - do { - if (!pivots[i]) - continue; - - if (gaps[i] > max_gap) - max_gap = gaps[i]; - } while(i--); - - return max_gap; + return ma_max_gap(pivots, gaps, mt); } static inline unsigned long mas_tree_gap(struct ma_state *mas) { @@ -1158,39 +1162,42 @@ static inline unsigned long mas_tree_gap(struct ma_state *mas) return mas_max_gap(mas); } -static inline unsigned long mas_find_gap(struct ma_state *mas) -{ - if (mte_is_leaf(mas->node)) - return mas_leaf_max_gap(mas); - return mas_max_gap(mas); -} - static inline void mas_parent_gap(struct ma_state *mas, unsigned char slot, unsigned long new) { unsigned long old_max_gap = 0; + struct maple_node *pnode, *gpnode = NULL; // parent and grand parent nodes. + struct maple_enode *penode; + unsigned long *ppivots, *pgaps, *gpgaps = NULL; + enum maple_type pmt, gpmt; - /* Don't mess with mas state, use a new state */ - MA_STATE(gaps, mas->tree, mas->index, mas->last); - mas_dup_state(&gaps, mas); + pnode = mte_parent(mas->node); + pmt = gpmt = mas_parent_enum(mas, mas->node); + penode = mt_mk_node(pnode, pmt); + pgaps = ma_gaps(pnode, pmt); ascend: - /* Go to the parent node. */ - gaps.node = mt_mk_node(mte_parent(gaps.node), - mas_parent_enum(&gaps, gaps.node)); - //old_max_gap = mas_max_gap(&gaps); - if (!mte_is_root(gaps.node)) - old_max_gap = mas_tree_gap(&gaps); - mte_set_gap(gaps.node, slot, new); - if (mte_is_root(gaps.node)) + if (!mte_is_root(penode)) { + gpnode = mte_parent(penode); + gpmt = mas_parent_enum(mas, penode); + gpgaps = ma_gaps(gpnode, gpmt); + old_max_gap = gpgaps[slot]; + } + pgaps[slot] = new; + if (mte_is_root(penode)) return; - new = mas_max_gap(&gaps); + ppivots = ma_pivots(pnode, pmt); + new = ma_max_gap(ppivots, pgaps, pmt); if (new == old_max_gap) return; - - slot = mte_parent_slot(gaps.node); + /* Go to the parent node. */ + pnode = gpnode; + pmt = gpmt; + pgaps = gpgaps; + slot = mte_parent_slot(penode); + penode = mt_mk_node(pnode, pmt); goto ascend; } @@ -1210,14 +1217,15 @@ static inline void mas_update_gap(struct ma_state *mas) if (mte_is_root(mas->node)) return; - max_gap = mas_find_gap(mas); + max_gap = mas_max_gap(mas); /* Get the gap reported in the parent */ pslot = mte_parent_slot(mas->node); p_gap = ma_gaps(mte_parent(mas->node), mas_parent_enum(mas, mas->node))[pslot]; - if (p_gap != max_gap) + if (p_gap != max_gap) { mas_parent_gap(mas, pslot, max_gap); + } } /* @@ -1990,7 +1998,7 @@ static inline void mab_set_b_end(struct maple_big_node *b_node, b_node->slot[b_node->b_end] = entry; if (mt_is_alloc(mas->tree)) - b_node->gap[b_node->b_end] = mas_find_gap(mas); + b_node->gap[b_node->b_end] = mas_max_gap(mas); b_node->pivot[b_node->b_end++] = mas->max; } -- 2.50.1