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 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, \ |

69 | struct rb_root_cached *root) \ |

70 | { \ |

71 | struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \ |

72 | ITTYPE start = ITSTART(node), last = ITLAST(node); \ |

73 | ITSTRUCT *parent; \ |

74 | bool leftmost = true; \ |

75 | \ |

76 | while (*link) { \ |

77 | rb_parent = *link; \ |

78 | parent = rb_entry(rb_parent, ITSTRUCT, ITRB); \ |

79 | if (parent->ITSUBTREE < last) \ |

80 | parent->ITSUBTREE = last; \ |

81 | if (start < ITSTART(parent)) \ |

82 | link = &parent->ITRB.rb_left; \ |

83 | else { \ |

84 | link = &parent->ITRB.rb_right; \ |

85 | leftmost = false; \ |

86 | } \ |

87 | } \ |

88 | \ |

89 | node->ITSUBTREE = last; \ |

90 | rb_link_node(&node->ITRB, rb_parent, link); \ |

91 | rb_insert_augmented_cached(&node->ITRB, root, \ |

92 | leftmost, &ITPREFIX ## _augment); \ |

93 | } \ |

94 | \ |

95 | ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \ |

96 | struct rb_root_cached *root) \ |

97 | { \ |

98 | rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment); \ |

99 | } \ |

100 | \ |

101 | /* \ |

102 | * Iterate over intervals intersecting [start;last] \ |

103 | * \ |

104 | * Note that a node's interval intersects [start;last] iff: \ |

105 | * Cond1: ITSTART(node) <= last \ |

106 | * and \ |

107 | * Cond2: start <= ITLAST(node) \ |

108 | */ \ |

109 | \ |

110 | static ITSTRUCT * \ |

111 | ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ |

112 | { \ |

113 | while (true) { \ |

114 | /* \ |

115 | * Loop invariant: start <= node->ITSUBTREE \ |

116 | * (Cond2 is satisfied by one of the subtree nodes) \ |

117 | */ \ |

118 | if (node->ITRB.rb_left) { \ |

119 | ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \ |

120 | ITSTRUCT, ITRB); \ |

121 | if (start <= left->ITSUBTREE) { \ |

122 | /* \ |

123 | * Some nodes in left subtree satisfy Cond2. \ |

124 | * Iterate to find the leftmost such node N. \ |

125 | * If it also satisfies Cond1, that's the \ |

126 | * match we are looking for. Otherwise, there \ |

127 | * is no matching interval as nodes to the \ |

128 | * right of N can't satisfy Cond1 either. \ |

129 | */ \ |

130 | node = left; \ |

131 | continue; \ |

132 | } \ |

133 | } \ |

134 | if (ITSTART(node) <= last) { /* Cond1 */ \ |

135 | if (start <= ITLAST(node)) /* Cond2 */ \ |

136 | return node; /* node is leftmost match */ \ |

137 | if (node->ITRB.rb_right) { \ |

138 | node = rb_entry(node->ITRB.rb_right, \ |

139 | ITSTRUCT, ITRB); \ |

140 | if (start <= node->ITSUBTREE) \ |

141 | continue; \ |

142 | } \ |

143 | } \ |

144 | return NULL; /* No match */ \ |

145 | } \ |

146 | } \ |

147 | \ |

148 | ITSTATIC ITSTRUCT * \ |

149 | ITPREFIX ## _iter_first(struct rb_root_cached *root, \ |

150 | ITTYPE start, ITTYPE last) \ |

151 | { \ |

152 | ITSTRUCT *node, *leftmost; \ |

153 | \ |

154 | if (!root->rb_root.rb_node) \ |

155 | return NULL; \ |

156 | \ |

157 | /* \ |

158 | * Fastpath range intersection/overlap between A: [a0, a1] and \ |

159 | * B: [b0, b1] is given by: \ |

160 | * \ |

161 | * a0 <= b1 && b0 <= a1 \ |

162 | * \ |

163 | * ... where A holds the lock range and B holds the smallest \ |

164 | * 'start' and largest 'last' in the tree. For the later, we \ |

165 | * rely on the root node, which by augmented interval tree \ |

166 | * property, holds the largest value in its last-in-subtree. \ |

167 | * This allows mitigating some of the tree walk overhead for \ |

168 | * for non-intersecting ranges, maintained and consulted in O(1). \ |

169 | */ \ |

170 | node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \ |

171 | if (node->ITSUBTREE < start) \ |

172 | return NULL; \ |

173 | \ |

174 | leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB); \ |

175 | if (ITSTART(leftmost) > last) \ |

176 | return NULL; \ |

177 | \ |

178 | return ITPREFIX ## _subtree_search(node, start, last); \ |

179 | } \ |

180 | \ |

181 | ITSTATIC ITSTRUCT * \ |

182 | ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ |

183 | { \ |

184 | struct rb_node *rb = node->ITRB.rb_right, *prev; \ |

185 | \ |

186 | while (true) { \ |

187 | /* \ |

188 | * Loop invariants: \ |

189 | * Cond1: ITSTART(node) <= last \ |

190 | * rb == node->ITRB.rb_right \ |

191 | * \ |

192 | * First, search right subtree if suitable \ |

193 | */ \ |

194 | if (rb) { \ |

195 | ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); \ |

196 | if (start <= right->ITSUBTREE) \ |

197 | return ITPREFIX ## _subtree_search(right, \ |

198 | start, last); \ |

199 | } \ |

200 | \ |

201 | /* Move up the tree until we come from a node's left child */ \ |

202 | do { \ |

203 | rb = rb_parent(&node->ITRB); \ |

204 | if (!rb) \ |

205 | return NULL; \ |

206 | prev = &node->ITRB; \ |

207 | node = rb_entry(rb, ITSTRUCT, ITRB); \ |

208 | rb = node->ITRB.rb_right; \ |

209 | } while (prev == rb); \ |

210 | \ |

211 | /* Check if the node intersects [start;last] */ \ |

212 | if (last < ITSTART(node)) /* !Cond1 */ \ |

213 | return NULL; \ |

214 | else if (start <= ITLAST(node)) /* Cond2 */ \ |

215 | return node; \ |

216 | } \ |

217 | } |

218 |