Home | History | Annotate | Line # | Download | only in linux
rbtree.h revision 1.9 
      1 /*	$NetBSD: rbtree.h,v 1.9 2021/12/19 11:00:18 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_cached(struct rb_root_cached *root)
     63 {
     64 	char *vnode = RB_TREE_MIN(&root->rb_root.rbr_tree);
     65 
     66 	if (vnode)
     67 		vnode += root->rb_root.rbr_tree.rbt_ops->rbto_node_offset;
     68 	return (struct rb_node *)vnode;
     69 }
     70 
     71 static inline void
     72 rb_erase(struct rb_node *rbnode, struct rb_root *root)
     73 {
     74 	struct rb_tree *tree = &root->rbr_tree;
     75 	void *node = (char *)rbnode - tree->rbt_ops->rbto_node_offset;
     76 
     77 	rb_tree_remove_node(tree, node);
     78 }
     79 
     80 static inline void
     81 rb_erase_cached(struct rb_node *rbnode, struct rb_root_cached *root)
     82 {
     83 	rb_erase(rbnode, &root->rb_root);
     84 }
     85 
     86 static inline void
     87 rb_replace_node(struct rb_node *old, struct rb_node *new, struct rb_root *root)
     88 {
     89 	void *vold = (char *)old - root->rbr_tree.rbt_ops->rbto_node_offset;
     90 	void *vnew = (char *)new - root->rbr_tree.rbt_ops->rbto_node_offset;
     91 	void *collision __diagused;
     92 
     93 	rb_tree_remove_node(&root->rbr_tree, vold);
     94 	collision = rb_tree_insert_node(&root->rbr_tree, vnew);
     95 	KASSERT(collision == vnew);
     96 }
     97 
     98 static inline void
     99 rb_replace_node_cached(struct rb_node *old, struct rb_node *new,
    100     struct rb_root_cached *root)
    101 {
    102 	rb_replace_node(old, new, &root->rb_root);
    103 }
    104 
    105 /*
    106  * XXX This is not actually postorder, but I can't fathom why you would
    107  * want postorder for an ordered tree; different insertion orders lead
    108  * to different traversal orders.
    109  */
    110 #define	rbtree_postorder_for_each_entry_safe(NODE, TMP, ROOT, FIELD)	      \
    111 	for ((NODE) = RB_TREE_MIN(&(ROOT)->rbr_tree);			      \
    112 		((NODE) != NULL &&					      \
    113 		    ((TMP) = rb_tree_iterate(&(ROOT)->rbr_tree, (NODE),	      \
    114 			RB_DIR_RIGHT)));				      \
    115 		(NODE) = (TMP))
    116 
    117 #endif  /* _LINUX_RBTREE_H_ */
    118