Lines Matching full:tree
3 * test_maple_tree.c: Test the maple tree API
7 * Any tests that only require the interface of the tree.
557 MT_BUG_ON(mas.tree, entry == NULL); in check_find()
1021 /* Create tree of 1-100 */ in check_ranges()
1029 /* Create tree of 1-200 */ in check_ranges()
1042 /* Create tree of 1-400 */ in check_ranges()
1070 /* Overwrite multiple levels at the end of the tree (slot 7) */ in check_ranges()
1134 * 8. Overwrite the whole tree in check_ranges()
1135 * 9. Try to overwrite the zero entry of an alloc tree. in check_ranges()
1287 /* Cause a 3 child split all the way up the tree. */ in check_ranges()
1395 * Store NULL at range [0, ULONG_MAX] to an empty tree should result in check_store_null()
1396 * in an empty tree in check_store_null()
1406 * Store NULL at any range to an empty tree should result in an empty in check_store_null()
1407 * tree in check_store_null()
1418 * Store NULL at range [0, ULONG_MAX] to a single entry tree should in check_store_null()
1419 * result in an empty tree in check_store_null()
1432 * Store NULL at range [0, n] to a single entry tree should in check_store_null()
1433 * result in an empty tree in check_store_null()
1446 * Store NULL at range [m, n] where m > 0 to a single entry tree in check_store_null()
1447 * should still be a single entry tree in check_store_null()
1461 * Store NULL at range [0, ULONG_MAX] to a tree with node should in check_store_null()
1462 * result in an empty tree in check_store_null()
1737 /* seq 2000 tests are for multi-level tree gaps */ in check_gap_combining()
1965 /* check_forking - simulate the kernel forking sequence with the tree. */
2092 newmas.tree = &newmt; in check_mas_store_gfp()
2237 /* Check across node boundaries of the tree */ in next_prev_test()
2254 /* Check across two levels of the tree */ in next_prev_test()
2899 * The table below shows the single entry tree (0-0 pointer) and normal tree
2913 * Single entry tree at 0-0
2923 * Normal tree
2937 * Single entry tree at 0-0
2950 * Normal tree
2966 * Single entry tree at 0-0
2978 * Normal tree
2991 * Single entry tree at 0-0
3003 * Normal tree
3016 * Single entry tree at 0-0
3029 * Normal tree
3678 static DEFINE_MTREE(tree);
3690 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3691 bench_slot_store(&tree); in maple_tree_seed()
3692 mtree_destroy(&tree); in maple_tree_seed()
3697 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3698 bench_node_store(&tree); in maple_tree_seed()
3699 mtree_destroy(&tree); in maple_tree_seed()
3704 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3705 bench_awalk(&tree); in maple_tree_seed()
3706 mtree_destroy(&tree); in maple_tree_seed()
3711 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3712 bench_walk(&tree); in maple_tree_seed()
3713 mtree_destroy(&tree); in maple_tree_seed()
3718 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3719 bench_load(&tree); in maple_tree_seed()
3720 mtree_destroy(&tree); in maple_tree_seed()
3730 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3731 bench_mt_for_each(&tree); in maple_tree_seed()
3732 mtree_destroy(&tree); in maple_tree_seed()
3737 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3738 bench_mas_for_each(&tree); in maple_tree_seed()
3739 mtree_destroy(&tree); in maple_tree_seed()
3744 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3745 bench_mas_prev(&tree); in maple_tree_seed()
3746 mtree_destroy(&tree); in maple_tree_seed()
3750 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3751 check_deficient_node(&tree); in maple_tree_seed()
3752 mtree_destroy(&tree); in maple_tree_seed()
3754 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3755 check_store_null(&tree); in maple_tree_seed()
3756 mtree_destroy(&tree); in maple_tree_seed()
3758 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3759 check_root_expand(&tree); in maple_tree_seed()
3760 mtree_destroy(&tree); in maple_tree_seed()
3762 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3763 check_iteration(&tree); in maple_tree_seed()
3764 mtree_destroy(&tree); in maple_tree_seed()
3768 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3769 check_mas_store_gfp(&tree); in maple_tree_seed()
3770 mtree_destroy(&tree); in maple_tree_seed()
3773 mt_init_flags(&tree, 0); in maple_tree_seed()
3774 check_ranges(&tree); in maple_tree_seed()
3775 mtree_destroy(&tree); in maple_tree_seed()
3779 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3780 check_alloc_range(&tree); in maple_tree_seed()
3781 mtree_destroy(&tree); in maple_tree_seed()
3783 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3784 check_alloc_rev_range(&tree); in maple_tree_seed()
3785 mtree_destroy(&tree); in maple_tree_seed()
3788 mt_init_flags(&tree, 0); in maple_tree_seed()
3790 check_load(&tree, set[0], NULL); /* See if 5015 -> NULL */ in maple_tree_seed()
3792 check_insert(&tree, set[9], &tree); /* Insert 0 */ in maple_tree_seed()
3793 check_load(&tree, set[9], &tree); /* See if 0 -> &tree */ in maple_tree_seed()
3794 check_load(&tree, set[0], NULL); /* See if 5015 -> NULL */ in maple_tree_seed()
3796 check_insert(&tree, set[10], ptr); /* Insert 5003 */ in maple_tree_seed()
3797 check_load(&tree, set[9], &tree); /* See if 0 -> &tree */ in maple_tree_seed()
3798 check_load(&tree, set[11], NULL); /* See if 5002 -> NULL */ in maple_tree_seed()
3799 check_load(&tree, set[10], ptr); /* See if 5003 -> ptr */ in maple_tree_seed()
3801 /* Clear out the tree */ in maple_tree_seed()
3802 mtree_destroy(&tree); in maple_tree_seed()
3805 mt_init_flags(&tree, 0); in maple_tree_seed()
3806 check_insert(&tree, set[0], &tree); /* Insert 5015 */ in maple_tree_seed()
3807 check_dup_insert(&tree, set[0], &tree); /* Insert 5015 again */ in maple_tree_seed()
3808 check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */ in maple_tree_seed()
3814 check_load(&tree, set[1], NULL); /* See if 5014 -> NULL */ in maple_tree_seed()
3815 check_insert(&tree, set[1], ptr); /* insert 5014 -> ptr */ in maple_tree_seed()
3816 check_load(&tree, set[1], ptr); /* See if 5014 -> ptr */ in maple_tree_seed()
3817 check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */ in maple_tree_seed()
3819 * Tree currently contains: in maple_tree_seed()
3820 * p[0]: 14 -> (nil) p[1]: 15 -> ptr p[2]: 16 -> &tree p[3]: 0 -> (nil) in maple_tree_seed()
3822 check_insert(&tree, set[6], ptr); /* insert 1002 -> ptr */ in maple_tree_seed()
3823 check_insert(&tree, set[7], &tree); /* insert 1003 -> &tree */ in maple_tree_seed()
3825 check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */ in maple_tree_seed()
3826 check_load(&tree, set[1], ptr); /* See if 5014 -> ptr */ in maple_tree_seed()
3827 check_load(&tree, set[6], ptr); /* See if 1002 -> ptr */ in maple_tree_seed()
3828 check_load(&tree, set[7], &tree); /* 1003 = &tree ? */ in maple_tree_seed()
3830 /* Clear out tree */ in maple_tree_seed()
3831 mtree_destroy(&tree); in maple_tree_seed()
3833 mt_init_flags(&tree, 0); in maple_tree_seed()
3835 check_insert(&tree, set[5], ptr); /* insert 1001 -> ptr */ in maple_tree_seed()
3836 check_insert(&tree, set[7], &tree); /* insert 1003 -> &tree */ in maple_tree_seed()
3837 check_insert(&tree, set[6], ptr); /* insert 1002 -> ptr */ in maple_tree_seed()
3838 check_load(&tree, set[5], ptr); /* See if 1001 -> ptr */ in maple_tree_seed()
3839 check_load(&tree, set[6], ptr); /* See if 1002 -> ptr */ in maple_tree_seed()
3840 check_load(&tree, set[7], &tree); /* See if 1003 -> &tree */ in maple_tree_seed()
3842 /* Clear out the tree */ in maple_tree_seed()
3843 mtree_destroy(&tree); in maple_tree_seed()
3845 mt_init_flags(&tree, 0); in maple_tree_seed()
3852 check_insert(&tree, set[0], ptr); /* 5015 */ in maple_tree_seed()
3853 check_insert(&tree, set[1], &tree); /* 5014 */ in maple_tree_seed()
3854 check_insert(&tree, set[2], ptr); /* 5017 */ in maple_tree_seed()
3855 check_insert(&tree, set[3], &tree); /* 25 */ in maple_tree_seed()
3856 check_load(&tree, set[0], ptr); in maple_tree_seed()
3857 check_load(&tree, set[1], &tree); in maple_tree_seed()
3858 check_load(&tree, set[2], ptr); in maple_tree_seed()
3859 check_load(&tree, set[3], &tree); in maple_tree_seed()
3860 check_insert(&tree, set[4], ptr); /* 1000 < Should split. */ in maple_tree_seed()
3861 check_load(&tree, set[0], ptr); in maple_tree_seed()
3862 check_load(&tree, set[1], &tree); in maple_tree_seed()
3863 check_load(&tree, set[2], ptr); in maple_tree_seed()
3864 check_load(&tree, set[3], &tree); /*25 */ in maple_tree_seed()
3865 check_load(&tree, set[4], ptr); in maple_tree_seed()
3866 check_insert(&tree, set[5], &tree); /* 1001 */ in maple_tree_seed()
3867 check_load(&tree, set[0], ptr); in maple_tree_seed()
3868 check_load(&tree, set[1], &tree); in maple_tree_seed()
3869 check_load(&tree, set[2], ptr); in maple_tree_seed()
3870 check_load(&tree, set[3], &tree); in maple_tree_seed()
3871 check_load(&tree, set[4], ptr); in maple_tree_seed()
3872 check_load(&tree, set[5], &tree); in maple_tree_seed()
3873 check_insert(&tree, set[6], ptr); in maple_tree_seed()
3874 check_load(&tree, set[0], ptr); in maple_tree_seed()
3875 check_load(&tree, set[1], &tree); in maple_tree_seed()
3876 check_load(&tree, set[2], ptr); in maple_tree_seed()
3877 check_load(&tree, set[3], &tree); in maple_tree_seed()
3878 check_load(&tree, set[4], ptr); in maple_tree_seed()
3879 check_load(&tree, set[5], &tree); in maple_tree_seed()
3880 check_load(&tree, set[6], ptr); in maple_tree_seed()
3881 check_insert(&tree, set[7], &tree); in maple_tree_seed()
3882 check_load(&tree, set[0], ptr); in maple_tree_seed()
3883 check_insert(&tree, set[8], ptr); in maple_tree_seed()
3885 check_insert(&tree, set[9], &tree); in maple_tree_seed()
3887 check_load(&tree, set[0], ptr); in maple_tree_seed()
3888 check_load(&tree, set[1], &tree); in maple_tree_seed()
3889 check_load(&tree, set[2], ptr); in maple_tree_seed()
3890 check_load(&tree, set[3], &tree); in maple_tree_seed()
3891 check_load(&tree, set[4], ptr); in maple_tree_seed()
3892 check_load(&tree, set[5], &tree); in maple_tree_seed()
3893 check_load(&tree, set[6], ptr); in maple_tree_seed()
3894 check_load(&tree, set[9], &tree); in maple_tree_seed()
3895 mtree_destroy(&tree); in maple_tree_seed()
3897 mt_init_flags(&tree, 0); in maple_tree_seed()
3898 check_seq(&tree, 16, false); in maple_tree_seed()
3899 mtree_destroy(&tree); in maple_tree_seed()
3901 mt_init_flags(&tree, 0); in maple_tree_seed()
3902 check_seq(&tree, 1000, true); in maple_tree_seed()
3903 mtree_destroy(&tree); in maple_tree_seed()
3905 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3906 check_rev_seq(&tree, 1000, true); in maple_tree_seed()
3907 mtree_destroy(&tree); in maple_tree_seed()
3909 check_lower_bound_split(&tree); in maple_tree_seed()
3910 check_upper_bound_split(&tree); in maple_tree_seed()
3911 check_mid_split(&tree); in maple_tree_seed()
3913 mt_init_flags(&tree, 0); in maple_tree_seed()
3914 check_next_entry(&tree); in maple_tree_seed()
3915 check_find(&tree); in maple_tree_seed()
3916 check_find_2(&tree); in maple_tree_seed()
3917 mtree_destroy(&tree); in maple_tree_seed()
3919 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3920 check_prev_entry(&tree); in maple_tree_seed()
3921 mtree_destroy(&tree); in maple_tree_seed()
3923 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3924 check_gap_combining(&tree); in maple_tree_seed()
3925 mtree_destroy(&tree); in maple_tree_seed()
3927 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3928 check_node_overwrite(&tree); in maple_tree_seed()
3929 mtree_destroy(&tree); in maple_tree_seed()
3931 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3932 next_prev_test(&tree); in maple_tree_seed()
3933 mtree_destroy(&tree); in maple_tree_seed()
3935 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3936 check_spanning_relatives(&tree); in maple_tree_seed()
3937 mtree_destroy(&tree); in maple_tree_seed()
3939 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3940 check_rev_find(&tree); in maple_tree_seed()
3941 mtree_destroy(&tree); in maple_tree_seed()
3943 mt_init_flags(&tree, 0); in maple_tree_seed()
3944 check_fuzzer(&tree); in maple_tree_seed()
3945 mtree_destroy(&tree); in maple_tree_seed()
3947 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3948 check_bnode_min_spanning(&tree); in maple_tree_seed()
3949 mtree_destroy(&tree); in maple_tree_seed()
3951 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3952 check_empty_area_window(&tree); in maple_tree_seed()
3953 mtree_destroy(&tree); in maple_tree_seed()
3955 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3956 check_empty_area_fill(&tree); in maple_tree_seed()
3957 mtree_destroy(&tree); in maple_tree_seed()
3959 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3960 check_state_handling(&tree); in maple_tree_seed()
3961 mtree_destroy(&tree); in maple_tree_seed()
3963 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); in maple_tree_seed()
3964 alloc_cyclic_testing(&tree); in maple_tree_seed()
3965 mtree_destroy(&tree); in maple_tree_seed()
3990 MODULE_DESCRIPTION("maple tree API test module");