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]),
750 new_s0->back_pointer = node->back_pointer;
751 new_s0->parent_slot = node->parent_slot;
772 /* This now reduces to a node splitting exercise for which we'll need
776 ptr = node->slots[i];
797 struct assoc_array_node *node, *new_n0, *side;
812 /* We need to split a shortcut and insert a node between the two
826 node = assoc_array_ptr_to_node(shortcut->back_pointer);
827 edit->set[0].ptr = &node->slots[shortcut->parent_slot];
834 /* Create a new node now since we're going to need it anyway */
841 /* Insert a new shortcut before the new node if this segment isn't of
842 * zero length - otherwise we just connect the new node directly to the
881 /* We need to know which slot in the new node is going to take a
890 /* Determine whether we need to follow the new node with a replacement
922 /* We don't have to replace the pointed-to node as long as we
934 /* Install the new leaf in a spare slot in the new node. */
990 /* Allocate a root node if there isn't one yet */
996 /* We found a node that doesn't have a node/shortcut pointer in
1037 struct assoc_array_node *node;
1043 * Subtree collapse to node iterator.
1055 collapse->node->slots[collapse->slot++] = assoc_array_leaf_to_ptr(leaf);
1084 struct assoc_array_node *node, *new_n0;
1101 /* We found a node that should contain the leaf we've been
1105 node = result.terminal_node.node;
1108 ptr = node->slots[slot];
1130 edit->dead_leaf = node->slots[slot];
1131 edit->set[0].ptr = &node->slots[slot];
1133 edit->adjust_count_on = node;
1150 * We go for a simple algorithm of: if this node has FAN_OUT or fewer
1155 * up space in this node.
1157 if (node->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
1161 /* First of all, we need to know if this node has metadata so
1167 ptr = node->slots[i];
1175 node->nr_leaves_on_branch - 1, has_meta);
1177 /* Look further up the tree to see if we can collapse this node
1178 * into a more proximal node too.
1180 parent = node;
1201 /* There's no point collapsing if the original node has no meta
1203 * node's ancestry.
1205 if (has_meta || parent != node) {
1206 node = parent;
1208 /* Create a new node to collapse into */
1214 new_n0->back_pointer = node->back_pointer;
1215 new_n0->parent_slot = node->parent_slot;
1216 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
1219 collapse.node = new_n0;
1222 assoc_array_subtree_iterate(assoc_array_node_to_ptr(node),
1223 node->back_pointer,
1229 if (!node->back_pointer) {
1231 } else if (assoc_array_ptr_is_leaf(node->back_pointer)) {
1233 } else if (assoc_array_ptr_is_node(node->back_pointer)) {
1235 assoc_array_ptr_to_node(node->back_pointer);
1236 edit->set[1].ptr = &p->slots[node->parent_slot];
1237 } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) {
1239 assoc_array_ptr_to_shortcut(node->back_pointer);
1243 edit->excised_subtree = assoc_array_node_to_ptr(node);
1348 struct assoc_array_node *node;
1376 node = edit->adjust_count_on;
1378 node->nr_leaves_on_branch += edit->adjust_count_by;
1380 ptr = node->back_pointer;
1390 node = assoc_array_ptr_to_node(ptr);
1459 struct assoc_array_node *node, *new_n;
1506 /* Duplicate the node at this position */
1507 node = assoc_array_ptr_to_node(cursor);
1511 pr_devel("dup node %p -> %p\n", node, new_n);
1513 new_n->parent_slot = node->parent_slot;
1521 ptr = node->slots[slot];
1541 pr_devel("-- compress node %p --\n", new_n);
1543 /* Count up the number of empty slots in this node and work out the
1578 /* Fold the child node into this one */
1579 pr_devel("[%d] fold node %lu/%d [nx %d]\n",
1605 pr_devel("[%d] retain node %lu/%d [nx %d]\n",
1620 /* Excise this node if it is singly occupied by a shortcut */
1628 pr_devel("excise node %p with 1 shortcut\n", new_n);
1699 ptr = node->back_pointer;
1707 slot = node->parent_slot;
1711 node = assoc_array_ptr_to_node(cursor);