Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
interval_tree_generic.h
Go to the documentation of this file.
1 /*
2  Interval Trees
3  (C) 2012 Michel Lespinasse <[email protected]>
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 }
Generated on Thu Jan 10 2013 14:51:38 for Linux Kernel by   doxygen 1.8.2