Lines Matching refs:node
26 const struct assoc_array_node *node;
40 node = assoc_array_ptr_to_node(cursor);
43 /* We perform two passes of each node.
45 * The first pass does all the leaves in this node. This means we
46 * don't miss any leaves if the node is split up by insertion whilst
52 ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */
68 * back to a replacement node with the leaves in a different layout.
79 node = assoc_array_ptr_to_node(cursor);
81 ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */
90 parent = READ_ONCE(node->back_pointer); /* Address dependency. */
91 slot = node->parent_slot;
104 /* Ascend to next slot in parent node */
153 struct assoc_array_node *node; /* Node in which leaf might be found */
167 * Navigate through the internal tree looking for the closest node to the key.
176 struct assoc_array_node *node;
194 * either empty or contains a leaf at which point we've found a node in
206 node = assoc_array_ptr_to_node(cursor);
209 ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */
215 /* The node doesn't have a node/shortcut pointer in the slot
218 result->terminal_node.node = node;
226 /* There is a pointer to a node in the slot corresponding to
299 * to the node that should contain the object and then searching the leaves
309 const struct assoc_array_node *node;
318 node = result.terminal_node.node;
321 * the terminal node.
324 ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */
347 struct assoc_array_node *node;
373 pr_devel("[%d] node\n", slot);
374 node = assoc_array_ptr_to_node(cursor);
375 BUG_ON(node->back_pointer != parent);
376 BUG_ON(slot != -1 && node->parent_slot != slot);
380 pr_devel("Node %p [back=%p]\n", node, node->back_pointer);
382 struct assoc_array_ptr *ptr = node->slots[slot];
397 parent = node->back_pointer;
398 slot = node->parent_slot;
399 pr_devel("free node\n");
400 kfree(node);
420 /* Ascend to next slot in parent node */
423 node = assoc_array_ptr_to_node(cursor);
472 * Handle insertion into a terminal node.
480 struct assoc_array_node *node, *new_n0, *new_n1, *side;
488 node = result->terminal_node.node;
494 /* We arrived at a node which doesn't have an onward node or shortcut
497 * need to split this node and insert in one of the fragments.
501 /* Firstly, we have to check the leaves in this node to see if there's
505 ptr = node->slots[i];
514 edit->leaf_p = &node->slots[i];
515 edit->dead_leaf = node->slots[i];
521 /* If there is a free slot in this node then we can just insert the
526 edit->leaf_p = &node->slots[free_slot];
527 edit->adjust_count_on = node;
532 /* The node has no spare slots - so we're either going to have to split
533 * it or insert another node before it.
552 ptr = node->slots[i];
569 /* The node contains only leaves */
579 * to insert a shortcut if the new node wants to cluster with them.
586 * create a new node (n0) to hold the new leaf and a pointer to
587 * a new node (n1) holding all the old leaves.
589 * This can be done by falling through to the node splitting
596 pr_devel("split node\n");
598 /* We need to split the current node. The node must contain anything
607 * leaves in the node and the new leaf. The current meta pointers can
610 * We need a new node (n0) to replace the current one and a new node to
614 new_n0->back_pointer = node->back_pointer;
615 new_n0->parent_slot = node->parent_slot;
622 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
648 if (assoc_array_ptr_is_meta(node->slots[i]))
649 new_n0->slots[i] = node->slots[i];
659 if (assoc_array_ptr_is_meta(node->slots[i]))
662 new_n1->slots[next_slot++] = node->slots[i];
668 new_n0->slots[free_slot] = node->slots[i];
690 ptr = node->slots[i];
702 ptr = node->back_pointer;
706 edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot];
709 edit->excised_meta[0] = assoc_array_node_to_ptr(node);
710 pr_devel("<--%s() = ok [split node]\n", __func__);
714 /* All the leaves, new and old, want to cluster together in this node
715 * in the same slot, so we have to replace this node with a shortcut to
731 int x = ops->diff_objects(assoc_array_ptr_to_leaf(node->slots[i]),
751 new_s0->back_pointer = node->back_pointer;
752 new_s0->parent_slot = node->parent_slot;
773 /* This now reduces to a node splitting exercise for which we'll need
777 ptr = node->slots[i];
798 struct assoc_array_node *node, *new_n0, *side;
813 /* We need to split a shortcut and insert a node between the two
827 node = assoc_array_ptr_to_node(shortcut->back_pointer);
828 edit->set[0].ptr = &node->slots[shortcut->parent_slot];
835 /* Create a new node now since we're going to need it anyway */
842 /* Insert a new shortcut before the new node if this segment isn't of
843 * zero length - otherwise we just connect the new node directly to the
882 /* We need to know which slot in the new node is going to take a
891 /* Determine whether we need to follow the new node with a replacement
923 /* We don't have to replace the pointed-to node as long as we
935 /* Install the new leaf in a spare slot in the new node. */
991 /* Allocate a root node if there isn't one yet */
997 /* We found a node that doesn't have a node/shortcut pointer in
1038 struct assoc_array_node *node;
1044 * Subtree collapse to node iterator.
1056 collapse->node->slots[collapse->slot++] = assoc_array_leaf_to_ptr(leaf);
1085 struct assoc_array_node *node, *new_n0;
1102 /* We found a node that should contain the leaf we've been
1106 node = result.terminal_node.node;
1109 ptr = node->slots[slot];
1131 edit->dead_leaf = node->slots[slot];
1132 edit->set[0].ptr = &node->slots[slot];
1134 edit->adjust_count_on = node;
1151 * We go for a simple algorithm of: if this node has FAN_OUT or fewer
1156 * up space in this node.
1158 if (node->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
1162 /* First of all, we need to know if this node has metadata so
1168 ptr = node->slots[i];
1176 node->nr_leaves_on_branch - 1, has_meta);
1178 /* Look further up the tree to see if we can collapse this node
1179 * into a more proximal node too.
1181 parent = node;
1202 /* There's no point collapsing if the original node has no meta
1204 * node's ancestry.
1206 if (has_meta || parent != node) {
1207 node = parent;
1209 /* Create a new node to collapse into */
1215 new_n0->back_pointer = node->back_pointer;
1216 new_n0->parent_slot = node->parent_slot;
1217 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
1220 collapse.node = new_n0;
1223 assoc_array_subtree_iterate(assoc_array_node_to_ptr(node),
1224 node->back_pointer,
1230 if (!node->back_pointer) {
1232 } else if (assoc_array_ptr_is_leaf(node->back_pointer)) {
1234 } else if (assoc_array_ptr_is_node(node->back_pointer)) {
1236 assoc_array_ptr_to_node(node->back_pointer);
1237 edit->set[1].ptr = &p->slots[node->parent_slot];
1238 } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) {
1240 assoc_array_ptr_to_shortcut(node->back_pointer);
1244 edit->excised_subtree = assoc_array_node_to_ptr(node);
1349 struct assoc_array_node *node;
1377 node = edit->adjust_count_on;
1379 node->nr_leaves_on_branch += edit->adjust_count_by;
1381 ptr = node->back_pointer;
1391 node = assoc_array_ptr_to_node(ptr);
1460 struct assoc_array_node *node, *new_n;
1508 /* Duplicate the node at this position */
1509 node = assoc_array_ptr_to_node(cursor);
1513 pr_devel("dup node %p -> %p\n", node, new_n);
1515 new_n->parent_slot = node->parent_slot;
1523 ptr = node->slots[slot];
1543 pr_devel("-- compress node %p --\n", new_n);
1545 /* Count up the number of empty slots in this node and work out the
1580 /* Fold the child node into this one */
1581 pr_devel("[%d] fold node %lu/%d [nx %d]\n",
1607 pr_devel("[%d] retain node %lu/%d [nx %d]\n",
1622 /* Excise this node if it is singly occupied by a shortcut */
1630 pr_devel("excise node %p with 1 shortcut\n", new_n);
1701 ptr = node->back_pointer;
1709 slot = node->parent_slot;
1713 node = assoc_array_ptr_to_node(cursor);