Lines Matching full:mt
215 static inline unsigned int mt_attr(struct maple_tree *mt) in mt_attr() argument
217 return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK; in mt_attr()
381 static __always_inline bool mt_is_alloc(struct maple_tree *mt) in mt_is_alloc() argument
383 return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE); in mt_is_alloc()
754 * @mt: The maple node type
758 static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt) in ma_slots() argument
760 switch (mt) { in ma_slots()
773 static inline bool mt_write_locked(const struct maple_tree *mt) in mt_write_locked() argument
775 return mt_external_lock(mt) ? mt_write_lock_is_held(mt) : in mt_write_locked()
776 lockdep_is_held(&mt->ma_lock); in mt_write_locked()
779 static __always_inline bool mt_locked(const struct maple_tree *mt) in mt_locked() argument
781 return mt_external_lock(mt) ? mt_lock_is_held(mt) : in mt_locked()
782 lockdep_is_held(&mt->ma_lock); in mt_locked()
785 static __always_inline void *mt_slot(const struct maple_tree *mt, in mt_slot() argument
788 return rcu_dereference_check(slots[offset], mt_locked(mt)); in mt_slot()
791 static __always_inline void *mt_slot_locked(struct maple_tree *mt, in mt_slot_locked() argument
794 return rcu_dereference_protected(slots[offset], mt_write_locked(mt)); in mt_slot_locked()
835 static inline void *mt_root_locked(struct maple_tree *mt) in mt_root_locked() argument
837 return rcu_dereference_protected(mt->ma_root, mt_write_locked(mt)); in mt_root_locked()
852 enum maple_type mt) in ma_meta() argument
854 switch (mt) { in ma_meta()
865 * @mt: The maple node type
869 static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt, in ma_set_meta() argument
872 struct maple_metadata *meta = ma_meta(mn, mt); in ma_set_meta()
880 * @mt: The maple tree
886 static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn, in mt_clear_meta() argument
899 next = mt_slot_locked(mt, slots, in mt_clear_meta()
920 * @mt: The maple node type
923 enum maple_type mt) in ma_meta_end() argument
925 struct maple_metadata *meta = ma_meta(mn, mt); in ma_meta_end()
945 static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt, in ma_set_meta_gap() argument
949 struct maple_metadata *meta = ma_meta(mn, mt); in ma_set_meta_gap()
976 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
1471 enum maple_type mt; in mas_leaf_max_gap() local
1479 mt = mte_node_type(mas->node); in mas_leaf_max_gap()
1481 slots = ma_slots(mn, mt); in mas_leaf_max_gap()
1483 if (unlikely(ma_is_dense(mt))) { in mas_leaf_max_gap()
1485 for (i = 0; i < mt_slots[mt]; i++) { in mas_leaf_max_gap()
1503 pivots = ma_pivots(mn, mt); in mas_leaf_max_gap()
1512 max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1; in mas_leaf_max_gap()
1546 * @mt: The maple node type
1554 ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, in ma_max_gap() argument
1560 i = offset = ma_meta_end(node, mt); in ma_max_gap()
1582 enum maple_type mt; in mas_max_gap() local
1585 mt = mte_node_type(mas->node); in mas_max_gap()
1586 if (ma_is_leaf(mt)) in mas_max_gap()
1590 MAS_BUG_ON(mas, mt != maple_arange_64); in mas_max_gap()
1592 gaps = ma_gaps(node, mt); in mas_max_gap()
1752 enum maple_type mt; in mas_find_child() local
1760 mt = mte_node_type(mas->node); in mas_find_child()
1762 slots = ma_slots(node, mt); in mas_find_child()
1763 pivots = ma_pivots(node, mt); in mas_find_child()
1764 end = ma_data_end(node, mt, pivots, mas->max); in mas_find_child()
1926 enum maple_type mt; in mas_mab_cp() local
1934 mt = mte_node_type(mas->node); in mas_mab_cp()
1935 pivots = ma_pivots(node, mt); in mas_mab_cp()
1943 piv_end = min(mas_end, mt_pivots[mt]); in mas_mab_cp()
1954 b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); in mas_mab_cp()
1959 slots = ma_slots(node, mt); in mas_mab_cp()
1961 if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) { in mas_mab_cp()
1962 gaps = ma_gaps(node, mt); in mas_mab_cp()
1971 * @mt: The maple type
1975 enum maple_type mt, unsigned char end) in mas_leaf_set_meta() argument
1977 if (end < mt_slots[mt] - 1) in mas_leaf_set_meta()
1978 ma_set_meta(node, mt, 0, end); in mas_leaf_set_meta()
1993 enum maple_type mt = mte_node_type(mas->node); in mab_mas_cp() local
1995 void __rcu **slots = ma_slots(node, mt); in mab_mas_cp()
1996 unsigned long *pivots = ma_pivots(node, mt); in mab_mas_cp()
2000 if (mab_end - mab_start > mt_pivots[mt]) in mab_mas_cp()
2003 if (!pivots[mt_pivots[mt] - 1]) in mab_mas_cp()
2004 slots[mt_pivots[mt]] = NULL; in mab_mas_cp()
2018 if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { in mab_mas_cp()
2022 gaps = ma_gaps(node, mt); in mab_mas_cp()
2031 ma_set_meta(node, mt, offset, end); in mab_mas_cp()
2033 mas_leaf_set_meta(node, mt, end); in mab_mas_cp()
2041 * @mt: The maple node type
2044 enum maple_type mt) in mas_bulk_rebalance() argument
2052 if (end > mt_min_slots[mt]) { in mas_bulk_rebalance()
3019 enum maple_type mt = mte_node_type(mas->node); in mas_destroy_rebalance() local
3022 unsigned char offset, tmp, split = mt_slots[mt] / 2; in mas_destroy_rebalance()
3046 slots = ma_slots(newnode, mt); in mas_destroy_rebalance()
3047 pivs = ma_pivots(newnode, mt); in mas_destroy_rebalance()
3049 l_slots = ma_slots(left, mt); in mas_destroy_rebalance()
3050 l_pivs = ma_pivots(left, mt); in mas_destroy_rebalance()
3058 memcpy(slots + tmp, ma_slots(node, mt), sizeof(void *) * end); in mas_destroy_rebalance()
3059 memcpy(pivs + tmp, ma_pivots(node, mt), sizeof(unsigned long) * end); in mas_destroy_rebalance()
3067 unsigned char max_p = mt_pivots[mt]; in mas_destroy_rebalance()
3068 unsigned char max_s = mt_slots[mt]; in mas_destroy_rebalance()
3074 if (tmp < mt_slots[mt]) in mas_destroy_rebalance()
3078 ma_set_meta(node, mt, 0, tmp - 1); in mas_destroy_rebalance()
3086 ma_set_meta(left, mt, 0, split); in mas_destroy_rebalance()
3093 mas->node = mt_mk_node(newnode, mt); in mas_destroy_rebalance()
3094 ma_set_meta(newnode, mt, 0, tmp); in mas_destroy_rebalance()
3098 mt = mte_node_type(l_mas.node); in mas_destroy_rebalance()
3099 slots = ma_slots(new_left, mt); in mas_destroy_rebalance()
3100 pivs = ma_pivots(new_left, mt); in mas_destroy_rebalance()
3103 ma_set_meta(new_left, mt, 0, split); in mas_destroy_rebalance()
3104 l_mas.node = mt_mk_node(new_left, mt); in mas_destroy_rebalance()
3108 mt = mas_parent_type(&l_mas, l_mas.node); in mas_destroy_rebalance()
3110 slots = ma_slots(parent, mt); in mas_destroy_rebalance()
3111 pivs = ma_pivots(parent, mt); in mas_destroy_rebalance()
3116 eparent = mt_mk_node(parent, mt); in mas_destroy_rebalance()
4325 enum maple_type mt; in mas_prev_node() local
4354 mt = mte_node_type(mas->node); in mas_prev_node()
4357 slots = ma_slots(node, mt); in mas_prev_node()
4362 mt = mte_node_type(mas->node); in mas_prev_node()
4364 pivots = ma_pivots(node, mt); in mas_prev_node()
4365 offset = ma_data_end(node, mt, pivots, max); in mas_prev_node()
4370 slots = ma_slots(node, mt); in mas_prev_node()
4372 pivots = ma_pivots(node, mt); in mas_prev_node()
4498 enum maple_type mt; in mas_next_node() local
4516 mt = mte_node_type(mas->node); in mas_next_node()
4517 pivots = ma_pivots(node, mt); in mas_next_node()
4518 node_end = ma_data_end(node, mt, pivots, mas->max); in mas_next_node()
4524 slots = ma_slots(node, mt); in mas_next_node()
4537 mt = mte_node_type(mas->node); in mas_next_node()
4538 slots = ma_slots(node, mt); in mas_next_node()
4545 pivots = ma_pivots(node, mt); in mas_next_node()
4547 mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt); in mas_next_node()
4549 mt = mte_node_type(enode); in mas_next_node()
4550 pivots = ma_pivots(tmp, mt); in mas_next_node()
4551 mas->end = ma_data_end(tmp, mt, pivots, mas->max); in mas_next_node()
5001 enum maple_type mt; in mas_empty_area() local
5034 mt = mte_node_type(mas->node); in mas_empty_area()
5035 pivots = ma_pivots(node, mt); in mas_empty_area()
5040 mas->end = ma_data_end(node, mt, pivots, mas->max); in mas_empty_area()
5117 unsigned char mte_dead_leaves(struct maple_enode *enode, struct maple_tree *mt, in mte_dead_leaves() argument
5126 entry = mt_slot(mt, slots, offset); in mte_dead_leaves()
5213 struct maple_tree *mt, struct maple_enode *prev, unsigned char offset) in mte_destroy_descend() argument
5226 next = mt_slot_locked(mt, slots, next_offset); in mte_destroy_descend()
5228 next = mt_slot_locked(mt, slots, ++next_offset); in mte_destroy_descend()
5242 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt, in mt_destroy_walk() argument
5255 slots = mte_destroy_descend(&enode, mt, start, 0); in mt_destroy_walk()
5262 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
5275 tmp = mt_slot_locked(mt, slots, offset); in mt_destroy_walk()
5279 slots = mte_destroy_descend(&enode, mt, parent, offset); in mt_destroy_walk()
5286 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
5294 mt_clear_meta(mt, node, node->type); in mt_destroy_walk()
5300 * @mt: the tree to free - needed for node types.
5305 struct maple_tree *mt) in mte_destroy_walk() argument
5309 if (mt_in_rcu(mt)) { in mte_destroy_walk()
5310 mt_destroy_walk(enode, mt, false); in mte_destroy_walk()
5313 mt_destroy_walk(enode, mt, true); in mte_destroy_walk()
5741 * @mt: The maple tree
5751 void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max) in mt_next() argument
5754 MA_STATE(mas, mt, index, index); in mt_next()
5871 * @mt: The maple tree
5881 void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min) in mt_prev() argument
5884 MA_STATE(mas, mt, index, index); in mt_prev()
6264 * @mt: The maple tree
6269 void *mtree_load(struct maple_tree *mt, unsigned long index) in mtree_load() argument
6271 MA_STATE(mas, mt, index, index); in mtree_load()
6302 * @mt: The maple tree
6311 int mtree_store_range(struct maple_tree *mt, unsigned long index, in mtree_store_range() argument
6314 MA_STATE(mas, mt, index, last); in mtree_store_range()
6324 mtree_lock(mt); in mtree_store_range()
6330 mtree_unlock(mt); in mtree_store_range()
6340 * @mt: The maple tree
6348 int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, in mtree_store() argument
6351 return mtree_store_range(mt, index, index, entry, gfp); in mtree_store()
6357 * @mt: The maple tree
6366 int mtree_insert_range(struct maple_tree *mt, unsigned long first, in mtree_insert_range() argument
6369 MA_STATE(ms, mt, first, last); in mtree_insert_range()
6377 mtree_lock(mt); in mtree_insert_range()
6383 mtree_unlock(mt); in mtree_insert_range()
6393 * @mt: The maple tree
6401 int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, in mtree_insert() argument
6404 return mtree_insert_range(mt, index, index, entry, gfp); in mtree_insert()
6408 int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, in mtree_alloc_range() argument
6414 MA_STATE(mas, mt, 0, 0); in mtree_alloc_range()
6415 if (!mt_is_alloc(mt)) in mtree_alloc_range()
6421 mtree_lock(mt); in mtree_alloc_range()
6441 mtree_unlock(mt); in mtree_alloc_range()
6446 int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, in mtree_alloc_rrange() argument
6452 MA_STATE(mas, mt, 0, 0); in mtree_alloc_rrange()
6453 if (!mt_is_alloc(mt)) in mtree_alloc_rrange()
6459 mtree_lock(mt); in mtree_alloc_rrange()
6479 mtree_unlock(mt); in mtree_alloc_rrange()
6486 * @mt: The maple tree
6494 void *mtree_erase(struct maple_tree *mt, unsigned long index) in mtree_erase() argument
6498 MA_STATE(mas, mt, index, index); in mtree_erase()
6501 mtree_lock(mt); in mtree_erase()
6503 mtree_unlock(mt); in mtree_erase()
6704 * @mt: The source maple tree
6723 int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) in __mt_dup() argument
6726 MA_STATE(mas, mt, 0, 0); in __mt_dup()
6742 * @mt: The source maple tree
6760 int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) in mtree_dup() argument
6763 MA_STATE(mas, mt, 0, 0); in mtree_dup()
6783 * @mt: The maple tree
6787 void __mt_destroy(struct maple_tree *mt) in __mt_destroy() argument
6789 void *root = mt_root_locked(mt); in __mt_destroy()
6791 rcu_assign_pointer(mt->ma_root, NULL); in __mt_destroy()
6793 mte_destroy_walk(root, mt); in __mt_destroy()
6795 mt->ma_flags = mt_attr(mt); in __mt_destroy()
6801 * @mt: The maple tree
6805 void mtree_destroy(struct maple_tree *mt) in mtree_destroy() argument
6807 mtree_lock(mt); in mtree_destroy()
6808 __mt_destroy(mt); in mtree_destroy()
6809 mtree_unlock(mt); in mtree_destroy()
6815 * @mt: The maple tree
6829 void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max) in mt_find() argument
6831 MA_STATE(mas, mt, *index, *index); in mt_find()
6867 if (MT_WARN_ON(mt, (*index) && ((*index) <= copy))) in mt_find()
6879 * @mt: The maple tree
6889 void *mt_find_after(struct maple_tree *mt, unsigned long *index, in mt_find_after() argument
6895 return mt_find(mt, index, max); in mt_find_after()
6999 static void mt_dump_node(const struct maple_tree *mt, void *entry,
7038 static void mt_dump_range64(const struct maple_tree *mt, void *entry, in mt_dump_range64() argument
7068 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_range64()
7071 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_range64()
7091 static void mt_dump_arange64(const struct maple_tree *mt, void *entry, in mt_dump_arange64() argument
7131 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_arange64()
7134 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_arange64()
7148 static void mt_dump_node(const struct maple_tree *mt, void *entry, in mt_dump_node() argument
7166 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_node()
7172 mt_dump_range64(mt, entry, min, max, depth, format); in mt_dump_node()
7175 mt_dump_arange64(mt, entry, min, max, depth, format); in mt_dump_node()
7183 void mt_dump(const struct maple_tree *mt, enum mt_dump_format format) in mt_dump() argument
7185 void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt)); in mt_dump()
7188 mt, mt->ma_flags, mt_height(mt), entry); in mt_dump()
7192 mt_dump_node(mt, entry, 0, mt_node_max(entry), 0, format); in mt_dump()
7204 enum maple_type mt = mte_node_type(mas->node); in mas_validate_gaps() local
7209 unsigned long *pivots = ma_pivots(node, mt); in mas_validate_gaps()
7212 if (ma_is_dense(mt)) { in mas_validate_gaps()
7225 gaps = ma_gaps(node, mt); in mas_validate_gaps()
7227 p_end = mas_safe_pivot(mas, pivots, i, mt); in mas_validate_gaps()
7255 if (mt == maple_arange_64) { in mas_validate_gaps()
7438 static void mt_validate_nulls(struct maple_tree *mt) in mt_validate_nulls() argument
7443 MA_STATE(mas, mt, 0, 0); in mt_validate_nulls()
7459 MT_BUG_ON(mt, !last && !entry); in mt_validate_nulls()
7480 void mt_validate(struct maple_tree *mt) in mt_validate() argument
7484 MA_STATE(mas, mt, 0, 0); in mt_validate()
7504 if (mt_is_alloc(mt)) in mt_validate()
7508 mt_validate_nulls(mt); in mt_validate()