Module Name: src
Committed By: roy
Date: Thu Mar 7 12:05:54 UTC 2019
Modified Files:
src/share/man/man3: rbtree.3
src/sys/sys: rbtree.h
Log Message:
rbtree(3): Implement _FOREACH_SAFE macros
And _NEXT and _PREV as well.
To generate a diff of this commit:
cvs rdiff -u -r1.12 -r1.13 src/share/man/man3/rbtree.3
cvs rdiff -u -r1.2 -r1.3 src/sys/sys/rbtree.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/share/man/man3/rbtree.3
diff -u src/share/man/man3/rbtree.3:1.12 src/share/man/man3/rbtree.3:1.13
--- src/share/man/man3/rbtree.3:1.12 Tue Aug 30 05:12:00 2016
+++ src/share/man/man3/rbtree.3 Thu Mar 7 12:05:54 2019
@@ -1,4 +1,4 @@
-.\" $NetBSD: rbtree.3,v 1.12 2016/08/30 05:12:00 dholland Exp $
+.\" $NetBSD: rbtree.3,v 1.13 2019/03/07 12:05:54 roy Exp $
.\"
.\" Copyright (c) 2010 The NetBSD Foundation, Inc.
.\" All rights reserved.
@@ -27,7 +27,7 @@
.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
.\" POSSIBILITY OF SUCH DAMAGE.
.\"
-.Dd August 29, 2016
+.Dd March 4, 2019
.Dt RBTREE 3
.Os
.Sh NAME
@@ -55,8 +55,12 @@
.Fn RB_TREE_MIN "rb_tree_t *rbt"
.Ft void *
.Fn RB_TREE_MAX "rb_tree_t *rbt"
+.Fn RB_TREE_NEXT "rb_tree_t *rbt" "void *rb"
+.Fn RB_TREE_PREV "rb_tree_t *rbt" "void *rb"
.Fn RB_TREE_FOREACH "void *rb" "rb_tree_t *rbt"
+.Fn RB_TREE_FOREACH_SAFE "void *rb" "rb_tree_t *rbt" "void *tmp"
.Fn RB_TREE_FOREACH_REVERSE "void *rb" "rb_tree_t *rbt"
+.Fn RB_TREE_FOREACH_REVERSE_SAFE "void *rb" "rb_tree_t *rbt" "void *tmp"
.Sh DESCRIPTION
.Nm
provides red-black trees.
@@ -242,6 +246,18 @@ i.e. the node with the greatest key, or
if
.Fa rbt
is empty.
+.It Fn RB_TREE_NEXT "rbt" "rb"
+Return the next node in
+.Fa rbt ,
+or
+.Dv NULL
+if there is none.
+.It Fn RB_TREE_PREV "rbt" "rb"
+Return the previous node in
+.Fa rbt ,
+or
+.Dv NULL
+if there is none.
.It Fn RB_TREE_FOREACH "rb" "rbt"
.Nm RB_TREE_FOREACH
is a macro to be used in the place of a
@@ -251,6 +267,11 @@ header preceding a statement to traverse
from least to greatest, assigning
.Fa rb
to each node in turn and executing the statement.
+.It Fn RB_TREE_FOREACH_SAFE "rb" "rbt" "tmp"
+Allows both the removal of
+.Fa rb
+as well as freeing it from within the loop safely without interfering
+with the traversal.
.It Fn RB_TREE_FOREACH_REVERSE "rb" "rbt"
.Nm RB_TREE_FOREACH_REVERSE
is a macro to be used in the place of a
@@ -260,6 +281,11 @@ header preceding a statement to traverse
from greatest to least, assigning
.Fa rb
to each node in turn and executing the statement.
+.It Fn RB_TREE_FOREACH_REVERSE_SAFE "rb" "rbt" "tmp"
+Allows both the removal of
+.Fa rb
+as well as freeing it from within the loop safely without interfering
+with the traversal.
.El
.Sh CODE REFERENCES
The
Index: src/sys/sys/rbtree.h
diff -u src/sys/sys/rbtree.h:1.2 src/sys/sys/rbtree.h:1.3
--- src/sys/sys/rbtree.h:1.2 Fri Feb 17 08:20:55 2012
+++ src/sys/sys/rbtree.h Thu Mar 7 12:05:54 2019
@@ -1,4 +1,4 @@
-/* $NetBSD: rbtree.h,v 1.2 2012/02/17 08:20:55 yamt Exp $ */
+/* $NetBSD: rbtree.h,v 1.3 2019/03/07 12:05:54 roy Exp $ */
/*-
* Copyright (c) 2001 The NetBSD Foundation, Inc.
@@ -102,12 +102,20 @@ typedef struct rb_node {
#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_NEXT(T, N) rb_tree_iterate((T), (N), RB_DIR_RIGHT)
+#define RB_TREE_PREV(T, N) rb_tree_iterate((T), (N), RB_DIR_LEFT)
#define RB_TREE_FOREACH(N, T) \
- for ((N) = RB_TREE_MIN(T); (N); \
- (N) = rb_tree_iterate((T), (N), RB_DIR_RIGHT))
+ for ((N) = RB_TREE_MIN(T); (N); (N) = RB_TREE_NEXT((T), (N)))
#define RB_TREE_FOREACH_REVERSE(N, T) \
- for ((N) = RB_TREE_MAX(T); (N); \
- (N) = rb_tree_iterate((T), (N), RB_DIR_LEFT))
+ for ((N) = RB_TREE_MAX(T); (N); (N) = RB_TREE_PREV((T), (N)))
+#define RB_TREE_FOREACH_SAFE(N, T, S) \
+ for ((N) = RB_TREE_MIN(T); \
+ (N) && ((S) = RB_TREE_NEXT((T), (N)), 1); \
+ (N) = (S))
+#define RB_TREE_FOREACH_REVERSE_SAFE(N, T, S) \
+ for ((N) = RB_TREE_MAX(T); \
+ (N) && ((S) = RB_TREE_PREV((T), (N)), 1); \
+ (N) = (S))
#ifdef RBDEBUG
TAILQ_HEAD(rb_node_qh, rb_node);
