1d7d2af7dSFrançois Tigeot /* 2d7d2af7dSFrançois Tigeot * Copyright (c) 2018 François Tigeot <ftigeot@wolfpond.org> 3*70abac43SMatthew Dillon * Copyright (c) 2019 Matthew Dillon <dillon@backplane.com> 4d7d2af7dSFrançois Tigeot * All rights reserved. 5d7d2af7dSFrançois Tigeot * 6d7d2af7dSFrançois Tigeot * Redistribution and use in source and binary forms, with or without 7d7d2af7dSFrançois Tigeot * modification, are permitted provided that the following conditions 8d7d2af7dSFrançois Tigeot * are met: 9d7d2af7dSFrançois Tigeot * 1. Redistributions of source code must retain the above copyright 10d7d2af7dSFrançois Tigeot * notice unmodified, this list of conditions, and the following 11d7d2af7dSFrançois Tigeot * disclaimer. 12d7d2af7dSFrançois Tigeot * 2. Redistributions in binary form must reproduce the above copyright 13d7d2af7dSFrançois Tigeot * notice, this list of conditions and the following disclaimer in the 14d7d2af7dSFrançois Tigeot * documentation and/or other materials provided with the distribution. 15d7d2af7dSFrançois Tigeot * 16d7d2af7dSFrançois Tigeot * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17d7d2af7dSFrançois Tigeot * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18d7d2af7dSFrançois Tigeot * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19d7d2af7dSFrançois Tigeot * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20d7d2af7dSFrançois Tigeot * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21d7d2af7dSFrançois Tigeot * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22d7d2af7dSFrançois Tigeot * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23d7d2af7dSFrançois Tigeot * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24d7d2af7dSFrançois Tigeot * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25d7d2af7dSFrançois Tigeot * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26d7d2af7dSFrançois Tigeot */ 27d7d2af7dSFrançois Tigeot 28d7d2af7dSFrançois Tigeot #ifndef _LINUX_INTERVAL_TREE_H_ 29d7d2af7dSFrançois Tigeot #define _LINUX_INTERVAL_TREE_H_ 30d7d2af7dSFrançois Tigeot 31d7d2af7dSFrançois Tigeot #include <linux/rbtree.h> 32d7d2af7dSFrançois Tigeot 33d7d2af7dSFrançois Tigeot struct interval_tree_node { 34*70abac43SMatthew Dillon struct interval_tree_node *next; 35*70abac43SMatthew Dillon long atroot; 36*70abac43SMatthew Dillon unsigned long start; /* Start of interval, inclusive */ 37*70abac43SMatthew Dillon unsigned long last; /* Last location _in_ interval, inclusive */ 38d7d2af7dSFrançois Tigeot }; 39d7d2af7dSFrançois Tigeot 40*70abac43SMatthew Dillon extern void 41*70abac43SMatthew Dillon interval_tree_insert(struct interval_tree_node *node, struct rb_root *root); 42*70abac43SMatthew Dillon 43*70abac43SMatthew Dillon extern void 44*70abac43SMatthew Dillon interval_tree_remove(struct interval_tree_node *node, struct rb_root *root); 45*70abac43SMatthew Dillon 46*70abac43SMatthew Dillon extern struct interval_tree_node * 47*70abac43SMatthew Dillon interval_tree_iter_first(struct rb_root *root, 48*70abac43SMatthew Dillon unsigned long start, unsigned long last); 49*70abac43SMatthew Dillon 50*70abac43SMatthew Dillon extern struct interval_tree_node * 51*70abac43SMatthew Dillon interval_tree_iter_next(struct interval_tree_node *node, 52*70abac43SMatthew Dillon unsigned long start, unsigned long last); 53*70abac43SMatthew Dillon 54d7d2af7dSFrançois Tigeot #endif /* _LINUX_INTERVAL_TREE_H_ */ 55