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()
748 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0); in assoc_array_insert_into_terminal_node()
750 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0); in assoc_array_insert_into_terminal_node()
781 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK; in assoc_array_insert_into_terminal_node()
786 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK; in assoc_array_insert_into_terminal_node()
793 static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit, in assoc_array_insert_mid_shortcut() argument
825 edit->set[0].ptr = &edit->array->root; in assoc_array_insert_mid_shortcut()
828 edit->set[0].ptr = &node->slots[shortcut->parent_slot]; in assoc_array_insert_mid_shortcut()
833 edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut); in assoc_array_insert_mid_shortcut()
839 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_mid_shortcut()
840 edit->adjust_count_on = new_n0; in assoc_array_insert_mid_shortcut()
856 edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0); in assoc_array_insert_mid_shortcut()
857 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0); in assoc_array_insert_mid_shortcut()
874 edit->set[0].to = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_mid_shortcut()
906 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1); in assoc_array_insert_mid_shortcut()
918 edit->set[1].ptr = &side->back_pointer; in assoc_array_insert_mid_shortcut()
919 edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1); in assoc_array_insert_mid_shortcut()
929 edit->set_parent_slot[0].p = &side->parent_slot; in assoc_array_insert_mid_shortcut()
930 edit->set_parent_slot[0].to = sc_slot; in assoc_array_insert_mid_shortcut()
931 edit->set[1].ptr = &side->back_pointer; in assoc_array_insert_mid_shortcut()
932 edit->set[1].to = assoc_array_node_to_ptr(new_n0); in assoc_array_insert_mid_shortcut()
937 edit->leaf_p = &new_n0->slots[1]; in assoc_array_insert_mid_shortcut()
939 edit->leaf_p = &new_n0->slots[0]; in assoc_array_insert_mid_shortcut()
942 return edit; in assoc_array_insert_mid_shortcut()
970 struct assoc_array_edit *edit; in assoc_array_insert() local
981 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL); in assoc_array_insert()
982 if (!edit) in assoc_array_insert()
984 edit->array = array; in assoc_array_insert()
985 edit->ops = ops; in assoc_array_insert()
986 edit->leaf = assoc_array_leaf_to_ptr(object); in assoc_array_insert()
987 edit->adjust_count_by = 1; in assoc_array_insert()
992 if (!assoc_array_insert_in_empty_tree(edit)) in assoc_array_insert()
994 return edit; in assoc_array_insert()
1001 if (!assoc_array_insert_into_terminal_node(edit, ops, index_key, in assoc_array_insert()
1004 return edit; in assoc_array_insert()
1010 if (!assoc_array_insert_mid_shortcut(edit, ops, &result)) in assoc_array_insert()
1012 return edit; in assoc_array_insert()
1018 assoc_array_cancel_edit(edit); in assoc_array_insert()
1031 void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object) in assoc_array_insert_set_object() argument
1034 edit->leaf = assoc_array_leaf_to_ptr(object); in assoc_array_insert_set_object()
1086 struct assoc_array_edit *edit; in assoc_array_delete() local
1093 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL); in assoc_array_delete()
1094 if (!edit) in assoc_array_delete()
1096 edit->array = array; in assoc_array_delete()
1097 edit->ops = ops; in assoc_array_delete()
1098 edit->adjust_count_by = -1; in assoc_array_delete()
1120 assoc_array_cancel_edit(edit); in assoc_array_delete()
1131 edit->dead_leaf = node->slots[slot]; in assoc_array_delete()
1132 edit->set[0].ptr = &node->slots[slot]; in assoc_array_delete()
1133 edit->set[0].to = NULL; in assoc_array_delete()
1134 edit->adjust_count_on = node; in assoc_array_delete()
1140 edit->set[1].ptr = &array->root; in assoc_array_delete()
1141 edit->set[1].to = NULL; in assoc_array_delete()
1142 edit->adjust_count_on = NULL; in assoc_array_delete()
1143 edit->excised_subtree = array->root; in assoc_array_delete()
1145 return edit; in assoc_array_delete()
1213 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0); in assoc_array_delete()
1218 edit->adjust_count_on = new_n0; in assoc_array_delete()
1221 collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf); in assoc_array_delete()
1231 edit->set[1].ptr = &array->root; in assoc_array_delete()
1237 edit->set[1].ptr = &p->slots[node->parent_slot]; in assoc_array_delete()
1241 edit->set[1].ptr = &s->next_node; in assoc_array_delete()
1243 edit->set[1].to = assoc_array_node_to_ptr(new_n0); in assoc_array_delete()
1244 edit->excised_subtree = assoc_array_node_to_ptr(node); in assoc_array_delete()
1248 return edit; in assoc_array_delete()
1253 assoc_array_cancel_edit(edit); in assoc_array_delete()
1278 struct assoc_array_edit *edit; in assoc_array_clear() local
1285 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL); in assoc_array_clear()
1286 if (!edit) in assoc_array_clear()
1288 edit->array = array; in assoc_array_clear()
1289 edit->ops = ops; in assoc_array_clear()
1290 edit->set[1].ptr = &array->root; in assoc_array_clear()
1291 edit->set[1].to = NULL; in assoc_array_clear()
1292 edit->excised_subtree = array->root; in assoc_array_clear()
1293 edit->ops_for_excised_subtree = ops; in assoc_array_clear()
1295 return edit; in assoc_array_clear()
1303 struct assoc_array_edit *edit = in assoc_array_rcu_cleanup() local
1309 if (edit->dead_leaf) in assoc_array_rcu_cleanup()
1310 edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf)); in assoc_array_rcu_cleanup()
1311 for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++) in assoc_array_rcu_cleanup()
1312 if (edit->excised_meta[i]) in assoc_array_rcu_cleanup()
1313 kfree(assoc_array_ptr_to_node(edit->excised_meta[i])); in assoc_array_rcu_cleanup()
1315 if (edit->excised_subtree) { in assoc_array_rcu_cleanup()
1316 BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree)); in assoc_array_rcu_cleanup()
1317 if (assoc_array_ptr_is_node(edit->excised_subtree)) { in assoc_array_rcu_cleanup()
1319 assoc_array_ptr_to_node(edit->excised_subtree); in assoc_array_rcu_cleanup()
1323 assoc_array_ptr_to_shortcut(edit->excised_subtree); in assoc_array_rcu_cleanup()
1326 assoc_array_destroy_subtree(edit->excised_subtree, in assoc_array_rcu_cleanup()
1327 edit->ops_for_excised_subtree); in assoc_array_rcu_cleanup()
1330 kfree(edit); in assoc_array_rcu_cleanup()
1346 void assoc_array_apply_edit(struct assoc_array_edit *edit) in assoc_array_apply_edit() argument
1356 if (edit->leaf_p) in assoc_array_apply_edit()
1357 *edit->leaf_p = edit->leaf; in assoc_array_apply_edit()
1360 for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++) in assoc_array_apply_edit()
1361 if (edit->set_parent_slot[i].p) in assoc_array_apply_edit()
1362 *edit->set_parent_slot[i].p = edit->set_parent_slot[i].to; in assoc_array_apply_edit()
1365 for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++) in assoc_array_apply_edit()
1366 if (edit->set_backpointers[i]) in assoc_array_apply_edit()
1367 *edit->set_backpointers[i] = edit->set_backpointers_to; in assoc_array_apply_edit()
1370 for (i = 0; i < ARRAY_SIZE(edit->set); i++) in assoc_array_apply_edit()
1371 if (edit->set[i].ptr) in assoc_array_apply_edit()
1372 *edit->set[i].ptr = edit->set[i].to; in assoc_array_apply_edit()
1374 if (edit->array->root == NULL) { in assoc_array_apply_edit()
1375 edit->array->nr_leaves_on_tree = 0; in assoc_array_apply_edit()
1376 } else if (edit->adjust_count_on) { in assoc_array_apply_edit()
1377 node = edit->adjust_count_on; in assoc_array_apply_edit()
1379 node->nr_leaves_on_branch += edit->adjust_count_by; in assoc_array_apply_edit()
1394 edit->array->nr_leaves_on_tree += edit->adjust_count_by; in assoc_array_apply_edit()
1397 call_rcu(&edit->rcu, assoc_array_rcu_cleanup); in assoc_array_apply_edit()
1410 void assoc_array_cancel_edit(struct assoc_array_edit *edit) in assoc_array_cancel_edit() argument
1418 for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) { in assoc_array_cancel_edit()
1419 ptr = edit->new_meta[i]; in assoc_array_cancel_edit()
1427 kfree(edit); in assoc_array_cancel_edit()
1461 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()
1718 edit->set[0].to = new_root; in assoc_array_gc()
1719 assoc_array_apply_edit(edit); in assoc_array_gc()
1725 assoc_array_destroy_subtree(new_root, edit->ops); in assoc_array_gc()
1726 kfree(edit); in assoc_array_gc()