drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h

   1 /*
   2  * Copyright (c) 2013, Cisco Systems, Inc. All rights reserved.
   3  *
   4  * This program is free software; you may redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; version 2 of the License.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   9  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  10  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  11  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  12  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  13  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  14  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  15  * SOFTWARE.
  16  *
  17  */
  18
  19 #ifndef USNIC_UIOM_INTERVAL_TREE_H_
  20 #define USNIC_UIOM_INTERVAL_TREE_H_
  21
  22 #include <linux/rbtree.h>
  23
  24 struct usnic_uiom_interval_node {
  25         struct rb_node                  rb;
  26         struct list_head                link;
  27         unsigned long                   start;
  28         unsigned long                   last;
  29         unsigned long                   __subtree_last;
  30         unsigned int                    ref_cnt;
  31         int                             flags;
  32 };
  33
  34 extern void
  35 usnic_uiom_interval_tree_insert(struct usnic_uiom_interval_node *node,
  36                                         struct rb_root *root);
  37 extern void
  38 usnic_uiom_interval_tree_remove(struct usnic_uiom_interval_node *node,
  39                                         struct rb_root *root);
  40 extern struct usnic_uiom_interval_node *
  41 usnic_uiom_interval_tree_iter_first(struct rb_root *root,
  42                                         unsigned long start,
  43                                         unsigned long last);
  44 extern struct usnic_uiom_interval_node *
  45 usnic_uiom_interval_tree_iter_next(struct usnic_uiom_interval_node *node,
  46                         unsigned long start, unsigned long last);
  47 /*
  48  * Inserts {start...last} into {root}.  If there are overlaps,
  49  * nodes will be broken up and merged
  50  */
  51 int usnic_uiom_insert_interval(struct rb_root *root,
  52                                 unsigned long start, unsigned long last,
  53                                 int flags);
  54 /*
  55  * Removed {start...last} from {root}.  The nodes removed are returned in
  56  * 'removed.' The caller is responsibile for freeing memory of nodes in
  57  * 'removed.'
  58  */
  59 void usnic_uiom_remove_interval(struct rb_root *root,
  60                                 unsigned long start, unsigned long last,
  61                                 struct list_head *removed);
  62 /*
  63  * Returns {start...last} - {root} (relative complement of {start...last} in
  64  * {root}) in diff_set sorted ascendingly
  65  */
  66 int usnic_uiom_get_intervals_diff(unsigned long start,
  67                                         unsigned long last, int flags,
  68                                         int flag_mask,
  69                                         struct rb_root *root,
  70                                         struct list_head *diff_set);
  71 /* Call this to free diff_set returned by usnic_uiom_get_intervals_diff */
  72 void usnic_uiom_put_interval_set(struct list_head *intervals);
  73 #endif /* USNIC_UIOM_INTERVAL_TREE_H_ */