Home | History | Annotate | Line # | Download | only in linux
rbtree.h revision 1.14 
      1 /*	$NetBSD: rbtree.h,v 1.14 2021/12/19 11:45:41 riastradh Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 2013 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_RBTREE_H_
     33 #define _LINUX_RBTREE_H_
     34 
     35 #include <sys/rbtree.h>
     36 
     37 #include <lib/libkern/libkern.h>
     38 
     39 struct rb_root {
     40 	struct rb_tree	rbr_tree;
     41 };
     42 
     43 struct rb_root_cached {
     44 	struct rb_root	rb_root; /* Linux API name */
     45 };
     46 
     47 #define	rb_entry(P, T, F) container_of(P, T, F)
     48 #define	rb_entry_safe(P, T, F)						      \
     49 ({									      \
     50 	__typeof__(P) __p = (P);					      \
     51 	__p ? container_of(__p, T, F) : NULL;				      \
     52 })
     53 
     54 /*
     55  * Several of these functions take const inputs and return non-const
     56  * outputs.  That is a deliberate choice.  It would be better if these
     57  * functions could be const-polymorphic -- return const if given const,
     58  * return non-const if given non-const -- but C doesn't let us express
     59  * that.  We are using them to adapt Linux code that is defined in
     60  * terms of token-substitution macros, without types of their own,
     61  * which happen to work out with both const and non-const variants.
     62  * Presumably the Linux code compiles upstream and has some level of
     63  * const type-checking in Linux, so this abuse of __UNCONST does not
     64  * carry substantial risk over to this code here.
     65  */
     66 
     67 static inline bool
     68 RB_EMPTY_ROOT(const struct rb_root *root)
     69 {
     70 
     71 	return RB_TREE_MIN(__UNCONST(&root->rbr_tree)) == NULL;
     72 }
     73 
     74 static inline struct rb_node *
     75 rb_first(const struct rb_root *root)
     76 {
     77 	char *vnode = RB_TREE_MIN(__UNCONST(&root->rbr_tree));
     78 
     79 	if (vnode)
     80 		vnode += root->rbr_tree.rbt_ops->rbto_node_offset;
     81 	return (struct rb_node *)vnode;
     82 }
     83 
     84 static inline struct rb_node *
     85 rb_next2(const struct rb_root *root, const struct rb_node *rbnode)
     86 {
     87 	char *vnode = (char *)__UNCONST(rbnode);
     88 
     89 	vnode -= root->rbr_tree.rbt_ops->rbto_node_offset;
     90 	return RB_TREE_NEXT(__UNCONST(&root->rbr_tree), vnode);
     91 }
     92 
     93 static inline struct rb_node *
     94 rb_last(const struct rb_root *root)
     95 {
     96 	char *vnode = RB_TREE_MAX(__UNCONST(&root->rbr_tree));
     97 
     98 	if (vnode)
     99 		vnode += root->rbr_tree.rbt_ops->rbto_node_offset;
    100 	return (struct rb_node *)vnode;
    101 }
    102 
    103 static inline struct rb_node *
    104 rb_first_cached(const struct rb_root_cached *root)
    105 {
    106 	return rb_first(&root->rb_root);
    107 }
    108 
    109 static inline void
    110 rb_erase(struct rb_node *rbnode, struct rb_root *root)
    111 {
    112 	struct rb_tree *tree = &root->rbr_tree;
    113 	void *node = (char *)rbnode - tree->rbt_ops->rbto_node_offset;
    114 
    115 	rb_tree_remove_node(tree, node);
    116 }
    117 
    118 static inline void
    119 rb_erase_cached(struct rb_node *rbnode, struct rb_root_cached *root)
    120 {
    121 	rb_erase(rbnode, &root->rb_root);
    122 }
    123 
    124 static inline void
    125 rb_replace_node(struct rb_node *old, struct rb_node *new, struct rb_root *root)
    126 {
    127 	void *vold = (char *)old - root->rbr_tree.rbt_ops->rbto_node_offset;
    128 	void *vnew = (char *)new - root->rbr_tree.rbt_ops->rbto_node_offset;
    129 	void *collision __diagused;
    130 
    131 	rb_tree_remove_node(&root->rbr_tree, vold);
    132 	collision = rb_tree_insert_node(&root->rbr_tree, vnew);
    133 	KASSERT(collision == vnew);
    134 }
    135 
    136 static inline void
    137 rb_replace_node_cached(struct rb_node *old, struct rb_node *new,
    138     struct rb_root_cached *root)
    139 {
    140 	rb_replace_node(old, new, &root->rb_root);
    141 }
    142 
    143 /*
    144  * XXX This is not actually postorder, but I can't fathom why you would
    145  * want postorder for an ordered tree; different insertion orders lead
    146  * to different traversal orders.
    147  */
    148 #define	rbtree_postorder_for_each_entry_safe(NODE, TMP, ROOT, FIELD)	      \
    149 	for ((NODE) = RB_TREE_MIN(&(ROOT)->rbr_tree);			      \
    150 		((NODE) != NULL &&					      \
    151 		    ((TMP) = rb_tree_iterate(&(ROOT)->rbr_tree, (NODE),	      \
    152 			RB_DIR_RIGHT)));				      \
    153 		(NODE) = (TMP))
    154 
    155 #endif  /* _LINUX_RBTREE_H_ */
    156