455 static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit)  in assoc_array_insert_in_empty_tree()  argument
465 	edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_in_empty_tree()
466 	edit->leaf_p = &new_n0->slots[0];  in assoc_array_insert_in_empty_tree()
467 	edit->adjust_count_on = new_n0;  in assoc_array_insert_in_empty_tree()
468 	edit->set[0].ptr = &edit->array->root;  in assoc_array_insert_in_empty_tree()
469 	edit->set[0].to = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_in_empty_tree()
478 static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,  in assoc_array_insert_into_terminal_node()  argument
494 	edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot;  in assoc_array_insert_into_terminal_node()
518 			edit->leaf_p = &node->slots[i];  in assoc_array_insert_into_terminal_node()
519 			edit->dead_leaf = node->slots[i];  in assoc_array_insert_into_terminal_node()
530 		edit->leaf_p = &node->slots[free_slot];  in assoc_array_insert_into_terminal_node()
531 		edit->adjust_count_on = node;  in assoc_array_insert_into_terminal_node()
546 	edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_into_terminal_node()
550 	edit->new_meta[1] = assoc_array_node_to_ptr(new_n1);  in assoc_array_insert_into_terminal_node()
558 			edit->segment_cache[i] = 0xff;  in assoc_array_insert_into_terminal_node()
565 		edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;  in assoc_array_insert_into_terminal_node()
575 	base_seg = edit->segment_cache[0];  in assoc_array_insert_into_terminal_node()
577 		dissimilarity |= edit->segment_cache[i] ^ base_seg;  in assoc_array_insert_into_terminal_node()
585 		if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)  in assoc_array_insert_into_terminal_node()
617 	edit->set[0].to = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_into_terminal_node()
636 		slot = edit->segment_cache[i];  in assoc_array_insert_into_terminal_node()
639 				if (edit->segment_cache[j] == slot)  in assoc_array_insert_into_terminal_node()
665 		if (edit->segment_cache[i] == slot) {  in assoc_array_insert_into_terminal_node()
678 	if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) {  in assoc_array_insert_into_terminal_node()
682 		edit->leaf_p = &new_n0->slots[free_slot];  in assoc_array_insert_into_terminal_node()
683 		edit->adjust_count_on = new_n0;  in assoc_array_insert_into_terminal_node()
685 		edit->leaf_p = &new_n1->slots[next_slot++];  in assoc_array_insert_into_terminal_node()
686 		edit->adjust_count_on = new_n1;  in assoc_array_insert_into_terminal_node()
691 	edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_into_terminal_node()
693 		if (edit->segment_cache[i] == 0xff) {  in assoc_array_insert_into_terminal_node()
698 				edit->set_backpointers[i] = &side->back_pointer;  in assoc_array_insert_into_terminal_node()
701 				edit->set_backpointers[i] = &shortcut->back_pointer;  in assoc_array_insert_into_terminal_node()
708 		edit->set[0].ptr = &edit->array->root;  in assoc_array_insert_into_terminal_node()
710 		edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot];  in assoc_array_insert_into_terminal_node()
712 		edit->set[0].ptr = &assoc_array_ptr_to_shortcut(ptr)->next_node;  in assoc_array_insert_into_terminal_node()
713 	edit->excised_meta[0] = assoc_array_node_to_ptr(node);  in assoc_array_insert_into_terminal_node()
752 	edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0);  in assoc_array_insert_into_terminal_node()
754 	edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);  in assoc_array_insert_into_terminal_node()
783 		edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;  in assoc_array_insert_into_terminal_node()
788 	edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK;  in assoc_array_insert_into_terminal_node()
795 static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,  in assoc_array_insert_mid_shortcut()  argument
827 		edit->set[0].ptr = &edit->array->root;  in assoc_array_insert_mid_shortcut()
830 		edit->set[0].ptr = &node->slots[shortcut->parent_slot];  in assoc_array_insert_mid_shortcut()
835 	edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);  in assoc_array_insert_mid_shortcut()
841 	edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_mid_shortcut()
842 	edit->adjust_count_on = new_n0;  in assoc_array_insert_mid_shortcut()
858 		edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);  in assoc_array_insert_mid_shortcut()
859 		edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);  in assoc_array_insert_mid_shortcut()
876 		edit->set[0].to = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_mid_shortcut()
908 		edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);  in assoc_array_insert_mid_shortcut()
920 		edit->set[1].ptr = &side->back_pointer;  in assoc_array_insert_mid_shortcut()
921 		edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);  in assoc_array_insert_mid_shortcut()
931 		edit->set_parent_slot[0].p = &side->parent_slot;  in assoc_array_insert_mid_shortcut()
932 		edit->set_parent_slot[0].to = sc_slot;  in assoc_array_insert_mid_shortcut()
933 		edit->set[1].ptr = &side->back_pointer;  in assoc_array_insert_mid_shortcut()
934 		edit->set[1].to = assoc_array_node_to_ptr(new_n0);  in assoc_array_insert_mid_shortcut()
939 		edit->leaf_p = &new_n0->slots[1];  in assoc_array_insert_mid_shortcut()
941 		edit->leaf_p = &new_n0->slots[0];  in assoc_array_insert_mid_shortcut()
944 	return edit;  in assoc_array_insert_mid_shortcut()
972 	struct assoc_array_edit *edit;  in assoc_array_insert()  local
983 	edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);  in assoc_array_insert()
984 	if (!edit)  in assoc_array_insert()
986 	edit->array = array;  in assoc_array_insert()
987 	edit->ops = ops;  in assoc_array_insert()
988 	edit->leaf = assoc_array_leaf_to_ptr(object);  in assoc_array_insert()
989 	edit->adjust_count_by = 1;  in assoc_array_insert()
994 		if (!assoc_array_insert_in_empty_tree(edit))  in assoc_array_insert()
996 		return edit;  in assoc_array_insert()
1003 		if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,  in assoc_array_insert()
1006 		return edit;  in assoc_array_insert()
1012 		if (!assoc_array_insert_mid_shortcut(edit, ops, &result))  in assoc_array_insert()
1014 		return edit;  in assoc_array_insert()
1020 	assoc_array_cancel_edit(edit);  in assoc_array_insert()
1033 void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)  in assoc_array_insert_set_object()  argument
1036 	edit->leaf = assoc_array_leaf_to_ptr(object);  in assoc_array_insert_set_object()
1088 	struct assoc_array_edit *edit;  in assoc_array_delete()  local
1095 	edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);  in assoc_array_delete()
1096 	if (!edit)  in assoc_array_delete()
1098 	edit->array = array;  in assoc_array_delete()
1099 	edit->ops = ops;  in assoc_array_delete()
1100 	edit->adjust_count_by = -1;  in assoc_array_delete()
1121 		assoc_array_cancel_edit(edit);  in assoc_array_delete()
1132 	edit->dead_leaf = node->slots[slot];  in assoc_array_delete()
1133 	edit->set[0].ptr = &node->slots[slot];  in assoc_array_delete()
1134 	edit->set[0].to = NULL;  in assoc_array_delete()
1135 	edit->adjust_count_on = node;  in assoc_array_delete()
1141 		edit->set[1].ptr = &array->root;  in assoc_array_delete()
1142 		edit->set[1].to = NULL;  in assoc_array_delete()
1143 		edit->adjust_count_on = NULL;  in assoc_array_delete()
1144 		edit->excised_subtree = array->root;  in assoc_array_delete()
1146 		return edit;  in assoc_array_delete()
1214 			edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);  in assoc_array_delete()
1219 			edit->adjust_count_on = new_n0;  in assoc_array_delete()
1222 			collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf);  in assoc_array_delete()
1232 				edit->set[1].ptr = &array->root;  in assoc_array_delete()
1238 				edit->set[1].ptr = &p->slots[node->parent_slot];  in assoc_array_delete()
1242 				edit->set[1].ptr = &s->next_node;  in assoc_array_delete()
1244 			edit->set[1].to = assoc_array_node_to_ptr(new_n0);  in assoc_array_delete()
1245 			edit->excised_subtree = assoc_array_node_to_ptr(node);  in assoc_array_delete()
1249 	return edit;  in assoc_array_delete()
1254 	assoc_array_cancel_edit(edit);  in assoc_array_delete()
1279 	struct assoc_array_edit *edit;  in assoc_array_clear()  local
1286 	edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);  in assoc_array_clear()
1287 	if (!edit)  in assoc_array_clear()
1289 	edit->array = array;  in assoc_array_clear()
1290 	edit->ops = ops;  in assoc_array_clear()
1291 	edit->set[1].ptr = &array->root;  in assoc_array_clear()
1292 	edit->set[1].to = NULL;  in assoc_array_clear()
1293 	edit->excised_subtree = array->root;  in assoc_array_clear()
1294 	edit->ops_for_excised_subtree = ops;  in assoc_array_clear()
1296 	return edit;  in assoc_array_clear()
1304 	struct assoc_array_edit *edit =  in assoc_array_rcu_cleanup()  local
1310 	if (edit->dead_leaf)  in assoc_array_rcu_cleanup()
1311 		edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf));  in assoc_array_rcu_cleanup()
1312 	for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++)  in assoc_array_rcu_cleanup()
1313 		if (edit->excised_meta[i])  in assoc_array_rcu_cleanup()
1314 			kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));  in assoc_array_rcu_cleanup()
1316 	if (edit->excised_subtree) {  in assoc_array_rcu_cleanup()
1317 		BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));  in assoc_array_rcu_cleanup()
1318 		if (assoc_array_ptr_is_node(edit->excised_subtree)) {  in assoc_array_rcu_cleanup()
1320 				assoc_array_ptr_to_node(edit->excised_subtree);  in assoc_array_rcu_cleanup()
1324 				assoc_array_ptr_to_shortcut(edit->excised_subtree);  in assoc_array_rcu_cleanup()
1327 		assoc_array_destroy_subtree(edit->excised_subtree,  in assoc_array_rcu_cleanup()
1328 					    edit->ops_for_excised_subtree);  in assoc_array_rcu_cleanup()
1331 	kfree(edit);  in assoc_array_rcu_cleanup()
1347 void assoc_array_apply_edit(struct assoc_array_edit *edit)  in assoc_array_apply_edit()  argument
1357 	if (edit->leaf_p)  in assoc_array_apply_edit()
1358 		*edit->leaf_p = edit->leaf;  in assoc_array_apply_edit()
1361 	for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++)  in assoc_array_apply_edit()
1362 		if (edit->set_parent_slot[i].p)  in assoc_array_apply_edit()
1363 			*edit->set_parent_slot[i].p = edit->set_parent_slot[i].to;  in assoc_array_apply_edit()
1366 	for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++)  in assoc_array_apply_edit()
1367 		if (edit->set_backpointers[i])  in assoc_array_apply_edit()
1368 			*edit->set_backpointers[i] = edit->set_backpointers_to;  in assoc_array_apply_edit()
1371 	for (i = 0; i < ARRAY_SIZE(edit->set); i++)  in assoc_array_apply_edit()
1372 		if (edit->set[i].ptr)  in assoc_array_apply_edit()
1373 			*edit->set[i].ptr = edit->set[i].to;  in assoc_array_apply_edit()
1375 	if (edit->array->root == NULL) {  in assoc_array_apply_edit()
1376 		edit->array->nr_leaves_on_tree = 0;  in assoc_array_apply_edit()
1377 	} else if (edit->adjust_count_on) {  in assoc_array_apply_edit()
1378 		node = edit->adjust_count_on;  in assoc_array_apply_edit()
1380 			node->nr_leaves_on_branch += edit->adjust_count_by;  in assoc_array_apply_edit()
1395 		edit->array->nr_leaves_on_tree += edit->adjust_count_by;  in assoc_array_apply_edit()
1398 	call_rcu(&edit->rcu, assoc_array_rcu_cleanup);  in assoc_array_apply_edit()
1411 void assoc_array_cancel_edit(struct assoc_array_edit *edit)  in assoc_array_cancel_edit()  argument
1419 	for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {  in assoc_array_cancel_edit()
1420 		ptr = edit->new_meta[i];  in assoc_array_cancel_edit()
1428 	kfree(edit);  in assoc_array_cancel_edit()
1462 	struct assoc_array_edit *edit;  in assoc_array_gc()  local
1473 	edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);  in assoc_array_gc()
1474 	if (!edit)  in assoc_array_gc()
1476 	edit->array = array;  in assoc_array_gc()
1477 	edit->ops = ops;  in assoc_array_gc()
1478 	edit->ops_for_excised_subtree = ops;  in assoc_array_gc()
1479 	edit->set[0].ptr = &array->root;  in assoc_array_gc()
1480 	edit->excised_subtree = array->root;  in assoc_array_gc()
1711 	edit->set[0].to = new_root;  in assoc_array_gc()
1712 	assoc_array_apply_edit(edit);  in assoc_array_gc()
1718 	assoc_array_destroy_subtree(new_root, edit->ops);  in assoc_array_gc()
1719 	kfree(edit);  in assoc_array_gc()