Lines Matching refs:mt
229 static inline unsigned int mt_attr(struct maple_tree *mt) in mt_attr() argument
231 return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK; in mt_attr()
395 static __always_inline bool mt_is_alloc(struct maple_tree *mt) in mt_is_alloc() argument
397 return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE); in mt_is_alloc()
773 static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt) in ma_slots() argument
775 switch (mt) { in ma_slots()
788 static inline bool mt_write_locked(const struct maple_tree *mt) in mt_write_locked() argument
790 return mt_external_lock(mt) ? mt_write_lock_is_held(mt) : in mt_write_locked()
791 lockdep_is_held(&mt->ma_lock); in mt_write_locked()
794 static __always_inline bool mt_locked(const struct maple_tree *mt) in mt_locked() argument
796 return mt_external_lock(mt) ? mt_lock_is_held(mt) : in mt_locked()
797 lockdep_is_held(&mt->ma_lock); in mt_locked()
800 static __always_inline void *mt_slot(const struct maple_tree *mt, in mt_slot() argument
803 return rcu_dereference_check(slots[offset], mt_locked(mt)); in mt_slot()
806 static __always_inline void *mt_slot_locked(struct maple_tree *mt, in mt_slot_locked() argument
809 return rcu_dereference_protected(slots[offset], mt_write_locked(mt)); in mt_slot_locked()
850 static inline void *mt_root_locked(struct maple_tree *mt) in mt_root_locked() argument
852 return rcu_dereference_protected(mt->ma_root, mt_write_locked(mt)); in mt_root_locked()
867 enum maple_type mt) in ma_meta() argument
869 switch (mt) { in ma_meta()
884 static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt, in ma_set_meta() argument
887 struct maple_metadata *meta = ma_meta(mn, mt); in ma_set_meta()
899 static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn, in mt_clear_meta() argument
912 next = mt_slot_locked(mt, slots, in mt_clear_meta()
936 enum maple_type mt) in ma_meta_end() argument
938 struct maple_metadata *meta = ma_meta(mn, mt); in ma_meta_end()
958 static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt, in ma_set_meta_gap() argument
962 struct maple_metadata *meta = ma_meta(mn, mt); in ma_set_meta_gap()
989 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
1484 enum maple_type mt; in mas_leaf_max_gap() local
1492 mt = mte_node_type(mas->node); in mas_leaf_max_gap()
1494 slots = ma_slots(mn, mt); in mas_leaf_max_gap()
1496 if (unlikely(ma_is_dense(mt))) { in mas_leaf_max_gap()
1498 for (i = 0; i < mt_slots[mt]; i++) { in mas_leaf_max_gap()
1516 pivots = ma_pivots(mn, mt); in mas_leaf_max_gap()
1525 max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1; in mas_leaf_max_gap()
1567 ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, in ma_max_gap() argument
1573 i = offset = ma_meta_end(node, mt); in ma_max_gap()
1595 enum maple_type mt; in mas_max_gap() local
1598 mt = mte_node_type(mas->node); in mas_max_gap()
1599 if (ma_is_leaf(mt)) in mas_max_gap()
1603 MAS_BUG_ON(mas, mt != maple_arange_64); in mas_max_gap()
1605 gaps = ma_gaps(node, mt); in mas_max_gap()
1765 enum maple_type mt; in mas_find_child() local
1773 mt = mte_node_type(mas->node); in mas_find_child()
1775 slots = ma_slots(node, mt); in mas_find_child()
1776 pivots = ma_pivots(node, mt); in mas_find_child()
1777 end = ma_data_end(node, mt, pivots, mas->max); in mas_find_child()
1928 enum maple_type mt; in mas_mab_cp() local
1936 mt = mte_node_type(mas->node); in mas_mab_cp()
1937 pivots = ma_pivots(node, mt); in mas_mab_cp()
1945 piv_end = min(mas_end, mt_pivots[mt]); in mas_mab_cp()
1955 b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); in mas_mab_cp()
1960 slots = ma_slots(node, mt); in mas_mab_cp()
1962 if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) { in mas_mab_cp()
1963 gaps = ma_gaps(node, mt); in mas_mab_cp()
1976 enum maple_type mt, unsigned char end) in mas_leaf_set_meta() argument
1978 if (end < mt_slots[mt] - 1) in mas_leaf_set_meta()
1979 ma_set_meta(node, mt, 0, end); in mas_leaf_set_meta()
1994 enum maple_type mt = mte_node_type(mas->node); in mab_mas_cp() local
1996 void __rcu **slots = ma_slots(node, mt); in mab_mas_cp()
1997 unsigned long *pivots = ma_pivots(node, mt); in mab_mas_cp()
2001 if (mab_end - mab_start > mt_pivots[mt]) in mab_mas_cp()
2004 if (!pivots[mt_pivots[mt] - 1]) in mab_mas_cp()
2005 slots[mt_pivots[mt]] = NULL; in mab_mas_cp()
2019 if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { in mab_mas_cp()
2023 gaps = ma_gaps(node, mt); in mab_mas_cp()
2032 ma_set_meta(node, mt, offset, end); in mab_mas_cp()
2034 mas_leaf_set_meta(node, mt, end); in mab_mas_cp()
2045 enum maple_type mt) in mas_bulk_rebalance() argument
2053 if (end > mt_min_slots[mt]) { in mas_bulk_rebalance()
3009 enum maple_type mt = mte_node_type(mas->node); in mas_destroy_rebalance() local
3012 unsigned char offset, tmp, split = mt_slots[mt] / 2; in mas_destroy_rebalance()
3031 slots = ma_slots(newnode, mt); in mas_destroy_rebalance()
3032 pivs = ma_pivots(newnode, mt); in mas_destroy_rebalance()
3034 l_slots = ma_slots(left, mt); in mas_destroy_rebalance()
3035 l_pivs = ma_pivots(left, mt); in mas_destroy_rebalance()
3043 memcpy(slots + tmp, ma_slots(node, mt), sizeof(void *) * end); in mas_destroy_rebalance()
3044 memcpy(pivs + tmp, ma_pivots(node, mt), sizeof(unsigned long) * end); in mas_destroy_rebalance()
3052 unsigned char max_p = mt_pivots[mt]; in mas_destroy_rebalance()
3053 unsigned char max_s = mt_slots[mt]; in mas_destroy_rebalance()
3059 if (tmp < mt_slots[mt]) in mas_destroy_rebalance()
3063 ma_set_meta(node, mt, 0, tmp - 1); in mas_destroy_rebalance()
3071 ma_set_meta(left, mt, 0, split); in mas_destroy_rebalance()
3078 mas->node = mt_mk_node(newnode, mt); in mas_destroy_rebalance()
3079 ma_set_meta(newnode, mt, 0, tmp); in mas_destroy_rebalance()
3083 mt = mte_node_type(l_mas.node); in mas_destroy_rebalance()
3084 slots = ma_slots(new_left, mt); in mas_destroy_rebalance()
3085 pivs = ma_pivots(new_left, mt); in mas_destroy_rebalance()
3088 ma_set_meta(new_left, mt, 0, split); in mas_destroy_rebalance()
3089 l_mas.node = mt_mk_node(new_left, mt); in mas_destroy_rebalance()
3093 mt = mas_parent_type(&l_mas, l_mas.node); in mas_destroy_rebalance()
3095 slots = ma_slots(parent, mt); in mas_destroy_rebalance()
3096 pivs = ma_pivots(parent, mt); in mas_destroy_rebalance()
3101 eparent = mt_mk_node(parent, mt); in mas_destroy_rebalance()
4402 enum maple_type mt; in mas_prev_node() local
4431 mt = mte_node_type(mas->node); in mas_prev_node()
4434 slots = ma_slots(node, mt); in mas_prev_node()
4439 mt = mte_node_type(mas->node); in mas_prev_node()
4441 pivots = ma_pivots(node, mt); in mas_prev_node()
4442 offset = ma_data_end(node, mt, pivots, max); in mas_prev_node()
4447 slots = ma_slots(node, mt); in mas_prev_node()
4449 pivots = ma_pivots(node, mt); in mas_prev_node()
4575 enum maple_type mt; in mas_next_node() local
4593 mt = mte_node_type(mas->node); in mas_next_node()
4594 pivots = ma_pivots(node, mt); in mas_next_node()
4595 node_end = ma_data_end(node, mt, pivots, mas->max); in mas_next_node()
4601 slots = ma_slots(node, mt); in mas_next_node()
4614 mt = mte_node_type(mas->node); in mas_next_node()
4615 slots = ma_slots(node, mt); in mas_next_node()
4622 pivots = ma_pivots(node, mt); in mas_next_node()
4624 mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt); in mas_next_node()
4626 mt = mte_node_type(enode); in mas_next_node()
4627 pivots = ma_pivots(tmp, mt); in mas_next_node()
4628 mas->end = ma_data_end(tmp, mt, pivots, mas->max); in mas_next_node()
5049 enum maple_type mt; in mas_empty_area() local
5079 mt = mte_node_type(mas->node); in mas_empty_area()
5080 pivots = ma_pivots(node, mt); in mas_empty_area()
5085 mas->end = ma_data_end(node, mt, pivots, mas->max); in mas_empty_area()
5162 unsigned char mte_dead_leaves(struct maple_enode *enode, struct maple_tree *mt, in mte_dead_leaves() argument
5171 entry = mt_slot(mt, slots, offset); in mte_dead_leaves()
5258 struct maple_tree *mt, struct maple_enode *prev, unsigned char offset) in mte_destroy_descend() argument
5271 next = mt_slot_locked(mt, slots, next_offset); in mte_destroy_descend()
5273 next = mt_slot_locked(mt, slots, ++next_offset); in mte_destroy_descend()
5287 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt, in mt_destroy_walk() argument
5300 slots = mte_destroy_descend(&enode, mt, start, 0); in mt_destroy_walk()
5307 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
5320 tmp = mt_slot_locked(mt, slots, offset); in mt_destroy_walk()
5324 slots = mte_destroy_descend(&enode, mt, parent, offset); in mt_destroy_walk()
5331 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
5339 mt_clear_meta(mt, node, node->type); in mt_destroy_walk()
5350 struct maple_tree *mt) in mte_destroy_walk() argument
5354 if (mt_in_rcu(mt)) { in mte_destroy_walk()
5355 mt_destroy_walk(enode, mt, false); in mte_destroy_walk()
5358 mt_destroy_walk(enode, mt, true); in mte_destroy_walk()
5749 void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max) in mt_next() argument
5752 MA_STATE(mas, mt, index, index); in mt_next()
5879 void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min) in mt_prev() argument
5882 MA_STATE(mas, mt, index, index); in mt_prev()
6273 void *mtree_load(struct maple_tree *mt, unsigned long index) in mtree_load() argument
6275 MA_STATE(mas, mt, index, index); in mtree_load()
6315 int mtree_store_range(struct maple_tree *mt, unsigned long index, in mtree_store_range() argument
6318 MA_STATE(mas, mt, index, last); in mtree_store_range()
6328 mtree_lock(mt); in mtree_store_range()
6330 mtree_unlock(mt); in mtree_store_range()
6346 int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, in mtree_store() argument
6349 return mtree_store_range(mt, index, index, entry, gfp); in mtree_store()
6364 int mtree_insert_range(struct maple_tree *mt, unsigned long first, in mtree_insert_range() argument
6367 MA_STATE(ms, mt, first, last); in mtree_insert_range()
6376 mtree_lock(mt); in mtree_insert_range()
6382 mtree_unlock(mt); in mtree_insert_range()
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()
6470 int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp, in mtree_alloc_cyclic() argument
6476 MA_STATE(mas, mt, 0, 0); in mtree_alloc_cyclic()
6478 if (!mt_is_alloc(mt)) in mtree_alloc_cyclic()
6482 mtree_lock(mt); in mtree_alloc_cyclic()
6485 mtree_unlock(mt); in mtree_alloc_cyclic()
6490 int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, in mtree_alloc_rrange() argument
6496 MA_STATE(mas, mt, 0, 0); in mtree_alloc_rrange()
6497 if (!mt_is_alloc(mt)) in mtree_alloc_rrange()
6503 mtree_lock(mt); in mtree_alloc_rrange()
6523 mtree_unlock(mt); in mtree_alloc_rrange()
6539 void *mtree_erase(struct maple_tree *mt, unsigned long index) in mtree_erase() argument
6543 MA_STATE(mas, mt, index, index); in mtree_erase()
6546 mtree_lock(mt); in mtree_erase()
6548 mtree_unlock(mt); in mtree_erase()
6768 int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) in __mt_dup() argument
6771 MA_STATE(mas, mt, 0, 0); in __mt_dup()
6805 int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) in mtree_dup() argument
6808 MA_STATE(mas, mt, 0, 0); in mtree_dup()
6832 void __mt_destroy(struct maple_tree *mt) in __mt_destroy() argument
6834 void *root = mt_root_locked(mt); in __mt_destroy()
6836 rcu_assign_pointer(mt->ma_root, NULL); in __mt_destroy()
6838 mte_destroy_walk(root, mt); in __mt_destroy()
6840 mt->ma_flags = mt_attr(mt); in __mt_destroy()
6850 void mtree_destroy(struct maple_tree *mt) in mtree_destroy() argument
6852 mtree_lock(mt); in mtree_destroy()
6853 __mt_destroy(mt); in mtree_destroy()
6854 mtree_unlock(mt); in mtree_destroy()
6874 void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max) in mt_find() argument
6876 MA_STATE(mas, mt, *index, *index); in mt_find()
6912 if (MT_WARN_ON(mt, (*index) && ((*index) <= copy))) in mt_find()
6934 void *mt_find_after(struct maple_tree *mt, unsigned long *index, in mt_find_after() argument
6940 return mt_find(mt, index, max); in mt_find_after()
7057 static void mt_dump_node(const struct maple_tree *mt, void *entry,
7096 static void mt_dump_range64(const struct maple_tree *mt, void *entry, in mt_dump_range64() argument
7126 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_range64()
7129 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_range64()
7149 static void mt_dump_arange64(const struct maple_tree *mt, void *entry, in mt_dump_arange64() argument
7188 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_arange64()
7208 static void mt_dump_node(const struct maple_tree *mt, void *entry, in mt_dump_node() argument
7226 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_node()
7232 mt_dump_range64(mt, entry, min, max, depth, format); in mt_dump_node()
7235 mt_dump_arange64(mt, entry, min, max, depth, format); in mt_dump_node()
7243 void mt_dump(const struct maple_tree *mt, enum mt_dump_format format) in mt_dump() argument
7245 void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt)); in mt_dump()
7248 mt, mt->ma_flags, mt_height(mt), entry); in mt_dump()
7250 mt_dump_node(mt, entry, 0, mt_node_max(entry), 0, format); in mt_dump()
7266 enum maple_type mt = mte_node_type(mas->node); in mas_validate_gaps() local
7271 unsigned long *pivots = ma_pivots(node, mt); in mas_validate_gaps()
7274 if (ma_is_dense(mt)) { in mas_validate_gaps()
7287 gaps = ma_gaps(node, mt); in mas_validate_gaps()
7289 p_end = mas_safe_pivot(mas, pivots, i, mt); in mas_validate_gaps()
7317 if (mt == maple_arange_64) { in mas_validate_gaps()
7500 static void mt_validate_nulls(struct maple_tree *mt) in mt_validate_nulls() argument
7505 MA_STATE(mas, mt, 0, 0); in mt_validate_nulls()
7521 MT_BUG_ON(mt, !last && !entry); in mt_validate_nulls()
7542 void mt_validate(struct maple_tree *mt) in mt_validate() argument
7547 MA_STATE(mas, mt, 0, 0); in mt_validate()
7567 if (mt_is_alloc(mt)) in mt_validate()
7571 mt_validate_nulls(mt); in mt_validate()