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/version.h>
  23 #include <linux/rbtree.h>
  24
  25 struct usnic_uiom_interval_node {
  26         struct rb_node                  rb;
  27         struct list_head                link;
  28         unsigned long                   start;
  29         unsigned long                   last;
  30         unsigned long                   __subtree_last;
  31         unsigned int                    ref_cnt;
  32         int                             flags;
  33 };
  34
  35 extern void
  36 usnic_uiom_interval_tree_insert(struct usnic_uiom_interval_node *node,
  37                                         struct rb_root *root);
  38 extern void
  39 usnic_uiom_interval_tree_remove(struct usnic_uiom_interval_node *node,
  40                                         struct rb_root *root);
  41 extern struct usnic_uiom_interval_node *
  42 usnic_uiom_interval_tree_iter_first(struct rb_root *root,
  43                                         unsigned long start,
  44                                         unsigned long last);
  45 extern struct usnic_uiom_interval_node *
  46 usnic_uiom_interval_tree_iter_next(struct usnic_uiom_interval_node *node,
  47                         unsigned long start, unsigned long last);
  48 /*
  49  * Inserts {start...last} into {root}.  If there are overlaps,
  50  * nodes will be broken up and merged
  51  */
  52 int usnic_uiom_insert_interval(struct rb_root *root,
  53                                 unsigned long start, unsigned long last,
  54                                 int flags);
  55 /*
  56  * Removed {start...last} from {root}.  The nodes removed are returned in
  57  * 'removed.' The caller is responsibile for freeing memory of nodes in
  58  * 'removed.'
  59  */
  60 void usnic_uiom_remove_interval(struct rb_root *root,
  61                                 unsigned long start, unsigned long last,
  62                                 struct list_head *removed);
  63 /*
  64  * Returns {start...last} - {root} (relative complement of {start...last} in
  65  * {root}) in diff_set sorted ascendingly
  66  */
  67 int usnic_uiom_get_intervals_diff(unsigned long start,
  68                                         unsigned long last, int flags,
  69                                         int flag_mask,
  70                                         struct rb_root *root,
  71                                         struct list_head *diff_set);
  72 /* Call this to free diff_set returned by usnic_uiom_get_intervals_diff */
  73 void usnic_uiom_put_interval_set(struct list_head *intervals);
  74 #endif /* USNIC_UIOM_INTERVAL_TREE_H_ */