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);
747 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0);
749 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
780 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
785 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK;
792 static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
824 edit->set[0].ptr = &edit->array->root;
827 edit->set[0].ptr = &node->slots[shortcut->parent_slot];
832 edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);
838 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
839 edit->adjust_count_on = new_n0;
855 edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);
856 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
873 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
905 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);
917 edit->set[1].ptr = &side->back_pointer;
918 edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);
928 edit->set_parent_slot[0].p = &side->parent_slot;
929 edit->set_parent_slot[0].to = sc_slot;
930 edit->set[1].ptr = &side->back_pointer;
931 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
936 edit->leaf_p = &new_n0->slots[1];
938 edit->leaf_p = &new_n0->slots[0];
941 return edit;
952 * object in an associative array. This results in an edit script that can
955 * The function returns a pointer to an edit script or -ENOMEM.
969 struct assoc_array_edit *edit;
980 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
981 if (!edit)
983 edit->array = array;
984 edit->ops = ops;
985 edit->leaf = assoc_array_leaf_to_ptr(object);
986 edit->adjust_count_by = 1;
991 if (!assoc_array_insert_in_empty_tree(edit))
993 return edit;
1000 if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,
1003 return edit;
1009 if (!assoc_array_insert_mid_shortcut(edit, ops, &result))
1011 return edit;
1017 assoc_array_cancel_edit(edit);
1022 * assoc_array_insert_set_object - Set the new object pointer in an edit script
1023 * @edit: The edit script to modify.
1026 * Change the object to be inserted in an edit script. The object pointed to
1030 void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)
1033 edit->leaf = assoc_array_leaf_to_ptr(object);
1066 * associative array. This results in an edit script that can either be
1069 * The function returns a pointer to an edit script if the object was found,
1085 struct assoc_array_edit *edit;
1092 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1093 if (!edit)
1095 edit->array = array;
1096 edit->ops = ops;
1097 edit->adjust_count_by = -1;
1119 assoc_array_cancel_edit(edit);
1130 edit->dead_leaf = node->slots[slot];
1131 edit->set[0].ptr = &node->slots[slot];
1132 edit->set[0].to = NULL;
1133 edit->adjust_count_on = node;
1139 edit->set[1].ptr = &array->root;
1140 edit->set[1].to = NULL;
1141 edit->adjust_count_on = NULL;
1142 edit->excised_subtree = array->root;
1144 return edit;
1212 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
1217 edit->adjust_count_on = new_n0;
1220 collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf);
1230 edit->set[1].ptr = &array->root;
1236 edit->set[1].ptr = &p->slots[node->parent_slot];
1240 edit->set[1].ptr = &s->next_node;
1242 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
1243 edit->excised_subtree = assoc_array_node_to_ptr(node);
1247 return edit;
1252 assoc_array_cancel_edit(edit);
1262 * from an associative array. This results in an edit script that can either
1265 * The function returns a pointer to an edit script if there are objects to be
1277 struct assoc_array_edit *edit;
1284 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1285 if (!edit)
1287 edit->array = array;
1288 edit->ops = ops;
1289 edit->set[1].ptr = &array->root;
1290 edit->set[1].to = NULL;
1291 edit->excised_subtree = array->root;
1292 edit->ops_for_excised_subtree = ops;
1294 return edit;
1298 * Handle the deferred destruction after an applied edit.
1302 struct assoc_array_edit *edit =
1308 if (edit->dead_leaf)
1309 edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf));
1310 for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++)
1311 if (edit->excised_meta[i])
1312 kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));
1314 if (edit->excised_subtree) {
1315 BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));
1316 if (assoc_array_ptr_is_node(edit->excised_subtree)) {
1318 assoc_array_ptr_to_node(edit->excised_subtree);
1322 assoc_array_ptr_to_shortcut(edit->excised_subtree);
1325 assoc_array_destroy_subtree(edit->excised_subtree,
1326 edit->ops_for_excised_subtree);
1329 kfree(edit);
1333 * assoc_array_apply_edit - Apply an edit script to an associative array
1334 * @edit: The script to apply.
1336 * Apply an edit script to an associative array to effect an insertion,
1337 * deletion or clearance. As the edit script includes preallocated memory,
1340 * The edit script, dead objects and dead metadata will be scheduled for
1343 * the edit is taking place.
1345 void assoc_array_apply_edit(struct assoc_array_edit *edit)
1355 if (edit->leaf_p)
1356 *edit->leaf_p = edit->leaf;
1359 for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++)
1360 if (edit->set_parent_slot[i].p)
1361 *edit->set_parent_slot[i].p = edit->set_parent_slot[i].to;
1364 for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++)
1365 if (edit->set_backpointers[i])
1366 *edit->set_backpointers[i] = edit->set_backpointers_to;
1369 for (i = 0; i < ARRAY_SIZE(edit->set); i++)
1370 if (edit->set[i].ptr)
1371 *edit->set[i].ptr = edit->set[i].to;
1373 if (edit->array->root == NULL) {
1374 edit->array->nr_leaves_on_tree = 0;
1375 } else if (edit->adjust_count_on) {
1376 node = edit->adjust_count_on;
1378 node->nr_leaves_on_branch += edit->adjust_count_by;
1393 edit->array->nr_leaves_on_tree += edit->adjust_count_by;
1396 call_rcu(&edit->rcu, assoc_array_rcu_cleanup);
1400 * assoc_array_cancel_edit - Discard an edit script.
1401 * @edit: The script to discard.
1403 * Free an edit script and all the preallocated data it holds without making
1409 void assoc_array_cancel_edit(struct assoc_array_edit *edit)
1417 for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {
1418 ptr = edit->new_meta[i];
1426 kfree(edit);
1460 struct assoc_array_edit *edit;
1472 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1473 if (!edit)
1475 edit->array = array;
1476 edit->ops = ops;
1477 edit->ops_for_excised_subtree = ops;
1478 edit->set[0].ptr = &array->root;
1479 edit->excised_subtree = array->root;
1716 edit->set[0].to = new_root;
1717 assoc_array_apply_edit(edit);
1723 assoc_array_destroy_subtree(new_root, edit->ops);
1724 kfree(edit);