1dbc920bdSVladimir Kondratyev /*- 2*4d846d26SWarner Losh * SPDX-License-Identifier: BSD-2-Clause 3dbc920bdSVladimir Kondratyev * 4dbc920bdSVladimir Kondratyev * Copyright (c) 2021 Vladimir Kondratyev <wulf@FreeBSD.org> 5dbc920bdSVladimir Kondratyev * 6dbc920bdSVladimir Kondratyev * Redistribution and use in source and binary forms, with or without 7dbc920bdSVladimir Kondratyev * modification, are permitted provided that the following conditions 8dbc920bdSVladimir Kondratyev * are met: 9dbc920bdSVladimir Kondratyev * 1. Redistributions of source code must retain the above copyright 10dbc920bdSVladimir Kondratyev * notice unmodified, this list of conditions, and the following 11dbc920bdSVladimir Kondratyev * disclaimer. 12dbc920bdSVladimir Kondratyev * 2. Redistributions in binary form must reproduce the above copyright 13dbc920bdSVladimir Kondratyev * notice, this list of conditions and the following disclaimer in the 14dbc920bdSVladimir Kondratyev * documentation and/or other materials provided with the distribution. 15dbc920bdSVladimir Kondratyev * 16dbc920bdSVladimir Kondratyev * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17dbc920bdSVladimir Kondratyev * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18dbc920bdSVladimir Kondratyev * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19dbc920bdSVladimir Kondratyev * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20dbc920bdSVladimir Kondratyev * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21dbc920bdSVladimir Kondratyev * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22dbc920bdSVladimir Kondratyev * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23dbc920bdSVladimir Kondratyev * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24dbc920bdSVladimir Kondratyev * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25dbc920bdSVladimir Kondratyev * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26dbc920bdSVladimir Kondratyev */ 27dbc920bdSVladimir Kondratyev 28307f78f3SVladimir Kondratyev #ifndef _LINUXKPI_LINUX_INTERVAL_TREE_H 29307f78f3SVladimir Kondratyev #define _LINUXKPI_LINUX_INTERVAL_TREE_H 30dbc920bdSVladimir Kondratyev 31dbc920bdSVladimir Kondratyev #include <linux/rbtree.h> 32dbc920bdSVladimir Kondratyev 33dbc920bdSVladimir Kondratyev struct interval_tree_node { 34dbc920bdSVladimir Kondratyev struct rb_node rb; 35dbc920bdSVladimir Kondratyev unsigned long start; 36dbc920bdSVladimir Kondratyev unsigned long last; 37dbc920bdSVladimir Kondratyev }; 38dbc920bdSVladimir Kondratyev 39dbc920bdSVladimir Kondratyev #define interval_tree_iter_first(...) \ 40dbc920bdSVladimir Kondratyev lkpi_interval_tree_iter_first(__VA_ARGS__) 41dbc920bdSVladimir Kondratyev #define interval_tree_iter_next(...) \ 42dbc920bdSVladimir Kondratyev lkpi_interval_tree_iter_next(__VA_ARGS__) 43dbc920bdSVladimir Kondratyev #define interval_tree_insert(...) lkpi_interval_tree_insert(__VA_ARGS__) 44dbc920bdSVladimir Kondratyev #define interval_tree_remove(...) lkpi_interval_tree_remove(__VA_ARGS__) 45dbc920bdSVladimir Kondratyev 46dbc920bdSVladimir Kondratyev struct interval_tree_node *lkpi_interval_tree_iter_first( 47dbc920bdSVladimir Kondratyev struct rb_root_cached *, unsigned long, unsigned long); 48dbc920bdSVladimir Kondratyev struct interval_tree_node *lkpi_interval_tree_iter_next( 49dbc920bdSVladimir Kondratyev struct interval_tree_node *, unsigned long, unsigned long); 50dbc920bdSVladimir Kondratyev void lkpi_interval_tree_insert(struct interval_tree_node *, 51dbc920bdSVladimir Kondratyev struct rb_root_cached *); 52dbc920bdSVladimir Kondratyev void lkpi_interval_tree_remove(struct interval_tree_node *, 53dbc920bdSVladimir Kondratyev struct rb_root_cached *); 54dbc920bdSVladimir Kondratyev 55307f78f3SVladimir Kondratyev #endif /* _LINUXKPI_LINUX_INTERVAL_TREE_H */ 56