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_subtree_search(struct usnic_uiom_interval_node *node, 57 unsigned long start, 58 unsigned long last); 59 extern struct usnic_uiom_interval_node * 60 usnic_uiom_interval_tree_iter_first(struct rb_root_cached *root, 61 unsigned long start, 62 unsigned long last); 63 extern struct usnic_uiom_interval_node * 64 usnic_uiom_interval_tree_iter_next(struct usnic_uiom_interval_node *node, 65 unsigned long start, unsigned long last); 66 /* 67 * Inserts {start...last} into {root}. If there are overlaps, 68 * nodes will be broken up and merged 69 */ 70 int usnic_uiom_insert_interval(struct rb_root_cached *root, 71 unsigned long start, unsigned long last, 72 int flags); 73 /* 74 * Removed {start...last} from {root}. The nodes removed are returned in 75 * 'removed.' The caller is responsibile for freeing memory of nodes in 76 * 'removed.' 77 */ 78 void usnic_uiom_remove_interval(struct rb_root_cached *root, 79 unsigned long start, unsigned long last, 80 struct list_head *removed); 81 /* 82 * Returns {start...last} - {root} (relative complement of {start...last} in 83 * {root}) in diff_set sorted ascendingly 84 */ 85 int usnic_uiom_get_intervals_diff(unsigned long start, 86 unsigned long last, int flags, 87 int flag_mask, 88 struct rb_root_cached *root, 89 struct list_head *diff_set); 90 /* Call this to free diff_set returned by usnic_uiom_get_intervals_diff */ 91 void usnic_uiom_put_interval_set(struct list_head *intervals); 92 #endif /* USNIC_UIOM_INTERVAL_TREE_H_ */ 93