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