[PATCH v2 4/5] maple_tree: refine mas_root_expand() on storing NULL

[Wei Yang]

Currently, when storing NULL on mas_root_expand(), the behavior could be
improved.

For example possible cases are:

  * store NULL at any range result a new node
  * store NULL at range [m, n] where m > 0 to a single entry tree result
    a new node with range [m, n] set to NULL
  * store NULL at range [m, n] where m > 0 to an empty tree result
    consecutive NULL slot

This patch tries to improve in:

  * memory efficient by setting to empty tree instead of using a node
  * remove the possibility of consecutive NULL slot which will prohibit
    extended null in later operation

Signed-off-by: Wei Yang <richard.weiyang at gmail.com>
CC: Liam R. Howlett <Liam.Howlett at Oracle.com>
CC: Sidhartha Kumar <sidhartha.kumar at oracle.com>
CC: Lorenzo Stoakes <lorenzo.stoakes at oracle.com>
---
 lib/maple_tree.c | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index a90c29156fe2..15d2124acc36 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3335,6 +3335,24 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)
 	unsigned long *pivots;
 	int slot = 0;
 
+	if (!entry) {
+		/*
+		 * We come here in two cases:
+		 * 1. This is an empty tree
+		 * 2. This is a single entry tree with range [0, 0]
+		 *
+		 * If this is an empty tree, the result should still be an
+		 * empty tree no matter what the range is.
+		 *
+		 * If this is a single entry tree, we should set it to an
+		 * empty tree if the range cover [0, 0]. Otherwise, we don't
+		 * need to change it.
+		 */
+		if (!mas->index && contents)
+			rcu_assign_pointer(mas->tree->ma_root, NULL);
+		return;
+	}
+
 	node = mas_pop_node(mas);
 	pivots = ma_pivots(node, type);
 	slots = ma_slots(node, type);
-- 
2.34.1