1 /* $NetBSD: interval_tree.h,v 1.12 2021/12/19 11:00:18 riastradh Exp $ */ 2 3 /*- 4 * Copyright (c) 2018 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Taylor R. Campbell. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* 33 * XXX WARNING: This does not actually implement interval trees -- it 34 * only implements trees of intervals. In particular, it does not 35 * support finding all intervals that contain a given point, or that 36 * intersect with a given interval. Another way to look at it is that 37 * this is an interval tree restricted to nonoverlapping intervals. 38 */ 39 40 #ifndef _LINUX_INTERVAL_TREE_H_ 41 #define _LINUX_INTERVAL_TREE_H_ 42 43 #include <linux/rbtree.h> 44 45 struct interval_tree_node { 46 struct rb_node itn_node; 47 unsigned long start; /* inclusive */ 48 unsigned long last; /* inclusive */ 49 }; 50 51 static inline int 52 interval_tree_compare_nodes(void *cookie, const void *va, const void *vb) 53 { 54 const struct interval_tree_node *na = va; 55 const struct interval_tree_node *nb = vb; 56 57 if (na->start < nb->start) 58 return -1; 59 if (na->start > nb->start) 60 return +1; 61 if (na->last < nb->last) 62 return -1; 63 if (na->last > nb->last) 64 return +1; 65 return 0; 66 } 67 68 static inline int 69 interval_tree_compare_key(void *cookie, const void *vn, const void *vk) 70 { 71 const struct interval_tree_node *n = vn; 72 const unsigned long *k = vk; 73 74 if (n->start < *k) 75 return -1; 76 if (*k < n->start) 77 return +1; 78 return 0; 79 } 80 81 static const rb_tree_ops_t interval_tree_ops = { 82 .rbto_compare_nodes = interval_tree_compare_nodes, 83 .rbto_compare_key = interval_tree_compare_key, 84 .rbto_node_offset = offsetof(struct interval_tree_node, itn_node), 85 }; 86 87 static inline void 88 interval_tree_init(struct rb_root_cached *root) 89 { 90 91 rb_tree_init(&root->rb_root.rbr_tree, &interval_tree_ops); 92 } 93 94 static inline void 95 interval_tree_insert(struct interval_tree_node *node, 96 struct rb_root_cached *root) 97 { 98 struct interval_tree_node *collision __diagused; 99 100 collision = rb_tree_insert_node(&root->rb_root.rbr_tree, node); 101 KASSERT(collision == node); 102 } 103 104 static inline void 105 interval_tree_remove(struct interval_tree_node *node, 106 struct rb_root_cached *root) 107 { 108 109 rb_tree_remove_node(&root->rb_root.rbr_tree, node); 110 } 111 112 static inline struct interval_tree_node * 113 interval_tree_iter_first(struct rb_root_cached *root, unsigned long start, 114 unsigned long last) 115 { 116 struct interval_tree_node *node; 117 118 node = rb_tree_find_node_geq(&root->rb_root.rbr_tree, &start); 119 if (node == NULL) 120 return NULL; 121 if (last < node->start) 122 return NULL; 123 KASSERT(node->start <= last && node->last >= start); 124 125 return node; 126 } 127 128 /* 129 * XXX Linux's interval_tree_iter_next doesn't take the root as an 130 * argument, which makes this difficult. So we'll just patch those 131 * uses. 132 */ 133 static inline struct interval_tree_node * 134 interval_tree_iter_next(struct rb_root_cached *root, 135 struct interval_tree_node *node, unsigned long start, unsigned long last) 136 { 137 struct interval_tree_node *next; 138 139 KASSERT(node != NULL); 140 next = rb_tree_iterate(&root->rb_root.rbr_tree, node, RB_DIR_RIGHT); 141 if (next == NULL) 142 return NULL; 143 if (last < next->start) 144 return NULL; 145 KASSERT(next->start <= last && next->last >= start); 146 147 return next; 148 } 149 150 #endif /* _LINUX_INTERVAL_TREE_H_ */ 151