sys/dev/drm/linux_interval_tree.c

   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 }