misc: Add twalk_r function

The twalk function is very difficult to use in a multi-threaded
program because there is no way to pass external state to the
iterator function.

Reviewed-by: Carlos O'Donell <carlos@redhat.com>
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>

2 files changed, 80 insertions, 1 deletions

diff --git a/manual/examples/twalk.c b/manual/examples/twalk.c
new file mode 100644
index 0000000000..04e32731d6
--- /dev/null
+++ b/manual/examples/twalk.c
@@ -0,0 +1,56 @@
+/* Implement twalk using twalk_r.
+   Copyright (C) 2019 Free Software Foundation, Inc.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include <search.h>
+
+struct twalk_with_twalk_r_closure
+{
+  void (*action) (const void *, VISIT, int);
+  int depth;
+};
+
+static void
+twalk_with_twalk_r_action (const void *nodep, VISIT which, void *closure0)
+{
+  struct twalk_with_twalk_r_closure *closure = closure0;
+
+  switch (which)
+    {
+    case leaf:
+      closure->action (nodep, which, closure->depth);
+      break;
+    case preorder:
+      closure->action (nodep, which, closure->depth);
+      ++closure->depth;
+      break;
+    case postorder:
+      /* The preorder action incremented the depth.  */
+      closure->action (nodep, which, closure->depth - 1);
+      break;
+    case endorder:
+      --closure->depth;
+      closure->action (nodep, which, closure->depth);
+      break;
+    }
+}
+
+void
+twalk (const void *root, void (*action) (const void *, VISIT, int))
+{
+  struct twalk_with_twalk_r_closure closure = { action, 0 };
+  twalk_r (root, twalk_with_twalk_r_action, &closure);
+}
diff --git a/manual/search.texi b/manual/search.texi
index 1574c96562..979732f027 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -618,5 +618,28 @@ Since the functions used for the @var{action} parameter to @code{twalk}
 must not modify the tree data, it is safe to run @code{twalk} in more
 than one thread at the same time, working on the same tree.  It is also
 safe to call @code{tfind} in parallel.  Functions which modify the tree
-must not be used, otherwise the behavior is undefined.
+must not be used, otherwise the behavior is undefined.  However, it is
+difficult to pass data external to the tree to the callback function
+without resorting to global variables (and thread safety issues), so
+see the @code{twalk_r} function below.
+@end deftypefun
+
+@deftypefun void twalk_r (const void *@var{root}, void (*@var{action}) (const void *@var{key}, VISIT @var{which}, void *@var{closure}), void *@var{closure})
+@standards{GNU, search.h}
+@safety{@prelim{}@mtsafe{@mtsrace{:root}}@assafe{}@acsafe{}}
+For each node in the tree with a node pointed to by @var{root}, the
+@code{twalk_r} function calls the function provided by the parameter
+@var{action}.  For leaf nodes the function is called exactly once with
+@var{value} set to @code{leaf}.  For internal nodes the function is
+called three times, setting the @var{value} parameter or @var{action} to
+the appropriate value.  The @var{closure} parameter is passed down to
+each call of the @var{action} function, unmodified.
+
+It is possible to implement the @code{twalk} function on top of the
+@code{twalk_r} function, which is why there is no separate level
+parameter.
+
+@smallexample
+@include twalk.c.texi
+@end smallexample
 @end deftypefun