117680Spst/* SPDX-License-Identifier: GPL-2.0 */ 2214478Srpaulo#include <linux/gfp.h> 3127668Sbms#include <linux/types.h> 4251158Sdelphij#include <linux/radix-tree.h> 5111726Sfenner#include <linux/rcupdate.h> 6251158Sdelphij 7172683Smlaierstruct item { 8251158Sdelphij struct rcu_head rcu_head; 9251158Sdelphij unsigned long index; 10251158Sdelphij unsigned int order; 11251158Sdelphij}; 12127668Sbms 13127668Sbmsstruct item *item_create(unsigned long index, unsigned int order); 14251158Sdelphijint item_insert(struct radix_tree_root *root, unsigned long index); 15251158Sdelphijvoid item_sanity(struct item *item, unsigned long index); 16251158Sdelphijvoid item_free(struct item *item, unsigned long index); 1775115Sfennerint item_delete(struct radix_tree_root *root, unsigned long index); 18172683Smlaierint item_delete_rcu(struct xarray *xa, unsigned long index); 19172683Smlaierstruct item *item_lookup(struct radix_tree_root *root, unsigned long index); 20251158Sdelphij 21127668Sbmsvoid item_check_present(struct radix_tree_root *root, unsigned long index); 22127668Sbmsvoid item_check_absent(struct radix_tree_root *root, unsigned long index); 23251158Sdelphijvoid item_gang_check_present(struct radix_tree_root *root, 24127668Sbms unsigned long start, unsigned long nr, 25127668Sbms int chunk, int hop); 26172683Smlaiervoid item_full_scan(struct radix_tree_root *root, unsigned long start, 27172683Smlaier unsigned long nr, int chunk); 28251158Sdelphijvoid item_kill_tree(struct radix_tree_root *root); 29251158Sdelphij 30251158Sdelphijint tag_tagged_items(struct xarray *, unsigned long start, unsigned long end, 31251158Sdelphij unsigned batch, xa_mark_t iftag, xa_mark_t thentag); 32251158Sdelphij 33172683Smlaiervoid xarray_tests(void); 34127668Sbmsvoid tag_check(void); 3575115Sfennervoid multiorder_checks(void); 36172683Smlaiervoid iteration_test(unsigned order, unsigned duration); 37251158Sdelphijvoid iteration_test2(unsigned duration); 38251158Sdelphijvoid benchmark(void); 39251158Sdelphijvoid idr_checks(void); 40251158Sdelphijvoid ida_tests(void); 41251158Sdelphij 42251158Sdelphijstruct item * 43251158Sdelphijitem_tag_set(struct radix_tree_root *root, unsigned long index, int tag); 44251158Sdelphijstruct item * 45251158Sdelphijitem_tag_clear(struct radix_tree_root *root, unsigned long index, int tag); 46251158Sdelphijint item_tag_get(struct radix_tree_root *root, unsigned long index, int tag); 47251158Sdelphijvoid tree_verify_min_height(struct radix_tree_root *root, int maxindex); 48251158Sdelphijvoid verify_tag_consistency(struct radix_tree_root *root, unsigned int tag); 49251158Sdelphij 50251158Sdelphijextern int nr_allocated; 51251158Sdelphij 52251158Sdelphij/* Normally private parts of lib/radix-tree.c */ 53251158Sdelphijstruct radix_tree_node *entry_to_node(void *ptr); 54251158Sdelphijvoid radix_tree_dump(struct radix_tree_root *root); 55251158Sdelphijint root_tag_get(struct radix_tree_root *root, unsigned int tag); 56251158Sdelphijunsigned long node_maxindex(struct radix_tree_node *); 57172683Smlaierunsigned long shift_maxindex(unsigned int shift); 58251158Sdelphijint radix_tree_cpu_dead(unsigned int cpu); 59251158Sdelphijextern struct radix_tree_preload radix_tree_preloads; 60251158Sdelphij