468 static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit)  in assoc_array_insert_in_empty_tree()  argument
478 	edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_in_empty_tree()
479 	edit->leaf_p = &new_n0->slots[0];  in assoc_array_insert_in_empty_tree()
480 	edit->adjust_count_on = new_n0;  in assoc_array_insert_in_empty_tree()
481 	edit->set[0].ptr = &edit->array->root;  in assoc_array_insert_in_empty_tree()
482 	edit->set[0].to = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_in_empty_tree()
491 static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,  in assoc_array_insert_into_terminal_node()  argument
507 	edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot;  in assoc_array_insert_into_terminal_node()
531 			edit->leaf_p = &node->slots[i];  in assoc_array_insert_into_terminal_node()
532 			edit->dead_leaf = node->slots[i];  in assoc_array_insert_into_terminal_node()
543 		edit->leaf_p = &node->slots[free_slot];  in assoc_array_insert_into_terminal_node()
544 		edit->adjust_count_on = node;  in assoc_array_insert_into_terminal_node()
559 	edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_into_terminal_node()
563 	edit->new_meta[1] = assoc_array_node_to_ptr(new_n1);  in assoc_array_insert_into_terminal_node()
571 			edit->segment_cache[i] = 0xff;  in assoc_array_insert_into_terminal_node()
578 		edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;  in assoc_array_insert_into_terminal_node()
588 	base_seg = edit->segment_cache[0];  in assoc_array_insert_into_terminal_node()
590 		dissimilarity |= edit->segment_cache[i] ^ base_seg;  in assoc_array_insert_into_terminal_node()
598 		if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)  in assoc_array_insert_into_terminal_node()
620 	edit->set[0].to = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_into_terminal_node()
639 		slot = edit->segment_cache[i];  in assoc_array_insert_into_terminal_node()
642 				if (edit->segment_cache[j] == slot)  in assoc_array_insert_into_terminal_node()
668 		if (edit->segment_cache[i] == slot) {  in assoc_array_insert_into_terminal_node()
681 	if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) {  in assoc_array_insert_into_terminal_node()
685 		edit->leaf_p = &new_n0->slots[free_slot];  in assoc_array_insert_into_terminal_node()
686 		edit->adjust_count_on = new_n0;  in assoc_array_insert_into_terminal_node()
688 		edit->leaf_p = &new_n1->slots[next_slot++];  in assoc_array_insert_into_terminal_node()
689 		edit->adjust_count_on = new_n1;  in assoc_array_insert_into_terminal_node()
694 	edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_into_terminal_node()
696 		if (edit->segment_cache[i] == 0xff) {  in assoc_array_insert_into_terminal_node()
701 				edit->set_backpointers[i] = &side->back_pointer;  in assoc_array_insert_into_terminal_node()
704 				edit->set_backpointers[i] = &shortcut->back_pointer;  in assoc_array_insert_into_terminal_node()
711 		edit->set[0].ptr = &edit->array->root;  in assoc_array_insert_into_terminal_node()
713 		edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot];  in assoc_array_insert_into_terminal_node()
715 		edit->set[0].ptr = &assoc_array_ptr_to_shortcut(ptr)->next_node;  in assoc_array_insert_into_terminal_node()
716 	edit->excised_meta[0] = assoc_array_node_to_ptr(node);  in assoc_array_insert_into_terminal_node()
731 	new_n1->parent_slot = edit->segment_cache[0];  in assoc_array_insert_into_terminal_node()
733 	edit->adjust_count_on = new_n0;  in assoc_array_insert_into_terminal_node()
738 	new_n0->slots[edit->segment_cache[0]] = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_into_terminal_node()
739 	edit->leaf_p = &new_n0->slots[edit->segment_cache[ASSOC_ARRAY_FAN_OUT]];  in assoc_array_insert_into_terminal_node()
741 	edit->set[0].ptr = &assoc_array_ptr_to_node(node->back_pointer)->slots[node->parent_slot];  in assoc_array_insert_into_terminal_node()
742 	edit->set[0].to = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_into_terminal_node()
743 	edit->excised_meta[0] = assoc_array_node_to_ptr(node);  in assoc_array_insert_into_terminal_node()
782 	edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0);  in assoc_array_insert_into_terminal_node()
784 	edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);  in assoc_array_insert_into_terminal_node()
813 		edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;  in assoc_array_insert_into_terminal_node()
818 	edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK;  in assoc_array_insert_into_terminal_node()
825 static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,  in assoc_array_insert_mid_shortcut()  argument
857 		edit->set[0].ptr = &edit->array->root;  in assoc_array_insert_mid_shortcut()
860 		edit->set[0].ptr = &node->slots[shortcut->parent_slot];  in assoc_array_insert_mid_shortcut()
865 	edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);  in assoc_array_insert_mid_shortcut()
871 	edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_mid_shortcut()
872 	edit->adjust_count_on = new_n0;  in assoc_array_insert_mid_shortcut()
888 		edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);  in assoc_array_insert_mid_shortcut()
889 		edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);  in assoc_array_insert_mid_shortcut()
906 		edit->set[0].to = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_mid_shortcut()
938 		edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);  in assoc_array_insert_mid_shortcut()
950 		edit->set[1].ptr = &side->back_pointer;  in assoc_array_insert_mid_shortcut()
951 		edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);  in assoc_array_insert_mid_shortcut()
961 		edit->set_parent_slot[0].p = &side->parent_slot;  in assoc_array_insert_mid_shortcut()
962 		edit->set_parent_slot[0].to = sc_slot;  in assoc_array_insert_mid_shortcut()
963 		edit->set[1].ptr = &side->back_pointer;  in assoc_array_insert_mid_shortcut()
964 		edit->set[1].to = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_mid_shortcut()
969 		edit->leaf_p = &new_n0->slots[1];  in assoc_array_insert_mid_shortcut()
971 		edit->leaf_p = &new_n0->slots[0];  in assoc_array_insert_mid_shortcut()
974 	return edit;  in assoc_array_insert_mid_shortcut()
1002 	struct assoc_array_edit *edit;  in assoc_array_insert()  local
1013 	edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);  in assoc_array_insert()
1014 	if (!edit)  in assoc_array_insert()
1016 	edit->array = array;  in assoc_array_insert()
1017 	edit->ops = ops;  in assoc_array_insert()
1018 	edit->leaf = assoc_array_leaf_to_ptr(object);  in assoc_array_insert()
1019 	edit->adjust_count_by = 1;  in assoc_array_insert()
1024 		if (!assoc_array_insert_in_empty_tree(edit))  in assoc_array_insert()
1026 		return edit;  in assoc_array_insert()
1033 		if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,  in assoc_array_insert()
1036 		return edit;  in assoc_array_insert()
1042 		if (!assoc_array_insert_mid_shortcut(edit, ops, &result))  in assoc_array_insert()
1044 		return edit;  in assoc_array_insert()
1050 	assoc_array_cancel_edit(edit);  in assoc_array_insert()
1063 void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)  in assoc_array_insert_set_object()  argument
1066 	edit->leaf = assoc_array_leaf_to_ptr(object);  in assoc_array_insert_set_object()
1118 	struct assoc_array_edit *edit;  in assoc_array_delete()  local
1125 	edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);  in assoc_array_delete()
1126 	if (!edit)  in assoc_array_delete()
1128 	edit->array = array;  in assoc_array_delete()
1129 	edit->ops = ops;  in assoc_array_delete()
1130 	edit->adjust_count_by = -1;  in assoc_array_delete()
1151 		assoc_array_cancel_edit(edit);  in assoc_array_delete()
1162 	edit->dead_leaf = node->slots[slot];  in assoc_array_delete()
1163 	edit->set[0].ptr = &node->slots[slot];  in assoc_array_delete()
1164 	edit->set[0].to = NULL;  in assoc_array_delete()
1165 	edit->adjust_count_on = node;  in assoc_array_delete()
1171 		edit->set[1].ptr = &array->root;  in assoc_array_delete()
1172 		edit->set[1].to = NULL;  in assoc_array_delete()
1173 		edit->adjust_count_on = NULL;  in assoc_array_delete()
1174 		edit->excised_subtree = array->root;  in assoc_array_delete()
1176 		return edit;  in assoc_array_delete()
1244 			edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);  in assoc_array_delete()
1249 			edit->adjust_count_on = new_n0;  in assoc_array_delete()
1252 			collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf);  in assoc_array_delete()
1262 				edit->set[1].ptr = &array->root;  in assoc_array_delete()
1268 				edit->set[1].ptr = &p->slots[node->parent_slot];  in assoc_array_delete()
1272 				edit->set[1].ptr = &s->next_node;  in assoc_array_delete()
1274 			edit->set[1].to = assoc_array_node_to_ptr(new_n0);  in assoc_array_delete()
1275 			edit->excised_subtree = assoc_array_node_to_ptr(node);  in assoc_array_delete()
1279 	return edit;  in assoc_array_delete()
1284 	assoc_array_cancel_edit(edit);  in assoc_array_delete()
1309 	struct assoc_array_edit *edit;  in assoc_array_clear()  local
1316 	edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);  in assoc_array_clear()
1317 	if (!edit)  in assoc_array_clear()
1319 	edit->array = array;  in assoc_array_clear()
1320 	edit->ops = ops;  in assoc_array_clear()
1321 	edit->set[1].ptr = &array->root;  in assoc_array_clear()
1322 	edit->set[1].to = NULL;  in assoc_array_clear()
1323 	edit->excised_subtree = array->root;  in assoc_array_clear()
1324 	edit->ops_for_excised_subtree = ops;  in assoc_array_clear()
1326 	return edit;  in assoc_array_clear()
1334 	struct assoc_array_edit *edit =  in assoc_array_rcu_cleanup()  local
1340 	if (edit->dead_leaf)  in assoc_array_rcu_cleanup()
1341 		edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf));  in assoc_array_rcu_cleanup()
1342 	for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++)  in assoc_array_rcu_cleanup()
1343 		if (edit->excised_meta[i])  in assoc_array_rcu_cleanup()
1344 			kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));  in assoc_array_rcu_cleanup()
1346 	if (edit->excised_subtree) {  in assoc_array_rcu_cleanup()
1347 		BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));  in assoc_array_rcu_cleanup()
1348 		if (assoc_array_ptr_is_node(edit->excised_subtree)) {  in assoc_array_rcu_cleanup()
1350 				assoc_array_ptr_to_node(edit->excised_subtree);  in assoc_array_rcu_cleanup()
1354 				assoc_array_ptr_to_shortcut(edit->excised_subtree);  in assoc_array_rcu_cleanup()
1357 		assoc_array_destroy_subtree(edit->excised_subtree,  in assoc_array_rcu_cleanup()
1358 					    edit->ops_for_excised_subtree);  in assoc_array_rcu_cleanup()
1361 	kfree(edit);  in assoc_array_rcu_cleanup()
1377 void assoc_array_apply_edit(struct assoc_array_edit *edit)  in assoc_array_apply_edit()  argument
1387 	if (edit->leaf_p)  in assoc_array_apply_edit()
1388 		*edit->leaf_p = edit->leaf;  in assoc_array_apply_edit()
1391 	for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++)  in assoc_array_apply_edit()
1392 		if (edit->set_parent_slot[i].p)  in assoc_array_apply_edit()
1393 			*edit->set_parent_slot[i].p = edit->set_parent_slot[i].to;  in assoc_array_apply_edit()
1396 	for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++)  in assoc_array_apply_edit()
1397 		if (edit->set_backpointers[i])  in assoc_array_apply_edit()
1398 			*edit->set_backpointers[i] = edit->set_backpointers_to;  in assoc_array_apply_edit()
1401 	for (i = 0; i < ARRAY_SIZE(edit->set); i++)  in assoc_array_apply_edit()
1402 		if (edit->set[i].ptr)  in assoc_array_apply_edit()
1403 			*edit->set[i].ptr = edit->set[i].to;  in assoc_array_apply_edit()
1405 	if (edit->array->root == NULL) {  in assoc_array_apply_edit()
1406 		edit->array->nr_leaves_on_tree = 0;  in assoc_array_apply_edit()
1407 	} else if (edit->adjust_count_on) {  in assoc_array_apply_edit()
1408 		node = edit->adjust_count_on;  in assoc_array_apply_edit()
1410 			node->nr_leaves_on_branch += edit->adjust_count_by;  in assoc_array_apply_edit()
1425 		edit->array->nr_leaves_on_tree += edit->adjust_count_by;  in assoc_array_apply_edit()
1428 	call_rcu(&edit->rcu, assoc_array_rcu_cleanup);  in assoc_array_apply_edit()
1441 void assoc_array_cancel_edit(struct assoc_array_edit *edit)  in assoc_array_cancel_edit()  argument
1449 	for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {  in assoc_array_cancel_edit()
1450 		ptr = edit->new_meta[i];  in assoc_array_cancel_edit()
1458 	kfree(edit);  in assoc_array_cancel_edit()
1492 	struct assoc_array_edit *edit;  in assoc_array_gc()  local
1503 	edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);  in assoc_array_gc()
1504 	if (!edit)  in assoc_array_gc()
1506 	edit->array = array;  in assoc_array_gc()
1507 	edit->ops = ops;  in assoc_array_gc()
1508 	edit->ops_for_excised_subtree = ops;  in assoc_array_gc()
1509 	edit->set[0].ptr = &array->root;  in assoc_array_gc()
1510 	edit->excised_subtree = array->root;  in assoc_array_gc()
1741 	edit->set[0].to = new_root;  in assoc_array_gc()
1742 	assoc_array_apply_edit(edit);  in assoc_array_gc()
1748 	assoc_array_destroy_subtree(new_root, edit->ops);  in assoc_array_gc()
1749 	kfree(edit);  in assoc_array_gc()