diff options
| -rw-r--r-- | lib/maple_tree.c | 229 |
1 files changed, 104 insertions, 125 deletions
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 536504c5ca28..205664f46e58 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4607,11 +4607,10 @@ no_entry: static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, unsigned long max) { - unsigned long min, pivot; + unsigned long min; unsigned long *pivots; struct maple_enode *enode; int level = 0; - unsigned char offset; unsigned char node_end; enum maple_type mt; void __rcu **slots; @@ -4619,19 +4618,16 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, if (mas->max >= max) goto no_entry; + min = mas->max + 1; level = 0; do { if (ma_is_root(node)) goto no_entry; - min = mas->max + 1; - if (min > max) - goto no_entry; - + /* Walk up. */ if (unlikely(mas_ascend(mas))) return 1; - offset = mas->offset; level++; node = mas_mn(mas); mt = mte_node_type(mas->node); @@ -4640,36 +4636,37 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, if (unlikely(ma_dead_node(node))) return 1; - } while (unlikely(offset == node_end)); + } while (unlikely(mas->offset == node_end)); slots = ma_slots(node, mt); - pivot = mas_safe_pivot(mas, pivots, ++offset, mt); - while (unlikely(level > 1)) { - /* Descend, if necessary */ - enode = mas_slot(mas, slots, offset); - if (unlikely(ma_dead_node(node))) - return 1; + mas->offset++; + enode = mas_slot(mas, slots, mas->offset); + if (unlikely(ma_dead_node(node))) + return 1; - mas->node = enode; + if (level > 1) + mas->offset = 0; + + while (unlikely(level > 1)) { level--; + mas->node = enode; node = mas_mn(mas); mt = mte_node_type(mas->node); slots = ma_slots(node, mt); - pivots = ma_pivots(node, mt); + enode = mas_slot(mas, slots, 0); if (unlikely(ma_dead_node(node))) return 1; - - offset = 0; - pivot = pivots[0]; } - enode = mas_slot(mas, slots, offset); + if (!mas->offset) + pivots = ma_pivots(node, mt); + + mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt); if (unlikely(ma_dead_node(node))) return 1; mas->node = enode; mas->min = min; - mas->max = pivot; return 0; no_entry: @@ -4680,83 +4677,106 @@ no_entry: return 0; } +static inline void mas_rewalk(struct ma_state *mas, unsigned long index) +{ +retry: + mas_set(mas, index); + mas_state_walk(mas); + if (mas_is_start(mas)) + goto retry; +} + +static inline bool mas_rewalk_if_dead(struct ma_state *mas, + struct maple_node *node, const unsigned long index) +{ + if (unlikely(ma_dead_node(node))) { + mas_rewalk(mas, index); + return true; + } + return false; +} + /* - * mas_next_nentry() - Get the next node entry - * @mas: The maple state - * @max: The maximum value to check - * @*range_start: Pointer to store the start of the range. + * mas_next_slot() - Get the entry in the next slot * - * Sets @mas->offset to the offset of the next node entry, @mas->last to the - * pivot of the entry. + * @mas: The maple state + * @max: The maximum starting range + * @empty: Can be empty * - * Return: The next entry, %NULL otherwise + * Return: The entry in the next slot which is possibly NULL */ -static inline void *mas_next_nentry(struct ma_state *mas, - struct maple_node *node, unsigned long max, enum maple_type type) +static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) { - unsigned char count; - unsigned long pivot; - unsigned long *pivots; void __rcu **slots; + unsigned long *pivots; + unsigned long pivot; + enum maple_type type; + struct maple_node *node; + unsigned char data_end; + unsigned long save_point = mas->last; void *entry; - if (mas->last == mas->max) { - mas->index = mas->max; - return NULL; - } - - slots = ma_slots(node, type); +retry: + node = mas_mn(mas); + type = mte_node_type(mas->node); pivots = ma_pivots(node, type); - count = ma_data_end(node, type, pivots, mas->max); - if (unlikely(ma_dead_node(node))) - return NULL; - - mas->index = mas_safe_min(mas, pivots, mas->offset); - if (unlikely(ma_dead_node(node))) - return NULL; - - if (mas->index > max) - return NULL; - - if (mas->offset > count) - return NULL; + data_end = ma_data_end(node, type, pivots, mas->max); + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; - while (mas->offset < count) { - pivot = pivots[mas->offset]; - entry = mas_slot(mas, slots, mas->offset); - if (ma_dead_node(node)) - return NULL; +again: + if (mas->max >= max) { + if (likely(mas->offset < data_end)) + pivot = pivots[mas->offset]; + else + return NULL; /* must be mas->max */ - mas->last = pivot; - if (entry) - return entry; + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; if (pivot >= max) return NULL; + } - if (pivot >= mas->max) + if (likely(mas->offset < data_end)) { + mas->index = pivots[mas->offset] + 1; + mas->offset++; + if (likely(mas->offset < data_end)) + mas->last = pivots[mas->offset]; + else + mas->last = mas->max; + } else { + if (mas_next_node(mas, node, max)) { + mas_rewalk(mas, save_point); + goto retry; + } + + if (mas_is_none(mas)) return NULL; - mas->index = pivot + 1; - mas->offset++; + mas->offset = 0; + mas->index = mas->min; + node = mas_mn(mas); + type = mte_node_type(mas->node); + pivots = ma_pivots(node, type); + mas->last = pivots[0]; } - pivot = mas_logical_pivot(mas, pivots, mas->offset, type); - entry = mas_slot(mas, slots, mas->offset); - if (ma_dead_node(node)) - return NULL; + slots = ma_slots(node, type); + entry = mt_slot(mas->tree, slots, mas->offset); + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; - mas->last = pivot; - return entry; -} + if (entry) + return entry; -static inline void mas_rewalk(struct ma_state *mas, unsigned long index) -{ -retry: - mas_set(mas, index); - mas_state_walk(mas); - if (mas_is_start(mas)) - goto retry; + if (!empty) { + if (!mas->offset) + data_end = 2; + goto again; + } + + return entry; } /* @@ -4774,47 +4794,12 @@ retry: static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) { void *entry = NULL; - struct maple_node *node; - unsigned long last; - enum maple_type mt; if (mas->last >= limit) return NULL; - last = mas->last; -retry: - node = mas_mn(mas); - mt = mte_node_type(mas->node); - mas->offset++; - if (unlikely(mas->offset >= mt_slots[mt])) { - mas->offset = mt_slots[mt] - 1; - goto next_node; - } - - while (!mas_is_none(mas)) { - entry = mas_next_nentry(mas, node, limit, mt); - if (unlikely(ma_dead_node(node))) { - mas_rewalk(mas, last); - goto retry; - } - - if (likely(entry)) - return entry; - - if (unlikely((mas->last >= limit))) - return NULL; - -next_node: - if (unlikely(mas_next_node(mas, node, limit))) { - mas_rewalk(mas, last); - goto retry; - } - mas->offset = 0; - node = mas_mn(mas); - mt = mte_node_type(mas->node); - } - - return NULL; + entry = mas_next_slot(mas, limit, false); + return entry; } /* @@ -4845,10 +4830,8 @@ retry: 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); + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) goto retry; - } offset = mas->offset - 1; if (offset >= mt_slots[mt]) @@ -4861,10 +4844,8 @@ retry: pivot = pivots[offset]; } - if (unlikely(ma_dead_node(mn))) { - mas_rewalk(mas, index); + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) goto retry; - } while (offset && !mas_slot(mas, slots, offset)) { pivot = pivots[--offset]; @@ -4881,10 +4862,8 @@ retry: min = mas_safe_min(mas, pivots, offset); entry = mas_slot(mas, slots, offset); - if (unlikely(ma_dead_node(mn))) { - mas_rewalk(mas, index); + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) goto retry; - } mas->offset = offset; mas->last = pivot; @@ -6103,8 +6082,8 @@ void *mas_find(struct ma_state *mas, unsigned long max) if (mas->index == max) return NULL; - /* Retries on dead nodes handled by mas_next_entry */ - return mas_next_entry(mas, max); + /* Retries on dead nodes handled by mas_next_slot */ + return mas_next_slot(mas, max, false); ptr_out_of_range: mas->node = MAS_NONE; |