~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/include/linux/interval_tree_generic.h

Version: ~ [ linux-5.3-rc5 ] ~ [ linux-5.2.9 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.67 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.139 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.189 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.189 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.72 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2   Interval Trees
  3   (C) 2012  Michel Lespinasse <walken@google.com>
  4 
  5   This program is free software; you can redistribute it and/or modify
  6   it under the terms of the GNU General Public License as published by
  7   the Free Software Foundation; either version 2 of the License, or
  8   (at your option) any later version.
  9 
 10   This program is distributed in the hope that it will be useful,
 11   but WITHOUT ANY WARRANTY; without even the implied warranty of
 12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 13   GNU General Public License for more details.
 14 
 15   You should have received a copy of the GNU General Public License
 16   along with this program; if not, write to the Free Software
 17   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 18 
 19   include/linux/interval_tree_generic.h
 20 */
 21 
 22 #include <linux/rbtree_augmented.h>
 23 
 24 /*
 25  * Template for implementing interval trees
 26  *
 27  * ITSTRUCT:   struct type of the interval tree nodes
 28  * ITRB:       name of struct rb_node field within ITSTRUCT
 29  * ITTYPE:     type of the interval endpoints
 30  * ITSUBTREE:  name of ITTYPE field within ITSTRUCT holding last-in-subtree
 31  * ITSTART(n): start endpoint of ITSTRUCT node n
 32  * ITLAST(n):  last endpoint of ITSTRUCT node n
 33  * ITSTATIC:   'static' or empty
 34  * ITPREFIX:   prefix to use for the inline tree definitions
 35  *
 36  * Note - before using this, please consider if non-generic version
 37  * (interval_tree.h) would work for you...
 38  */
 39 
 40 #define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE,               \
 41                              ITSTART, ITLAST, ITSTATIC, ITPREFIX)             \
 42                                                                               \
 43 /* Callbacks for augmented rbtree insert and remove */                        \
 44                                                                               \
 45 static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node)        \
 46 {                                                                             \
 47         ITTYPE max = ITLAST(node), subtree_last;                              \
 48         if (node->ITRB.rb_left) {                                             \
 49                 subtree_last = rb_entry(node->ITRB.rb_left,                   \
 50                                         ITSTRUCT, ITRB)->ITSUBTREE;           \
 51                 if (max < subtree_last)                                       \
 52                         max = subtree_last;                                   \
 53         }                                                                     \
 54         if (node->ITRB.rb_right) {                                            \
 55                 subtree_last = rb_entry(node->ITRB.rb_right,                  \
 56                                         ITSTRUCT, ITRB)->ITSUBTREE;           \
 57                 if (max < subtree_last)                                       \
 58                         max = subtree_last;                                   \
 59         }                                                                     \
 60         return max;                                                           \
 61 }                                                                             \
 62                                                                               \
 63 RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB,            \
 64                      ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last)    \
 65                                                                               \
 66 /* Insert / remove interval nodes from the tree */                            \
 67                                                                               \
 68 ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root)       \
 69 {                                                                             \
 70         struct rb_node **link = &root->rb_node, *rb_parent = NULL;            \
 71         ITTYPE start = ITSTART(node), last = ITLAST(node);                    \
 72         ITSTRUCT *parent;                                                     \
 73                                                                               \
 74         while (*link) {                                                       \
 75                 rb_parent = *link;                                            \
 76                 parent = rb_entry(rb_parent, ITSTRUCT, ITRB);                 \
 77                 if (parent->ITSUBTREE < last)                                 \
 78                         parent->ITSUBTREE = last;                             \
 79                 if (start < ITSTART(parent))                                  \
 80                         link = &parent->ITRB.rb_left;                         \
 81                 else                                                          \
 82                         link = &parent->ITRB.rb_right;                        \
 83         }                                                                     \
 84                                                                               \
 85         node->ITSUBTREE = last;                                               \
 86         rb_link_node(&node->ITRB, rb_parent, link);                           \
 87         rb_insert_augmented(&node->ITRB, root, &ITPREFIX ## _augment);        \
 88 }                                                                             \
 89                                                                               \
 90 ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, struct rb_root *root)       \
 91 {                                                                             \
 92         rb_erase_augmented(&node->ITRB, root, &ITPREFIX ## _augment);         \
 93 }                                                                             \
 94                                                                               \
 95 /*                                                                            \
 96  * Iterate over intervals intersecting [start;last]                           \
 97  *                                                                            \
 98  * Note that a node's interval intersects [start;last] iff:                   \
 99  *   Cond1: ITSTART(node) <= last                                             \
100  * and                                                                        \
101  *   Cond2: start <= ITLAST(node)                                             \
102  */                                                                           \
103                                                                               \
104 static ITSTRUCT *                                                             \
105 ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last)        \
106 {                                                                             \
107         while (true) {                                                        \
108                 /*                                                            \
109                  * Loop invariant: start <= node->ITSUBTREE                   \
110                  * (Cond2 is satisfied by one of the subtree nodes)           \
111                  */                                                           \
112                 if (node->ITRB.rb_left) {                                     \
113                         ITSTRUCT *left = rb_entry(node->ITRB.rb_left,         \
114                                                   ITSTRUCT, ITRB);            \
115                         if (start <= left->ITSUBTREE) {                       \
116                                 /*                                            \
117                                  * Some nodes in left subtree satisfy Cond2.  \
118                                  * Iterate to find the leftmost such node N.  \
119                                  * If it also satisfies Cond1, that's the     \
120                                  * match we are looking for. Otherwise, there \
121                                  * is no matching interval as nodes to the    \
122                                  * right of N can't satisfy Cond1 either.     \
123                                  */                                           \
124                                 node = left;                                  \
125                                 continue;                                     \
126                         }                                                     \
127                 }                                                             \
128                 if (ITSTART(node) <= last) {            /* Cond1 */           \
129                         if (start <= ITLAST(node))      /* Cond2 */           \
130                                 return node;    /* node is leftmost match */  \
131                         if (node->ITRB.rb_right) {                            \
132                                 node = rb_entry(node->ITRB.rb_right,          \
133                                                 ITSTRUCT, ITRB);              \
134                                 if (start <= node->ITSUBTREE)                 \
135                                         continue;                             \
136                         }                                                     \
137                 }                                                             \
138                 return NULL;    /* No match */                                \
139         }                                                                     \
140 }                                                                             \
141                                                                               \
142 ITSTATIC ITSTRUCT *                                                           \
143 ITPREFIX ## _iter_first(struct rb_root *root, ITTYPE start, ITTYPE last)      \
144 {                                                                             \
145         ITSTRUCT *node;                                                       \
146                                                                               \
147         if (!root->rb_node)                                                   \
148                 return NULL;                                                  \
149         node = rb_entry(root->rb_node, ITSTRUCT, ITRB);                       \
150         if (node->ITSUBTREE < start)                                          \
151                 return NULL;                                                  \
152         return ITPREFIX ## _subtree_search(node, start, last);                \
153 }                                                                             \
154                                                                               \
155 ITSTATIC ITSTRUCT *                                                           \
156 ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last)             \
157 {                                                                             \
158         struct rb_node *rb = node->ITRB.rb_right, *prev;                      \
159                                                                               \
160         while (true) {                                                        \
161                 /*                                                            \
162                  * Loop invariants:                                           \
163                  *   Cond1: ITSTART(node) <= last                             \
164                  *   rb == node->ITRB.rb_right                                \
165                  *                                                            \
166                  * First, search right subtree if suitable                    \
167                  */                                                           \
168                 if (rb) {                                                     \
169                         ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB);       \
170                         if (start <= right->ITSUBTREE)                        \
171                                 return ITPREFIX ## _subtree_search(right,     \
172                                                                 start, last); \
173                 }                                                             \
174                                                                               \
175                 /* Move up the tree until we come from a node's left child */ \
176                 do {                                                          \
177                         rb = rb_parent(&node->ITRB);                          \
178                         if (!rb)                                              \
179                                 return NULL;                                  \
180                         prev = &node->ITRB;                                   \
181                         node = rb_entry(rb, ITSTRUCT, ITRB);                  \
182                         rb = node->ITRB.rb_right;                             \
183                 } while (prev == rb);                                         \
184                                                                               \
185                 /* Check if the node intersects [start;last] */               \
186                 if (last < ITSTART(node))               /* !Cond1 */          \
187                         return NULL;                                          \
188                 else if (start <= ITLAST(node))         /* Cond2 */           \
189                         return node;                                          \
190         }                                                                     \
191 }
192 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp