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