xref: /minix3/common/lib/libprop/prop_rb_impl.h (revision f14fb602092e015ff630df58e17c2a9cd57d29b3)
1*f14fb602SLionel Sambuc /*	$NetBSD: prop_rb_impl.h,v 1.9 2012/07/27 09:11:00 pooka Exp $	*/
26b6d114aSBen Gras 
36b6d114aSBen Gras /*-
46b6d114aSBen Gras  * Copyright (c) 2001 The NetBSD Foundation, Inc.
56b6d114aSBen Gras  * All rights reserved.
66b6d114aSBen Gras  *
76b6d114aSBen Gras  * This code is derived from software contributed to The NetBSD Foundation
86b6d114aSBen Gras  * by Matt Thomas <matt@3am-software.com>.
96b6d114aSBen Gras  *
106b6d114aSBen Gras  * Redistribution and use in source and binary forms, with or without
116b6d114aSBen Gras  * modification, are permitted provided that the following conditions
126b6d114aSBen Gras  * are met:
136b6d114aSBen Gras  * 1. Redistributions of source code must retain the above copyright
146b6d114aSBen Gras  *    notice, this list of conditions and the following disclaimer.
156b6d114aSBen Gras  * 2. Redistributions in binary form must reproduce the above copyright
166b6d114aSBen Gras  *    notice, this list of conditions and the following disclaimer in the
176b6d114aSBen Gras  *    documentation and/or other materials provided with the distribution.
186b6d114aSBen Gras  *
196b6d114aSBen Gras  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
206b6d114aSBen Gras  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
216b6d114aSBen Gras  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
226b6d114aSBen Gras  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
236b6d114aSBen Gras  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
246b6d114aSBen Gras  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
256b6d114aSBen Gras  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
266b6d114aSBen Gras  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
276b6d114aSBen Gras  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
286b6d114aSBen Gras  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
296b6d114aSBen Gras  * POSSIBILITY OF SUCH DAMAGE.
306b6d114aSBen Gras  */
316b6d114aSBen Gras 
326b6d114aSBen Gras #ifndef _PROP_RB_IMPL_H_
336b6d114aSBen Gras #define	_PROP_RB_IMPL_H_
346b6d114aSBen Gras 
356b6d114aSBen Gras #if defined(__NetBSD__) || defined(__minix)
366b6d114aSBen Gras #include <sys/rbtree.h>
376b6d114aSBen Gras 
386b6d114aSBen Gras /*
396b6d114aSBen Gras  * Define local names for common rb_tree functions.
406b6d114aSBen Gras  */
416b6d114aSBen Gras #define	_prop_rb_tree_init		rb_tree_init
426b6d114aSBen Gras #define	_prop_rb_tree_insert_node	rb_tree_insert_node
436b6d114aSBen Gras #define	_prop_rb_tree_find		rb_tree_find_node
446b6d114aSBen Gras #define	_prop_rb_tree_remove_node	rb_tree_remove_node
456b6d114aSBen Gras #define	_prop_rb_tree_iterate		rb_tree_iterate
466b6d114aSBen Gras 
476b6d114aSBen Gras #else	/* __NetBSD__ */
486b6d114aSBen Gras 
496b6d114aSBen Gras #include <sys/types.h>
50*f14fb602SLionel Sambuc #ifdef RBDEBUG
516b6d114aSBen Gras #include <sys/queue.h>
52*f14fb602SLionel Sambuc #endif
536b6d114aSBen Gras 
54*f14fb602SLionel Sambuc typedef struct rb_node {
55*f14fb602SLionel Sambuc 	struct rb_node *rb_nodes[2];
56*f14fb602SLionel Sambuc #define	RB_DIR_LEFT		0
57*f14fb602SLionel Sambuc #define	RB_DIR_RIGHT		1
58*f14fb602SLionel Sambuc #define	RB_DIR_OTHER		1
59*f14fb602SLionel Sambuc #define	rb_left			rb_nodes[RB_DIR_LEFT]
60*f14fb602SLionel Sambuc #define	rb_right		rb_nodes[RB_DIR_RIGHT]
61*f14fb602SLionel Sambuc 
62*f14fb602SLionel Sambuc 	/*
63*f14fb602SLionel Sambuc 	 * rb_info contains the two flags and the parent back pointer.
64*f14fb602SLionel Sambuc 	 * We put the two flags in the low two bits since we know that
65*f14fb602SLionel Sambuc 	 * rb_node will have an alignment of 4 or 8 bytes.
66*f14fb602SLionel Sambuc 	 */
67*f14fb602SLionel Sambuc 	uintptr_t rb_info;
68*f14fb602SLionel Sambuc #define	RB_FLAG_POSITION	0x2
69*f14fb602SLionel Sambuc #define	RB_FLAG_RED		0x1
70*f14fb602SLionel Sambuc #define	RB_FLAG_MASK		(RB_FLAG_POSITION|RB_FLAG_RED)
71*f14fb602SLionel Sambuc #define	RB_FATHER(rb) \
72*f14fb602SLionel Sambuc     ((struct rb_node *)((rb)->rb_info & ~RB_FLAG_MASK))
73*f14fb602SLionel Sambuc #define	RB_SET_FATHER(rb, father) \
74*f14fb602SLionel Sambuc     ((void)((rb)->rb_info = (uintptr_t)(father)|((rb)->rb_info & RB_FLAG_MASK)))
75*f14fb602SLionel Sambuc 
76*f14fb602SLionel Sambuc #define	RB_SENTINEL_P(rb)	((rb) == NULL)
77*f14fb602SLionel Sambuc #define	RB_LEFT_SENTINEL_P(rb)	RB_SENTINEL_P((rb)->rb_left)
78*f14fb602SLionel Sambuc #define	RB_RIGHT_SENTINEL_P(rb)	RB_SENTINEL_P((rb)->rb_right)
79*f14fb602SLionel Sambuc #define	RB_FATHER_SENTINEL_P(rb) RB_SENTINEL_P(RB_FATHER((rb)))
80*f14fb602SLionel Sambuc #define	RB_CHILDLESS_P(rb) \
81*f14fb602SLionel Sambuc     (RB_SENTINEL_P(rb) || (RB_LEFT_SENTINEL_P(rb) && RB_RIGHT_SENTINEL_P(rb)))
82*f14fb602SLionel Sambuc #define	RB_TWOCHILDREN_P(rb) \
83*f14fb602SLionel Sambuc     (!RB_SENTINEL_P(rb) && !RB_LEFT_SENTINEL_P(rb) && !RB_RIGHT_SENTINEL_P(rb))
84*f14fb602SLionel Sambuc 
85*f14fb602SLionel Sambuc #define	RB_POSITION(rb)	\
86*f14fb602SLionel Sambuc     (((rb)->rb_info & RB_FLAG_POSITION) ? RB_DIR_RIGHT : RB_DIR_LEFT)
87*f14fb602SLionel Sambuc #define	RB_RIGHT_P(rb)		(RB_POSITION(rb) == RB_DIR_RIGHT)
88*f14fb602SLionel Sambuc #define	RB_LEFT_P(rb)		(RB_POSITION(rb) == RB_DIR_LEFT)
89*f14fb602SLionel Sambuc #define	RB_RED_P(rb) 		(!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0)
90*f14fb602SLionel Sambuc #define	RB_BLACK_P(rb) 		(RB_SENTINEL_P(rb) || ((rb)->rb_info & RB_FLAG_RED) == 0)
91*f14fb602SLionel Sambuc #define	RB_MARK_RED(rb) 	((void)((rb)->rb_info |= RB_FLAG_RED))
92*f14fb602SLionel Sambuc #define	RB_MARK_BLACK(rb) 	((void)((rb)->rb_info &= ~RB_FLAG_RED))
93*f14fb602SLionel Sambuc #define	RB_INVERT_COLOR(rb) 	((void)((rb)->rb_info ^= RB_FLAG_RED))
94*f14fb602SLionel Sambuc #define	RB_ROOT_P(rbt, rb)	((rbt)->rbt_root == (rb))
95*f14fb602SLionel Sambuc #define	RB_SET_POSITION(rb, position) \
96*f14fb602SLionel Sambuc     ((void)((position) ? ((rb)->rb_info |= RB_FLAG_POSITION) : \
97*f14fb602SLionel Sambuc     ((rb)->rb_info &= ~RB_FLAG_POSITION)))
98*f14fb602SLionel Sambuc #define	RB_ZERO_PROPERTIES(rb)	((void)((rb)->rb_info &= ~RB_FLAG_MASK))
99*f14fb602SLionel Sambuc #define	RB_COPY_PROPERTIES(dst, src) \
100*f14fb602SLionel Sambuc     ((void)((dst)->rb_info ^= ((dst)->rb_info ^ (src)->rb_info) & RB_FLAG_MASK))
101*f14fb602SLionel Sambuc #define RB_SWAP_PROPERTIES(a, b) do { \
102*f14fb602SLionel Sambuc     uintptr_t xorinfo = ((a)->rb_info ^ (b)->rb_info) & RB_FLAG_MASK; \
103*f14fb602SLionel Sambuc     (a)->rb_info ^= xorinfo; \
104*f14fb602SLionel Sambuc     (b)->rb_info ^= xorinfo; \
105*f14fb602SLionel Sambuc   } while (/*CONSTCOND*/ 0)
1066b6d114aSBen Gras #ifdef RBDEBUG
1076b6d114aSBen Gras 	TAILQ_ENTRY(rb_node) rb_link;
1086b6d114aSBen Gras #endif
109*f14fb602SLionel Sambuc } rb_node_t;
110*f14fb602SLionel Sambuc 
111*f14fb602SLionel Sambuc #define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
112*f14fb602SLionel Sambuc #define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
113*f14fb602SLionel Sambuc #define RB_TREE_FOREACH(N, T) \
114*f14fb602SLionel Sambuc     for ((N) = RB_TREE_MIN(T); (N); \
115*f14fb602SLionel Sambuc 	(N) = rb_tree_iterate((T), (N), RB_DIR_RIGHT))
116*f14fb602SLionel Sambuc #define RB_TREE_FOREACH_REVERSE(N, T) \
117*f14fb602SLionel Sambuc     for ((N) = RB_TREE_MAX(T); (N); \
118*f14fb602SLionel Sambuc 	(N) = rb_tree_iterate((T), (N), RB_DIR_LEFT))
1196b6d114aSBen Gras 
1206b6d114aSBen Gras #ifdef RBDEBUG
1216b6d114aSBen Gras TAILQ_HEAD(rb_node_qh, rb_node);
1226b6d114aSBen Gras 
123*f14fb602SLionel Sambuc #define	RB_TAILQ_REMOVE(a, b, c)		TAILQ_REMOVE(a, b, c)
124*f14fb602SLionel Sambuc #define	RB_TAILQ_INIT(a)			TAILQ_INIT(a)
125*f14fb602SLionel Sambuc #define	RB_TAILQ_INSERT_HEAD(a, b, c)		TAILQ_INSERT_HEAD(a, b, c)
126*f14fb602SLionel Sambuc #define	RB_TAILQ_INSERT_BEFORE(a, b, c)		TAILQ_INSERT_BEFORE(a, b, c)
127*f14fb602SLionel Sambuc #define	RB_TAILQ_INSERT_AFTER(a, b, c, d)	TAILQ_INSERT_AFTER(a, b, c, d)
1286b6d114aSBen Gras #else
1296b6d114aSBen Gras #define	RB_TAILQ_REMOVE(a, b, c)		do { } while (/*CONSTCOND*/0)
1306b6d114aSBen Gras #define	RB_TAILQ_INIT(a)			do { } while (/*CONSTCOND*/0)
1316b6d114aSBen Gras #define	RB_TAILQ_INSERT_HEAD(a, b, c)		do { } while (/*CONSTCOND*/0)
1326b6d114aSBen Gras #define	RB_TAILQ_INSERT_BEFORE(a, b, c)		do { } while (/*CONSTCOND*/0)
1336b6d114aSBen Gras #define	RB_TAILQ_INSERT_AFTER(a, b, c, d)	do { } while (/*CONSTCOND*/0)
134*f14fb602SLionel Sambuc #endif /* RBDEBUG */
1356b6d114aSBen Gras 
136*f14fb602SLionel Sambuc /*
137*f14fb602SLionel Sambuc  * rbto_compare_nodes_fn:
138*f14fb602SLionel Sambuc  *	return a positive value if the first node > the second node.
139*f14fb602SLionel Sambuc  *	return a negative value if the first node < the second node.
140*f14fb602SLionel Sambuc  *	return 0 if they are considered same.
141*f14fb602SLionel Sambuc  *
142*f14fb602SLionel Sambuc  * rbto_compare_key_fn:
143*f14fb602SLionel Sambuc  *	return a positive value if the node > the key.
144*f14fb602SLionel Sambuc  *	return a negative value if the node < the key.
145*f14fb602SLionel Sambuc  *	return 0 if they are considered same.
146*f14fb602SLionel Sambuc  */
1476b6d114aSBen Gras 
148*f14fb602SLionel Sambuc typedef signed int (*rbto_compare_nodes_fn)(void *, const void *, const void *);
149*f14fb602SLionel Sambuc typedef signed int (*rbto_compare_key_fn)(void *, const void *, const void *);
1506b6d114aSBen Gras 
151*f14fb602SLionel Sambuc typedef struct {
152*f14fb602SLionel Sambuc 	rbto_compare_nodes_fn rbto_compare_nodes;
153*f14fb602SLionel Sambuc 	rbto_compare_key_fn rbto_compare_key;
154*f14fb602SLionel Sambuc 	size_t rbto_node_offset;
155*f14fb602SLionel Sambuc 	void *rbto_context;
156*f14fb602SLionel Sambuc } rb_tree_ops_t;
157*f14fb602SLionel Sambuc 
158*f14fb602SLionel Sambuc typedef struct rb_tree {
1596b6d114aSBen Gras 	struct rb_node *rbt_root;
160*f14fb602SLionel Sambuc 	const rb_tree_ops_t *rbt_ops;
161*f14fb602SLionel Sambuc 	struct rb_node *rbt_minmax[2];
1626b6d114aSBen Gras #ifdef RBDEBUG
1636b6d114aSBen Gras 	struct rb_node_qh rbt_nodes;
1646b6d114aSBen Gras #endif
165*f14fb602SLionel Sambuc #ifdef RBSTATS
1666b6d114aSBen Gras 	unsigned int rbt_count;
167*f14fb602SLionel Sambuc 	unsigned int rbt_insertions;
168*f14fb602SLionel Sambuc 	unsigned int rbt_removals;
169*f14fb602SLionel Sambuc 	unsigned int rbt_insertion_rebalance_calls;
170*f14fb602SLionel Sambuc 	unsigned int rbt_insertion_rebalance_passes;
171*f14fb602SLionel Sambuc 	unsigned int rbt_removal_rebalance_calls;
172*f14fb602SLionel Sambuc 	unsigned int rbt_removal_rebalance_passes;
1736b6d114aSBen Gras #endif
174*f14fb602SLionel Sambuc } rb_tree_t;
1756b6d114aSBen Gras 
176*f14fb602SLionel Sambuc #ifdef RBSTATS
177*f14fb602SLionel Sambuc #define	RBSTAT_INC(v)	((void)((v)++))
178*f14fb602SLionel Sambuc #define	RBSTAT_DEC(v)	((void)((v)--))
179*f14fb602SLionel Sambuc #else
180*f14fb602SLionel Sambuc #define	RBSTAT_INC(v)	do { } while (/*CONSTCOND*/0)
181*f14fb602SLionel Sambuc #define	RBSTAT_DEC(v)	do { } while (/*CONSTCOND*/0)
182*f14fb602SLionel Sambuc #endif
183*f14fb602SLionel Sambuc 
184*f14fb602SLionel Sambuc void	_prop_rb_tree_init(rb_tree_t *, const rb_tree_ops_t *);
185*f14fb602SLionel Sambuc void *	_prop_rb_tree_insert_node(rb_tree_t *, void *);
186*f14fb602SLionel Sambuc void *	_prop_rb_tree_find(rb_tree_t *, const void *);
187*f14fb602SLionel Sambuc void *	_prop_rb_tree_find_node(rb_tree_t *, const void *);
188*f14fb602SLionel Sambuc void	_prop_rb_tree_remove_node(rb_tree_t *, void *);
189*f14fb602SLionel Sambuc void *	_prop_rb_tree_iterate(rb_tree_t *, void *, const unsigned int);
1906b6d114aSBen Gras #ifdef RBDEBUG
1916b6d114aSBen Gras void	_prop_rb_tree_check(const struct rb_tree *, bool);
1926b6d114aSBen Gras #endif
1936b6d114aSBen Gras 
1946b6d114aSBen Gras #endif /* __NetBSD__ */
1956b6d114aSBen Gras 
1966b6d114aSBen Gras #endif	/* _PROP_RB_IMPL_H_*/
197