interval_tree_generic.h revision 1.3
1 /* $NetBSD: interval_tree_generic.h,v 1.3 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 #ifndef _LINUX_INTERVAL_TREE_GENERIC_H_ 33 #define _LINUX_INTERVAL_TREE_GENERIC_H_ 34 35 #define INTERVAL_TREE_DEFINE(T, F, KT, KLAST, NSTART, NLAST, QUAL, PREFIX) \ 36 \ 37 static inline int \ 38 PREFIX##__compare_nodes(void *__cookie, const void *__va, const void *__vb) \ 39 { \ 40 const T *__na = __va; \ 41 const T *__nb = __vb; \ 42 const KT __astart = START(__na), __alast = LAST(__na); \ 43 const KT __bstart = START(__nb), __blast = LAST(__nb); \ 44 \ 45 if (__astart < __bstart) \ 46 return -1; \ 47 if (__astart > __bstart) \ 48 return +1; \ 49 if (__alast < __blast) \ 50 return -1; \ 51 if (__alast > __blast) \ 52 return -1; \ 53 return 0; \ 54 } \ 55 \ 56 static inline int \ 57 PREFIX##__compare_key(void *__cookie, const void *__vn, const void *__vk) \ 58 { \ 59 const T *__n = __vn; \ 60 const KT *__k = __vk; \ 61 const KT __nstart = START(__n), __nlast = LAST(__n); \ 62 \ 63 if (__nlast < *__k) \ 64 return -1; \ 65 if (*__k < __nstart) \ 66 return +1; \ 67 return 0; \ 68 } \ 69 \ 70 static const rb_tree_ops_t PREFIX##__rbtree_ops = { \ 71 .rbto_compare_nodes = PREFIX##__compare_nodes, \ 72 .rbto_compare_key = PREFIX##__compare_key, \ 73 .rbto_node_offset = offsetof(T, F), \ 74 }; \ 75 \ 76 /* Not in Linux API, needed for us. */ \ 77 QUAL void \ 78 PREFIX##_init(struct rb_root_cached *__root) \ 79 { \ 80 rb_tree_init(&__root->rb_root.rbr_tree, &PREFIX##__rbtree_ops); \ 81 } \ 82 \ 83 QUAL void \ 84 PREFIX##_insert(T *__node, struct rb_root_cached *__root) \ 85 { \ 86 T *__collision __diagused; \ 87 \ 88 __collision = rb_tree_insert_node(&__root->rb_root.rbr_tree, __node); \ 89 KASSERT(__collision == __node); \ 90 } \ 91 \ 92 QUAL void \ 93 PREFIX##_remove(T *__node, struct rb_root_cached *__root) \ 94 { \ 95 rb_tree_remove_node(&__root->rb_root.rbr_tree, __node); \ 96 } \ 97 \ 98 QUAL T * \ 99 PREFIX##_iter_first(struct rb_root_cached *__root, KT __start, KT __last) \ 100 { \ 101 T *__node; \ 102 \ 103 __node = rb_tree_find_node_geq(&__root->rb_root.rbr_tree, &__start); \ 104 if (__node == NULL) \ 105 return NULL; \ 106 KASSERT(START(__node) <= __start); \ 107 if (__last < START(__node)) \ 108 return NULL; \ 109 \ 110 return __node; \ 111 } 112 113 #endif /* _LINUX_INTERVAL_TREE_GENERIC_H_ */ 114
Indexes created Tue Sep 30 20:09:53 GMT 2025