Lines Matching defs:edit
451 static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit)
461 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
462 edit->leaf_p = &new_n0->slots[0];
463 edit->adjust_count_on = new_n0;
464 edit->set[0].ptr = &edit->array->root;
465 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
474 static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
490 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot;
514 edit->leaf_p = &node->slots[i];
515 edit->dead_leaf = node->slots[i];
526 edit->leaf_p = &node->slots[free_slot];
527 edit->adjust_count_on = node;
542 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
546 edit->new_meta[1] = assoc_array_node_to_ptr(new_n1);
554 edit->segment_cache[i] = 0xff;
561 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
571 base_seg = edit->segment_cache[0];
573 dissimilarity |= edit->segment_cache[i] ^ base_seg;
581 if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)
613 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
632 slot = edit->segment_cache[i];
635 if (edit->segment_cache[j] == slot)
661 if (edit->segment_cache[i] == slot) {
674 if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) {
678 edit->leaf_p = &new_n0->slots[free_slot];
679 edit->adjust_count_on = new_n0;
681 edit->leaf_p = &new_n1->slots[next_slot++];
682 edit->adjust_count_on = new_n1;
687 edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0);
689 if (edit->segment_cache[i] == 0xff) {
694 edit->set_backpointers[i] = &side->back_pointer;
697 edit->set_backpointers[i] = &shortcut->back_pointer;
704 edit->set[0].ptr = &edit->array->root;
706 edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot];
708 edit->set[0].ptr = &assoc_array_ptr_to_shortcut(ptr)->next_node;
709 edit->excised_meta[0] = assoc_array_node_to_ptr(node);
748 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0);
750 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
781 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
786 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK;
793 static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
825 edit->set[0].ptr = &edit->array->root;
828 edit->set[0].ptr = &node->slots[shortcut->parent_slot];
833 edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);
839 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
840 edit->adjust_count_on = new_n0;
856 edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);
857 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
874 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
906 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);
918 edit->set[1].ptr = &side->back_pointer;
919 edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);
929 edit->set_parent_slot[0].p = &side->parent_slot;
930 edit->set_parent_slot[0].to = sc_slot;
931 edit->set[1].ptr = &side->back_pointer;
932 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
937 edit->leaf_p = &new_n0->slots[1];
939 edit->leaf_p = &new_n0->slots[0];
942 return edit;
953 * object in an associative array. This results in an edit script that can
956 * The function returns a pointer to an edit script or -ENOMEM.
970 struct assoc_array_edit *edit;
981 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
982 if (!edit)
984 edit->array = array;
985 edit->ops = ops;
986 edit->leaf = assoc_array_leaf_to_ptr(object);
987 edit->adjust_count_by = 1;
992 if (!assoc_array_insert_in_empty_tree(edit))
994 return edit;
1001 if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,
1004 return edit;
1010 if (!assoc_array_insert_mid_shortcut(edit, ops, &result))
1012 return edit;
1018 assoc_array_cancel_edit(edit);
1023 * assoc_array_insert_set_object - Set the new object pointer in an edit script
1024 * @edit: The edit script to modify.
1027 * Change the object to be inserted in an edit script. The object pointed to
1031 void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)
1034 edit->leaf = assoc_array_leaf_to_ptr(object);
1067 * associative array. This results in an edit script that can either be
1070 * The function returns a pointer to an edit script if the object was found,
1086 struct assoc_array_edit *edit;
1093 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1094 if (!edit)
1096 edit->array = array;
1097 edit->ops = ops;
1098 edit->adjust_count_by = -1;
1120 assoc_array_cancel_edit(edit);
1131 edit->dead_leaf = node->slots[slot];
1132 edit->set[0].ptr = &node->slots[slot];
1133 edit->set[0].to = NULL;
1134 edit->adjust_count_on = node;
1140 edit->set[1].ptr = &array->root;
1141 edit->set[1].to = NULL;
1142 edit->adjust_count_on = NULL;
1143 edit->excised_subtree = array->root;
1145 return edit;
1213 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
1218 edit->adjust_count_on = new_n0;
1221 collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf);
1231 edit->set[1].ptr = &array->root;
1237 edit->set[1].ptr = &p->slots[node->parent_slot];
1241 edit->set[1].ptr = &s->next_node;
1243 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
1244 edit->excised_subtree = assoc_array_node_to_ptr(node);
1248 return edit;
1253 assoc_array_cancel_edit(edit);
1263 * from an associative array. This results in an edit script that can either
1266 * The function returns a pointer to an edit script if there are objects to be
1278 struct assoc_array_edit *edit;
1285 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1286 if (!edit)
1288 edit->array = array;
1289 edit->ops = ops;
1290 edit->set[1].ptr = &array->root;
1291 edit->set[1].to = NULL;
1292 edit->excised_subtree = array->root;
1293 edit->ops_for_excised_subtree = ops;
1295 return edit;
1299 * Handle the deferred destruction after an applied edit.
1303 struct assoc_array_edit *edit =
1309 if (edit->dead_leaf)
1310 edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf));
1311 for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++)
1312 if (edit->excised_meta[i])
1313 kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));
1315 if (edit->excised_subtree) {
1316 BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));
1317 if (assoc_array_ptr_is_node(edit->excised_subtree)) {
1319 assoc_array_ptr_to_node(edit->excised_subtree);
1323 assoc_array_ptr_to_shortcut(edit->excised_subtree);
1326 assoc_array_destroy_subtree(edit->excised_subtree,
1327 edit->ops_for_excised_subtree);
1330 kfree(edit);
1334 * assoc_array_apply_edit - Apply an edit script to an associative array
1335 * @edit: The script to apply.
1337 * Apply an edit script to an associative array to effect an insertion,
1338 * deletion or clearance. As the edit script includes preallocated memory,
1341 * The edit script, dead objects and dead metadata will be scheduled for
1344 * the edit is taking place.
1346 void assoc_array_apply_edit(struct assoc_array_edit *edit)
1356 if (edit->leaf_p)
1357 *edit->leaf_p = edit->leaf;
1360 for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++)
1361 if (edit->set_parent_slot[i].p)
1362 *edit->set_parent_slot[i].p = edit->set_parent_slot[i].to;
1365 for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++)
1366 if (edit->set_backpointers[i])
1367 *edit->set_backpointers[i] = edit->set_backpointers_to;
1370 for (i = 0; i < ARRAY_SIZE(edit->set); i++)
1371 if (edit->set[i].ptr)
1372 *edit->set[i].ptr = edit->set[i].to;
1374 if (edit->array->root == NULL) {
1375 edit->array->nr_leaves_on_tree = 0;
1376 } else if (edit->adjust_count_on) {
1377 node = edit->adjust_count_on;
1379 node->nr_leaves_on_branch += edit->adjust_count_by;
1394 edit->array->nr_leaves_on_tree += edit->adjust_count_by;
1397 call_rcu(&edit->rcu, assoc_array_rcu_cleanup);
1401 * assoc_array_cancel_edit - Discard an edit script.
1402 * @edit: The script to discard.
1404 * Free an edit script and all the preallocated data it holds without making
1410 void assoc_array_cancel_edit(struct assoc_array_edit *edit)
1418 for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {
1419 ptr = edit->new_meta[i];
1427 kfree(edit);
1461 struct assoc_array_edit *edit;
1473 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1474 if (!edit)
1476 edit->array = array;
1477 edit->ops = ops;
1478 edit->ops_for_excised_subtree = ops;
1479 edit->set[0].ptr = &array->root;
1480 edit->excised_subtree = array->root;
1718 edit->set[0].to = new_root;
1719 assoc_array_apply_edit(edit);
1725 assoc_array_destroy_subtree(new_root, edit->ops);
1726 kfree(edit);