[src/trunk]: src/sys/sys rbtree(3): Implement _FOREACH_SAFE macros

[roy <roy%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/db882e022d37
branches:  trunk
changeset: 997418:db882e022d37
user:      roy <roy%NetBSD.org@localhost>
date:      Thu Mar 07 12:05:54 2019 +0000

description:
rbtree(3): Implement _FOREACH_SAFE macros

And _NEXT and _PREV as well.

diffstat:

 share/man/man3/rbtree.3 |  30 ++++++++++++++++++++++++++++--
 sys/sys/rbtree.h        |  18 +++++++++++++-----
 2 files changed, 41 insertions(+), 7 deletions(-)

diffs (108 lines):

diff -r cdf86091dddd -r db882e022d37 share/man/man3/rbtree.3
--- a/share/man/man3/rbtree.3   Thu Mar 07 11:09:48 2019 +0000
+++ b/share/man/man3/rbtree.3   Thu Mar 07 12:05:54 2019 +0000
@@ -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 @@
 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 @@
 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 @@
 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
diff -r cdf86091dddd -r db882e022d37 sys/sys/rbtree.h
--- a/sys/sys/rbtree.h  Thu Mar 07 11:09:48 2019 +0000
+++ b/sys/sys/rbtree.h  Thu Mar 07 12:05:54 2019 +0000
@@ -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 @@
 
 #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);