1/* $NetBSD: interval_tree.h,v 1.14 2023/05/01 09:41:55 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 45struct interval_tree_node { 46 struct rb_node rb; 47 unsigned long start; /* inclusive */ 48 unsigned long last; /* inclusive */ 49}; 50 51static inline int 52interval_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 68static inline int 69interval_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 81static 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, rb), 85}; 86 87static inline void 88interval_tree_init(struct rb_root_cached *root) 89{ 90 91 rb_tree_init(&root->rb_root.rbr_tree, &interval_tree_ops); 92} 93 94static inline void 95interval_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 104static inline void 105interval_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 112static inline struct interval_tree_node * 113interval_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); 124 KASSERT(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 */ 134static inline struct interval_tree_node * 135interval_tree_iter_next(struct rb_root_cached *root, 136 struct interval_tree_node *node, unsigned long start, unsigned long last) 137{ 138 struct interval_tree_node *next; 139 140 KASSERT(node != NULL); 141 next = rb_tree_iterate(&root->rb_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); 147 KASSERT(next->last >= start); 148 149 return next; 150} 151 152#endif /* _LINUX_INTERVAL_TREE_H_ */ 153