Lines Matching full:mt
351 static inline bool mt_is_alloc(struct maple_tree *mt) in mt_is_alloc() argument
353 return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE); in mt_is_alloc()
426 struct maple_tree *mt) in mte_parent_enum() argument
439 if (mt_is_alloc(mt)) in mte_parent_enum()
780 * @mt: The maple node type
784 static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt) in ma_slots() argument
786 switch (mt) { in ma_slots()
798 static inline bool mt_locked(const struct maple_tree *mt) in mt_locked() argument
800 return mt_external_lock(mt) ? mt_lock_is_held(mt) : in mt_locked()
801 lockdep_is_held(&mt->ma_lock); in mt_locked()
804 static inline void *mt_slot(const struct maple_tree *mt, in mt_slot() argument
807 return rcu_dereference_check(slots[offset], mt_locked(mt)); in mt_slot()
849 static inline void *mt_root_locked(struct maple_tree *mt) in mt_root_locked() argument
851 return rcu_dereference_protected(mt->ma_root, mt_locked(mt)); in mt_root_locked()
866 enum maple_type mt) in ma_meta() argument
868 switch (mt) { in ma_meta()
879 * @mt: The maple node type
883 static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt, in ma_set_meta() argument
886 struct maple_metadata *meta = ma_meta(mn, mt); in ma_set_meta()
895 * @mt: The maple node type
898 enum maple_type mt) in ma_meta_end() argument
900 struct maple_metadata *meta = ma_meta(mn, mt); in ma_meta_end()
908 * @mt: The maple node type
911 enum maple_type mt) in ma_meta_gap() argument
913 BUG_ON(mt != maple_arange_64); in ma_meta_gap()
924 static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt, in ma_set_meta_gap() argument
928 struct maple_metadata *meta = ma_meta(mn, mt); in ma_set_meta_gap()
1449 enum maple_type mt; in mas_leaf_max_gap() local
1457 mt = mte_node_type(mas->node); in mas_leaf_max_gap()
1459 slots = ma_slots(mn, mt); in mas_leaf_max_gap()
1461 if (unlikely(ma_is_dense(mt))) { in mas_leaf_max_gap()
1463 for (i = 0; i < mt_slots[mt]; i++) { in mas_leaf_max_gap()
1481 pivots = ma_pivots(mn, mt); in mas_leaf_max_gap()
1490 max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1; in mas_leaf_max_gap()
1521 * @mt: The maple node type
1529 ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, in ma_max_gap() argument
1535 i = offset = ma_meta_end(node, mt); in ma_max_gap()
1559 enum maple_type mt; in mas_max_gap() local
1562 mt = mte_node_type(mas->node); in mas_max_gap()
1563 if (ma_is_leaf(mt)) in mas_max_gap()
1567 offset = ma_meta_gap(node, mt); in mas_max_gap()
1571 gaps = ma_gaps(node, mt); in mas_max_gap()
1731 enum maple_type mt; in mas_new_child() local
1739 mt = mte_node_type(mas->node); in mas_new_child()
1741 slots = ma_slots(node, mt); in mas_new_child()
1742 pivots = ma_pivots(node, mt); in mas_new_child()
1743 end = ma_data_end(node, mt, pivots, mas->max); in mas_new_child()
1905 enum maple_type mt; in mas_mab_cp() local
1913 mt = mte_node_type(mas->node); in mas_mab_cp()
1914 pivots = ma_pivots(node, mt); in mas_mab_cp()
1922 piv_end = min(mas_end, mt_pivots[mt]); in mas_mab_cp()
1933 b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); in mas_mab_cp()
1938 slots = ma_slots(node, mt); in mas_mab_cp()
1940 if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) { in mas_mab_cp()
1941 gaps = ma_gaps(node, mt); in mas_mab_cp()
1952 * @mt: The maple type
1961 enum maple_type mt, unsigned char end) in mas_leaf_set_meta() argument
1964 if (mt_pivots[mt] <= end) in mas_leaf_set_meta()
1970 if (end < mt_slots[mt] - 1) in mas_leaf_set_meta()
1971 ma_set_meta(node, mt, 0, end); in mas_leaf_set_meta()
1986 enum maple_type mt = mte_node_type(mas->node); in mab_mas_cp() local
1988 void __rcu **slots = ma_slots(node, mt); in mab_mas_cp()
1989 unsigned long *pivots = ma_pivots(node, mt); in mab_mas_cp()
1993 if (mab_end - mab_start > mt_pivots[mt]) in mab_mas_cp()
1996 if (!pivots[mt_pivots[mt] - 1]) in mab_mas_cp()
1997 slots[mt_pivots[mt]] = NULL; in mab_mas_cp()
2011 if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { in mab_mas_cp()
2015 gaps = ma_gaps(node, mt); in mab_mas_cp()
2024 ma_set_meta(node, mt, offset, end); in mab_mas_cp()
2026 mas_leaf_set_meta(mas, node, pivots, mt, end); in mab_mas_cp()
2084 * @mt: The maple node type
2087 enum maple_type mt) in mas_bulk_rebalance() argument
2095 if (end > mt_min_slots[mt]) { in mas_bulk_rebalance()
3162 enum maple_type mt = mte_node_type(mas->node); in mas_destroy_rebalance() local
3165 unsigned char offset, tmp, split = mt_slots[mt] / 2; in mas_destroy_rebalance()
3189 slots = ma_slots(newnode, mt); in mas_destroy_rebalance()
3190 pivs = ma_pivots(newnode, mt); in mas_destroy_rebalance()
3192 l_slots = ma_slots(left, mt); in mas_destroy_rebalance()
3193 l_pivs = ma_pivots(left, mt); in mas_destroy_rebalance()
3201 memcpy(slots + tmp, ma_slots(node, mt), sizeof(void *) * end); in mas_destroy_rebalance()
3202 memcpy(pivs + tmp, ma_pivots(node, mt), sizeof(unsigned long) * end); in mas_destroy_rebalance()
3210 unsigned char max_p = mt_pivots[mt]; in mas_destroy_rebalance()
3211 unsigned char max_s = mt_slots[mt]; in mas_destroy_rebalance()
3217 if (tmp < mt_slots[mt]) in mas_destroy_rebalance()
3221 ma_set_meta(node, mt, 0, tmp - 1); in mas_destroy_rebalance()
3229 ma_set_meta(left, mt, 0, split); in mas_destroy_rebalance()
3235 mas->node = mt_mk_node(newnode, mt); in mas_destroy_rebalance()
3236 ma_set_meta(newnode, mt, 0, tmp); in mas_destroy_rebalance()
3240 mt = mte_node_type(l_mas.node); in mas_destroy_rebalance()
3241 slots = ma_slots(new_left, mt); in mas_destroy_rebalance()
3242 pivs = ma_pivots(new_left, mt); in mas_destroy_rebalance()
3245 ma_set_meta(new_left, mt, 0, split); in mas_destroy_rebalance()
3246 l_mas.node = mt_mk_node(new_left, mt); in mas_destroy_rebalance()
3250 mt = mas_parent_enum(&l_mas, l_mas.node); in mas_destroy_rebalance()
3252 slots = ma_slots(parent, mt); in mas_destroy_rebalance()
3253 pivs = ma_pivots(parent, mt); in mas_destroy_rebalance()
3258 eparent = mt_mk_node(parent, mt); in mas_destroy_rebalance()
4472 enum maple_type mt; in mas_prev_node() local
4496 mt = mte_node_type(mas->node); in mas_prev_node()
4498 slots = ma_slots(node, mt); in mas_prev_node()
4499 pivots = ma_pivots(node, mt); in mas_prev_node()
4516 mt = mte_node_type(mas->node); in mas_prev_node()
4518 slots = ma_slots(node, mt); in mas_prev_node()
4519 pivots = ma_pivots(node, mt); in mas_prev_node()
4520 offset = ma_data_end(node, mt, pivots, mas->max); in mas_prev_node()
4524 if (offset < mt_pivots[mt]) in mas_prev_node()
4569 enum maple_type mt; in mas_next_node() local
4590 mt = mte_node_type(mas->node); in mas_next_node()
4591 pivots = ma_pivots(node, mt); in mas_next_node()
4592 } while (unlikely(offset == ma_data_end(node, mt, pivots, mas->max))); in mas_next_node()
4594 slots = ma_slots(node, mt); in mas_next_node()
4595 pivot = mas_safe_pivot(mas, pivots, ++offset, mt); in mas_next_node()
4605 mt = mte_node_type(mas->node); in mas_next_node()
4606 slots = ma_slots(node, mt); in mas_next_node()
4607 pivots = ma_pivots(node, mt); in mas_next_node()
4736 enum maple_type mt; in mas_next_entry() local
4743 mt = mte_node_type(mas->node); in mas_next_entry()
4745 if (unlikely(mas->offset >= mt_slots[mt])) { in mas_next_entry()
4746 mas->offset = mt_slots[mt] - 1; in mas_next_entry()
4751 entry = mas_next_nentry(mas, node, limit, mt); in mas_next_entry()
4772 mt = mte_node_type(mas->node); in mas_next_entry()
4794 enum maple_type mt; in mas_prev_nentry() local
4804 mt = mte_node_type(mas->node); in mas_prev_nentry()
4806 if (offset >= mt_slots[mt]) in mas_prev_nentry()
4807 offset = mt_slots[mt] - 1; in mas_prev_nentry()
4809 slots = ma_slots(mn, mt); in mas_prev_nentry()
4810 pivots = ma_pivots(mn, mt); in mas_prev_nentry()
4811 if (offset == mt_pivots[mt]) in mas_prev_nentry()
5091 enum maple_type mt; in mas_skip_node() local
5093 mt = mte_node_type(mas->node); in mas_skip_node()
5094 slot_count = mt_slots[mt] - 1; in mas_skip_node()
5105 mt = mte_node_type(mas->node); in mas_skip_node()
5106 slot_count = mt_slots[mt] - 1; in mas_skip_node()
5111 pivots = ma_pivots(mas_mn(mas), mt); in mas_skip_node()
5231 enum maple_type mt; in mas_empty_area() local
5258 mt = mte_node_type(mas->node); in mas_empty_area()
5259 pivots = ma_pivots(mas_mn(mas), mt); in mas_empty_area()
5263 if (offset < mt_pivots[mt]) in mas_empty_area()
5458 struct maple_tree mt; in mt_free_walk() local
5461 MA_STATE(mas, &mt, 0, 0); in mt_free_walk()
5468 mt_init_flags(&mt, node->ma_flags); in mt_free_walk()
5530 struct maple_tree mt; in mt_destroy_walk() local
5532 MA_STATE(mas, &mt, 0, 0); in mt_destroy_walk()
5537 mt_init_flags(&mt, ma_flags); in mt_destroy_walk()
5592 struct maple_tree *mt) in mte_destroy_walk() argument
5596 if (mt_in_rcu(mt)) { in mte_destroy_walk()
5597 mt_destroy_walk(enode, mt->ma_flags, false); in mte_destroy_walk()
5600 mt_destroy_walk(enode, mt->ma_flags, true); in mte_destroy_walk()
5874 * @mt: The maple tree
5880 void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max) in mt_next() argument
5883 MA_STATE(mas, mt, index, index); in mt_next()
5938 * @mt: The maple tree
5944 void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min) in mt_prev() argument
5947 MA_STATE(mas, mt, index, index); in mt_prev()
6140 * @mt: The maple tree
6145 void *mtree_load(struct maple_tree *mt, unsigned long index) in mtree_load() argument
6147 MA_STATE(mas, mt, index, index); in mtree_load()
6178 * @mt: The maple tree
6187 int mtree_store_range(struct maple_tree *mt, unsigned long index, in mtree_store_range() argument
6190 MA_STATE(mas, mt, index, last); in mtree_store_range()
6200 mtree_lock(mt); in mtree_store_range()
6206 mtree_unlock(mt); in mtree_store_range()
6216 * @mt: The maple tree
6224 int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, in mtree_store() argument
6227 return mtree_store_range(mt, index, index, entry, gfp); in mtree_store()
6233 * @mt: The maple tree
6242 int mtree_insert_range(struct maple_tree *mt, unsigned long first, in mtree_insert_range() argument
6245 MA_STATE(ms, mt, first, last); in mtree_insert_range()
6253 mtree_lock(mt); in mtree_insert_range()
6259 mtree_unlock(mt); in mtree_insert_range()
6269 * @mt: The maple tree
6277 int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, in mtree_insert() argument
6280 return mtree_insert_range(mt, index, index, entry, gfp); in mtree_insert()
6284 int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, in mtree_alloc_range() argument
6290 MA_STATE(mas, mt, min, max - size); in mtree_alloc_range()
6291 if (!mt_is_alloc(mt)) in mtree_alloc_range()
6306 mtree_lock(mt); in mtree_alloc_range()
6315 mtree_unlock(mt); in mtree_alloc_range()
6320 int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, in mtree_alloc_rrange() argument
6326 MA_STATE(mas, mt, min, max - size); in mtree_alloc_rrange()
6327 if (!mt_is_alloc(mt)) in mtree_alloc_rrange()
6342 mtree_lock(mt); in mtree_alloc_rrange()
6348 mtree_unlock(mt); in mtree_alloc_rrange()
6355 * @mt: The maple tree
6363 void *mtree_erase(struct maple_tree *mt, unsigned long index) in mtree_erase() argument
6367 MA_STATE(mas, mt, index, index); in mtree_erase()
6370 mtree_lock(mt); in mtree_erase()
6372 mtree_unlock(mt); in mtree_erase()
6380 * @mt: The maple tree
6384 void __mt_destroy(struct maple_tree *mt) in __mt_destroy() argument
6386 void *root = mt_root_locked(mt); in __mt_destroy()
6388 rcu_assign_pointer(mt->ma_root, NULL); in __mt_destroy()
6390 mte_destroy_walk(root, mt); in __mt_destroy()
6392 mt->ma_flags = 0; in __mt_destroy()
6398 * @mt: The maple tree
6402 void mtree_destroy(struct maple_tree *mt) in mtree_destroy() argument
6404 mtree_lock(mt); in mtree_destroy()
6405 __mt_destroy(mt); in mtree_destroy()
6406 mtree_unlock(mt); in mtree_destroy()
6412 * @mt: The maple tree
6420 void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max) in mt_find() argument
6422 MA_STATE(mas, mt, *index, *index); in mt_find()
6461 MT_BUG_ON(mt, (*index) && ((*index) <= copy)); in mt_find()
6471 * @mt: The maple tree
6479 void *mt_find_after(struct maple_tree *mt, unsigned long *index, in mt_find_after() argument
6485 return mt_find(mt, index, max); in mt_find_after()
6592 unsigned long limit, enum maple_type mt) in mas_first_entry() argument
6606 while (likely(!ma_is_leaf(mt))) { in mas_first_entry()
6608 slots = ma_slots(mn, mt); in mas_first_entry()
6609 pivots = ma_pivots(mn, mt); in mas_first_entry()
6616 mt = mte_node_type(mas->node); in mas_first_entry()
6621 slots = ma_slots(mn, mt); in mas_first_entry()
6633 pivots = ma_pivots(mn, mt); in mas_first_entry()
6684 static void mt_dump_node(const struct maple_tree *mt, void *entry,
6713 static void mt_dump_range64(const struct maple_tree *mt, void *entry, in mt_dump_range64() argument
6735 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_range64()
6738 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_range64()
6752 static void mt_dump_arange64(const struct maple_tree *mt, void *entry, in mt_dump_arange64() argument
6777 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_arange64()
6780 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_arange64()
6794 static void mt_dump_node(const struct maple_tree *mt, void *entry, in mt_dump_node() argument
6811 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_node()
6817 mt_dump_range64(mt, entry, min, max, depth); in mt_dump_node()
6820 mt_dump_arange64(mt, entry, min, max, depth); in mt_dump_node()
6828 void mt_dump(const struct maple_tree *mt) in mt_dump() argument
6830 void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt)); in mt_dump()
6833 mt, mt->ma_flags, mt_height(mt), entry); in mt_dump()
6837 mt_dump_node(mt, entry, 0, mt_max[mte_node_type(entry)], 0); in mt_dump()
7073 static void mt_validate_nulls(struct maple_tree *mt) in mt_validate_nulls() argument
7078 MA_STATE(mas, mt, 0, 0); in mt_validate_nulls()
7094 MT_BUG_ON(mt, !last && !entry); in mt_validate_nulls()
7115 void mt_validate(struct maple_tree *mt) in mt_validate() argument
7119 MA_STATE(mas, mt, 0, 0); in mt_validate()
7141 if (mt_is_alloc(mt)) in mt_validate()
7145 mt_validate_nulls(mt); in mt_validate()