1 /* 2 * Copyright (c) 2013, Cisco Systems, Inc. All rights reserved. 3 * 4 * This software is available to you under a choice of one of two 5 * licenses. You may choose to be licensed under the terms of the GNU 6 * General Public License (GPL) Version 2, available from the file 7 * COPYING in the main directory of this source tree, or the 8 * BSD license below: 9 * 10 * Redistribution and use in source and binary forms, with or 11 * without modification, are permitted provided that the following 12 * conditions are met: 13 * 14 * - Redistributions of source code must retain the above 15 * copyright notice, this list of conditions and the following 16 * disclaimer. 17 * 18 * - Redistributions in binary form must reproduce the above 19 * copyright notice, this list of conditions and the following 20 * disclaimer in the documentation and/or other materials 21 * provided with the distribution. 22 * 23 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 24 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 25 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 26 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 27 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 28 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 29 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 30 * SOFTWARE. 31 * 32 */ 33 34 #ifndef USNIC_UIOM_INTERVAL_TREE_H_ 35 #define USNIC_UIOM_INTERVAL_TREE_H_ 36 37 #include <linux/rbtree.h> 38 39 struct usnic_uiom_interval_node { 40 struct rb_node rb; 41 struct list_head link; 42 unsigned long start; 43 unsigned long last; 44 unsigned long __subtree_last; 45 unsigned int ref_cnt; 46 int flags; 47 }; 48 49 extern void 50 usnic_uiom_interval_tree_insert(struct usnic_uiom_interval_node *node, 51 struct rb_root_cached *root); 52 extern void 53 usnic_uiom_interval_tree_remove(struct usnic_uiom_interval_node *node, 54 struct rb_root_cached *root); 55 extern struct usnic_uiom_interval_node * 56 usnic_uiom_interval_tree_iter_first(struct rb_root_cached *root, 57 unsigned long start, 58 unsigned long last); 59 extern struct usnic_uiom_interval_node * 60 usnic_uiom_interval_tree_iter_next(struct usnic_uiom_interval_node *node, 61 unsigned long start, unsigned long last); 62 /* 63 * Inserts {start...last} into {root}. If there are overlaps, 64 * nodes will be broken up and merged 65 */ 66 int usnic_uiom_insert_interval(struct rb_root_cached *root, 67 unsigned long start, unsigned long last, 68 int flags); 69 /* 70 * Removed {start...last} from {root}. The nodes removed are returned in 71 * 'removed.' The caller is responsibile for freeing memory of nodes in 72 * 'removed.' 73 */ 74 void usnic_uiom_remove_interval(struct rb_root_cached *root, 75 unsigned long start, unsigned long last, 76 struct list_head *removed); 77 /* 78 * Returns {start...last} - {root} (relative complement of {start...last} in 79 * {root}) in diff_set sorted ascendingly 80 */ 81 int usnic_uiom_get_intervals_diff(unsigned long start, 82 unsigned long last, int flags, 83 int flag_mask, 84 struct rb_root_cached *root, 85 struct list_head *diff_set); 86 /* Call this to free diff_set returned by usnic_uiom_get_intervals_diff */ 87 void usnic_uiom_put_interval_set(struct list_head *intervals); 88 #endif /* USNIC_UIOM_INTERVAL_TREE_H_ */ 89