Home | History | Annotate | Line # | Download | only in linux
rbtree.h revision 1.12 
      1 /*	$NetBSD: rbtree.h,v 1.12 2021/12/19 11:19:24 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 static inline bool
     55 RB_EMPTY_ROOT(struct rb_root *root)
     56 {
     57 
     58 	return RB_TREE_MIN(&root->rbr_tree) == NULL;
     59 }
     60 
     61 static inline struct rb_node *
     62 rb_first(struct rb_root *root)
     63 {
     64 	char *vnode = RB_TREE_MIN(&root->rbr_tree);
     65 
     66 	if (vnode)
     67 		vnode += root->rbr_tree.rbt_ops->rbto_node_offset;
     68 	return (struct rb_node *)vnode;
     69 }
     70 
     71 static inline struct rb_node *
     72 rb_next2(struct rb_root *root, struct rb_node *rb)
     73 {
     74 	return RB_TREE_NEXT(&root->rbr_tree, rb);
     75 }
     76 
     77 static inline struct rb_node *
     78 rb_last(struct rb_root *root)
     79 {
     80 	char *vnode = RB_TREE_MAX(&root->rbr_tree);
     81 
     82 	if (vnode)
     83 		vnode += root->rbr_tree.rbt_ops->rbto_node_offset;
     84 	return (struct rb_node *)vnode;
     85 }
     86 
     87 static inline struct rb_node *
     88 rb_first_cached(struct rb_root_cached *root)
     89 {
     90 	return rb_first(&root->rb_root);
     91 }
     92 
     93 static inline void
     94 rb_erase(struct rb_node *rbnode, struct rb_root *root)
     95 {
     96 	struct rb_tree *tree = &root->rbr_tree;
     97 	void *node = (char *)rbnode - tree->rbt_ops->rbto_node_offset;
     98 
     99 	rb_tree_remove_node(tree, node);
    100 }
    101 
    102 static inline void
    103 rb_erase_cached(struct rb_node *rbnode, struct rb_root_cached *root)
    104 {
    105 	rb_erase(rbnode, &root->rb_root);
    106 }
    107 
    108 static inline void
    109 rb_replace_node(struct rb_node *old, struct rb_node *new, struct rb_root *root)
    110 {
    111 	void *vold = (char *)old - root->rbr_tree.rbt_ops->rbto_node_offset;
    112 	void *vnew = (char *)new - root->rbr_tree.rbt_ops->rbto_node_offset;
    113 	void *collision __diagused;
    114 
    115 	rb_tree_remove_node(&root->rbr_tree, vold);
    116 	collision = rb_tree_insert_node(&root->rbr_tree, vnew);
    117 	KASSERT(collision == vnew);
    118 }
    119 
    120 static inline void
    121 rb_replace_node_cached(struct rb_node *old, struct rb_node *new,
    122     struct rb_root_cached *root)
    123 {
    124 	rb_replace_node(old, new, &root->rb_root);
    125 }
    126 
    127 /*
    128  * XXX This is not actually postorder, but I can't fathom why you would
    129  * want postorder for an ordered tree; different insertion orders lead
    130  * to different traversal orders.
    131  */
    132 #define	rbtree_postorder_for_each_entry_safe(NODE, TMP, ROOT, FIELD)	      \
    133 	for ((NODE) = RB_TREE_MIN(&(ROOT)->rbr_tree);			      \
    134 		((NODE) != NULL &&					      \
    135 		    ((TMP) = rb_tree_iterate(&(ROOT)->rbr_tree, (NODE),	      \
    136 			RB_DIR_RIGHT)));				      \
    137 		(NODE) = (TMP))
    138 
    139 #endif  /* _LINUX_RBTREE_H_ */
    140