From b358aed72d31f6f3ed598ab92142e8d237132ad7 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Tue, 27 Oct 2020 20:24:50 -0400
Subject: [PATCH] maple_tree: Some optimizations, I hope

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
 lib/maple_tree.c | 53 ++++++++++++++++++++++++------------------------
 1 file changed, 27 insertions(+), 26 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index f2035bb0e3b1..b76f0100f2fc 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1038,21 +1038,20 @@ static inline unsigned char mas_data_end(struct ma_state *mas)
 	unsigned long piv, *pivots = ma_pivots(mas_mn(mas), type);
 
 	if (pivots[offset]) {
-		while (offset < mt_slots[type]) {
+		do {
 			piv = mas_logical_pivot(mas, pivots, offset, type);
 			if (piv >= mas->max)
 				break;
 
-			offset++;
-		}
+		} while (++offset < mt_slots[type]);
 	} else {
-		offset--;
-		do {
-			if (pivots[offset])
+		while (--offset) {
+			if (pivots[offset]) {
+				if (pivots[offset] < mas->max)
+					offset++;
 				break;
-		} while (--offset);
-		if (pivots[offset] < mas->max)
-			offset++;
+			}
+		};
 	}
 
 	return offset;
@@ -1066,14 +1065,15 @@ static inline unsigned char mas_data_end(struct ma_state *mas)
 static inline unsigned long mas_leaf_max_gap(struct ma_state *mas)
 {
 	enum maple_type mt = mte_node_type(mas->node);
-	unsigned long *pivots = ma_pivots(mas_mn(mas), mt);
 	unsigned long pstart, pend, gap = 0, max_gap = 0;
-	void **slots = ma_slots(mas_mn(mas), mt);
+	struct maple_node *mn = mas_mn(mas);
+	unsigned long *pivots = ma_pivots(mn, mt);
+	void **slots = ma_slots(mn, mt);
 	unsigned char i;
 
 	if (ma_is_dense(mt)) {
 		for (i = 0; i < mt_slot_count(mas->node); i++) {
-			if (mas_slot_locked(mas, slots, i)) {
+			if (slots[i]) {
 				if (gap > max_gap)
 					max_gap = gap;
 				gap = 0;
@@ -2877,21 +2877,22 @@ bool mas_is_span_wr(struct ma_state *mas, unsigned long piv,
 	if (piv > mas->last) // Contained in this pivot
 		return false;
 
+	if (ma_is_leaf(type)) {
+		if (mas->last < mas->max) // Fits in the node, but may span slots.
+			return false;
+
+		if ((mas->last == mas->max) && entry) // Writes to the end of the node but not null.
+			return false;
+	} else if ((piv == mas->last) && entry) {
+		return false;
+	}
+
 	/* Writing ULONG_MAX is not a spanning write regardless of the value
 	 * being written as long as the range fits in the node.
 	 */
 	if ((mas->last == ULONG_MAX) && (mas->last == mas->max))
 		return false;
 
-	if (ma_is_leaf(type)) {
-		if (mas->last < mas->max) // Fits in the node, but may span slots.
-			return false;
-		if (entry && (mas->last == mas->max)) // Writes to the end of the node but not null.
-			return false;
-	} else {
-		if (entry && piv == mas->last)
-			return false;
-	}
 	trace_mas_is_span_wr(mas, piv, entry);
 
 	return true;
@@ -2962,7 +2963,7 @@ bool mas_wr_walk(struct ma_state *mas, unsigned long *range_min,
 			return false;
 
 		if (ma_is_leaf(type))
-			break;
+			return true;
 
 		// Traverse.
 		mas->max = *range_max;
@@ -4351,16 +4352,16 @@ static inline void *mas_range_load(struct ma_state *mas, unsigned long *range_mi
 
 retry:
 	if (_mas_walk(mas, range_min, range_max)) {
-		unsigned char slot = MAPLE_NODE_SLOTS;
+		unsigned char offset = MAPLE_NODE_SLOTS;
 
 		if (mas_is_ptr(mas) && mas->last == 0)
 			return mte_safe_root(mas->tree->ma_root);
 
-		slot = mas_offset(mas);
-		if (slot >= MAPLE_NODE_SLOTS)
+		offset = mas_offset(mas);
+		if (offset >= MAPLE_NODE_SLOTS)
 			return NULL;
 
-		entry = mas_get_slot(mas, slot);
+		entry = mas_get_slot(mas, offset);
 		if (mte_dead_node(mas->node))
 			goto retry;
 	}
-- 
2.50.1