Lines Matching refs:edit
451 static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit) in assoc_array_insert_in_empty_tree() argument
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()
474 static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit, in assoc_array_insert_into_terminal_node() argument
490 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot; 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()
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()
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()
554 edit->segment_cache[i] = 0xff; 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()
613 edit->set[0].to = assoc_array_node_to_ptr(new_n0); 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()
661 if (edit->segment_cache[i] == slot) { in assoc_array_insert_into_terminal_node()
674 if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) { 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()
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()
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()
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()
780 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK; 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()
792 static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit, in assoc_array_insert_mid_shortcut() argument
824 edit->set[0].ptr = &edit->array->root; 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()
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()
873 edit->set[0].to = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_mid_shortcut()
905 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1); 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()
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()
941 return edit; in assoc_array_insert_mid_shortcut()
969 struct assoc_array_edit *edit; in assoc_array_insert() local
980 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL); in assoc_array_insert()
981 if (!edit) 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()
991 if (!assoc_array_insert_in_empty_tree(edit)) in assoc_array_insert()
993 return edit; in assoc_array_insert()
1000 if (!assoc_array_insert_into_terminal_node(edit, ops, index_key, in assoc_array_insert()
1003 return edit; in assoc_array_insert()
1009 if (!assoc_array_insert_mid_shortcut(edit, ops, &result)) in assoc_array_insert()
1011 return edit; in assoc_array_insert()
1017 assoc_array_cancel_edit(edit); in assoc_array_insert()
1030 void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object) in assoc_array_insert_set_object() argument
1033 edit->leaf = assoc_array_leaf_to_ptr(object); in assoc_array_insert_set_object()
1085 struct assoc_array_edit *edit; in assoc_array_delete() local
1092 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL); in assoc_array_delete()
1093 if (!edit) 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()
1119 assoc_array_cancel_edit(edit); 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()
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()
1144 return edit; in assoc_array_delete()
1212 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0); 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()
1230 edit->set[1].ptr = &array->root; in assoc_array_delete()
1236 edit->set[1].ptr = &p->slots[node->parent_slot]; 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()
1247 return edit; in assoc_array_delete()
1252 assoc_array_cancel_edit(edit); in assoc_array_delete()
1277 struct assoc_array_edit *edit; in assoc_array_clear() local
1284 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL); in assoc_array_clear()
1285 if (!edit) 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()
1294 return edit; in assoc_array_clear()
1302 struct assoc_array_edit *edit = in assoc_array_rcu_cleanup() local
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()
1322 assoc_array_ptr_to_shortcut(edit->excised_subtree); 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()
1329 kfree(edit); in assoc_array_rcu_cleanup()
1345 void assoc_array_apply_edit(struct assoc_array_edit *edit) in assoc_array_apply_edit() argument
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()
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()
1409 void assoc_array_cancel_edit(struct assoc_array_edit *edit) in assoc_array_cancel_edit() argument
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()
1426 kfree(edit); in assoc_array_cancel_edit()
1460 struct assoc_array_edit *edit; in assoc_array_gc() local
1472 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL); in assoc_array_gc()
1473 if (!edit) 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()
1716 edit->set[0].to = new_root; in assoc_array_gc()
1717 assoc_array_apply_edit(edit); in assoc_array_gc()
1723 assoc_array_destroy_subtree(new_root, edit->ops); in assoc_array_gc()
1724 kfree(edit); in assoc_array_gc()