1 /* 2 * Copyright (c) 2019 Matthew Dillon <dillon@backplane.com> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice unmodified, this list of conditions, and the following 10 * disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 #include <linux/init.h> 28 #include <linux/interval_tree.h> 29 #include <linux/module.h> 30 31 typedef struct interval_tree_node itnode_t; 32 33 void 34 interval_tree_insert(struct interval_tree_node *node, struct rb_root *root) 35 { 36 itnode_t *scan; 37 38 scan = (itnode_t *)root->rb_node; 39 if (scan) { 40 node->next = scan->next; 41 node->atroot = 0; 42 scan->next = node; 43 } else { 44 root->rb_node = (void *)node; 45 node->atroot = 1; 46 node->next = node; 47 } 48 } 49 50 void 51 interval_tree_remove(struct interval_tree_node *node, struct rb_root *root) 52 { 53 itnode_t *scan; 54 55 scan = (itnode_t *)root->rb_node; 56 KKASSERT(scan != NULL); 57 while (scan->next != node) { 58 scan = scan->next; 59 } 60 scan->next = node->next; 61 if (scan == node) { 62 /* 63 * Last element is being removed 64 */ 65 root->rb_node = NULL; 66 node->atroot = 0; 67 } else if ((itnode_t *)root->rb_node == node) { 68 /* 69 * Root pointer is the node being removed, move the root 70 * pointer. 71 */ 72 node->atroot = 0; 73 scan->atroot = 1; 74 root->rb_node = (void *)scan; 75 } 76 } 77 78 struct interval_tree_node * 79 interval_tree_iter_first(struct rb_root *root, 80 unsigned long start, unsigned long last) 81 { 82 itnode_t *scan; 83 84 scan = (itnode_t *)root->rb_node; 85 if (scan) { 86 do { 87 if (start <= scan->last && 88 last >= scan->start) { 89 return scan; 90 } 91 scan = scan->next; 92 } while (scan->atroot == 0); 93 scan = NULL; 94 } 95 return scan; 96 } 97 98 struct interval_tree_node * 99 interval_tree_iter_next(struct interval_tree_node *node, 100 unsigned long start, unsigned long last) 101 { 102 itnode_t *scan; 103 104 scan = node->next; 105 while (scan->atroot == 0) { 106 if (start <= scan->last && 107 last >= scan->start) { 108 return scan; 109 } 110 scan = scan->next; 111 } 112 return NULL; 113 } 114