| Author | Tokens | Token Proportion | Commits | Commit Proportion |
|---|---|---|---|---|
| Michel Lespinasse | 52 | 91.23% | 1 | 33.33% |
| Davidlohr Bueso A | 5 | 8.77% | 2 | 66.67% |
| Total | 57 | 3 |
/* 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 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_cached *root) \ { \ struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \ ITTYPE start = ITSTART(node), last = ITLAST(node); \ ITSTRUCT *parent; \ bool leftmost = true; \ \ 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; \ leftmost = false; \ } \ } \ \ node->ITSUBTREE = last; \ rb_link_node(&node->ITRB, rb_parent, link); \ rb_insert_augmented_cached(&node->ITRB, root, \ leftmost, &ITPREFIX ## _augment); \ } \ \ ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \ struct rb_root_cached *root) \ { \ rb_erase_augmented_cached(&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_cached *root, \ ITTYPE start, ITTYPE last) \ { \ ITSTRUCT *node, *leftmost; \ \ if (!root->rb_root.rb_node) \ return NULL; \ \ /* \ * Fastpath range intersection/overlap between A: [a0, a1] and \ * B: [b0, b1] is given by: \ * \ * a0 <= b1 && b0 <= a1 \ * \ * ... where A holds the lock range and B holds the smallest \ * 'start' and largest 'last' in the tree. For the later, we \ * rely on the root node, which by augmented interval tree \ * property, holds the largest value in its last-in-subtree. \ * This allows mitigating some of the tree walk overhead for \ * for non-intersecting ranges, maintained and consulted in O(1). \ */ \ node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \ if (node->ITSUBTREE < start) \ return NULL; \ \ leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB); \ if (ITSTART(leftmost) > last) \ 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; \ } \ }
Information contained on this website is for historical information purposes only and does not indicate or represent copyright ownership.
Created with Cregit http://github.com/cregit/cregit
Version 2.0-RC1