Module Name: src
Committed By: matt
Date: Sat Sep 25 01:42:40 UTC 2010
Modified Files:
src/common/lib/libc/gen: rb.c
src/common/lib/libprop: prop_rb_impl.h
src/distrib/sets/lists/comp: mi
src/sys/fs/udf: udf.h
src/sys/kern: subr_lockdebug.c
src/sys/net/npf: npf_impl.h
src/sys/nfs: nfsmount.h nfsnode.h
src/sys/sys: Makefile
src/sys/uvm: uvm_map.h uvm_object.h uvm_page.h
Added Files:
src/sys/sys: rbtree.h
Removed Files:
src/sys/sys: rb.h
Log Message:
Rename rb.h to rbtree.h, as it is more appropriate (c.f. ptree.h). Also
helps find code that hasn't been updated to use the new rbtree API.
To generate a diff of this commit:
cvs rdiff -u -r1.7 -r1.8 src/common/lib/libc/gen/rb.c
cvs rdiff -u -r1.7 -r1.8 src/common/lib/libprop/prop_rb_impl.h
cvs rdiff -u -r1.1509 -r1.1510 src/distrib/sets/lists/comp/mi
cvs rdiff -u -r1.42 -r1.43 src/sys/fs/udf/udf.h
cvs rdiff -u -r1.42 -r1.43 src/sys/kern/subr_lockdebug.c
cvs rdiff -u -r1.2 -r1.3 src/sys/net/npf/npf_impl.h
cvs rdiff -u -r1.49 -r1.50 src/sys/nfs/nfsmount.h
cvs rdiff -u -r1.71 -r1.72 src/sys/nfs/nfsnode.h
cvs rdiff -u -r1.127 -r1.128 src/sys/sys/Makefile
cvs rdiff -u -r1.14 -r0 src/sys/sys/rb.h
cvs rdiff -u -r0 -r1.1 src/sys/sys/rbtree.h
cvs rdiff -u -r1.64 -r1.65 src/sys/uvm/uvm_map.h
cvs rdiff -u -r1.27 -r1.28 src/sys/uvm/uvm_object.h
cvs rdiff -u -r1.60 -r1.61 src/sys/uvm/uvm_page.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/common/lib/libc/gen/rb.c
diff -u src/common/lib/libc/gen/rb.c:1.7 src/common/lib/libc/gen/rb.c:1.8
--- src/common/lib/libc/gen/rb.c:1.7 Fri Sep 24 22:51:51 2010
+++ src/common/lib/libc/gen/rb.c Sat Sep 25 01:42:38 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: rb.c,v 1.7 2010/09/24 22:51:51 rmind Exp $ */
+/* $NetBSD: rb.c,v 1.8 2010/09/25 01:42:38 matt Exp $ */
/*-
* Copyright (c) 2001 The NetBSD Foundation, Inc.
@@ -70,9 +70,9 @@
#endif
#ifdef RBTEST
-#include "rb.h"
+#include "rbtree.h"
#else
-#include <sys/rb.h>
+#include <sys/rbtree.h>
#endif
static void rb_tree_insert_rebalance(struct rb_tree *, struct rb_node *);
Index: src/common/lib/libprop/prop_rb_impl.h
diff -u src/common/lib/libprop/prop_rb_impl.h:1.7 src/common/lib/libprop/prop_rb_impl.h:1.8
--- src/common/lib/libprop/prop_rb_impl.h:1.7 Mon Jun 30 20:14:09 2008
+++ src/common/lib/libprop/prop_rb_impl.h Sat Sep 25 01:42:38 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: prop_rb_impl.h,v 1.7 2008/06/30 20:14:09 matt Exp $ */
+/* $NetBSD: prop_rb_impl.h,v 1.8 2010/09/25 01:42:38 matt Exp $ */
/*-
* Copyright (c) 2001 The NetBSD Foundation, Inc.
@@ -33,7 +33,7 @@
#define _PROP_RB_IMPL_H_
#ifdef __NetBSD__
-#include <sys/rb.h>
+#include <sys/rbtree.h>
/*
* Define local names for common rb_tree functions.
Index: src/distrib/sets/lists/comp/mi
diff -u src/distrib/sets/lists/comp/mi:1.1509 src/distrib/sets/lists/comp/mi:1.1510
--- src/distrib/sets/lists/comp/mi:1.1509 Fri Sep 24 21:53:00 2010
+++ src/distrib/sets/lists/comp/mi Sat Sep 25 01:42:38 2010
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.1509 2010/09/24 21:53:00 christos Exp $
+# $NetBSD: mi,v 1.1510 2010/09/25 01:42:38 matt Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -2086,7 +2086,8 @@
./usr/include/sys/queue.h comp-c-include
./usr/include/sys/radioio.h comp-c-include
./usr/include/sys/ras.h comp-c-include
-./usr/include/sys/rb.h comp-c-include
+./usr/include/sys/rb.h comp-obsolete obsolete
+./usr/include/sys/rbtree.h comp-c-include
./usr/include/sys/reboot.h comp-c-include
./usr/include/sys/resource.h comp-c-include
./usr/include/sys/resourcevar.h comp-c-include
Index: src/sys/fs/udf/udf.h
diff -u src/sys/fs/udf/udf.h:1.42 src/sys/fs/udf/udf.h:1.43
--- src/sys/fs/udf/udf.h:1.42 Fri Sep 24 22:51:50 2010
+++ src/sys/fs/udf/udf.h Sat Sep 25 01:42:40 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: udf.h,v 1.42 2010/09/24 22:51:50 rmind Exp $ */
+/* $NetBSD: udf.h,v 1.43 2010/09/25 01:42:40 matt Exp $ */
/*
* Copyright (c) 2006, 2008 Reinoud Zandijk
@@ -30,7 +30,7 @@
#define _FS_UDF_UDF_H_
#include <sys/queue.h>
-#include <sys/rb.h>
+#include <sys/rbtree.h>
#include <sys/uio.h>
#include <sys/mutex.h>
Index: src/sys/kern/subr_lockdebug.c
diff -u src/sys/kern/subr_lockdebug.c:1.42 src/sys/kern/subr_lockdebug.c:1.43
--- src/sys/kern/subr_lockdebug.c:1.42 Fri Sep 24 22:51:50 2010
+++ src/sys/kern/subr_lockdebug.c Sat Sep 25 01:42:39 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: subr_lockdebug.c,v 1.42 2010/09/24 22:51:50 rmind Exp $ */
+/* $NetBSD: subr_lockdebug.c,v 1.43 2010/09/25 01:42:39 matt Exp $ */
/*-
* Copyright (c) 2006, 2007, 2008 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: subr_lockdebug.c,v 1.42 2010/09/24 22:51:50 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: subr_lockdebug.c,v 1.43 2010/09/25 01:42:39 matt Exp $");
#include "opt_ddb.h"
@@ -48,7 +48,7 @@
#include <sys/cpu.h>
#include <sys/atomic.h>
#include <sys/lock.h>
-#include <sys/rb.h>
+#include <sys/rbtree.h>
#include <machine/lock.h>
Index: src/sys/net/npf/npf_impl.h
diff -u src/sys/net/npf/npf_impl.h:1.2 src/sys/net/npf/npf_impl.h:1.3
--- src/sys/net/npf/npf_impl.h:1.2 Thu Sep 16 04:53:27 2010
+++ src/sys/net/npf/npf_impl.h Sat Sep 25 01:42:39 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: npf_impl.h,v 1.2 2010/09/16 04:53:27 rmind Exp $ */
+/* $NetBSD: npf_impl.h,v 1.3 2010/09/25 01:42:39 matt Exp $ */
/*-
* Copyright (c) 2009-2010 The NetBSD Foundation, Inc.
@@ -37,7 +37,7 @@
#ifndef _NPF_IMPL_H_
#define _NPF_IMPL_H_
-#include <sys/rb.h>
+#include <sys/rbtree.h>
#include <sys/hash.h>
#include <sys/queue.h>
#include <sys/types.h>
Index: src/sys/nfs/nfsmount.h
diff -u src/sys/nfs/nfsmount.h:1.49 src/sys/nfs/nfsmount.h:1.50
--- src/sys/nfs/nfsmount.h:1.49 Sat Mar 14 14:46:11 2009
+++ src/sys/nfs/nfsmount.h Sat Sep 25 01:42:39 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: nfsmount.h,v 1.49 2009/03/14 14:46:11 dsl Exp $ */
+/* $NetBSD: nfsmount.h,v 1.50 2010/09/25 01:42:39 matt Exp $ */
/*
* Copyright (c) 1989, 1993
@@ -42,7 +42,7 @@
#include <sys/rwlock.h>
#include <sys/mutex.h>
#include <sys/disk.h>
-#include <sys/rb.h>
+#include <sys/rbtree.h>
#endif
/*
Index: src/sys/nfs/nfsnode.h
diff -u src/sys/nfs/nfsnode.h:1.71 src/sys/nfs/nfsnode.h:1.72
--- src/sys/nfs/nfsnode.h:1.71 Sat Mar 14 14:46:11 2009
+++ src/sys/nfs/nfsnode.h Sat Sep 25 01:42:39 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: nfsnode.h,v 1.71 2009/03/14 14:46:11 dsl Exp $ */
+/* $NetBSD: nfsnode.h,v 1.72 2010/09/25 01:42:39 matt Exp $ */
/*
* Copyright (c) 1989, 1993
@@ -40,7 +40,7 @@
#include <sys/condvar.h>
#include <sys/mutex.h>
-#include <sys/rb.h>
+#include <sys/rbtree.h>
#ifndef _NFS_NFS_H_
#include <nfs/nfs.h>
Index: src/sys/sys/Makefile
diff -u src/sys/sys/Makefile:1.127 src/sys/sys/Makefile:1.128
--- src/sys/sys/Makefile:1.127 Tue Jun 1 13:52:08 2010
+++ src/sys/sys/Makefile Sat Sep 25 01:42:40 2010
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.127 2010/06/01 13:52:08 tnozaki Exp $
+# $NetBSD: Makefile,v 1.128 2010/09/25 01:42:40 matt Exp $
.include <bsd.sys.mk>
@@ -27,7 +27,7 @@
param.h pipe.h pmc.h poll.h pool.h power.h proc.h \
protosw.h pset.h ptrace.h ptree.h \
queue.h \
- ras.h rb.h reboot.h radioio.h resource.h resourcevar.h rmd160.h \
+ ras.h rbtree.h reboot.h radioio.h resource.h resourcevar.h rmd160.h \
rnd.h rwlock.h sa.h satypes.h \
scanio.h sched.h scsiio.h sdt.h select.h selinfo.h sem.h sha1.h \
sha2.h shm.h siginfo.h signal.h signalvar.h sigtypes.h simplelock.h \
Index: src/sys/uvm/uvm_map.h
diff -u src/sys/uvm/uvm_map.h:1.64 src/sys/uvm/uvm_map.h:1.65
--- src/sys/uvm/uvm_map.h:1.64 Sat Aug 1 16:35:51 2009
+++ src/sys/uvm/uvm_map.h Sat Sep 25 01:42:40 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: uvm_map.h,v 1.64 2009/08/01 16:35:51 yamt Exp $ */
+/* $NetBSD: uvm_map.h,v 1.65 2010/09/25 01:42:40 matt Exp $ */
/*
* Copyright (c) 1997 Charles D. Cranor and Washington University.
@@ -110,7 +110,7 @@
#endif /* _KERNEL */
-#include <sys/rb.h>
+#include <sys/rbtree.h>
#include <sys/pool.h>
#include <sys/rwlock.h>
#include <sys/mutex.h>
Index: src/sys/uvm/uvm_object.h
diff -u src/sys/uvm/uvm_object.h:1.27 src/sys/uvm/uvm_object.h:1.28
--- src/sys/uvm/uvm_object.h:1.27 Fri Sep 24 22:51:51 2010
+++ src/sys/uvm/uvm_object.h Sat Sep 25 01:42:40 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: uvm_object.h,v 1.27 2010/09/24 22:51:51 rmind Exp $ */
+/* $NetBSD: uvm_object.h,v 1.28 2010/09/25 01:42:40 matt Exp $ */
/*
*
@@ -41,7 +41,7 @@
* uvm_object.h
*/
-#include <sys/rb.h>
+#include <sys/rbtree.h>
/*
* uvm_object: all that is left of mach objects.
Index: src/sys/uvm/uvm_page.h
diff -u src/sys/uvm/uvm_page.h:1.60 src/sys/uvm/uvm_page.h:1.61
--- src/sys/uvm/uvm_page.h:1.60 Thu Jul 29 10:54:51 2010
+++ src/sys/uvm/uvm_page.h Sat Sep 25 01:42:40 2010
@@ -1,4 +1,4 @@
-/* $NetBSD: uvm_page.h,v 1.60 2010/07/29 10:54:51 hannken Exp $ */
+/* $NetBSD: uvm_page.h,v 1.61 2010/09/25 01:42:40 matt Exp $ */
/*
* Copyright (c) 1997 Charles D. Cranor and Washington University.
@@ -118,7 +118,7 @@
#include <uvm/uvm_extern.h>
#include <uvm/uvm_pglist.h>
-#include <sys/rb.h>
+#include <sys/rbtree.h>
struct vm_page {
struct rb_node rb_node; /* tree of pages in obj (O) */
Added files:
Index: src/sys/sys/rbtree.h
diff -u /dev/null src/sys/sys/rbtree.h:1.1
--- /dev/null Sat Sep 25 01:42:41 2010
+++ src/sys/sys/rbtree.h Sat Sep 25 01:42:40 2010
@@ -0,0 +1,194 @@
+/* $NetBSD: rbtree.h,v 1.1 2010/09/25 01:42:40 matt Exp $ */
+
+/*-
+ * Copyright (c) 2001 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Matt Thomas <m...@3am-software.com>.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef _SYS_RBTREE_H_
+#define _SYS_RBTREE_H_
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+#include <sys/types.h>
+#else
+#include <stdbool.h>
+#include <inttypes.h>
+#endif
+#include <sys/queue.h>
+#include <sys/endian.h>
+
+__BEGIN_DECLS
+
+typedef struct rb_node {
+ struct rb_node *rb_nodes[2];
+#define RB_DIR_LEFT 0
+#define RB_DIR_RIGHT 1
+#define RB_DIR_OTHER 1
+#define rb_left rb_nodes[RB_DIR_LEFT]
+#define rb_right rb_nodes[RB_DIR_RIGHT]
+
+ /*
+ * rb_info contains the two flags and the parent back pointer.
+ * We put the two flags in the low two bits since we know that
+ * rb_node will have an alignment of 4 or 8 bytes.
+ */
+ uintptr_t rb_info;
+#define RB_FLAG_POSITION 0x2
+#define RB_FLAG_RED 0x1
+#define RB_FLAG_MASK (RB_FLAG_POSITION|RB_FLAG_RED)
+#define RB_FATHER(rb) \
+ ((struct rb_node *)((rb)->rb_info & ~RB_FLAG_MASK))
+#define RB_SET_FATHER(rb, father) \
+ ((void)((rb)->rb_info = (uintptr_t)(father)|((rb)->rb_info & RB_FLAG_MASK)))
+
+#define RB_SENTINEL_P(rb) ((rb) == NULL)
+#define RB_LEFT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_left)
+#define RB_RIGHT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_right)
+#define RB_FATHER_SENTINEL_P(rb) RB_SENTINEL_P(RB_FATHER((rb)))
+#define RB_CHILDLESS_P(rb) \
+ (RB_SENTINEL_P(rb) || (RB_LEFT_SENTINEL_P(rb) && RB_RIGHT_SENTINEL_P(rb)))
+#define RB_TWOCHILDREN_P(rb) \
+ (!RB_SENTINEL_P(rb) && !RB_LEFT_SENTINEL_P(rb) && !RB_RIGHT_SENTINEL_P(rb))
+
+#define RB_POSITION(rb) \
+ (((rb)->rb_info & RB_FLAG_POSITION) ? RB_DIR_RIGHT : RB_DIR_LEFT)
+#define RB_RIGHT_P(rb) (RB_POSITION(rb) == RB_DIR_RIGHT)
+#define RB_LEFT_P(rb) (RB_POSITION(rb) == RB_DIR_LEFT)
+#define RB_RED_P(rb) (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0)
+#define RB_BLACK_P(rb) (RB_SENTINEL_P(rb) || ((rb)->rb_info & RB_FLAG_RED) == 0)
+#define RB_MARK_RED(rb) ((void)((rb)->rb_info |= RB_FLAG_RED))
+#define RB_MARK_BLACK(rb) ((void)((rb)->rb_info &= ~RB_FLAG_RED))
+#define RB_INVERT_COLOR(rb) ((void)((rb)->rb_info ^= RB_FLAG_RED))
+#define RB_ROOT_P(rbt, rb) ((rbt)->rbt_root == (rb))
+#define RB_SET_POSITION(rb, position) \
+ ((void)((position) ? ((rb)->rb_info |= RB_FLAG_POSITION) : \
+ ((rb)->rb_info &= ~RB_FLAG_POSITION)))
+#define RB_ZERO_PROPERTIES(rb) ((void)((rb)->rb_info &= ~RB_FLAG_MASK))
+#define RB_COPY_PROPERTIES(dst, src) \
+ ((void)((dst)->rb_info ^= ((dst)->rb_info ^ (src)->rb_info) & RB_FLAG_MASK))
+#define RB_SWAP_PROPERTIES(a, b) do { \
+ uintptr_t xorinfo = ((a)->rb_info ^ (b)->rb_info) & RB_FLAG_MASK; \
+ (a)->rb_info ^= xorinfo; \
+ (b)->rb_info ^= xorinfo; \
+ } while (/*CONSTCOND*/ 0)
+#ifdef RBDEBUG
+ TAILQ_ENTRY(rb_node) rb_link;
+#endif
+} rb_node_t;
+
+#define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
+#define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
+#define RB_TREE_FOREACH(N, T) \
+ for ((N) = RB_TREE_MIN(T); (N); \
+ (N) = rb_tree_iterate((T), (N), RB_DIR_RIGHT))
+#define RB_TREE_FOREACH_REVERSE(N, T) \
+ for ((N) = RB_TREE_MAX(T); (N); \
+ (N) = rb_tree_iterate((T), (N), RB_DIR_LEFT))
+
+#ifdef RBDEBUG
+TAILQ_HEAD(rb_node_qh, rb_node);
+
+#define RB_TAILQ_REMOVE(a, b, c) TAILQ_REMOVE(a, b, c)
+#define RB_TAILQ_INIT(a) TAILQ_INIT(a)
+#define RB_TAILQ_INSERT_HEAD(a, b, c) TAILQ_INSERT_HEAD(a, b, c)
+#define RB_TAILQ_INSERT_BEFORE(a, b, c) TAILQ_INSERT_BEFORE(a, b, c)
+#define RB_TAILQ_INSERT_AFTER(a, b, c, d) TAILQ_INSERT_AFTER(a, b, c, d)
+#else
+#define RB_TAILQ_REMOVE(a, b, c) do { } while (/*CONSTCOND*/0)
+#define RB_TAILQ_INIT(a) do { } while (/*CONSTCOND*/0)
+#define RB_TAILQ_INSERT_HEAD(a, b, c) do { } while (/*CONSTCOND*/0)
+#define RB_TAILQ_INSERT_BEFORE(a, b, c) do { } while (/*CONSTCOND*/0)
+#define RB_TAILQ_INSERT_AFTER(a, b, c, d) do { } while (/*CONSTCOND*/0)
+#endif /* RBDEBUG */
+
+/*
+ * rbto_compare_nodes_fn:
+ * return a positive value if the first node > the second node.
+ * return a negative value if the first node < the second node.
+ * return 0 if they are considered same.
+ *
+ * rbto_compare_key_fn:
+ * return a positive value if the node > the key.
+ * return a negative value if the node < the key.
+ * return 0 if they are considered same.
+ */
+
+typedef signed int (*const rbto_compare_nodes_fn)(void *,
+ const void *, const void *);
+typedef signed int (*const rbto_compare_key_fn)(void *,
+ const void *, const void *);
+
+typedef struct {
+ rbto_compare_nodes_fn rbto_compare_nodes;
+ rbto_compare_key_fn rbto_compare_key;
+ size_t rbto_node_offset;
+ void *rbto_context;
+} rb_tree_ops_t;
+
+typedef struct rb_tree {
+ struct rb_node *rbt_root;
+ const rb_tree_ops_t *rbt_ops;
+ struct rb_node *rbt_minmax[2];
+#ifdef RBDEBUG
+ struct rb_node_qh rbt_nodes;
+#endif
+#ifdef RBSTATS
+ unsigned int rbt_count;
+ unsigned int rbt_insertions;
+ unsigned int rbt_removals;
+ unsigned int rbt_insertion_rebalance_calls;
+ unsigned int rbt_insertion_rebalance_passes;
+ unsigned int rbt_removal_rebalance_calls;
+ unsigned int rbt_removal_rebalance_passes;
+#endif
+} rb_tree_t;
+
+#ifdef RBSTATS
+#define RBSTAT_INC(v) ((void)((v)++))
+#define RBSTAT_DEC(v) ((void)((v)--))
+#else
+#define RBSTAT_INC(v) do { } while (/*CONSTCOND*/0)
+#define RBSTAT_DEC(v) do { } while (/*CONSTCOND*/0)
+#endif
+
+void rb_tree_init(rb_tree_t *, const rb_tree_ops_t *);
+void * rb_tree_insert_node(rb_tree_t *, void *);
+void * rb_tree_find_node(rb_tree_t *, const void *);
+void * rb_tree_find_node_geq(rb_tree_t *, const void *);
+void * rb_tree_find_node_leq(rb_tree_t *, const void *);
+void rb_tree_remove_node(rb_tree_t *, void *);
+void * rb_tree_iterate(rb_tree_t *, void *, const unsigned int);
+#ifdef RBDEBUG
+void rb_tree_check(const rb_tree_t *, bool);
+#endif
+#ifdef RBSTATS
+void rb_tree_depths(const rb_tree_t *, size_t *);
+#endif
+
+__END_DECLS
+
+#endif /* _SYS_RBTREE_H_*/
