0,0 → 1,191 |
/* |
Interval Trees |
(C) 2012 Michel Lespinasse <walken@google.com> |
|
This program is free software; you can redistribute it and/or modify |
it under the terms of the GNU General Public License as published by |
the Free Software Foundation; either version 2 of the License, or |
(at your option) any later version. |
|
This program is distributed in the hope that it will be useful, |
but WITHOUT ANY WARRANTY; without even the implied warranty of |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
GNU General Public License for more details. |
|
You should have received a copy of the GNU General Public License |
along with this program; if not, write to the Free Software |
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
|
include/linux/interval_tree_generic.h |
*/ |
|
#include <linux/rbtree_augmented.h> |
|
/* |
* Template for implementing interval trees |
* |
* ITSTRUCT: struct type of the interval tree nodes |
* ITRB: name of struct rb_node field within ITSTRUCT |
* ITTYPE: type of the interval endpoints |
* ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree |
* ITSTART(n): start endpoint of ITSTRUCT node n |
* ITLAST(n): last endpoint of ITSTRUCT node n |
* ITSTATIC: 'static' or empty |
* ITPREFIX: prefix to use for the inline tree definitions |
* |
* Note - before using this, please consider if non-generic version |
* (interval_tree.h) would work for you... |
*/ |
|
#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, \ |
ITSTART, ITLAST, ITSTATIC, ITPREFIX) \ |
\ |
/* Callbacks for augmented rbtree insert and remove */ \ |
\ |
static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node) \ |
{ \ |
ITTYPE max = ITLAST(node), subtree_last; \ |
if (node->ITRB.rb_left) { \ |
subtree_last = rb_entry(node->ITRB.rb_left, \ |
ITSTRUCT, ITRB)->ITSUBTREE; \ |
if (max < subtree_last) \ |
max = subtree_last; \ |
} \ |
if (node->ITRB.rb_right) { \ |
subtree_last = rb_entry(node->ITRB.rb_right, \ |
ITSTRUCT, ITRB)->ITSUBTREE; \ |
if (max < subtree_last) \ |
max = subtree_last; \ |
} \ |
return max; \ |
} \ |
\ |
RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB, \ |
ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last) \ |
\ |
/* Insert / remove interval nodes from the tree */ \ |
\ |
ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root) \ |
{ \ |
struct rb_node **link = &root->rb_node, *rb_parent = NULL; \ |
ITTYPE start = ITSTART(node), last = ITLAST(node); \ |
ITSTRUCT *parent; \ |
\ |
while (*link) { \ |
rb_parent = *link; \ |
parent = rb_entry(rb_parent, ITSTRUCT, ITRB); \ |
if (parent->ITSUBTREE < last) \ |
parent->ITSUBTREE = last; \ |
if (start < ITSTART(parent)) \ |
link = &parent->ITRB.rb_left; \ |
else \ |
link = &parent->ITRB.rb_right; \ |
} \ |
\ |
node->ITSUBTREE = last; \ |
rb_link_node(&node->ITRB, rb_parent, link); \ |
rb_insert_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \ |
} \ |
\ |
ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, struct rb_root *root) \ |
{ \ |
rb_erase_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \ |
} \ |
\ |
/* \ |
* Iterate over intervals intersecting [start;last] \ |
* \ |
* Note that a node's interval intersects [start;last] iff: \ |
* Cond1: ITSTART(node) <= last \ |
* and \ |
* Cond2: start <= ITLAST(node) \ |
*/ \ |
\ |
static ITSTRUCT * \ |
ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ |
{ \ |
while (true) { \ |
/* \ |
* Loop invariant: start <= node->ITSUBTREE \ |
* (Cond2 is satisfied by one of the subtree nodes) \ |
*/ \ |
if (node->ITRB.rb_left) { \ |
ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \ |
ITSTRUCT, ITRB); \ |
if (start <= left->ITSUBTREE) { \ |
/* \ |
* Some nodes in left subtree satisfy Cond2. \ |
* Iterate to find the leftmost such node N. \ |
* If it also satisfies Cond1, that's the \ |
* match we are looking for. Otherwise, there \ |
* is no matching interval as nodes to the \ |
* right of N can't satisfy Cond1 either. \ |
*/ \ |
node = left; \ |
continue; \ |
} \ |
} \ |
if (ITSTART(node) <= last) { /* Cond1 */ \ |
if (start <= ITLAST(node)) /* Cond2 */ \ |
return node; /* node is leftmost match */ \ |
if (node->ITRB.rb_right) { \ |
node = rb_entry(node->ITRB.rb_right, \ |
ITSTRUCT, ITRB); \ |
if (start <= node->ITSUBTREE) \ |
continue; \ |
} \ |
} \ |
return NULL; /* No match */ \ |
} \ |
} \ |
\ |
ITSTATIC ITSTRUCT * \ |
ITPREFIX ## _iter_first(struct rb_root *root, ITTYPE start, ITTYPE last) \ |
{ \ |
ITSTRUCT *node; \ |
\ |
if (!root->rb_node) \ |
return NULL; \ |
node = rb_entry(root->rb_node, ITSTRUCT, ITRB); \ |
if (node->ITSUBTREE < start) \ |
return NULL; \ |
return ITPREFIX ## _subtree_search(node, start, last); \ |
} \ |
\ |
ITSTATIC ITSTRUCT * \ |
ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ |
{ \ |
struct rb_node *rb = node->ITRB.rb_right, *prev; \ |
\ |
while (true) { \ |
/* \ |
* Loop invariants: \ |
* Cond1: ITSTART(node) <= last \ |
* rb == node->ITRB.rb_right \ |
* \ |
* First, search right subtree if suitable \ |
*/ \ |
if (rb) { \ |
ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); \ |
if (start <= right->ITSUBTREE) \ |
return ITPREFIX ## _subtree_search(right, \ |
start, last); \ |
} \ |
\ |
/* Move up the tree until we come from a node's left child */ \ |
do { \ |
rb = rb_parent(&node->ITRB); \ |
if (!rb) \ |
return NULL; \ |
prev = &node->ITRB; \ |
node = rb_entry(rb, ITSTRUCT, ITRB); \ |
rb = node->ITRB.rb_right; \ |
} while (prev == rb); \ |
\ |
/* Check if the node intersects [start;last] */ \ |
if (last < ITSTART(node)) /* !Cond1 */ \ |
return NULL; \ |
else if (start <= ITLAST(node)) /* Cond2 */ \ |
return node; \ |
} \ |
} |