Lines Matching refs:mt
378 static inline bool mt_is_alloc(struct maple_tree *mt)
380 return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE);
779 * @mt: The maple node type
783 static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt)
785 switch (mt) {
797 static inline bool mt_write_locked(const struct maple_tree *mt)
799 return mt_external_lock(mt) ? mt_write_lock_is_held(mt) :
800 lockdep_is_held(&mt->ma_lock);
803 static inline bool mt_locked(const struct maple_tree *mt)
805 return mt_external_lock(mt) ? mt_lock_is_held(mt) :
806 lockdep_is_held(&mt->ma_lock);
809 static inline void *mt_slot(const struct maple_tree *mt,
812 return rcu_dereference_check(slots[offset], mt_locked(mt));
815 static inline void *mt_slot_locked(struct maple_tree *mt, void __rcu **slots,
818 return rcu_dereference_protected(slots[offset], mt_write_locked(mt));
859 static inline void *mt_root_locked(struct maple_tree *mt)
861 return rcu_dereference_protected(mt->ma_root, mt_write_locked(mt));
876 enum maple_type mt)
878 switch (mt) {
889 * @mt: The maple node type
893 static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt,
896 struct maple_metadata *meta = ma_meta(mn, mt);
904 * @mt: The maple tree
910 static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn,
923 next = mt_slot_locked(mt, slots,
944 * @mt: The maple node type
947 enum maple_type mt)
949 struct maple_metadata *meta = ma_meta(mn, mt);
957 * @mt: The maple node type
960 enum maple_type mt)
971 static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt,
975 struct maple_metadata *meta = ma_meta(mn, mt);
1002 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
1494 enum maple_type mt;
1502 mt = mte_node_type(mas->node);
1504 slots = ma_slots(mn, mt);
1506 if (unlikely(ma_is_dense(mt))) {
1508 for (i = 0; i < mt_slots[mt]; i++) {
1526 pivots = ma_pivots(mn, mt);
1535 max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1;
1566 * @mt: The maple node type
1574 ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt,
1580 i = offset = ma_meta_end(node, mt);
1602 enum maple_type mt;
1605 mt = mte_node_type(mas->node);
1606 if (ma_is_leaf(mt))
1610 MAS_BUG_ON(mas, mt != maple_arange_64);
1611 offset = ma_meta_gap(node, mt);
1612 gaps = ma_gaps(node, mt);
1772 enum maple_type mt;
1780 mt = mte_node_type(mas->node);
1782 slots = ma_slots(node, mt);
1783 pivots = ma_pivots(node, mt);
1784 end = ma_data_end(node, mt, pivots, mas->max);
1946 enum maple_type mt;
1954 mt = mte_node_type(mas->node);
1955 pivots = ma_pivots(node, mt);
1963 piv_end = min(mas_end, mt_pivots[mt]);
1974 b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt);
1979 slots = ma_slots(node, mt);
1981 if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) {
1982 gaps = ma_gaps(node, mt);
1993 * @mt: The maple type
2002 enum maple_type mt, unsigned char end)
2005 if (mt_pivots[mt] <= end)
2011 if (end < mt_slots[mt] - 1)
2012 ma_set_meta(node, mt, 0, end);
2027 enum maple_type mt = mte_node_type(mas->node);
2029 void __rcu **slots = ma_slots(node, mt);
2030 unsigned long *pivots = ma_pivots(node, mt);
2034 if (mab_end - mab_start > mt_pivots[mt])
2037 if (!pivots[mt_pivots[mt] - 1])
2038 slots[mt_pivots[mt]] = NULL;
2052 if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) {
2056 gaps = ma_gaps(node, mt);
2065 ma_set_meta(node, mt, offset, end);
2067 mas_leaf_set_meta(mas, node, pivots, mt, end);
2075 * @mt: The maple node type
2078 enum maple_type mt)
2086 if (end > mt_min_slots[mt]) {
3051 enum maple_type mt = mte_node_type(mas->node);
3054 unsigned char offset, tmp, split = mt_slots[mt] / 2;
3078 slots = ma_slots(newnode, mt);
3079 pivs = ma_pivots(newnode, mt);
3081 l_slots = ma_slots(left, mt);
3082 l_pivs = ma_pivots(left, mt);
3090 memcpy(slots + tmp, ma_slots(node, mt), sizeof(void *) * end);
3091 memcpy(pivs + tmp, ma_pivots(node, mt), sizeof(unsigned long) * end);
3099 unsigned char max_p = mt_pivots[mt];
3100 unsigned char max_s = mt_slots[mt];
3106 if (tmp < mt_slots[mt])
3110 ma_set_meta(node, mt, 0, tmp - 1);
3118 ma_set_meta(left, mt, 0, split);
3125 mas->node = mt_mk_node(newnode, mt);
3126 ma_set_meta(newnode, mt, 0, tmp);
3130 mt = mte_node_type(l_mas.node);
3131 slots = ma_slots(new_left, mt);
3132 pivs = ma_pivots(new_left, mt);
3135 ma_set_meta(new_left, mt, 0, split);
3136 l_mas.node = mt_mk_node(new_left, mt);
3140 mt = mas_parent_type(&l_mas, l_mas.node);
3142 slots = ma_slots(parent, mt);
3143 pivs = ma_pivots(parent, mt);
3148 eparent = mt_mk_node(parent, mt);
4361 enum maple_type mt;
4390 mt = mte_node_type(mas->node);
4393 slots = ma_slots(node, mt);
4398 mt = mte_node_type(mas->node);
4400 pivots = ma_pivots(node, mt);
4401 offset = ma_data_end(node, mt, pivots, max);
4406 slots = ma_slots(node, mt);
4408 pivots = ma_pivots(node, mt);
4527 enum maple_type mt;
4545 mt = mte_node_type(mas->node);
4546 pivots = ma_pivots(node, mt);
4547 node_end = ma_data_end(node, mt, pivots, mas->max);
4553 slots = ma_slots(node, mt);
4566 mt = mte_node_type(mas->node);
4567 slots = ma_slots(node, mt);
4574 pivots = ma_pivots(node, mt);
4576 mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt);
5028 enum maple_type mt;
5059 mt = mte_node_type(mas->node);
5060 pivots = ma_pivots(mas_mn(mas), mt);
5140 unsigned char mte_dead_leaves(struct maple_enode *enode, struct maple_tree *mt,
5149 entry = mt_slot(mt, slots, offset);
5236 struct maple_tree *mt, struct maple_enode *prev, unsigned char offset)
5249 next = mt_slot_locked(mt, slots, next_offset);
5251 next = mt_slot_locked(mt, slots, ++next_offset);
5265 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
5278 slots = mte_destroy_descend(&enode, mt, start, 0);
5285 node->slot_len = mte_dead_leaves(enode, mt, slots);
5298 tmp = mt_slot_locked(mt, slots, offset);
5302 slots = mte_destroy_descend(&enode, mt, parent, offset);
5309 node->slot_len = mte_dead_leaves(enode, mt, slots);
5317 mt_clear_meta(mt, node, node->type);
5323 * @mt: the tree to free - needed for node types.
5328 struct maple_tree *mt)
5332 if (mt_in_rcu(mt)) {
5333 mt_destroy_walk(enode, mt, false);
5336 mt_destroy_walk(enode, mt, true);
5751 * @mt: The maple tree
5761 void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max)
5764 MA_STATE(mas, mt, index, index);
5874 * @mt: The maple tree
5884 void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min)
5887 MA_STATE(mas, mt, index, index);
6234 * @mt: The maple tree
6239 void *mtree_load(struct maple_tree *mt, unsigned long index)
6241 MA_STATE(mas, mt, index, index);
6272 * @mt: The maple tree
6281 int mtree_store_range(struct maple_tree *mt, unsigned long index,
6284 MA_STATE(mas, mt, index, last);
6294 mtree_lock(mt);
6300 mtree_unlock(mt);
6310 * @mt: The maple tree
6318 int mtree_store(struct maple_tree *mt, unsigned long index, void *entry,
6321 return mtree_store_range(mt, index, index, entry, gfp);
6327 * @mt: The maple tree
6336 int mtree_insert_range(struct maple_tree *mt, unsigned long first,
6339 MA_STATE(ms, mt, first, last);
6347 mtree_lock(mt);
6353 mtree_unlock(mt);
6363 * @mt: The maple tree
6371 int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry,
6374 return mtree_insert_range(mt, index, index, entry, gfp);
6378 int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
6384 MA_STATE(mas, mt, 0, 0);
6385 if (!mt_is_alloc(mt))
6391 mtree_lock(mt);
6411 mtree_unlock(mt);
6416 int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
6422 MA_STATE(mas, mt, 0, 0);
6423 if (!mt_is_alloc(mt))
6429 mtree_lock(mt);
6449 mtree_unlock(mt);
6456 * @mt: The maple tree
6464 void *mtree_erase(struct maple_tree *mt, unsigned long index)
6468 MA_STATE(mas, mt, index, index);
6471 mtree_lock(mt);
6473 mtree_unlock(mt);
6481 * @mt: The maple tree
6485 void __mt_destroy(struct maple_tree *mt)
6487 void *root = mt_root_locked(mt);
6489 rcu_assign_pointer(mt->ma_root, NULL);
6491 mte_destroy_walk(root, mt);
6493 mt->ma_flags = 0;
6499 * @mt: The maple tree
6503 void mtree_destroy(struct maple_tree *mt)
6505 mtree_lock(mt);
6506 __mt_destroy(mt);
6507 mtree_unlock(mt);
6513 * @mt: The maple tree
6527 void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max)
6529 MA_STATE(mas, mt, *index, *index);
6565 if (MT_WARN_ON(mt, (*index) && ((*index) <= copy)))
6577 * @mt: The maple tree
6587 void *mt_find_after(struct maple_tree *mt, unsigned long *index,
6593 return mt_find(mt, index, max);
6717 static void mt_dump_node(const struct maple_tree *mt, void *entry,
6757 static void mt_dump_range64(const struct maple_tree *mt, void *entry,
6788 mt_dump_entry(mt_slot(mt, node->slot, i),
6791 mt_dump_node(mt, mt_slot(mt, node->slot, i),
6812 static void mt_dump_arange64(const struct maple_tree *mt, void *entry,
6854 mt_dump_entry(mt_slot(mt, node->slot, i),
6857 mt_dump_node(mt, mt_slot(mt, node->slot, i),
6871 static void mt_dump_node(const struct maple_tree *mt, void *entry,
6889 mt_dump_entry(mt_slot(mt, node->slot, i),
6895 mt_dump_range64(mt, entry, min, max, depth, format);
6898 mt_dump_arange64(mt, entry, min, max, depth, format);
6906 void mt_dump(const struct maple_tree *mt, enum mt_dump_format format)
6908 void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt));
6911 mt, mt->ma_flags, mt_height(mt), entry);
6915 mt_dump_node(mt, entry, 0, mt_node_max(entry), 0, format);
6927 enum maple_type mt = mte_node_type(mas->node);
6932 unsigned long *pivots = ma_pivots(node, mt);
6935 if (ma_is_dense(mt)) {
6948 gaps = ma_gaps(node, mt);
6950 p_end = mas_safe_pivot(mas, pivots, i, mt);
6978 if (mt == maple_arange_64) {
6979 offset = ma_meta_gap(node, mt);
7161 static void mt_validate_nulls(struct maple_tree *mt)
7166 MA_STATE(mas, mt, 0, 0);
7182 MT_BUG_ON(mt, !last && !entry);
7203 void mt_validate(struct maple_tree *mt)
7207 MA_STATE(mas, mt, 0, 0);
7227 if (mt_is_alloc(mt))
7231 mt_validate_nulls(mt);