Lines Matching refs:parent
121 struct maple_pnode *parent;
184 * The maple tree uses the parent pointer to indicate this node is no longer in
189 WARN_ON(node->parent != ma_parent_ptr(node));
320 mte_to_node(mn)->parent = ma_parent_ptr(mte_to_node(mn));
365 return ((unsigned long)node->parent & MA_ROOT_PARENT);
385 * Excluding root, the parent pointer is 256B aligned like all other tree nodes.
417 * mte_parent_shift() - Get the parent shift for the slot storage.
418 * @parent: The parent pointer cast as an unsigned long
421 static inline unsigned long mte_parent_shift(unsigned long parent)
424 if (likely(parent & MAPLE_PARENT_NOT_RANGE16))
431 * mte_parent_slot_mask() - Get the slot mask for the parent.
432 * @parent: The parent pointer cast as an unsigned long.
433 * Return: The slot mask for that parent.
435 static inline unsigned long mte_parent_slot_mask(unsigned long parent)
438 if (likely(parent & MAPLE_PARENT_NOT_RANGE16))
445 * mas_parent_type() - Return the maple_type of the parent from the stored
446 * parent type.
448 * @enode: The maple_enode to extract the parent's enum
449 * Return: The node->parent maple_type
456 p_type = (unsigned long)mte_to_node(enode)->parent;
473 * mas_set_parent() - Set the parent node and encode the slot
475 * @parent: The encoded maple node that is the parent of @enode.
476 * @slot: The slot that @enode resides in @parent.
478 * Slot number is encoded in the enode->parent bit 3-6 or 2-6, depending on the
479 * parent type.
483 const struct maple_enode *parent, unsigned char slot)
485 unsigned long val = (unsigned long)parent;
488 enum maple_type p_type = mte_node_type(parent);
506 val &= ~MAPLE_NODE_MASK; /* Clear all node metadata in parent */
508 mte_to_node(enode)->parent = ma_parent_ptr(val);
512 * mte_parent_slot() - get the parent slot of @enode.
515 * Return: The slot in the parent node where @enode resides.
519 unsigned long val = (unsigned long)mte_to_node(enode)->parent;
526 * by shift if the parent shift is MAPLE_PARENT_SLOT_SHIFT
532 * mte_parent() - Get the parent of @node.
535 * Return: The parent maple node.
540 (mte_to_node(enode)->parent) & ~MAPLE_NODE_MASK);
551 struct maple_node *parent;
553 /* Do not reorder reads from the node prior to the parent check */
555 parent = (void *)((unsigned long) node->parent & ~MAPLE_NODE_MASK);
556 return (parent == node);
567 struct maple_node *parent, *node;
570 /* Do not reorder reads from the node prior to the parent check */
572 parent = mte_parent(enode);
573 return (parent == node);
1079 struct maple_enode *p_enode; /* parent enode. */
1082 struct maple_node *p_node; /* parent node. */
1103 /* Check to make sure all parent information is still accurate */
1617 * mas_parent_gap() - Set the parent gap and any gaps above, as needed
1619 * @offset: The gap offset in the parent to set
1622 * Set the parent gap then continue to set the gap upwards, using the metadata
1623 * of the parent to see if it is necessary to check the node above.
1663 /* Go to the parent node. */
1699 * mas_adopt_children() - Set the parent pointer of all nodes in @parent to
1700 * @parent with the slot encoded.
1702 * @parent - the maple encoded node containing the children.
1705 struct maple_enode *parent)
1707 enum maple_type type = mte_node_type(parent);
1708 struct maple_node *node = mte_to_node(parent);
1717 mas_set_parent(mas, child, parent, offset);
1735 mas_mn(mas)->parent = ma_parent_ptr(mas_tree_parent(mas));
1752 * the parent encoding to locate the maple node in the tree.
1765 * mas_find_child() - Find a child who has the parent @mas->node.
1766 * @mas: the maple state with the parent.
1903 * also be located in different parent nodes which are also full. This can
2168 * mas_prev_sibling() - Find the previous node with the same parent.
2190 * mas_next_sibling() - Find the next node with the same parent.
2197 MA_STATE(parent, mas->tree, mas->index, mas->last);
2202 parent = *mas;
2203 mas_ascend(&parent);
2204 parent.offset = mte_parent_slot(mas->node) + 1;
2205 if (parent.offset > mas_data_end(&parent))
2208 *mas = parent;
2448 * mas_set_split_parent() - combine_then_separate helper function. Sets the parent
2451 * @mas - the maple state with the node that needs a parent
2452 * @left - possible parent 1
2453 * @right - possible parent 2
2563 * parent links within the new tree. Iterate over the dead sub-tree and collect
2566 * The new tree will have up to three children with the correct parent. Keep
2570 * The old tree will have up to three children with the old parent. Keep track
2589 /* Update the parent pointers in the tree */
2896 * will have the incorrect parent pointers and currently be in two trees: the
2897 * original tree and the partially new tree. To remedy the parent pointers in
2899 * the tree is performed and the parent pointers are updated.
2964 mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas));
2968 mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent;
3008 * causes just one node to be produced instead of two, then the parent
3052 struct maple_node reuse, *newnode, *parent, *new_left, *left, *node;
3066 /* Allocate for both left and right as well as parent. */
3077 newnode->parent = node->parent;
3124 /* RCU requires replacing both l_mas, mas, and parent. */
3129 new_left->parent = left->parent;
3138 /* replace parent. */
3141 parent = mas_pop_node(mas);
3142 slots = ma_slots(parent, mt);
3143 pivs = ma_pivots(parent, mt);
3144 memcpy(parent, mte_to_node(old_eparent), sizeof(struct maple_node));
3148 eparent = mt_mk_node(parent, mt);
3189 mte_to_node(ancestor)->parent = mas_mn(mas)->parent;
3332 /* Update parent slot for split calculation. */
3492 node->parent = mas_mn(wr_mas->mas)->parent;
3522 node->parent = ma_parent_ptr(mas_tree_parent(mas));
3799 node->parent = ma_parent_ptr(mas_tree_parent(mas));
3953 newnode->parent = mas_mn(mas)->parent;
4970 * go back to parent (ascend)
5283 struct maple_enode *parent, *tmp;
5300 parent = enode;
5302 slots = mte_destroy_descend(&enode, mt, parent, offset);
6881 pr_cont("node %p depth %d type %d parent %p", node, depth, type,
6882 node ? node->parent : NULL);
6921 * the parent (unless root).
7016 struct maple_node *parent;
7028 parent = mte_parent(mas->node);
7029 slots = ma_slots(parent, p_type);
7030 MT_BUG_ON(mas->tree, mas_mn(mas) == parent);
7032 /* Check prev/next parent slot for duplicate node entry */
7038 pr_err("parent %p[%u] does not have %p\n",
7039 parent, i, mas_mn(mas));
7042 pr_err("Invalid child %p at parent %p[%u] p_slot %u\n",
7043 mas_mn(mas), parent, i, p_slot);
7077 pr_err("child %p has parent %p not %p\n",