Lines Matching refs: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);
1021 /* Create tree of 1-100 */
1029 /* Create tree of 1-200 */
1042 /* Create tree of 1-400 */
1070 /* Overwrite multiple levels at the end of the tree (slot 7) */
1134 * 8. Overwrite the whole tree
1135 * 9. Try to overwrite the zero entry of an alloc tree.
1287 /* Cause a 3 child split all the way up the tree. */
1395 * Store NULL at range [0, ULONG_MAX] to an empty tree should result
1396 * in an empty tree
1406 * Store NULL at any range to an empty tree should result in an empty
1407 * tree
1418 * Store NULL at range [0, ULONG_MAX] to a single entry tree should
1419 * result in an empty tree
1432 * Store NULL at range [0, n] to a single entry tree should
1433 * result in an empty tree
1446 * Store NULL at range [m, n] where m > 0 to a single entry tree
1447 * should still be a single entry tree
1461 * Store NULL at range [0, ULONG_MAX] to a tree with node should
1462 * result in an empty tree
1737 /* seq 2000 tests are for multi-level tree gaps */
1965 /* check_forking - simulate the kernel forking sequence with the tree. */
2092 newmas.tree = &newmt;
2237 /* Check across node boundaries of the tree */
2254 /* Check across two levels of the tree */
2749 /* duplicate the tree with a specific gap */
2849 /* Check non-allocation tree not starting at zero */
2861 /* Check non-allocation tree starting at zero */
3032 * The table below shows the single entry tree (0-0 pointer) and normal tree
3046 * Single entry tree at 0-0
3056 * Normal tree
3070 * Single entry tree at 0-0
3083 * Normal tree
3099 * Single entry tree at 0-0
3111 * Normal tree
3124 * Single entry tree at 0-0
3136 * Normal tree
3149 * Single entry tree at 0-0
3162 * Normal tree
3779 static DEFINE_MTREE(tree);
3791 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3792 bench_slot_store(&tree);
3793 mtree_destroy(&tree);
3798 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3799 bench_node_store(&tree);
3800 mtree_destroy(&tree);
3805 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3806 bench_awalk(&tree);
3807 mtree_destroy(&tree);
3812 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3813 bench_walk(&tree);
3814 mtree_destroy(&tree);
3819 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3820 bench_load(&tree);
3821 mtree_destroy(&tree);
3831 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3832 bench_mt_for_each(&tree);
3833 mtree_destroy(&tree);
3838 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3839 bench_mas_for_each(&tree);
3840 mtree_destroy(&tree);
3845 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3846 bench_mas_prev(&tree);
3847 mtree_destroy(&tree);
3851 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3852 check_deficient_node(&tree);
3853 mtree_destroy(&tree);
3855 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3856 check_store_null(&tree);
3857 mtree_destroy(&tree);
3859 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3860 check_root_expand(&tree);
3861 mtree_destroy(&tree);
3863 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3864 check_iteration(&tree);
3865 mtree_destroy(&tree);
3869 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3870 check_mas_store_gfp(&tree);
3871 mtree_destroy(&tree);
3874 mt_init_flags(&tree, 0);
3875 check_ranges(&tree);
3876 mtree_destroy(&tree);
3880 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3881 check_alloc_range(&tree);
3882 mtree_destroy(&tree);
3884 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3885 check_alloc_rev_range(&tree);
3886 mtree_destroy(&tree);
3889 mt_init_flags(&tree, 0);
3891 check_load(&tree, set[0], NULL); /* See if 5015 -> NULL */
3893 check_insert(&tree, set[9], &tree); /* Insert 0 */
3894 check_load(&tree, set[9], &tree); /* See if 0 -> &tree */
3895 check_load(&tree, set[0], NULL); /* See if 5015 -> NULL */
3897 check_insert(&tree, set[10], ptr); /* Insert 5003 */
3898 check_load(&tree, set[9], &tree); /* See if 0 -> &tree */
3899 check_load(&tree, set[11], NULL); /* See if 5002 -> NULL */
3900 check_load(&tree, set[10], ptr); /* See if 5003 -> ptr */
3902 /* Clear out the tree */
3903 mtree_destroy(&tree);
3906 mt_init_flags(&tree, 0);
3907 check_insert(&tree, set[0], &tree); /* Insert 5015 */
3908 check_dup_insert(&tree, set[0], &tree); /* Insert 5015 again */
3909 check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */
3915 check_load(&tree, set[1], NULL); /* See if 5014 -> NULL */
3916 check_insert(&tree, set[1], ptr); /* insert 5014 -> ptr */
3917 check_load(&tree, set[1], ptr); /* See if 5014 -> ptr */
3918 check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */
3921 * p[0]: 14 -> (nil) p[1]: 15 -> ptr p[2]: 16 -> &tree p[3]: 0 -> (nil)
3923 check_insert(&tree, set[6], ptr); /* insert 1002 -> ptr */
3924 check_insert(&tree, set[7], &tree); /* insert 1003 -> &tree */
3926 check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */
3927 check_load(&tree, set[1], ptr); /* See if 5014 -> ptr */
3928 check_load(&tree, set[6], ptr); /* See if 1002 -> ptr */
3929 check_load(&tree, set[7], &tree); /* 1003 = &tree ? */
3931 /* Clear out tree */
3932 mtree_destroy(&tree);
3934 mt_init_flags(&tree, 0);
3936 check_insert(&tree, set[5], ptr); /* insert 1001 -> ptr */
3937 check_insert(&tree, set[7], &tree); /* insert 1003 -> &tree */
3938 check_insert(&tree, set[6], ptr); /* insert 1002 -> ptr */
3939 check_load(&tree, set[5], ptr); /* See if 1001 -> ptr */
3940 check_load(&tree, set[6], ptr); /* See if 1002 -> ptr */
3941 check_load(&tree, set[7], &tree); /* See if 1003 -> &tree */
3943 /* Clear out the tree */
3944 mtree_destroy(&tree);
3946 mt_init_flags(&tree, 0);
3953 check_insert(&tree, set[0], ptr); /* 5015 */
3954 check_insert(&tree, set[1], &tree); /* 5014 */
3955 check_insert(&tree, set[2], ptr); /* 5017 */
3956 check_insert(&tree, set[3], &tree); /* 25 */
3957 check_load(&tree, set[0], ptr);
3958 check_load(&tree, set[1], &tree);
3959 check_load(&tree, set[2], ptr);
3960 check_load(&tree, set[3], &tree);
3961 check_insert(&tree, set[4], ptr); /* 1000 < Should split. */
3962 check_load(&tree, set[0], ptr);
3963 check_load(&tree, set[1], &tree);
3964 check_load(&tree, set[2], ptr);
3965 check_load(&tree, set[3], &tree); /*25 */
3966 check_load(&tree, set[4], ptr);
3967 check_insert(&tree, set[5], &tree); /* 1001 */
3968 check_load(&tree, set[0], ptr);
3969 check_load(&tree, set[1], &tree);
3970 check_load(&tree, set[2], ptr);
3971 check_load(&tree, set[3], &tree);
3972 check_load(&tree, set[4], ptr);
3973 check_load(&tree, set[5], &tree);
3974 check_insert(&tree, set[6], ptr);
3975 check_load(&tree, set[0], ptr);
3976 check_load(&tree, set[1], &tree);
3977 check_load(&tree, set[2], ptr);
3978 check_load(&tree, set[3], &tree);
3979 check_load(&tree, set[4], ptr);
3980 check_load(&tree, set[5], &tree);
3981 check_load(&tree, set[6], ptr);
3982 check_insert(&tree, set[7], &tree);
3983 check_load(&tree, set[0], ptr);
3984 check_insert(&tree, set[8], ptr);
3986 check_insert(&tree, set[9], &tree);
3988 check_load(&tree, set[0], ptr);
3989 check_load(&tree, set[1], &tree);
3990 check_load(&tree, set[2], ptr);
3991 check_load(&tree, set[3], &tree);
3992 check_load(&tree, set[4], ptr);
3993 check_load(&tree, set[5], &tree);
3994 check_load(&tree, set[6], ptr);
3995 check_load(&tree, set[9], &tree);
3996 mtree_destroy(&tree);
3998 mt_init_flags(&tree, 0);
3999 check_seq(&tree, 16, false);
4000 mtree_destroy(&tree);
4002 mt_init_flags(&tree, 0);
4003 check_seq(&tree, 1000, true);
4004 mtree_destroy(&tree);
4006 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4007 check_rev_seq(&tree, 1000, true);
4008 mtree_destroy(&tree);
4010 check_lower_bound_split(&tree);
4011 check_upper_bound_split(&tree);
4012 check_mid_split(&tree);
4014 mt_init_flags(&tree, 0);
4015 check_next_entry(&tree);
4016 check_find(&tree);
4017 check_find_2(&tree);
4018 mtree_destroy(&tree);
4020 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4021 check_prev_entry(&tree);
4022 mtree_destroy(&tree);
4024 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4025 check_gap_combining(&tree);
4026 mtree_destroy(&tree);
4028 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4029 check_node_overwrite(&tree);
4030 mtree_destroy(&tree);
4032 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4033 next_prev_test(&tree);
4034 mtree_destroy(&tree);
4036 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4037 check_spanning_relatives(&tree);
4038 mtree_destroy(&tree);
4040 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4041 check_rev_find(&tree);
4042 mtree_destroy(&tree);
4044 mt_init_flags(&tree, 0);
4045 check_fuzzer(&tree);
4046 mtree_destroy(&tree);
4048 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4049 check_dup(&tree);
4050 mtree_destroy(&tree);
4052 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4053 check_bnode_min_spanning(&tree);
4054 mtree_destroy(&tree);
4056 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4057 check_empty_area_window(&tree);
4058 mtree_destroy(&tree);
4060 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4061 check_empty_area_fill(&tree);
4062 mtree_destroy(&tree);
4064 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4065 check_state_handling(&tree);
4066 mtree_destroy(&tree);
4068 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
4069 alloc_cyclic_testing(&tree);
4070 mtree_destroy(&tree);
4095 MODULE_DESCRIPTION("maple tree API test module");