1*b7953797SAlexei Starovoitov /* SPDX-License-Identifier: GPL-2.0-only */ 2*b7953797SAlexei Starovoitov /* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */ 3*b7953797SAlexei Starovoitov #ifndef _RANGE_TREE_H 4*b7953797SAlexei Starovoitov #define _RANGE_TREE_H 1 5*b7953797SAlexei Starovoitov 6*b7953797SAlexei Starovoitov struct range_tree { 7*b7953797SAlexei Starovoitov /* root of interval tree */ 8*b7953797SAlexei Starovoitov struct rb_root_cached it_root; 9*b7953797SAlexei Starovoitov /* root of rbtree of interval sizes */ 10*b7953797SAlexei Starovoitov struct rb_root_cached range_size_root; 11*b7953797SAlexei Starovoitov }; 12*b7953797SAlexei Starovoitov 13*b7953797SAlexei Starovoitov void range_tree_init(struct range_tree *rt); 14*b7953797SAlexei Starovoitov void range_tree_destroy(struct range_tree *rt); 15*b7953797SAlexei Starovoitov 16*b7953797SAlexei Starovoitov int range_tree_clear(struct range_tree *rt, u32 start, u32 len); 17*b7953797SAlexei Starovoitov int range_tree_set(struct range_tree *rt, u32 start, u32 len); 18*b7953797SAlexei Starovoitov int is_range_tree_set(struct range_tree *rt, u32 start, u32 len); 19*b7953797SAlexei Starovoitov s64 range_tree_find(struct range_tree *rt, u32 len); 20*b7953797SAlexei Starovoitov 21*b7953797SAlexei Starovoitov #endif 22