/*
  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;                                          \
        }                                                                     \
}