Home | History | Annotate | Line # | Download | only in linux
interval_tree.h revision 1.1 
      1 /*	$NetBSD: interval_tree.h,v 1.1 2018/08/27 06:32:17 riastradh Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 2018 The NetBSD Foundation, Inc.
      5  * All rights reserved.
      6  *
      7  * This code is derived from software contributed to The NetBSD Foundation
      8  * by Taylor R. Campbell.
      9  *
     10  * Redistribution and use in source and binary forms, with or without
     11  * modification, are permitted provided that the following conditions
     12  * are met:
     13  * 1. Redistributions of source code must retain the above copyright
     14  *    notice, this list of conditions and the following disclaimer.
     15  * 2. Redistributions in binary form must reproduce the above copyright
     16  *    notice, this list of conditions and the following disclaimer in the
     17  *    documentation and/or other materials provided with the distribution.
     18  *
     19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     29  * POSSIBILITY OF SUCH DAMAGE.
     30  */
     31 
     32 #ifndef	_LINUX_INTERVAL_TREE_H_
     33 #define	_LINUX_INTERVAL_TREE_H_
     34 
     35 #include <sys/rbtree.h>
     36 
     37 struct rb_root {
     38 	struct rb_tree	rbr_tree;
     39 };
     40 
     41 struct interval_tree_node {
     42 	struct rb_node	itn_node;
     43 	unsigned long	start;	/* inclusive */
     44 	unsigned long	last;	/* inclusive */
     45 };
     46 
     47 static inline int
     48 interval_tree_compare_nodes(void *cookie, const void *va, const void *vb)
     49 {
     50 	const struct interval_tree_node *na = va;
     51 	const struct interval_tree_node *nb = vb;
     52 
     53 	if (na->start < nb->start)
     54 		return -1;
     55 	if (na->start > nb->start)
     56 		return +1;
     57 	if (na->last < nb->last)
     58 		return -1;
     59 	if (na->last > nb->last)
     60 		return +1;
     61 	return 0;
     62 }
     63 
     64 static inline int
     65 interval_tree_compare_key(void *cookie, const void *vn, const void *vk)
     66 {
     67 	const struct interval_tree_node *n = va;
     68 	const unsigned long *k = vk;
     69 
     70 	if (n->last < k)
     71 		return -1;
     72 	if (k < n->first)
     73 		return +1;
     74 	return 0;
     75 }
     76 
     77 static const struct rb_tree_ops interval_tree_ops = {
     78 	.rbto_compare_nodes_fn = interval_tree_compare_nodes,
     79 	.rbto_compare_key_fn = interval_tree_compare_key,
     80 	.rbto_node_offset = offsetof(struct interval_tree_node, itn_node),
     81 };
     82 
     83 static inline void
     84 interval_tree_insert(struct interval_tree_node *node, struct rb_root *root)
     85 {
     86 	struct interval_tree_node *collision __diagused;
     87 
     88 	collision = rb_tree_insert_node(&root->rbr_tree, node);
     89 	KASSERT(collision == node);
     90 }
     91 
     92 static inline void
     93 interval_tree_remove(struct interval_tree_node *node, struct rb_root *root)
     94 {
     95 
     96 	rb_tree_remove_node(&root->rbr_tree, node);
     97 }
     98 
     99 static inline struct interval_node *
    100 interval_tree_iter_first(struct rb_root *root, unsigned long start,
    101     unsigned long last)
    102 {
    103 	struct interval_node *node;
    104 
    105 	node = rb_tree_find_node_geq(&root->rbr_tree, &start);
    106 	if (node == NULL)
    107 		return NULL;
    108 	KASSERT(node->start <= start);
    109 	if (last < node->start)
    110 		return NULL;
    111 
    112 	return node;
    113 }
    114 
    115 /*
    116  * XXX Linux's interval_tree_iter_next doesn't take the root as an
    117  * argument, which makes this difficult.  So we'll just patch those
    118  * uses.
    119  */
    120 static inline struct interval_node *
    121 interval_tree_iter_next(struct rb_root *root, struct interval_node *node,
    122     unsigned long start, unsigned long last)
    123 {
    124 	struct interval_node *next;
    125 
    126 	KASSERT(node != NULL);
    127 	next = rb_tree_iterate(&root->rbr_tree, node, RB_DIR_RIGHT);
    128 	if (next == NULL)
    129 		return NULL;
    130 	KASSERT(node->start <= start);
    131 	if (last < node->start)
    132 		return NULL;
    133 }
    134 
    135 #endif	/* _LINUX_INTERVAL_TREE_H_ */
    136