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_ */ 74