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