89 lines · c
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 two5 * licenses. You may choose to be licensed under the terms of the GNU6 * General Public License (GPL) Version 2, available from the file7 * COPYING in the main directory of this source tree, or the8 * BSD license below:9 *10 * Redistribution and use in source and binary forms, with or11 * without modification, are permitted provided that the following12 * conditions are met:13 *14 * - Redistributions of source code must retain the above15 * copyright notice, this list of conditions and the following16 * disclaimer.17 *18 * - Redistributions in binary form must reproduce the above19 * copyright notice, this list of conditions and the following20 * disclaimer in the documentation and/or other materials21 * 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 OF25 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND26 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS27 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN28 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN29 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE30 * 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 39struct 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 49extern void50usnic_uiom_interval_tree_insert(struct usnic_uiom_interval_node *node,51 struct rb_root_cached *root);52extern void53usnic_uiom_interval_tree_remove(struct usnic_uiom_interval_node *node,54 struct rb_root_cached *root);55extern struct usnic_uiom_interval_node *56usnic_uiom_interval_tree_iter_first(struct rb_root_cached *root,57 unsigned long start,58 unsigned long last);59extern struct usnic_uiom_interval_node *60usnic_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 merged65 */66int 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 in71 * 'removed.' The caller is responsibile for freeing memory of nodes in72 * 'removed.'73 */74void 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} in79 * {root}) in diff_set sorted ascendingly80 */81int 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 */87void usnic_uiom_put_interval_set(struct list_head *intervals);88#endif /* USNIC_UIOM_INTERVAL_TREE_H_ */89