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