Lines Matching refs:entry
18 * subtree with an entry attached to the value where as keys are unique to a
47 * the B-tree variants, it is known that one entry will either be added or
208 static inline enum maple_type mte_node_type(const struct maple_enode *entry)
210 return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) &
224 static inline bool mte_is_leaf(const struct maple_enode *entry)
226 return ma_is_leaf(mte_node_type(entry));
233 static inline bool mt_is_reserved(const void *entry)
235 return ((unsigned long)entry < MAPLE_RESERVED_RANGE) &&
236 xa_is_internal(entry);
286 static inline struct maple_node *mte_to_node(const struct maple_enode *entry)
288 return (struct maple_node *)((unsigned long)entry & ~MAPLE_NODE_MASK);
293 * @entry: The maple encoded node
297 static inline struct maple_topiary *mte_to_mat(const struct maple_enode *entry)
300 ((unsigned long)entry & ~MAPLE_NODE_MASK);
826 * Return: The entry stored in @slots at the @offset.
840 * Return: The entry stored in @slots at the @offset
1372 * - If it's a single entry: The entry & mas->node == MAS_ROOT
1404 /* Single entry tree */
1408 /* Single entry tree. */
1776 struct maple_enode *entry;
1786 entry = mas_slot_locked(mas, slots, offset);
1787 if (mte_parent(entry) == node) {
1881 * end on a NULL entry, with the exception of the left-most leaf. The
1924 /* Avoid ending a node on a NULL entry */
2093 * mas_store_b_node() - Store an @entry into the b_node while also copying the
2129 /* Store the new entry. */
2131 b_node->slot[b_end] = wr_mas->entry;
2428 * mab_set_b_end() - Add entry to b_node at b_node->b_end and increment the end
2430 * @b_node - the big node to add the entry
2432 * @entry - the entry to add, if NULL nothing happens.
2436 void *entry)
2438 if (!entry)
2441 b_node->slot[b_node->b_end] = entry;
3362 * overwrite more than one range or result in changing one entry into 3
3368 * for an entry followed by a contraction when the entry is removed. To
3504 * @entry: The entry to store into the tree
3506 static inline int mas_root_expand(struct ma_state *mas, void *entry)
3534 rcu_assign_pointer(slots[slot], entry);
3548 static inline void mas_store_root(struct ma_state *mas, void *entry)
3551 mas_root_expand(mas, entry);
3552 else if (((unsigned long) (entry) & 3) == 2)
3553 mas_root_expand(mas, entry);
3555 rcu_assign_pointer(mas->tree->ma_root, entry);
3566 * @entry: The data to write
3578 void *entry = wr_mas->entry;
3592 * The last entry of leaf node cannot be NULL unless it is the
3595 if (entry || last == ULONG_MAX)
3599 trace_ma_write(__func__, wr_mas->mas, wr_mas->r_max, entry);
3703 void *entry;
3705 entry = mas_start(mas);
3710 return entry;
3722 * Return: The entry for @mas->index or %NULL on dead node.
3767 * mas_new_root() - Create a new root node that only contains the entry passed
3770 * @entry: The entry to store.
3776 static inline int mas_new_root(struct ma_state *mas, void *entry)
3784 if (!entry && !mas->index && mas->last == ULONG_MAX) {
3787 rcu_assign_pointer(mas->tree->ma_root, entry);
3801 rcu_assign_pointer(slots[0], entry);
3832 MA_WR_STATE(r_wr_mas, &r_mas, wr_mas->entry);
3833 MA_WR_STATE(l_wr_mas, &l_mas, wr_mas->entry);
3843 * written to the last entry of a node is considered a spanning store as
3851 return mas_new_root(mas, wr_mas->entry);
3879 if (!wr_mas->entry) {
3889 return mas_new_root(mas, wr_mas->entry);
3966 /* Store the new entry and range end. */
3969 rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);
3999 trace_ma_write(__func__, mas, 0, wr_mas->entry);
4023 rcu_assign_pointer(slots[offset], wr_mas->entry);
4027 rcu_assign_pointer(slots[offset + 1], wr_mas->entry);
4037 rcu_assign_pointer(slots[offset + 1], wr_mas->entry);
4045 trace_ma_write(__func__, mas, 0, wr_mas->entry);
4047 * Only update gap when the new entry is empty or there is an empty
4048 * entry in the original two ranges.
4050 if (!wr_mas->entry || gap)
4103 if (!wr_mas->entry)
4160 rcu_assign_pointer(slots[new_end], wr_mas->entry);
4167 rcu_assign_pointer(slots[end], wr_mas->entry);
4173 rcu_assign_pointer(slots[end + 1], wr_mas->entry);
4178 if (!wr_mas->content || !wr_mas->entry)
4181 trace_ma_write(__func__, mas, new_end, wr_mas->entry);
4195 trace_ma_write(__func__, wr_mas->mas, 0, wr_mas->entry);
4208 rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry);
4209 if (!!wr_mas->entry ^ !!wr_mas->content)
4242 * @entry: The entry to store.
4252 mas_store_root(mas, wr_mas->entry);
4265 mas_new_root(mas, wr_mas->entry);
4276 * @entry: The entry to store
4281 static inline void *mas_insert(struct ma_state *mas, void *entry)
4283 MA_WR_STATE(wr_mas, mas, entry);
4290 * single pivot needs to be inserted (as well as writing the entry). If
4293 * usual, the entry must be written. Most operations require a new node
4304 mas_store_root(mas, entry);
4319 if (!entry)
4351 * mas_prev_node() - Find the prev non-null entry at the same level in the
4430 * mas_prev_slot() - Get the entry in the previous slot
4437 * Return: The entry in the previous slot which is possibly NULL
4442 void *entry;
4489 entry = mas_slot(mas, slots, mas->offset);
4493 if (likely(entry))
4494 return entry;
4503 return entry;
4593 * mas_next_slot() - Get the entry in the next slot
4601 * Return: The entry in the next slot which is possibly NULL
4613 void *entry;
4665 entry = mt_slot(mas->tree, slots, mas->offset);
4669 if (entry)
4670 return entry;
4681 return entry;
4690 * mas_next_entry() - Internal function to get the next entry.
4694 * Set the @mas->node to the next entry and the range_start to
4695 * the beginning value for the entry. Does not check beyond @limit.
4700 * Return: the next entry or %NULL.
4879 * Return: the entry at the location or %NULL.
4883 void *entry;
4888 entry = mas_state_walk(mas);
4897 return entry;
4906 return entry;
5145 void *entry;
5149 entry = mt_slot(mt, slots, offset);
5150 type = mte_node_type(entry);
5151 node = mte_to_node(entry);
5156 mte_set_node_dead(entry);
5367 if (wr_mas->entry)
5383 * mas_store() - Store an @entry.
5385 * @entry: The entry to store.
5387 * The @mas->index and @mas->last is used to set the range for the @entry.
5389 * store the entry. Please see mas_expected_entries()/mas_destroy() for more details.
5391 * Return: the first entry between mas->index and mas->last or %NULL.
5393 void *mas_store(struct ma_state *mas, void *entry)
5395 MA_WR_STATE(wr_mas, mas, entry);
5397 trace_ma_write(__func__, mas, 0, entry);
5400 pr_err("Error %lX > %lX %p\n", mas->index, mas->last, entry);
5424 * @entry: The entry to store
5430 int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp)
5432 MA_WR_STATE(wr_mas, mas, entry);
5435 trace_ma_write(__func__, mas, 0, entry);
5452 * @entry: The entry to store.
5454 void mas_store_prealloc(struct ma_state *mas, void *entry)
5456 MA_WR_STATE(wr_mas, mas, entry);
5459 trace_ma_write(__func__, mas, 0, entry);
5469 * @entry: The entry that will be stored
5474 int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
5476 MA_WR_STATE(wr_mas, mas, entry);
5628 * Avoid overflow, assume a gap between each entry and a trailing null.
5658 void **entry)
5677 *entry = mas_walk(mas);
5678 if (*entry)
5683 *entry = mas_walk(mas); /* Retries on dead nodes handled by mas_walk */
5686 *entry = NULL;
5704 * mas_next() - Get the next entry.
5708 * Returns the next entry after @mas->index.
5710 * Can return the zero entry.
5712 * Return: The next entry or %NULL
5716 void *entry = NULL;
5718 if (mas_next_setup(mas, max, &entry))
5719 return entry;
5733 * Can return the zero entry.
5735 * Return: The next entry or %NULL
5739 void *entry = NULL;
5741 if (mas_next_setup(mas, max, &entry))
5742 return entry;
5759 * Return: The entry higher than @index or %NULL if nothing is found.
5763 void *entry = NULL;
5767 entry = mas_next(&mas, max);
5769 return entry;
5774 void **entry)
5786 *entry = mas_walk(mas);
5787 if (*entry)
5805 *entry = mas_root(mas);
5814 *entry = mas_root(mas);
5828 * mas_prev() - Get the previous entry
5840 void *entry = NULL;
5842 if (mas_prev_setup(mas, min, &entry))
5843 return entry;
5863 void *entry = NULL;
5865 if (mas_prev_setup(mas, min, &entry))
5866 return entry;
5882 * Return: The entry before @index or %NULL if nothing is found.
5886 void *entry = NULL;
5890 entry = mas_prev(&mas, min);
5892 return entry;
5902 * on an entry. Those users should call this function before they drop
5919 * @entry: Pointer to the entry
5921 * Returns: True if entry is the answer, false otherwise.
5924 void **entry)
5959 *entry = mas_walk(mas);
5960 if (*entry)
5985 * mas_find() - On the first call, find the entry at or after mas->index up to
5986 * %max. Otherwise, find the entry after mas->index.
5991 * If an entry exists, last and index are updated accordingly.
5994 * Return: The entry or %NULL.
5998 void *entry = NULL;
6000 if (mas_find_setup(mas, max, &entry))
6001 return entry;
6009 * mas_find_range() - On the first call, find the entry at or after
6015 * If an entry exists, last and index are updated accordingly.
6018 * Return: The entry or %NULL.
6022 void *entry = NULL;
6024 if (mas_find_setup(mas, max, &entry))
6025 return entry;
6036 * @entry: Pointer to the entry
6038 * Returns: True if entry is the answer, false otherwise.
6041 void **entry)
6077 *entry = mas_walk(mas);
6078 if (*entry)
6093 *entry = mas_root(mas);
6109 * mas_find_rev: On the first call, find the first non-null entry at or below
6110 * mas->index down to %min. Otherwise find the first non-null entry below
6116 * If an entry exists, last and index are updated accordingly.
6119 * Return: The entry or %NULL.
6123 void *entry = NULL;
6125 if (mas_find_rev_setup(mas, min, &entry))
6126 return entry;
6135 * mas_find_range_rev: On the first call, find the first non-null entry at or
6142 * If an entry exists, last and index are updated accordingly.
6145 * Return: The entry or %NULL.
6149 void *entry = NULL;
6151 if (mas_find_rev_setup(mas, min, &entry))
6152 return entry;
6168 * Return: the entry that was erased or %NULL, @mas->index and @mas->last are updated.
6172 void *entry;
6179 entry = mas_state_walk(mas);
6180 if (!entry)
6191 return entry;
6237 * Return: the entry or %NULL
6242 void *entry;
6247 entry = mas_start(&mas);
6253 entry = NULL;
6258 entry = mtree_lookup_walk(&mas);
6259 if (!entry && unlikely(mas_is_start(&mas)))
6263 if (xa_is_zero(entry))
6266 return entry;
6271 * mtree_store_range() - Store an entry at a given range.
6275 * @entry: The entry to store
6282 unsigned long last, void *entry, gfp_t gfp)
6285 MA_WR_STATE(wr_mas, &mas, entry);
6287 trace_ma_write(__func__, &mas, 0, entry);
6288 if (WARN_ON_ONCE(xa_is_advanced(entry)))
6309 * mtree_store() - Store an entry at a given index.
6312 * @entry: The entry to store
6318 int mtree_store(struct maple_tree *mt, unsigned long index, void *entry,
6321 return mtree_store_range(mt, index, index, entry, gfp);
6326 * mtree_insert_range() - Insert an entry at a given range if there is no value.
6330 * @entry: The entry to store
6337 unsigned long last, void *entry, gfp_t gfp)
6341 if (WARN_ON_ONCE(xa_is_advanced(entry)))
6349 mas_insert(&ms, entry);
6362 * mtree_insert() - Insert an entry at a given index if there is no value.
6365 * @entry: The entry to store
6371 int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry,
6374 return mtree_insert_range(mt, index, index, entry, gfp);
6379 void *entry, unsigned long size, unsigned long min,
6388 if (WARN_ON_ONCE(mt_is_reserved(entry)))
6397 mas_insert(&mas, entry);
6417 void *entry, unsigned long size, unsigned long min,
6426 if (WARN_ON_ONCE(mt_is_reserved(entry)))
6435 mas_insert(&mas, entry);
6459 * Erasing is the same as a walk to an entry then a store of a NULL to that
6462 * Return: The entry stored at the @index or %NULL
6466 void *entry = NULL;
6472 entry = mas_erase(&mas);
6475 return entry;
6512 * mt_find() - Search from the start up until an entry is found.
6521 * In case that an entry is found @index is updated to point to the next
6522 * possible entry independent whether the found entry is occupying a
6525 * Return: The entry at or after the @index or %NULL
6530 void *entry;
6542 entry = mas_state_walk(&mas);
6546 if (unlikely(xa_is_zero(entry)))
6547 entry = NULL;
6549 if (entry)
6553 entry = mas_next_entry(&mas, max);
6554 if (likely(entry && !xa_is_zero(entry)))
6558 if (unlikely(xa_is_zero(entry)))
6559 entry = NULL;
6562 if (likely(entry)) {
6571 return entry;
6576 * mt_find_after() - Search from the start up until an entry is found.
6585 * Return: The entry at or after the @index or %NULL
6675 * mas_get_slot() - Get the entry in the maple state node stored at @offset.
6679 * Return: The entry stored at @offset.
6717 static void mt_dump_node(const struct maple_tree *mt, void *entry,
6741 static void mt_dump_entry(void *entry, unsigned long min, unsigned long max,
6746 if (xa_is_value(entry))
6747 pr_cont("value %ld (0x%lx) [%p]\n", xa_to_value(entry),
6748 xa_to_value(entry), entry);
6749 else if (xa_is_zero(entry))
6750 pr_cont("zero (%ld)\n", xa_to_internal(entry));
6751 else if (mt_is_reserved(entry))
6752 pr_cont("UNKNOWN ENTRY (%p)\n", entry);
6754 pr_cont("%p\n", entry);
6757 static void mt_dump_range64(const struct maple_tree *mt, void *entry,
6761 struct maple_range_64 *node = &mte_to_node(entry)->mr64;
6762 bool leaf = mte_is_leaf(entry);
6783 else if (!node->slot[i] && max != mt_node_max(entry))
6812 static void mt_dump_arange64(const struct maple_tree *mt, void *entry,
6816 struct maple_arange_64 *node = &mte_to_node(entry)->ma64;
6817 bool leaf = mte_is_leaf(entry);
6871 static void mt_dump_node(const struct maple_tree *mt, void *entry,
6875 struct maple_node *node = mte_to_node(entry);
6876 unsigned int type = mte_node_type(entry);
6895 mt_dump_range64(mt, entry, min, max, depth, format);
6898 mt_dump_arange64(mt, entry, min, max, depth, format);
6908 void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt));
6911 mt, mt->ma_flags, mt_height(mt), entry);
6912 if (!xa_is_node(entry))
6913 mt_dump_entry(entry, 0, 0, 0, format);
6914 else if (entry)
6915 mt_dump_node(mt, entry, 0, mt_node_max(entry), 0, format);
6956 void *entry = mas_get_slot(mas, i);
6959 MT_BUG_ON(mas->tree, !entry);
7032 /* Check prev/next parent slot for duplicate node entry */
7140 void *entry = mas_slot(mas, slots, i);
7142 if (entry && (i != mt_slots[type] - 1)) {
7143 pr_err("%p[%u] should not have entry %p\n", mas_mn(mas),
7144 i, entry);
7145 MT_BUG_ON(mas->tree, entry != NULL);
7163 void *entry, *last = (void *)1;
7177 entry = mas_slot(&mas, slots, offset);
7178 if (!last && !entry) {
7182 MT_BUG_ON(mt, !last && !entry);
7183 last = entry;