1e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi/* 2e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * Copyright (c) 2013, Cisco Systems, Inc. All rights reserved. 3e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * 4e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * This program is free software; you may redistribute it and/or modify 5e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * it under the terms of the GNU General Public License as published by 6e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * the Free Software Foundation; version 2 of the License. 7e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * 8e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 9e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 10e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 11e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 12e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 13e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 14e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 15e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * SOFTWARE. 16e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * 17e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi */ 18e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi 19e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi#ifndef USNIC_UIOM_INTERVAL_TREE_H_ 20e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi#define USNIC_UIOM_INTERVAL_TREE_H_ 21e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi 22e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi#include <linux/rbtree.h> 23e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi 24e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhistruct usnic_uiom_interval_node { 25e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi struct rb_node rb; 26e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi struct list_head link; 27e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi unsigned long start; 28e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi unsigned long last; 29e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi unsigned long __subtree_last; 30e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi unsigned int ref_cnt; 31e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi int flags; 32e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi}; 33e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi 34e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhiextern void 35e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhiusnic_uiom_interval_tree_insert(struct usnic_uiom_interval_node *node, 36e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi struct rb_root *root); 37e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhiextern void 38e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhiusnic_uiom_interval_tree_remove(struct usnic_uiom_interval_node *node, 39e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi struct rb_root *root); 40e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhiextern struct usnic_uiom_interval_node * 41e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhiusnic_uiom_interval_tree_iter_first(struct rb_root *root, 42e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi unsigned long start, 43e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi unsigned long last); 44e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhiextern struct usnic_uiom_interval_node * 45e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhiusnic_uiom_interval_tree_iter_next(struct usnic_uiom_interval_node *node, 46e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi unsigned long start, unsigned long last); 47e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi/* 48e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * Inserts {start...last} into {root}. If there are overlaps, 49e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * nodes will be broken up and merged 50e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi */ 51e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhiint usnic_uiom_insert_interval(struct rb_root *root, 52e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi unsigned long start, unsigned long last, 53e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi int flags); 54e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi/* 55e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * Removed {start...last} from {root}. The nodes removed are returned in 56e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * 'removed.' The caller is responsibile for freeing memory of nodes in 57e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * 'removed.' 58e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi */ 59e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhivoid usnic_uiom_remove_interval(struct rb_root *root, 60e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi unsigned long start, unsigned long last, 61e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi struct list_head *removed); 62e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi/* 63e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * Returns {start...last} - {root} (relative complement of {start...last} in 64e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi * {root}) in diff_set sorted ascendingly 65e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi */ 66e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhiint usnic_uiom_get_intervals_diff(unsigned long start, 67e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi unsigned long last, int flags, 68e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi int flag_mask, 69e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi struct rb_root *root, 70e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi struct list_head *diff_set); 71e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi/* Call this to free diff_set returned by usnic_uiom_get_intervals_diff */ 72e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhivoid usnic_uiom_put_interval_set(struct list_head *intervals); 73e3cf00d0a87f025db5855a43a67c67a41fa79fefUpinder Malhi#endif /* USNIC_UIOM_INTERVAL_TREE_H_ */ 74