Lines Matching full:mt
378 static inline bool mt_is_alloc(struct maple_tree *mt) in mt_is_alloc() argument
380 return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE); in mt_is_alloc()
779 * @mt: The maple node type
783 static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt) in ma_slots() argument
785 switch (mt) { in ma_slots()
797 static inline bool mt_write_locked(const struct maple_tree *mt) in mt_write_locked() argument
799 return mt_external_lock(mt) ? mt_write_lock_is_held(mt) : in mt_write_locked()
800 lockdep_is_held(&mt->ma_lock); in mt_write_locked()
803 static inline bool mt_locked(const struct maple_tree *mt) in mt_locked() argument
805 return mt_external_lock(mt) ? mt_lock_is_held(mt) : in mt_locked()
806 lockdep_is_held(&mt->ma_lock); in mt_locked()
809 static inline void *mt_slot(const struct maple_tree *mt, in mt_slot() argument
812 return rcu_dereference_check(slots[offset], mt_locked(mt)); in mt_slot()
815 static inline void *mt_slot_locked(struct maple_tree *mt, void __rcu **slots, in mt_slot_locked() argument
818 return rcu_dereference_protected(slots[offset], mt_write_locked(mt)); in mt_slot_locked()
859 static inline void *mt_root_locked(struct maple_tree *mt) in mt_root_locked() argument
861 return rcu_dereference_protected(mt->ma_root, mt_write_locked(mt)); in mt_root_locked()
876 enum maple_type mt) in ma_meta() argument
878 switch (mt) { in ma_meta()
889 * @mt: The maple node type
893 static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt, in ma_set_meta() argument
896 struct maple_metadata *meta = ma_meta(mn, mt); in ma_set_meta()
904 * @mt: The maple tree
910 static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn, in mt_clear_meta() argument
923 next = mt_slot_locked(mt, slots, in mt_clear_meta()
944 * @mt: The maple node type
947 enum maple_type mt) in ma_meta_end() argument
949 struct maple_metadata *meta = ma_meta(mn, mt); in ma_meta_end()
957 * @mt: The maple node type
960 enum maple_type mt) in ma_meta_gap() argument
971 static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt, in ma_set_meta_gap() argument
975 struct maple_metadata *meta = ma_meta(mn, mt); in ma_set_meta_gap()
1002 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
1494 enum maple_type mt; in mas_leaf_max_gap() local
1502 mt = mte_node_type(mas->node); in mas_leaf_max_gap()
1504 slots = ma_slots(mn, mt); in mas_leaf_max_gap()
1506 if (unlikely(ma_is_dense(mt))) { in mas_leaf_max_gap()
1508 for (i = 0; i < mt_slots[mt]; i++) { in mas_leaf_max_gap()
1526 pivots = ma_pivots(mn, mt); in mas_leaf_max_gap()
1535 max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1; in mas_leaf_max_gap()
1566 * @mt: The maple node type
1574 ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, in ma_max_gap() argument
1580 i = offset = ma_meta_end(node, mt); in ma_max_gap()
1602 enum maple_type mt; in mas_max_gap() local
1605 mt = mte_node_type(mas->node); in mas_max_gap()
1606 if (ma_is_leaf(mt)) in mas_max_gap()
1610 MAS_BUG_ON(mas, mt != maple_arange_64); in mas_max_gap()
1611 offset = ma_meta_gap(node, mt); in mas_max_gap()
1612 gaps = ma_gaps(node, mt); in mas_max_gap()
1772 enum maple_type mt; in mas_find_child() local
1780 mt = mte_node_type(mas->node); in mas_find_child()
1782 slots = ma_slots(node, mt); in mas_find_child()
1783 pivots = ma_pivots(node, mt); in mas_find_child()
1784 end = ma_data_end(node, mt, pivots, mas->max); in mas_find_child()
1935 enum maple_type mt; in mas_mab_cp() local
1943 mt = mte_node_type(mas->node); in mas_mab_cp()
1944 pivots = ma_pivots(node, mt); in mas_mab_cp()
1952 piv_end = min(mas_end, mt_pivots[mt]); in mas_mab_cp()
1963 b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); in mas_mab_cp()
1968 slots = ma_slots(node, mt); in mas_mab_cp()
1970 if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) { in mas_mab_cp()
1971 gaps = ma_gaps(node, mt); in mas_mab_cp()
1982 * @mt: The maple type
1991 enum maple_type mt, unsigned char end) in mas_leaf_set_meta() argument
1994 if (mt_pivots[mt] <= end) in mas_leaf_set_meta()
2000 if (end < mt_slots[mt] - 1) in mas_leaf_set_meta()
2001 ma_set_meta(node, mt, 0, end); in mas_leaf_set_meta()
2016 enum maple_type mt = mte_node_type(mas->node); in mab_mas_cp() local
2018 void __rcu **slots = ma_slots(node, mt); in mab_mas_cp()
2019 unsigned long *pivots = ma_pivots(node, mt); in mab_mas_cp()
2023 if (mab_end - mab_start > mt_pivots[mt]) in mab_mas_cp()
2026 if (!pivots[mt_pivots[mt] - 1]) in mab_mas_cp()
2027 slots[mt_pivots[mt]] = NULL; in mab_mas_cp()
2041 if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { in mab_mas_cp()
2045 gaps = ma_gaps(node, mt); in mab_mas_cp()
2054 ma_set_meta(node, mt, offset, end); in mab_mas_cp()
2056 mas_leaf_set_meta(mas, node, pivots, mt, end); in mab_mas_cp()
2064 * @mt: The maple node type
2067 enum maple_type mt) in mas_bulk_rebalance() argument
2075 if (end > mt_min_slots[mt]) { in mas_bulk_rebalance()
3042 enum maple_type mt = mte_node_type(mas->node); in mas_destroy_rebalance() local
3045 unsigned char offset, tmp, split = mt_slots[mt] / 2; in mas_destroy_rebalance()
3069 slots = ma_slots(newnode, mt); in mas_destroy_rebalance()
3070 pivs = ma_pivots(newnode, mt); in mas_destroy_rebalance()
3072 l_slots = ma_slots(left, mt); in mas_destroy_rebalance()
3073 l_pivs = ma_pivots(left, mt); in mas_destroy_rebalance()
3081 memcpy(slots + tmp, ma_slots(node, mt), sizeof(void *) * end); in mas_destroy_rebalance()
3082 memcpy(pivs + tmp, ma_pivots(node, mt), sizeof(unsigned long) * end); in mas_destroy_rebalance()
3090 unsigned char max_p = mt_pivots[mt]; in mas_destroy_rebalance()
3091 unsigned char max_s = mt_slots[mt]; in mas_destroy_rebalance()
3097 if (tmp < mt_slots[mt]) in mas_destroy_rebalance()
3101 ma_set_meta(node, mt, 0, tmp - 1); in mas_destroy_rebalance()
3109 ma_set_meta(left, mt, 0, split); in mas_destroy_rebalance()
3116 mas->node = mt_mk_node(newnode, mt); in mas_destroy_rebalance()
3117 ma_set_meta(newnode, mt, 0, tmp); in mas_destroy_rebalance()
3121 mt = mte_node_type(l_mas.node); in mas_destroy_rebalance()
3122 slots = ma_slots(new_left, mt); in mas_destroy_rebalance()
3123 pivs = ma_pivots(new_left, mt); in mas_destroy_rebalance()
3126 ma_set_meta(new_left, mt, 0, split); in mas_destroy_rebalance()
3127 l_mas.node = mt_mk_node(new_left, mt); in mas_destroy_rebalance()
3131 mt = mas_parent_type(&l_mas, l_mas.node); in mas_destroy_rebalance()
3133 slots = ma_slots(parent, mt); in mas_destroy_rebalance()
3134 pivs = ma_pivots(parent, mt); in mas_destroy_rebalance()
3139 eparent = mt_mk_node(parent, mt); in mas_destroy_rebalance()
4361 enum maple_type mt; in mas_prev_node() local
4390 mt = mte_node_type(mas->node); in mas_prev_node()
4393 slots = ma_slots(node, mt); in mas_prev_node()
4398 mt = mte_node_type(mas->node); in mas_prev_node()
4400 pivots = ma_pivots(node, mt); in mas_prev_node()
4401 offset = ma_data_end(node, mt, pivots, max); in mas_prev_node()
4406 slots = ma_slots(node, mt); in mas_prev_node()
4408 pivots = ma_pivots(node, mt); in mas_prev_node()
4527 enum maple_type mt; in mas_next_node() local
4545 mt = mte_node_type(mas->node); in mas_next_node()
4546 pivots = ma_pivots(node, mt); in mas_next_node()
4547 node_end = ma_data_end(node, mt, pivots, mas->max); in mas_next_node()
4553 slots = ma_slots(node, mt); in mas_next_node()
4566 mt = mte_node_type(mas->node); in mas_next_node()
4567 slots = ma_slots(node, mt); in mas_next_node()
4574 pivots = ma_pivots(node, mt); in mas_next_node()
4576 mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt); in mas_next_node()
5028 enum maple_type mt; in mas_empty_area() local
5059 mt = mte_node_type(mas->node); in mas_empty_area()
5060 pivots = ma_pivots(mas_mn(mas), mt); in mas_empty_area()
5140 unsigned char mte_dead_leaves(struct maple_enode *enode, struct maple_tree *mt, in mte_dead_leaves() argument
5149 entry = mt_slot(mt, slots, offset); in mte_dead_leaves()
5236 struct maple_tree *mt, struct maple_enode *prev, unsigned char offset) in mte_destroy_descend() argument
5249 next = mt_slot_locked(mt, slots, next_offset); in mte_destroy_descend()
5251 next = mt_slot_locked(mt, slots, ++next_offset); in mte_destroy_descend()
5265 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt, in mt_destroy_walk() argument
5279 slots = mte_destroy_descend(&enode, mt, start, 0); in mt_destroy_walk()
5286 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
5299 tmp = mt_slot_locked(mt, slots, offset); in mt_destroy_walk()
5303 slots = mte_destroy_descend(&enode, mt, parent, offset); in mt_destroy_walk()
5310 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
5318 mt_clear_meta(mt, node, node->type); in mt_destroy_walk()
5324 * @mt: the tree to free - needed for node types.
5329 struct maple_tree *mt) in mte_destroy_walk() argument
5333 if (mt_in_rcu(mt)) { in mte_destroy_walk()
5334 mt_destroy_walk(enode, mt, false); in mte_destroy_walk()
5337 mt_destroy_walk(enode, mt, true); in mte_destroy_walk()
5755 * @mt: The maple tree
5765 void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max) in mt_next() argument
5768 MA_STATE(mas, mt, index, index); in mt_next()
5878 * @mt: The maple tree
5888 void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min) in mt_prev() argument
5891 MA_STATE(mas, mt, index, index); in mt_prev()
6238 * @mt: The maple tree
6243 void *mtree_load(struct maple_tree *mt, unsigned long index) in mtree_load() argument
6245 MA_STATE(mas, mt, index, index); in mtree_load()
6276 * @mt: The maple tree
6285 int mtree_store_range(struct maple_tree *mt, unsigned long index, in mtree_store_range() argument
6288 MA_STATE(mas, mt, index, last); in mtree_store_range()
6298 mtree_lock(mt); in mtree_store_range()
6304 mtree_unlock(mt); in mtree_store_range()
6314 * @mt: The maple tree
6322 int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, in mtree_store() argument
6325 return mtree_store_range(mt, index, index, entry, gfp); in mtree_store()
6331 * @mt: The maple tree
6340 int mtree_insert_range(struct maple_tree *mt, unsigned long first, in mtree_insert_range() argument
6343 MA_STATE(ms, mt, first, last); in mtree_insert_range()
6351 mtree_lock(mt); in mtree_insert_range()
6357 mtree_unlock(mt); in mtree_insert_range()
6367 * @mt: The maple tree
6375 int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, in mtree_insert() argument
6378 return mtree_insert_range(mt, index, index, entry, gfp); in mtree_insert()
6382 int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, in mtree_alloc_range() argument
6388 MA_STATE(mas, mt, 0, 0); in mtree_alloc_range()
6389 if (!mt_is_alloc(mt)) in mtree_alloc_range()
6395 mtree_lock(mt); in mtree_alloc_range()
6415 mtree_unlock(mt); in mtree_alloc_range()
6420 int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, in mtree_alloc_rrange() argument
6426 MA_STATE(mas, mt, 0, 0); in mtree_alloc_rrange()
6427 if (!mt_is_alloc(mt)) in mtree_alloc_rrange()
6433 mtree_lock(mt); in mtree_alloc_rrange()
6453 mtree_unlock(mt); in mtree_alloc_rrange()
6460 * @mt: The maple tree
6468 void *mtree_erase(struct maple_tree *mt, unsigned long index) in mtree_erase() argument
6472 MA_STATE(mas, mt, index, index); in mtree_erase()
6475 mtree_lock(mt); in mtree_erase()
6477 mtree_unlock(mt); in mtree_erase()
6485 * @mt: The maple tree
6489 void __mt_destroy(struct maple_tree *mt) in __mt_destroy() argument
6491 void *root = mt_root_locked(mt); in __mt_destroy()
6493 rcu_assign_pointer(mt->ma_root, NULL); in __mt_destroy()
6495 mte_destroy_walk(root, mt); in __mt_destroy()
6497 mt->ma_flags = 0; in __mt_destroy()
6503 * @mt: The maple tree
6507 void mtree_destroy(struct maple_tree *mt) in mtree_destroy() argument
6509 mtree_lock(mt); in mtree_destroy()
6510 __mt_destroy(mt); in mtree_destroy()
6511 mtree_unlock(mt); in mtree_destroy()
6517 * @mt: The maple tree
6531 void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max) in mt_find() argument
6533 MA_STATE(mas, mt, *index, *index); in mt_find()
6569 if (MT_WARN_ON(mt, (*index) && ((*index) <= copy))) in mt_find()
6581 * @mt: The maple tree
6591 void *mt_find_after(struct maple_tree *mt, unsigned long *index, in mt_find_after() argument
6597 return mt_find(mt, index, max); in mt_find_after()
6721 static void mt_dump_node(const struct maple_tree *mt, void *entry,
6761 static void mt_dump_range64(const struct maple_tree *mt, void *entry, in mt_dump_range64() argument
6792 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_range64()
6795 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_range64()
6816 static void mt_dump_arange64(const struct maple_tree *mt, void *entry, in mt_dump_arange64() argument
6858 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_arange64()
6861 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_arange64()
6875 static void mt_dump_node(const struct maple_tree *mt, void *entry, in mt_dump_node() argument
6893 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_node()
6899 mt_dump_range64(mt, entry, min, max, depth, format); in mt_dump_node()
6902 mt_dump_arange64(mt, entry, min, max, depth, format); in mt_dump_node()
6910 void mt_dump(const struct maple_tree *mt, enum mt_dump_format format) in mt_dump() argument
6912 void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt)); in mt_dump()
6915 mt, mt->ma_flags, mt_height(mt), entry); in mt_dump()
6919 mt_dump_node(mt, entry, 0, mt_node_max(entry), 0, format); in mt_dump()
6931 enum maple_type mt = mte_node_type(mas->node); in mas_validate_gaps() local
6936 unsigned long *pivots = ma_pivots(node, mt); in mas_validate_gaps()
6939 if (ma_is_dense(mt)) { in mas_validate_gaps()
6952 gaps = ma_gaps(node, mt); in mas_validate_gaps()
6954 p_end = mas_safe_pivot(mas, pivots, i, mt); in mas_validate_gaps()
6982 if (mt == maple_arange_64) { in mas_validate_gaps()
6983 offset = ma_meta_gap(node, mt); in mas_validate_gaps()
7165 static void mt_validate_nulls(struct maple_tree *mt) in mt_validate_nulls() argument
7170 MA_STATE(mas, mt, 0, 0); in mt_validate_nulls()
7186 MT_BUG_ON(mt, !last && !entry); in mt_validate_nulls()
7207 void mt_validate(struct maple_tree *mt) in mt_validate() argument
7211 MA_STATE(mas, mt, 0, 0); in mt_validate()
7231 if (mt_is_alloc(mt)) in mt_validate()
7235 mt_validate_nulls(mt); in mt_validate()