Lines Matching +full:pre +full:- +full:cursor
1 // SPDX-License-Identifier: GPL-2.0-or-later
4 * See Documentation/core-api/assoc_array.rst for information.
27 const struct assoc_array_ptr *cursor, *ptr, *parent; in assoc_array_subtree_iterate() local
31 cursor = root; in assoc_array_subtree_iterate()
34 if (assoc_array_ptr_is_shortcut(cursor)) { in assoc_array_subtree_iterate()
36 shortcut = assoc_array_ptr_to_shortcut(cursor); in assoc_array_subtree_iterate()
37 cursor = READ_ONCE(shortcut->next_node); /* Address dependency. */ in assoc_array_subtree_iterate()
40 node = assoc_array_ptr_to_node(cursor); in assoc_array_subtree_iterate()
52 ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */ in assoc_array_subtree_iterate()
71 * a particular portion of the key space cannot change - and we in assoc_array_subtree_iterate()
79 node = assoc_array_ptr_to_node(cursor); in assoc_array_subtree_iterate()
81 ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */ in assoc_array_subtree_iterate()
83 cursor = ptr; in assoc_array_subtree_iterate()
90 parent = READ_ONCE(node->back_pointer); /* Address dependency. */ in assoc_array_subtree_iterate()
91 slot = node->parent_slot; in assoc_array_subtree_iterate()
97 cursor = parent; in assoc_array_subtree_iterate()
98 parent = READ_ONCE(shortcut->back_pointer); /* Address dependency. */ in assoc_array_subtree_iterate()
99 slot = shortcut->parent_slot; in assoc_array_subtree_iterate()
105 cursor = parent; in assoc_array_subtree_iterate()
111 * assoc_array_iterate - Pass all objects in the array to a callback
121 * callback more than once - though every object should be passed at least
127 * immediately if any call to the iteration function results in a non-zero
138 struct assoc_array_ptr *root = READ_ONCE(array->root); /* Address dependency. */ in assoc_array_iterate()
177 struct assoc_array_ptr *cursor, *ptr; in assoc_array_walk() local
183 pr_devel("-->%s()\n", __func__); in assoc_array_walk()
185 cursor = READ_ONCE(array->root); /* Address dependency. */ in assoc_array_walk()
186 if (!cursor) in assoc_array_walk()
199 segments = ops->get_key_chunk(index_key, level); in assoc_array_walk()
202 if (assoc_array_ptr_is_shortcut(cursor)) in assoc_array_walk()
206 node = assoc_array_ptr_to_node(cursor); in assoc_array_walk()
209 ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */ in assoc_array_walk()
218 result->terminal_node.node = node; in assoc_array_walk()
219 result->terminal_node.level = level; in assoc_array_walk()
220 result->terminal_node.slot = slot; in assoc_array_walk()
221 pr_devel("<--%s() = terminal_node\n", __func__); in assoc_array_walk()
229 cursor = ptr; in assoc_array_walk()
240 cursor = ptr; in assoc_array_walk()
242 shortcut = assoc_array_ptr_to_shortcut(cursor); in assoc_array_walk()
243 pr_devel("shortcut to %d\n", shortcut->skip_to_level); in assoc_array_walk()
245 BUG_ON(sc_level > shortcut->skip_to_level); in assoc_array_walk()
253 segments = ops->get_key_chunk(index_key, sc_level); in assoc_array_walk()
255 sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT]; in assoc_array_walk()
258 if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) { in assoc_array_walk()
260 int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK; in assoc_array_walk()
262 next_sc_level = shortcut->skip_to_level; in assoc_array_walk()
270 result->wrong_shortcut.shortcut = shortcut; in assoc_array_walk()
271 result->wrong_shortcut.level = level; in assoc_array_walk()
272 result->wrong_shortcut.sc_level = sc_level; in assoc_array_walk()
273 result->wrong_shortcut.sc_segments = sc_segments; in assoc_array_walk()
274 result->wrong_shortcut.dissimilarity = dissimilarity; in assoc_array_walk()
279 } while (sc_level < shortcut->skip_to_level); in assoc_array_walk()
282 cursor = READ_ONCE(shortcut->next_node); /* Address dependency. */ in assoc_array_walk()
293 * assoc_array_find - Find an object by index key
324 ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */ in assoc_array_find()
327 * and dereferencing the pointer - but only if we are in assoc_array_find()
331 if (ops->compare_object(leaf, index_key)) in assoc_array_find()
348 struct assoc_array_ptr *cursor, *parent = NULL; in assoc_array_destroy_subtree() local
349 int slot = -1; in assoc_array_destroy_subtree()
351 pr_devel("-->%s()\n", __func__); in assoc_array_destroy_subtree()
353 cursor = root; in assoc_array_destroy_subtree()
354 if (!cursor) { in assoc_array_destroy_subtree()
360 if (assoc_array_ptr_is_shortcut(cursor)) { in assoc_array_destroy_subtree()
363 BUG_ON(!assoc_array_ptr_is_shortcut(cursor)); in assoc_array_destroy_subtree()
364 shortcut = assoc_array_ptr_to_shortcut(cursor); in assoc_array_destroy_subtree()
365 BUG_ON(shortcut->back_pointer != parent); in assoc_array_destroy_subtree()
366 BUG_ON(slot != -1 && shortcut->parent_slot != slot); in assoc_array_destroy_subtree()
367 parent = cursor; in assoc_array_destroy_subtree()
368 cursor = shortcut->next_node; in assoc_array_destroy_subtree()
369 slot = -1; in assoc_array_destroy_subtree()
370 BUG_ON(!assoc_array_ptr_is_node(cursor)); in assoc_array_destroy_subtree()
374 node = assoc_array_ptr_to_node(cursor); in assoc_array_destroy_subtree()
375 BUG_ON(node->back_pointer != parent); in assoc_array_destroy_subtree()
376 BUG_ON(slot != -1 && node->parent_slot != slot); in assoc_array_destroy_subtree()
380 pr_devel("Node %p [back=%p]\n", node, node->back_pointer); in assoc_array_destroy_subtree()
382 struct assoc_array_ptr *ptr = node->slots[slot]; in assoc_array_destroy_subtree()
386 parent = cursor; in assoc_array_destroy_subtree()
387 cursor = ptr; in assoc_array_destroy_subtree()
393 ops->free_object(assoc_array_ptr_to_leaf(ptr)); in assoc_array_destroy_subtree()
397 parent = node->back_pointer; in assoc_array_destroy_subtree()
398 slot = node->parent_slot; in assoc_array_destroy_subtree()
408 BUG_ON(shortcut->next_node != cursor); in assoc_array_destroy_subtree()
409 cursor = parent; in assoc_array_destroy_subtree()
410 parent = shortcut->back_pointer; in assoc_array_destroy_subtree()
411 slot = shortcut->parent_slot; in assoc_array_destroy_subtree()
422 cursor = parent; in assoc_array_destroy_subtree()
423 node = assoc_array_ptr_to_node(cursor); in assoc_array_destroy_subtree()
429 * assoc_array_destroy - Destroy an associative array
438 * attempt is made to adjust pointers gracefully to permit RCU readlock-holding
444 assoc_array_destroy_subtree(array->root, ops); in assoc_array_destroy()
445 array->root = NULL; in assoc_array_destroy()
455 pr_devel("-->%s()\n", __func__); in assoc_array_insert_in_empty_tree()
461 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_in_empty_tree()
462 edit->leaf_p = &new_n0->slots[0]; in assoc_array_insert_in_empty_tree()
463 edit->adjust_count_on = new_n0; in assoc_array_insert_in_empty_tree()
464 edit->set[0].ptr = &edit->array->root; in assoc_array_insert_in_empty_tree()
465 edit->set[0].to = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_in_empty_tree()
467 pr_devel("<--%s() = ok [no root]\n", __func__); in assoc_array_insert_in_empty_tree()
488 node = result->terminal_node.node; in assoc_array_insert_into_terminal_node()
489 level = result->terminal_node.level; in assoc_array_insert_into_terminal_node()
490 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot; in assoc_array_insert_into_terminal_node()
492 pr_devel("-->%s()\n", __func__); in assoc_array_insert_into_terminal_node()
499 free_slot = -1; in assoc_array_insert_into_terminal_node()
505 ptr = node->slots[i]; in assoc_array_insert_into_terminal_node()
511 ops->compare_object(assoc_array_ptr_to_leaf(ptr), in assoc_array_insert_into_terminal_node()
514 edit->leaf_p = &node->slots[i]; in assoc_array_insert_into_terminal_node()
515 edit->dead_leaf = node->slots[i]; in assoc_array_insert_into_terminal_node()
516 pr_devel("<--%s() = ok [replace]\n", __func__); in assoc_array_insert_into_terminal_node()
526 edit->leaf_p = &node->slots[free_slot]; in assoc_array_insert_into_terminal_node()
527 edit->adjust_count_on = node; in assoc_array_insert_into_terminal_node()
528 pr_devel("<--%s() = ok [insert]\n", __func__); in assoc_array_insert_into_terminal_node()
532 /* The node has no spare slots - so we're either going to have to split in assoc_array_insert_into_terminal_node()
535 * Whatever, we're going to need at least two new nodes - so allocate in assoc_array_insert_into_terminal_node()
542 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_into_terminal_node()
546 edit->new_meta[1] = assoc_array_node_to_ptr(new_n1); in assoc_array_insert_into_terminal_node()
552 ptr = node->slots[i]; in assoc_array_insert_into_terminal_node()
554 edit->segment_cache[i] = 0xff; in assoc_array_insert_into_terminal_node()
558 base_seg = ops->get_object_key_chunk( in assoc_array_insert_into_terminal_node()
561 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK; in assoc_array_insert_into_terminal_node()
571 base_seg = edit->segment_cache[0]; in assoc_array_insert_into_terminal_node()
573 dissimilarity |= edit->segment_cache[i] ^ base_seg; in assoc_array_insert_into_terminal_node()
581 if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0) in assoc_array_insert_into_terminal_node()
585 * the new leaf wants to go into a different slot - so we in assoc_array_insert_into_terminal_node()
600 * with the new leaf) and the rest meta-pointers, to all leaves, some in assoc_array_insert_into_terminal_node()
613 edit->set[0].to = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_into_terminal_node()
614 new_n0->back_pointer = node->back_pointer; in assoc_array_insert_into_terminal_node()
615 new_n0->parent_slot = node->parent_slot; in assoc_array_insert_into_terminal_node()
616 new_n1->back_pointer = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_into_terminal_node()
617 new_n1->parent_slot = -1; /* Need to calculate this */ in assoc_array_insert_into_terminal_node()
622 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch; in assoc_array_insert_into_terminal_node()
623 new_n1->nr_leaves_on_branch = 0; in assoc_array_insert_into_terminal_node()
626 * that match - even if there are meta pointers - because any leaf that in assoc_array_insert_into_terminal_node()
632 slot = edit->segment_cache[i]; in assoc_array_insert_into_terminal_node()
635 if (edit->segment_cache[j] == slot) in assoc_array_insert_into_terminal_node()
644 new_n1->parent_slot = slot; in assoc_array_insert_into_terminal_node()
648 if (assoc_array_ptr_is_meta(node->slots[i])) in assoc_array_insert_into_terminal_node()
649 new_n0->slots[i] = node->slots[i]; in assoc_array_insert_into_terminal_node()
651 new_n0->slots[i] = NULL; in assoc_array_insert_into_terminal_node()
652 BUG_ON(new_n0->slots[slot] != NULL); in assoc_array_insert_into_terminal_node()
653 new_n0->slots[slot] = assoc_array_node_to_ptr(new_n1); in assoc_array_insert_into_terminal_node()
656 free_slot = -1; in assoc_array_insert_into_terminal_node()
659 if (assoc_array_ptr_is_meta(node->slots[i])) in assoc_array_insert_into_terminal_node()
661 if (edit->segment_cache[i] == slot) { in assoc_array_insert_into_terminal_node()
662 new_n1->slots[next_slot++] = node->slots[i]; in assoc_array_insert_into_terminal_node()
663 new_n1->nr_leaves_on_branch++; in assoc_array_insert_into_terminal_node()
667 } while (new_n0->slots[free_slot] != NULL); in assoc_array_insert_into_terminal_node()
668 new_n0->slots[free_slot] = node->slots[i]; in assoc_array_insert_into_terminal_node()
674 if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) { in assoc_array_insert_into_terminal_node()
677 } while (new_n0->slots[free_slot] != NULL); in assoc_array_insert_into_terminal_node()
678 edit->leaf_p = &new_n0->slots[free_slot]; in assoc_array_insert_into_terminal_node()
679 edit->adjust_count_on = new_n0; in assoc_array_insert_into_terminal_node()
681 edit->leaf_p = &new_n1->slots[next_slot++]; in assoc_array_insert_into_terminal_node()
682 edit->adjust_count_on = new_n1; in assoc_array_insert_into_terminal_node()
687 edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_into_terminal_node()
689 if (edit->segment_cache[i] == 0xff) { in assoc_array_insert_into_terminal_node()
690 ptr = node->slots[i]; in assoc_array_insert_into_terminal_node()
694 edit->set_backpointers[i] = &side->back_pointer; in assoc_array_insert_into_terminal_node()
697 edit->set_backpointers[i] = &shortcut->back_pointer; in assoc_array_insert_into_terminal_node()
702 ptr = node->back_pointer; in assoc_array_insert_into_terminal_node()
704 edit->set[0].ptr = &edit->array->root; in assoc_array_insert_into_terminal_node()
706 edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot]; in assoc_array_insert_into_terminal_node()
708 edit->set[0].ptr = &assoc_array_ptr_to_shortcut(ptr)->next_node; in assoc_array_insert_into_terminal_node()
709 edit->excised_meta[0] = assoc_array_node_to_ptr(node); in assoc_array_insert_into_terminal_node()
710 pr_devel("<--%s() = ok [split node]\n", __func__); in assoc_array_insert_into_terminal_node()
731 int x = ops->diff_objects(assoc_array_ptr_to_leaf(node->slots[i]), in assoc_array_insert_into_terminal_node()
747 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0); in assoc_array_insert_into_terminal_node()
749 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0); in assoc_array_insert_into_terminal_node()
750 new_s0->back_pointer = node->back_pointer; in assoc_array_insert_into_terminal_node()
751 new_s0->parent_slot = node->parent_slot; in assoc_array_insert_into_terminal_node()
752 new_s0->next_node = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_into_terminal_node()
753 new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0); in assoc_array_insert_into_terminal_node()
754 new_n0->parent_slot = 0; in assoc_array_insert_into_terminal_node()
755 new_n1->back_pointer = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_into_terminal_node()
756 new_n1->parent_slot = -1; /* Need to calculate this */ in assoc_array_insert_into_terminal_node()
758 new_s0->skip_to_level = level = diff & ~ASSOC_ARRAY_LEVEL_STEP_MASK; in assoc_array_insert_into_terminal_node()
763 new_s0->index_key[i] = in assoc_array_insert_into_terminal_node()
764 ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE); in assoc_array_insert_into_terminal_node()
768 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank); in assoc_array_insert_into_terminal_node()
769 new_s0->index_key[keylen - 1] &= ~blank; in assoc_array_insert_into_terminal_node()
776 ptr = node->slots[i]; in assoc_array_insert_into_terminal_node()
777 base_seg = ops->get_object_key_chunk(assoc_array_ptr_to_leaf(ptr), in assoc_array_insert_into_terminal_node()
780 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK; in assoc_array_insert_into_terminal_node()
783 base_seg = ops->get_key_chunk(index_key, level); in assoc_array_insert_into_terminal_node()
785 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK; in assoc_array_insert_into_terminal_node()
803 shortcut = result->wrong_shortcut.shortcut; in assoc_array_insert_mid_shortcut()
804 level = result->wrong_shortcut.level; in assoc_array_insert_mid_shortcut()
805 sc_level = result->wrong_shortcut.sc_level; in assoc_array_insert_mid_shortcut()
806 sc_segments = result->wrong_shortcut.sc_segments; in assoc_array_insert_mid_shortcut()
807 dissimilarity = result->wrong_shortcut.dissimilarity; in assoc_array_insert_mid_shortcut()
809 pr_devel("-->%s(ix=%d dis=%lx scix=%d)\n", in assoc_array_insert_mid_shortcut()
813 * pieces. Zero-length pieces will be dispensed with entirely. in assoc_array_insert_mid_shortcut()
823 if (!shortcut->back_pointer) { in assoc_array_insert_mid_shortcut()
824 edit->set[0].ptr = &edit->array->root; in assoc_array_insert_mid_shortcut()
825 } else if (assoc_array_ptr_is_node(shortcut->back_pointer)) { in assoc_array_insert_mid_shortcut()
826 node = assoc_array_ptr_to_node(shortcut->back_pointer); in assoc_array_insert_mid_shortcut()
827 edit->set[0].ptr = &node->slots[shortcut->parent_slot]; in assoc_array_insert_mid_shortcut()
832 edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut); in assoc_array_insert_mid_shortcut()
838 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_mid_shortcut()
839 edit->adjust_count_on = new_n0; in assoc_array_insert_mid_shortcut()
842 * zero length - otherwise we just connect the new node directly to the in assoc_array_insert_mid_shortcut()
847 pr_devel("pre-shortcut %d...%d\n", level, diff); in assoc_array_insert_mid_shortcut()
855 edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0); in assoc_array_insert_mid_shortcut()
856 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0); in assoc_array_insert_mid_shortcut()
857 new_s0->back_pointer = shortcut->back_pointer; in assoc_array_insert_mid_shortcut()
858 new_s0->parent_slot = shortcut->parent_slot; in assoc_array_insert_mid_shortcut()
859 new_s0->next_node = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_mid_shortcut()
860 new_s0->skip_to_level = diff; in assoc_array_insert_mid_shortcut()
862 new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0); in assoc_array_insert_mid_shortcut()
863 new_n0->parent_slot = 0; in assoc_array_insert_mid_shortcut()
865 memcpy(new_s0->index_key, shortcut->index_key, in assoc_array_insert_mid_shortcut()
869 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank); in assoc_array_insert_mid_shortcut()
870 new_s0->index_key[keylen - 1] &= ~blank; in assoc_array_insert_mid_shortcut()
872 pr_devel("no pre-shortcut\n"); in assoc_array_insert_mid_shortcut()
873 edit->set[0].to = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_mid_shortcut()
874 new_n0->back_pointer = shortcut->back_pointer; in assoc_array_insert_mid_shortcut()
875 new_n0->parent_slot = shortcut->parent_slot; in assoc_array_insert_mid_shortcut()
878 side = assoc_array_ptr_to_node(shortcut->next_node); in assoc_array_insert_mid_shortcut()
879 new_n0->nr_leaves_on_branch = side->nr_leaves_on_branch; in assoc_array_insert_mid_shortcut()
887 pr_devel("new slot %lx >> %d -> %d\n", in assoc_array_insert_mid_shortcut()
892 * shortcut if its parent slot number doesn't change - but that's a in assoc_array_insert_mid_shortcut()
893 * 1-in-16 chance so not worth expending the code upon. in assoc_array_insert_mid_shortcut()
896 if (level < shortcut->skip_to_level) { in assoc_array_insert_mid_shortcut()
897 pr_devel("post-shortcut %d...%d\n", level, shortcut->skip_to_level); in assoc_array_insert_mid_shortcut()
898 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE); in assoc_array_insert_mid_shortcut()
905 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1); in assoc_array_insert_mid_shortcut()
907 new_s1->back_pointer = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_mid_shortcut()
908 new_s1->parent_slot = sc_slot; in assoc_array_insert_mid_shortcut()
909 new_s1->next_node = shortcut->next_node; in assoc_array_insert_mid_shortcut()
910 new_s1->skip_to_level = shortcut->skip_to_level; in assoc_array_insert_mid_shortcut()
912 new_n0->slots[sc_slot] = assoc_array_shortcut_to_ptr(new_s1); in assoc_array_insert_mid_shortcut()
914 memcpy(new_s1->index_key, shortcut->index_key, in assoc_array_insert_mid_shortcut()
917 edit->set[1].ptr = &side->back_pointer; in assoc_array_insert_mid_shortcut()
918 edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1); in assoc_array_insert_mid_shortcut()
920 pr_devel("no post-shortcut\n"); in assoc_array_insert_mid_shortcut()
922 /* We don't have to replace the pointed-to node as long as we in assoc_array_insert_mid_shortcut()
927 new_n0->slots[sc_slot] = shortcut->next_node; in assoc_array_insert_mid_shortcut()
928 edit->set_parent_slot[0].p = &side->parent_slot; in assoc_array_insert_mid_shortcut()
929 edit->set_parent_slot[0].to = sc_slot; in assoc_array_insert_mid_shortcut()
930 edit->set[1].ptr = &side->back_pointer; in assoc_array_insert_mid_shortcut()
931 edit->set[1].to = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_mid_shortcut()
936 edit->leaf_p = &new_n0->slots[1]; in assoc_array_insert_mid_shortcut()
938 edit->leaf_p = &new_n0->slots[0]; in assoc_array_insert_mid_shortcut()
940 pr_devel("<--%s() = ok [split shortcut]\n", __func__); in assoc_array_insert_mid_shortcut()
945 * assoc_array_insert - Script insertion of an object into an associative array
955 * The function returns a pointer to an edit script or -ENOMEM.
971 pr_devel("-->%s()\n", __func__); in assoc_array_insert()
974 * use those for type-marking the pointer. NULL pointers are also not in assoc_array_insert()
982 return ERR_PTR(-ENOMEM); in assoc_array_insert()
983 edit->array = array; in assoc_array_insert()
984 edit->ops = ops; in assoc_array_insert()
985 edit->leaf = assoc_array_leaf_to_ptr(object); in assoc_array_insert()
986 edit->adjust_count_by = 1; in assoc_array_insert()
1018 return ERR_PTR(-ENOMEM); in assoc_array_insert()
1022 * assoc_array_insert_set_object - Set the new object pointer in an edit script
1033 edit->leaf = assoc_array_leaf_to_ptr(object); in assoc_array_insert_set_object()
1050 if (leaf == collapse->skip_leaf) in assoc_array_delete_collapse_iterator()
1053 BUG_ON(collapse->slot >= ASSOC_ARRAY_FAN_OUT); in assoc_array_delete_collapse_iterator()
1055 collapse->node->slots[collapse->slot++] = assoc_array_leaf_to_ptr(leaf); in assoc_array_delete_collapse_iterator()
1060 * assoc_array_delete - Script deletion of an object from an associative array
1070 * NULL if the object was not found or -ENOMEM.
1090 pr_devel("-->%s()\n", __func__); in assoc_array_delete()
1094 return ERR_PTR(-ENOMEM); in assoc_array_delete()
1095 edit->array = array; in assoc_array_delete()
1096 edit->ops = ops; in assoc_array_delete()
1097 edit->adjust_count_by = -1; in assoc_array_delete()
1102 * asked to remove - *if* it's in the tree. in assoc_array_delete()
1108 ptr = node->slots[slot]; in assoc_array_delete()
1111 ops->compare_object(assoc_array_ptr_to_leaf(ptr), in assoc_array_delete()
1125 BUG_ON(array->nr_leaves_on_tree <= 0); in assoc_array_delete()
1130 edit->dead_leaf = node->slots[slot]; in assoc_array_delete()
1131 edit->set[0].ptr = &node->slots[slot]; in assoc_array_delete()
1132 edit->set[0].to = NULL; in assoc_array_delete()
1133 edit->adjust_count_on = node; in assoc_array_delete()
1138 if (array->nr_leaves_on_tree == 1) { in assoc_array_delete()
1139 edit->set[1].ptr = &array->root; in assoc_array_delete()
1140 edit->set[1].to = NULL; in assoc_array_delete()
1141 edit->adjust_count_on = NULL; in assoc_array_delete()
1142 edit->excised_subtree = array->root; in assoc_array_delete()
1151 * leaves in it, then attempt to collapse it - and attempt to in assoc_array_delete()
1157 if (node->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) { in assoc_array_delete()
1167 ptr = node->slots[i]; in assoc_array_delete()
1175 node->nr_leaves_on_branch - 1, has_meta); in assoc_array_delete()
1182 pr_devel("collapse subtree: %ld\n", parent->nr_leaves_on_branch); in assoc_array_delete()
1184 ptr = parent->back_pointer; in assoc_array_delete()
1189 ptr = s->back_pointer; in assoc_array_delete()
1195 if (grandparent->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) { in assoc_array_delete()
1212 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0); in assoc_array_delete()
1214 new_n0->back_pointer = node->back_pointer; in assoc_array_delete()
1215 new_n0->parent_slot = node->parent_slot; in assoc_array_delete()
1216 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch; in assoc_array_delete()
1217 edit->adjust_count_on = new_n0; in assoc_array_delete()
1220 collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf); in assoc_array_delete()
1223 node->back_pointer, in assoc_array_delete()
1226 pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_branch); in assoc_array_delete()
1227 BUG_ON(collapse.slot != new_n0->nr_leaves_on_branch - 1); in assoc_array_delete()
1229 if (!node->back_pointer) { in assoc_array_delete()
1230 edit->set[1].ptr = &array->root; in assoc_array_delete()
1231 } else if (assoc_array_ptr_is_leaf(node->back_pointer)) { in assoc_array_delete()
1233 } else if (assoc_array_ptr_is_node(node->back_pointer)) { in assoc_array_delete()
1235 assoc_array_ptr_to_node(node->back_pointer); in assoc_array_delete()
1236 edit->set[1].ptr = &p->slots[node->parent_slot]; in assoc_array_delete()
1237 } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) { in assoc_array_delete()
1239 assoc_array_ptr_to_shortcut(node->back_pointer); in assoc_array_delete()
1240 edit->set[1].ptr = &s->next_node; in assoc_array_delete()
1242 edit->set[1].to = assoc_array_node_to_ptr(new_n0); in assoc_array_delete()
1243 edit->excised_subtree = assoc_array_node_to_ptr(node); in assoc_array_delete()
1253 return ERR_PTR(-ENOMEM); in assoc_array_delete()
1257 * assoc_array_clear - Script deletion of all objects from an associative array
1266 * deleted, NULL if there are no objects in the array or -ENOMEM.
1279 pr_devel("-->%s()\n", __func__); in assoc_array_clear()
1281 if (!array->root) in assoc_array_clear()
1286 return ERR_PTR(-ENOMEM); in assoc_array_clear()
1287 edit->array = array; in assoc_array_clear()
1288 edit->ops = ops; in assoc_array_clear()
1289 edit->set[1].ptr = &array->root; in assoc_array_clear()
1290 edit->set[1].to = NULL; in assoc_array_clear()
1291 edit->excised_subtree = array->root; in assoc_array_clear()
1292 edit->ops_for_excised_subtree = ops; in assoc_array_clear()
1306 pr_devel("-->%s()\n", __func__); in assoc_array_rcu_cleanup()
1308 if (edit->dead_leaf) in assoc_array_rcu_cleanup()
1309 edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf)); in assoc_array_rcu_cleanup()
1310 for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++) in assoc_array_rcu_cleanup()
1311 if (edit->excised_meta[i]) in assoc_array_rcu_cleanup()
1312 kfree(assoc_array_ptr_to_node(edit->excised_meta[i])); in assoc_array_rcu_cleanup()
1314 if (edit->excised_subtree) { in assoc_array_rcu_cleanup()
1315 BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree)); in assoc_array_rcu_cleanup()
1316 if (assoc_array_ptr_is_node(edit->excised_subtree)) { in assoc_array_rcu_cleanup()
1318 assoc_array_ptr_to_node(edit->excised_subtree); in assoc_array_rcu_cleanup()
1319 n->back_pointer = NULL; in assoc_array_rcu_cleanup()
1322 assoc_array_ptr_to_shortcut(edit->excised_subtree); in assoc_array_rcu_cleanup()
1323 s->back_pointer = NULL; in assoc_array_rcu_cleanup()
1325 assoc_array_destroy_subtree(edit->excised_subtree, in assoc_array_rcu_cleanup()
1326 edit->ops_for_excised_subtree); in assoc_array_rcu_cleanup()
1333 * assoc_array_apply_edit - Apply an edit script to an associative array
1341 * destruction after an RCU grace period to permit those doing read-only
1352 pr_devel("-->%s()\n", __func__); in assoc_array_apply_edit()
1355 if (edit->leaf_p) in assoc_array_apply_edit()
1356 *edit->leaf_p = edit->leaf; in assoc_array_apply_edit()
1359 for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++) in assoc_array_apply_edit()
1360 if (edit->set_parent_slot[i].p) in assoc_array_apply_edit()
1361 *edit->set_parent_slot[i].p = edit->set_parent_slot[i].to; in assoc_array_apply_edit()
1364 for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++) in assoc_array_apply_edit()
1365 if (edit->set_backpointers[i]) in assoc_array_apply_edit()
1366 *edit->set_backpointers[i] = edit->set_backpointers_to; in assoc_array_apply_edit()
1369 for (i = 0; i < ARRAY_SIZE(edit->set); i++) in assoc_array_apply_edit()
1370 if (edit->set[i].ptr) in assoc_array_apply_edit()
1371 *edit->set[i].ptr = edit->set[i].to; in assoc_array_apply_edit()
1373 if (edit->array->root == NULL) { in assoc_array_apply_edit()
1374 edit->array->nr_leaves_on_tree = 0; in assoc_array_apply_edit()
1375 } else if (edit->adjust_count_on) { in assoc_array_apply_edit()
1376 node = edit->adjust_count_on; in assoc_array_apply_edit()
1378 node->nr_leaves_on_branch += edit->adjust_count_by; in assoc_array_apply_edit()
1380 ptr = node->back_pointer; in assoc_array_apply_edit()
1385 ptr = shortcut->back_pointer; in assoc_array_apply_edit()
1393 edit->array->nr_leaves_on_tree += edit->adjust_count_by; in assoc_array_apply_edit()
1396 call_rcu(&edit->rcu, assoc_array_rcu_cleanup); in assoc_array_apply_edit()
1400 * assoc_array_cancel_edit - Discard an edit script.
1414 pr_devel("-->%s()\n", __func__); in assoc_array_cancel_edit()
1417 for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) { in assoc_array_cancel_edit()
1418 ptr = edit->new_meta[i]; in assoc_array_cancel_edit()
1430 * assoc_array_gc - Garbage collect an associative array.
1444 * This function returns 0 if successful or -ENOMEM if out of memory. In the
1461 struct assoc_array_ptr *cursor, *ptr; in assoc_array_gc() local
1467 pr_devel("-->%s()\n", __func__); in assoc_array_gc()
1469 if (!array->root) in assoc_array_gc()
1474 return -ENOMEM; in assoc_array_gc()
1475 edit->array = array; in assoc_array_gc()
1476 edit->ops = ops; in assoc_array_gc()
1477 edit->ops_for_excised_subtree = ops; in assoc_array_gc()
1478 edit->set[0].ptr = &array->root; in assoc_array_gc()
1479 edit->excised_subtree = array->root; in assoc_array_gc()
1483 cursor = array->root; in assoc_array_gc()
1487 * advance the target cursor. in assoc_array_gc()
1489 if (assoc_array_ptr_is_shortcut(cursor)) { in assoc_array_gc()
1490 shortcut = assoc_array_ptr_to_shortcut(cursor); in assoc_array_gc()
1491 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE); in assoc_array_gc()
1497 pr_devel("dup shortcut %p -> %p\n", shortcut, new_s); in assoc_array_gc()
1499 new_s->back_pointer = new_parent; in assoc_array_gc()
1500 new_s->parent_slot = shortcut->parent_slot; in assoc_array_gc()
1502 new_ptr_pp = &new_s->next_node; in assoc_array_gc()
1503 cursor = shortcut->next_node; in assoc_array_gc()
1507 node = assoc_array_ptr_to_node(cursor); in assoc_array_gc()
1511 pr_devel("dup node %p -> %p\n", node, new_n); in assoc_array_gc()
1512 new_n->back_pointer = new_parent; in assoc_array_gc()
1513 new_n->parent_slot = node->parent_slot; in assoc_array_gc()
1521 ptr = node->slots[slot]; in assoc_array_gc()
1531 new_n->slots[slot] = ptr; in assoc_array_gc()
1535 new_ptr_pp = &new_n->slots[slot]; in assoc_array_gc()
1536 cursor = ptr; in assoc_array_gc()
1541 pr_devel("-- compress node %p --\n", new_n); in assoc_array_gc()
1546 new_n->nr_leaves_on_branch = 0; in assoc_array_gc()
1549 ptr = new_n->slots[slot]; in assoc_array_gc()
1553 new_n->nr_leaves_on_branch++; in assoc_array_gc()
1555 pr_devel("free=%d, leaves=%lu\n", nr_free, new_n->nr_leaves_on_branch); in assoc_array_gc()
1564 ptr = new_n->slots[slot]; in assoc_array_gc()
1571 ptr = s->next_node; in assoc_array_gc()
1575 new_n->nr_leaves_on_branch += child->nr_leaves_on_branch; in assoc_array_gc()
1577 if (child->nr_leaves_on_branch <= nr_free + 1) { in assoc_array_gc()
1580 slot, child->nr_leaves_on_branch, nr_free + 1, in assoc_array_gc()
1588 new_n->slots[slot] = NULL; in assoc_array_gc()
1593 struct assoc_array_ptr *p = child->slots[i]; in assoc_array_gc()
1597 while (new_n->slots[next_slot]) in assoc_array_gc()
1600 new_n->slots[next_slot++] = p; in assoc_array_gc()
1601 nr_free--; in assoc_array_gc()
1606 slot, child->nr_leaves_on_branch, nr_free + 1, in assoc_array_gc()
1612 if (retained && new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) { in assoc_array_gc()
1616 pr_devel("after: %lu\n", new_n->nr_leaves_on_branch); in assoc_array_gc()
1618 nr_leaves_on_tree = new_n->nr_leaves_on_branch; in assoc_array_gc()
1621 if (nr_free == ASSOC_ARRAY_FAN_OUT - 1) { in assoc_array_gc()
1623 if ((ptr = new_n->slots[slot])) in assoc_array_gc()
1630 new_parent = new_n->back_pointer; in assoc_array_gc()
1631 slot = new_n->parent_slot; in assoc_array_gc()
1634 new_s->back_pointer = NULL; in assoc_array_gc()
1635 new_s->parent_slot = 0; in assoc_array_gc()
1647 new_parent = new_s->back_pointer = s->back_pointer; in assoc_array_gc()
1648 slot = new_s->parent_slot = s->parent_slot; in assoc_array_gc()
1651 new_s->back_pointer = NULL; in assoc_array_gc()
1652 new_s->parent_slot = 0; in assoc_array_gc()
1658 new_s->back_pointer = new_parent; in assoc_array_gc()
1659 new_s->parent_slot = slot; in assoc_array_gc()
1661 new_n->slots[slot] = ptr; in assoc_array_gc()
1669 ptr = new_n->back_pointer; in assoc_array_gc()
1675 new_parent = new_s->back_pointer; in assoc_array_gc()
1676 slot = new_s->parent_slot; in assoc_array_gc()
1678 if (new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) { in assoc_array_gc()
1682 new_n->back_pointer = new_parent; in assoc_array_gc()
1683 new_n->parent_slot = slot; in assoc_array_gc()
1691 n->slots[slot] = assoc_array_node_to_ptr(new_n); in assoc_array_gc()
1699 ptr = node->back_pointer; in assoc_array_gc()
1702 slot = shortcut->parent_slot; in assoc_array_gc()
1703 cursor = shortcut->back_pointer; in assoc_array_gc()
1704 if (!cursor) in assoc_array_gc()
1707 slot = node->parent_slot; in assoc_array_gc()
1708 cursor = ptr; in assoc_array_gc()
1710 BUG_ON(!cursor); in assoc_array_gc()
1711 node = assoc_array_ptr_to_node(cursor); in assoc_array_gc()
1716 edit->set[0].to = new_root; in assoc_array_gc()
1718 array->nr_leaves_on_tree = nr_leaves_on_tree; in assoc_array_gc()
1723 assoc_array_destroy_subtree(new_root, edit->ops); in assoc_array_gc()
1725 return -ENOMEM; in assoc_array_gc()