Edit File: interval_tree_generic.h
/* 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)) { \ gmb(); \ link = &parent->ITRB.rb_left; \ } else { \ gmb(); \ 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; \ } \ }