1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3 * 4 * Copyright (c) 2019 Mark Kettenis <kettenis@OpenBSD.org> 5 * Copyright (c) 2021 Vladimir Kondratyev <wulf@FreeBSD.org> 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice unmodified, this list of conditions, and the following 12 * disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 #include <linux/rbtree.h> 30 31 #define INTERVAL_TREE_DEFINE(type, field, valtype, dummy, START, LAST, \ 32 attr, name) \ 33 __IT_DEFINE_ITER_FROM(type, field, valtype, START, LAST, name) \ 34 __IT_DEFINE_ITER_FIRST(type, valtype, attr, name) \ 35 __IT_DEFINE_ITER_NEXT(type, field, valtype, attr, name) \ 36 __IT_DEFINE_INSERT(type, field, START, attr, name) \ 37 __IT_DEFINE_REMOVE(type, field, attr, name) 38 39 #define __IT_DEFINE_ITER_FROM(type, field, valtype, START, LAST, name) \ 40 static inline type * \ 41 name##_iter_from(struct rb_node *rb, valtype start, valtype last) \ 42 { \ 43 type *node; \ 44 \ 45 while (rb != NULL) { \ 46 node = rb_entry(rb, type, field); \ 47 if (LAST(node) >= start && START(node) <= last) \ 48 return (node); \ 49 else if (START(node) > last) \ 50 break; \ 51 rb = rb_next(rb); \ 52 } \ 53 return (NULL); \ 54 } 55 56 #define __IT_DEFINE_ITER_FIRST(type, valtype, attr, name) \ 57 attr type * \ 58 name##_iter_first(struct rb_root_cached *root, valtype start, valtype last) \ 59 { \ 60 return (name##_iter_from(rb_first_cached(root), start, last)); \ 61 } 62 63 #define __IT_DEFINE_ITER_NEXT(type, field, valtype, attr, name) \ 64 attr type * \ 65 name##_iter_next(type *node, valtype start, valtype last) \ 66 { \ 67 return (name##_iter_from(rb_next(&node->field), start, last)); \ 68 } 69 70 #define __IT_DEFINE_INSERT(type, field, START, attr, name) \ 71 attr void \ 72 name##_insert(type *node, struct rb_root_cached *root) \ 73 { \ 74 struct rb_node **iter = &root->rb_root.rb_node; \ 75 struct rb_node *parent = NULL; \ 76 type *iter_node; \ 77 bool min_entry = true; \ 78 \ 79 while (*iter != NULL) { \ 80 parent = *iter; \ 81 iter_node = rb_entry(parent, type, field); \ 82 if (START(node) < START(iter_node)) \ 83 iter = &parent->rb_left; \ 84 else { \ 85 iter = &parent->rb_right; \ 86 min_entry = false; \ 87 } \ 88 } \ 89 \ 90 rb_link_node(&node->field, parent, iter); \ 91 rb_insert_color_cached(&node->field, root, min_entry); \ 92 } 93 94 #define __IT_DEFINE_REMOVE(type, field, attr, name) \ 95 attr void \ 96 name##_remove(type *node, struct rb_root_cached *root) \ 97 { \ 98 rb_erase_cached(&node->field, root); \ 99 } 100