Lines Matching refs:shortcut
25 const struct assoc_array_shortcut *shortcut;
35 /* Descend through a shortcut */
36 shortcut = assoc_array_ptr_to_shortcut(cursor);
37 cursor = READ_ONCE(shortcut->next_node); /* Address dependency. */
89 /* Move up to the parent (may need to skip back over a shortcut) */
96 shortcut = assoc_array_ptr_to_shortcut(parent);
98 parent = READ_ONCE(shortcut->back_pointer); /* Address dependency. */
99 slot = shortcut->parent_slot;
158 struct assoc_array_shortcut *shortcut;
175 struct assoc_array_shortcut *shortcut;
215 /* The node doesn't have a node/shortcut pointer in the slot
236 /* There is a shortcut in the slot corresponding to the index key
237 * segment. We follow the shortcut if its partial index key matches
238 * this leaf's. Otherwise we need to split the shortcut.
242 shortcut = assoc_array_ptr_to_shortcut(cursor);
243 pr_devel("shortcut to %d\n", shortcut->skip_to_level);
245 BUG_ON(sc_level > shortcut->skip_to_level);
248 /* Check the leaf against the shortcut's index key a word at a
249 * time, trimming the final word (the shortcut stores the index
250 * key completely from the root to the shortcut's target).
255 sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
258 if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) {
259 /* Trim segments that are beyond the shortcut */
260 int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
262 next_sc_level = shortcut->skip_to_level;
269 /* This shortcut points elsewhere */
270 result->wrong_shortcut.shortcut = shortcut;
279 } while (sc_level < shortcut->skip_to_level);
281 /* The shortcut matches the leaf's index to this point. */
282 cursor = READ_ONCE(shortcut->next_node); /* Address dependency. */
346 struct assoc_array_shortcut *shortcut;
361 /* Descend through a shortcut */
362 pr_devel("[%d] shortcut\n", slot);
364 shortcut = assoc_array_ptr_to_shortcut(cursor);
365 BUG_ON(shortcut->back_pointer != parent);
366 BUG_ON(slot != -1 && shortcut->parent_slot != slot);
368 cursor = shortcut->next_node;
404 /* Move back up to the parent (may need to free a shortcut on
407 shortcut = assoc_array_ptr_to_shortcut(parent);
408 BUG_ON(shortcut->next_node != cursor);
410 parent = shortcut->back_pointer;
411 slot = shortcut->parent_slot;
412 pr_devel("free shortcut\n");
413 kfree(shortcut);
479 struct assoc_array_shortcut *shortcut, *new_s0;
494 /* We arrived at a node which doesn't have an onward node or shortcut
536 * those now. We may also need a new shortcut, but we deal with that
579 * to insert a shortcut if the new node wants to cluster with them.
696 shortcut = assoc_array_ptr_to_shortcut(ptr);
697 edit->set_backpointers[i] = &shortcut->back_pointer;
715 * in the same slot, so we have to replace this node with a shortcut to
717 * nodes, one inside the other, at the end of the shortcut and
721 * bit position into their keys so that we know how big the shortcut
791 * Handle insertion into the middle of a shortcut.
797 struct assoc_array_shortcut *shortcut, *new_s0, *new_s1;
804 shortcut = result->wrong_shortcut.shortcut;
813 /* We need to split a shortcut and insert a node between the two
824 if (!shortcut->back_pointer) {
826 } else if (assoc_array_ptr_is_node(shortcut->back_pointer)) {
827 node = assoc_array_ptr_to_node(shortcut->back_pointer);
828 edit->set[0].ptr = &node->slots[shortcut->parent_slot];
833 edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);
842 /* Insert a new shortcut before the new node if this segment isn't of
848 pr_devel("pre-shortcut %d...%d\n", level, diff);
858 new_s0->back_pointer = shortcut->back_pointer;
859 new_s0->parent_slot = shortcut->parent_slot;
866 memcpy(new_s0->index_key, shortcut->index_key,
873 pr_devel("no pre-shortcut\n");
875 new_n0->back_pointer = shortcut->back_pointer;
876 new_n0->parent_slot = shortcut->parent_slot;
879 side = assoc_array_ptr_to_node(shortcut->next_node);
892 * for the current shortcut. We could in theory reuse the current
893 * shortcut if its parent slot number doesn't change - but that's a
897 if (level < shortcut->skip_to_level) {
898 pr_devel("post-shortcut %d...%d\n", level, shortcut->skip_to_level);
899 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
910 new_s1->next_node = shortcut->next_node;
911 new_s1->skip_to_level = shortcut->skip_to_level;
915 memcpy(new_s1->index_key, shortcut->index_key,
921 pr_devel("no post-shortcut\n");
926 * irrelevant to the old parent shortcut).
928 new_n0->slots[sc_slot] = shortcut->next_node;
941 pr_devel("<--%s() = ok [split shortcut]\n", __func__);
997 /* We found a node that doesn't have a node/shortcut pointer in
1007 /* We found a shortcut that didn't match our key in a slot we
1348 struct assoc_array_shortcut *shortcut;
1385 shortcut = assoc_array_ptr_to_shortcut(ptr);
1386 ptr = shortcut->back_pointer;
1459 struct assoc_array_shortcut *shortcut, *new_s;
1487 /* If this point is a shortcut, then we need to duplicate it and
1491 shortcut = assoc_array_ptr_to_shortcut(cursor);
1492 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
1498 pr_devel("dup shortcut %p -> %p\n", shortcut, new_s);
1499 memcpy(new_s, shortcut, (sizeof(struct assoc_array_shortcut) +
1502 new_s->parent_slot = shortcut->parent_slot;
1505 cursor = shortcut->next_node;
1585 /* We would already have reaped an intervening shortcut
1622 /* Excise this node if it is singly occupied by a shortcut */
1630 pr_devel("excise node %p with 1 shortcut\n", new_n);
1643 /* We can discard any preceding shortcut also */
1647 pr_devel("excise preceding shortcut\n");
1683 pr_devel("excise shortcut\n");
1703 shortcut = assoc_array_ptr_to_shortcut(ptr);
1704 slot = shortcut->parent_slot;
1705 cursor = shortcut->back_pointer;