maple_tree: try harder to keep active node with mas_prev()

[linux-block.git] / lib / maple_tree.c

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 3fa127624520c193f594c09be2bb9a434a407fe9..cd14c1db6b4d005ebfbb9ce2178db5d6304b1458 100644 (file)
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4828,7 +4828,7 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit,
                                    unsigned long index)
 {
        unsigned long pivot, min;
-       unsigned char offset;
+       unsigned char offset, count;
        struct maple_node *mn;
        enum maple_type mt;
        unsigned long *pivots;
@@ -4842,29 +4842,42 @@ retry:
        mn = mas_mn(mas);
        mt = mte_node_type(mas->node);
        offset = mas->offset - 1;
-       if (offset >= mt_slots[mt])
-               offset = mt_slots[mt] - 1;
-
        slots = ma_slots(mn, mt);
        pivots = ma_pivots(mn, mt);
+       count = ma_data_end(mn, mt, pivots, mas->max);
        if (unlikely(ma_dead_node(mn))) {
                mas_rewalk(mas, index);
                goto retry;
        }
 
-       if (offset == mt_pivots[mt])
+       offset = mas->offset - 1;
+       if (offset >= mt_slots[mt])
+               offset = mt_slots[mt] - 1;
+
+       if (offset >= count) {
                pivot = mas->max;
-       else
+               offset = count;
+       } else {
                pivot = pivots[offset];
+       }
 
        if (unlikely(ma_dead_node(mn))) {
                mas_rewalk(mas, index);
                goto retry;
        }
 
-       while (offset && ((!mas_slot(mas, slots, offset) && pivot >= limit) ||
-              !pivot))
+       while (offset && !mas_slot(mas, slots, offset)) {
                pivot = pivots[--offset];
+               if (pivot >= limit)
+                       break;
+       }
+
+       /*
+        * If the slot was null but we've shifted outside the limits, then set
+        * the range to the last NULL.
+        */
+       if (unlikely((pivot < limit) && (offset < mas->offset)))
+               pivot = pivots[++offset];
 
        min = mas_safe_min(mas, pivots, offset);
        entry = mas_slot(mas, slots, offset);
@@ -4873,32 +4886,33 @@ retry:
                goto retry;
        }
 
-       if (likely(entry)) {
-               mas->offset = offset;
-               mas->last = pivot;
-               mas->index = min;
-       }
+       mas->offset = offset;
+       mas->last = pivot;
+       mas->index = min;
        return entry;
 }
 
 static inline void *mas_prev_entry(struct ma_state *mas, unsigned long min)
 {
        void *entry;
+       struct maple_enode *prev_enode;
+       unsigned char prev_offset;
 
-       if (mas->index < min) {
-               mas->index = mas->last = min;
-               mas->node = MAS_NONE;
+       if (mas->index < min)
                return NULL;
-       }
+
 retry:
+       prev_enode = mas->node;
+       prev_offset = mas->offset;
        while (likely(!mas_is_none(mas))) {
                entry = mas_prev_nentry(mas, min, mas->index);
-               if (unlikely(mas->last < min))
-                       goto not_found;
 
                if (likely(entry))
                        return entry;
 
+               if (unlikely(mas->index <= min))
+                       return NULL;
+
                if (unlikely(mas_prev_node(mas, min))) {
                        mas_rewalk(mas, mas->index);
                        goto retry;
@@ -4907,9 +4921,8 @@ retry:
                mas->offset++;
        }
 
-       mas->offset--;
-not_found:
-       mas->index = mas->last = min;
+       mas->node = prev_enode;
+       mas->offset = prev_offset;
        return NULL;
 }
 
@@ -5952,15 +5965,8 @@ EXPORT_SYMBOL_GPL(mt_next);
  */
 void *mas_prev(struct ma_state *mas, unsigned long min)
 {
-       if (!mas->index) {
-               /* Nothing comes before 0 */
-               mas->last = 0;
-               mas->node = MAS_NONE;
-               return NULL;
-       }
-
-       if (unlikely(mas_is_ptr(mas)))
-               return NULL;
+       if (mas->index <= min)
+               goto none;
 
        if (mas_is_none(mas) || mas_is_paused(mas))
                mas->node = MAS_START;
@@ -5968,19 +5974,30 @@ void *mas_prev(struct ma_state *mas, unsigned long min)
        if (mas_is_start(mas)) {
                mas_walk(mas);
                if (!mas->index)
-                       return NULL;
+                       goto none;
        }
 
-       if (mas_is_ptr(mas)) {
-               if (!mas->index) {
-                       mas->last = 0;
-                       return NULL;
-               }
-
+       if (unlikely(mas_is_ptr(mas))) {
+               if (!mas->index)
+                       goto none;
                mas->index = mas->last = 0;
-               return mas_root_locked(mas);
+               return mas_root(mas);
+       }
+
+       if (mas_is_none(mas)) {
+               if (mas->index) {
+                       /* Walked to out-of-range pointer? */
+                       mas->index = mas->last = 0;
+                       mas->node = MAS_ROOT;
+                       return mas_root(mas);
+               }
+               return NULL;
        }
        return mas_prev_entry(mas, min);
+
+none:
+       mas->node = MAS_NONE;
+       return NULL;
 }
 EXPORT_SYMBOL_GPL(mas_prev);
 
@@ -6106,8 +6123,16 @@ EXPORT_SYMBOL_GPL(mas_find);
  */
 void *mas_find_rev(struct ma_state *mas, unsigned long min)
 {
+       if (unlikely(mas_is_none(mas))) {
+               if (mas->index <= min)
+                       goto none;
+
+               mas->last = mas->index;
+               mas->node = MAS_START;
+       }
+
        if (unlikely(mas_is_paused(mas))) {
-               if (unlikely(mas->last == ULONG_MAX)) {
+               if (unlikely(mas->index <= min)) {
                        mas->node = MAS_NONE;
                        return NULL;
                }
@@ -6127,14 +6152,30 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min)
                        return entry;
        }
 
-       if (unlikely(!mas_searchable(mas)))
-               return NULL;
+       if (unlikely(!mas_searchable(mas))) {
+               if (mas_is_ptr(mas))
+                       goto none;
+
+               if (mas_is_none(mas)) {
+                       /*
+                        * Walked to the location, and there was nothing so the
+                        * previous location is 0.
+                        */
+                       mas->last = mas->index = 0;
+                       mas->node = MAS_ROOT;
+                       return mas_root(mas);
+               }
+       }
 
        if (mas->index < min)
                return NULL;
 
        /* Retries on dead nodes handled by mas_prev_entry */
        return mas_prev_entry(mas, min);
+
+none:
+       mas->node = MAS_NONE;
+       return NULL;
 }
 EXPORT_SYMBOL_GPL(mas_find_rev);