1 /* $NetBSD: interval_tree.h,v 1.8 2019/01/04 20:22:32 tnn 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 #ifndef _LINUX_INTERVAL_TREE_H_ 33 #define _LINUX_INTERVAL_TREE_H_ 34 35 #include <sys/rbtree.h> 36 37 struct rb_root { 38 struct rb_tree rbr_tree; 39 }; 40 41 static inline bool 42 RB_EMPTY_ROOT(struct rb_root *root) 43 { 44 45 return RB_TREE_MIN(&root->rbr_tree) == NULL; 46 } 47 48 struct interval_tree_node { 49 struct rb_node itn_node; 50 unsigned long start; /* inclusive */ 51 unsigned long last; /* inclusive */ 52 }; 53 54 static inline int 55 interval_tree_compare_nodes(void *cookie, const void *va, const void *vb) 56 { 57 const struct interval_tree_node *na = va; 58 const struct interval_tree_node *nb = vb; 59 60 if (na->start < nb->start) 61 return -1; 62 if (na->start > nb->start) 63 return +1; 64 if (na->last < nb->last) 65 return -1; 66 if (na->last > nb->last) 67 return +1; 68 return 0; 69 } 70 71 static inline int 72 interval_tree_compare_key(void *cookie, const void *vn, const void *vk) 73 { 74 const struct interval_tree_node *n = vn; 75 const unsigned long *k = vk; 76 77 if (n->start < *k) 78 return -1; 79 if (*k < n->start) 80 return +1; 81 return 0; 82 } 83 84 static const rb_tree_ops_t interval_tree_ops = { 85 .rbto_compare_nodes = interval_tree_compare_nodes, 86 .rbto_compare_key = interval_tree_compare_key, 87 .rbto_node_offset = offsetof(struct interval_tree_node, itn_node), 88 }; 89 90 static inline void 91 interval_tree_init(struct rb_root *root) 92 { 93 94 rb_tree_init(&root->rbr_tree, &interval_tree_ops); 95 } 96 97 static inline void 98 interval_tree_insert(struct interval_tree_node *node, struct rb_root *root) 99 { 100 struct interval_tree_node *collision __diagused; 101 102 collision = rb_tree_insert_node(&root->rbr_tree, node); 103 KASSERT(collision == node); 104 } 105 106 static inline void 107 interval_tree_remove(struct interval_tree_node *node, struct rb_root *root) 108 { 109 110 rb_tree_remove_node(&root->rbr_tree, node); 111 } 112 113 static inline struct interval_tree_node * 114 interval_tree_iter_first(struct rb_root *root, unsigned long start, 115 unsigned long last) 116 { 117 struct interval_tree_node *node; 118 119 node = rb_tree_find_node_geq(&root->rbr_tree, &start); 120 if (node == NULL) 121 return NULL; 122 if (last < node->start) 123 return NULL; 124 KASSERT(node->start <= last && node->last >= start); 125 126 return node; 127 } 128 129 /* 130 * XXX Linux's interval_tree_iter_next doesn't take the root as an 131 * argument, which makes this difficult. So we'll just patch those 132 * uses. 133 */ 134 static inline struct interval_tree_node * 135 interval_tree_iter_next(struct rb_root *root, struct interval_tree_node *node, 136 unsigned long start, unsigned long last) 137 { 138 struct interval_tree_node *next; 139 140 KASSERT(node != NULL); 141 next = rb_tree_iterate(&root->rbr_tree, node, RB_DIR_RIGHT); 142 if (next == NULL) 143 return NULL; 144 if (last < next->start) 145 return NULL; 146 KASSERT(next->start <= last && next->last >= start); 147 148 return next; 149 } 150 151 /* 152 * XXX This is not actually postorder, but I can't fathom why you would 153 * want postorder for an ordered tree; different insertion orders lead 154 * to different traversal orders. 155 */ 156 #define rbtree_postorder_for_each_entry_safe(NODE, TMP, ROOT, FIELD) \ 157 for ((NODE) = RB_TREE_MIN(&(ROOT)->rbr_tree); \ 158 ((NODE) != NULL && \ 159 ((TMP) = rb_tree_iterate(&(ROOT)->rbr_tree, (NODE), \ 160 RB_DIR_RIGHT))); \ 161 (NODE) = (TMP)) 162 163 #endif /* _LINUX_INTERVAL_TREE_H_ */ 164