From aa043687683687848b4b37bc2249643a33ca6633 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 29 Oct 2020 13:54:49 -0400 Subject: [PATCH] maple_tree: Don't use mas_extend_null in _mas_store() mas_extend_null() is too heavy when the nulls are contained within a single node. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 44 +++++++++++++++++++++++++++++++++----------- 1 file changed, 33 insertions(+), 11 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ce4e13738b3a..eb8f549b4537 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3303,20 +3303,42 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite } if (!entry) { - unsigned long rmin, rmax; enum maple_type mt = mte_node_type(mas->node); unsigned long *pivots = ma_pivots(mas_mn(mas),mt); + void **slots = ma_slots(mas_mn(mas), mt); + unsigned char offset_end = mas->offset; + + if (!content) { + if (mas->index > r_min) + mas->index = r_min; + if (mas->last < r_max) + mas->last = r_max; + // if this one is null the next and prev are not. + } else { + // Check prev slot if we are overwriting the start. + if (mas->index == r_min && mas->offset && + !slots[mas->offset - 1]) { + mas->offset--; + r_min = mas->index = mas_safe_min(mas, pivots, + mas->offset); + r_max = pivots[mas->offset]; + } - MA_STATE(r_mas, mas->tree, mas->last, mas->last); - - r_mas.offset = mas->offset; - r_mas.node = mas->node; - mas_node_walk(&r_mas, mte_node_type(r_mas.node), &rmin, - &rmax); - mas_extend_null(mas, &r_mas); - mas->last = r_mas.last; - r_min = mas_safe_min(mas, pivots, mas->offset); - r_max = _mas_safe_pivot(mas, pivots, mas->offset, mt); + // Check next slot if we are overwriting the end. + if (mas->last == r_max && !slots[mas->offset + 1]) { + mas->last = pivots[mas->offset + 1]; + } + else if (mas->last > r_max) { // expand over this slot if necessary. + unsigned long piv; + do { + piv = _mas_safe_pivot(mas, pivots, + ++offset_end, mt); + } while (mas->last > piv); + + if (!slots[offset_end]) + mas->last = piv; + } + } } end = mas_data_end(mas); -- 2.50.1