Upinder Malhi | e3cf00d | 2013-09-10 03:38:16 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (c) 2013, Cisco Systems, Inc. All rights reserved. |
| 3 | * |
Jeff Squyres | 3805ead | 2015-09-30 13:34:00 -0700 | [diff] [blame] | 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. |
Upinder Malhi | e3cf00d | 2013-09-10 03:38:16 +0000 | [diff] [blame] | 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 | |
Upinder Malhi | e3cf00d | 2013-09-10 03:38:16 +0000 | [diff] [blame] | 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, |
Davidlohr Bueso | f808c13 | 2017-09-08 16:15:08 -0700 | [diff] [blame^] | 51 | struct rb_root_cached *root); |
Upinder Malhi | e3cf00d | 2013-09-10 03:38:16 +0000 | [diff] [blame] | 52 | extern void |
| 53 | usnic_uiom_interval_tree_remove(struct usnic_uiom_interval_node *node, |
Davidlohr Bueso | f808c13 | 2017-09-08 16:15:08 -0700 | [diff] [blame^] | 54 | struct rb_root_cached *root); |
Upinder Malhi | e3cf00d | 2013-09-10 03:38:16 +0000 | [diff] [blame] | 55 | extern struct usnic_uiom_interval_node * |
Davidlohr Bueso | f808c13 | 2017-09-08 16:15:08 -0700 | [diff] [blame^] | 56 | usnic_uiom_interval_tree_iter_first(struct rb_root_cached *root, |
Upinder Malhi | e3cf00d | 2013-09-10 03:38:16 +0000 | [diff] [blame] | 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 | */ |
Davidlohr Bueso | f808c13 | 2017-09-08 16:15:08 -0700 | [diff] [blame^] | 66 | int usnic_uiom_insert_interval(struct rb_root_cached *root, |
Upinder Malhi | e3cf00d | 2013-09-10 03:38:16 +0000 | [diff] [blame] | 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 | */ |
Davidlohr Bueso | f808c13 | 2017-09-08 16:15:08 -0700 | [diff] [blame^] | 74 | void usnic_uiom_remove_interval(struct rb_root_cached *root, |
Upinder Malhi | e3cf00d | 2013-09-10 03:38:16 +0000 | [diff] [blame] | 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, |
Davidlohr Bueso | f808c13 | 2017-09-08 16:15:08 -0700 | [diff] [blame^] | 84 | struct rb_root_cached *root, |
Upinder Malhi | e3cf00d | 2013-09-10 03:38:16 +0000 | [diff] [blame] | 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_ */ |