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>

4 files changed, 132 insertions, 3 deletions

diff --git a/misc/Versions b/misc/Versions
index 900e4ff..e749582 100644
--- a/misc/Versions
+++ b/misc/Versions
@@ -158,11 +158,14 @@ libc {
   GLIBC_2.26 {
     preadv2; preadv64v2; pwritev2; pwritev64v2;
   }
+  GLIBC_2.30 {
+    twalk_r;
+  }
   GLIBC_PRIVATE {
     __madvise;
     __mktemp;
     __libc_ifunc_impl_list;
-    __tdelete; __tfind; __tsearch; __twalk;
+    __tdelete; __tfind; __tsearch; __twalk; __twalk_r;
     __mmap; __munmap; __mprotect;
     __sched_get_priority_min; __sched_get_priority_max;
     __libc_allocate_once_slow;
diff --git a/misc/search.h b/misc/search.h
index 47e8a43..4659c59 100644
--- a/misc/search.h
+++ b/misc/search.h
@@ -150,6 +150,13 @@ typedef void (*__action_fn_t) (const void *__nodep, VISIT __value,
 extern void twalk (const void *__root, __action_fn_t __action);
 
 #ifdef __USE_GNU
+/* Like twalk, but pass down a closure parameter instead of the
+   level.  */
+extern void twalk_r (const void *__root,
+		     void (*) (const void *__nodep, VISIT __value,
+			       void *__closure),
+		     void *__closure);
+
 /* Callback type for function to free a tree node.  If the keys are atomic
    data this function should do nothing.  */
 typedef void (*__free_fn_t) (void *__nodep);
diff --git a/misc/tsearch.c b/misc/tsearch.c
index 5c19082..edf0fec 100644
--- a/misc/tsearch.c
+++ b/misc/tsearch.c
@@ -719,7 +719,41 @@ __twalk (const void *vroot, __action_fn_t action)
 libc_hidden_def (__twalk)
 weak_alias (__twalk, twalk)
 
+/* twalk_r is the same as twalk, but with a closure parameter instead
+   of the level.  */
+static void
+trecurse_r (const void *vroot, void (*action) (const void *, VISIT, void *),
+	    void *closure)
+{
+  const_node root = (const_node) vroot;
 
+  if (LEFT(root) == NULL && RIGHT(root) == NULL)
+    (*action) (root, leaf, closure);
+  else
+    {
+      (*action) (root, preorder, closure);
+      if (LEFT(root) != NULL)
+	trecurse_r (LEFT(root), action, closure);
+      (*action) (root, postorder, closure);
+      if (RIGHT(root) != NULL)
+	trecurse_r (RIGHT(root), action, closure);
+      (*action) (root, endorder, closure);
+    }
+}
+
+void
+__twalk_r (const void *vroot, void (*action) (const void *, VISIT, void *),
+	   void *closure)
+{
+  const_node root = (const_node) vroot;
+
+  CHECK_TREE ((node) root);
+
+  if (root != NULL && action != NULL)
+    trecurse_r (root, action, closure);
+}
+libc_hidden_def (__twalk_r)
+weak_alias (__twalk_r, twalk_r)
 
 /* The standardized functions miss an important functionality: the
    tree cannot be removed easily.  We provide a function to do this.  */
diff --git a/misc/tst-tsearch.c b/misc/tst-tsearch.c
index 5803a45..9a570dd 100644
--- a/misc/tst-tsearch.c
+++ b/misc/tst-tsearch.c
@@ -25,6 +25,7 @@
 #include <string.h>
 #include <search.h>
 #include <tst-stack-align.h>
+#include <support/check.h>
 
 #define SEED 0
 #define BALANCED 1
@@ -74,6 +75,20 @@ static int max_depth;
 
 static int stack_align_check[2];
 
+/* Used to compare walk traces between the two implementations.  */
+struct walk_trace_element
+{
+  const void *key;
+  VISIT which;
+  int depth;
+};
+#define DYNARRAY_STRUCT walk_trace_list
+#define DYNARRAY_ELEMENT struct walk_trace_element
+#define DYNARRAY_PREFIX walk_trace_
+#define DYNARRAY_INITIAL_SIZE 0
+#include <malloc/dynarray-skeleton.c>
+static struct walk_trace_list walk_trace;
+
 /* Compare two keys.  */
 static int
 cmp_fn (const void *a, const void *b)
@@ -102,11 +117,54 @@ memfry (int *string)
     }
 }
 
+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;
+    }
+}
+
+static void
+twalk_with_twalk_r (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);
+  TEST_COMPARE (closure.depth, 0);
+}
+
 static void
 walk_action (const void *nodep, const VISIT which, const int depth)
 {
   int key = **(int **) nodep;
 
+  walk_trace_add (&walk_trace,
+		  (struct walk_trace_element) { nodep, which, depth });
+
   if (!stack_align_check[1])
     stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1;
 
@@ -128,14 +186,16 @@ walk_action (const void *nodep, const VISIT which, const int depth)
 }
 
 static void
-walk_tree (void *root, int expected_count)
+walk_tree_with (void *root, int expected_count,
+		void (*walk) (const void *,
+			      void (*) (const void *, VISIT, int)))
 {
   int i;
 
   memset (z, 0, sizeof z);
   max_depth = 0;
 
-  twalk (root, walk_action);
+  walk (root, walk_action);
   for (i = 0; i < expected_count; ++i)
     if (z[i] != 1)
       {
@@ -154,6 +214,31 @@ walk_tree (void *root, int expected_count)
     }
 }
 
+static void
+walk_tree (void *root, int expected_count)
+{
+  walk_trace_clear (&walk_trace);
+  walk_tree_with (root, expected_count, twalk);
+  TEST_VERIFY (!walk_trace_has_failed (&walk_trace));
+  size_t first_list_size;
+  struct walk_trace_element *first_list
+    = walk_trace_finalize (&walk_trace, &first_list_size);
+
+  walk_tree_with (root, expected_count, twalk_with_twalk_r);
+
+  /* Compare the two traces.  */
+  TEST_COMPARE (first_list_size, walk_trace_size (&walk_trace));
+  for (size_t i = 0; i < first_list_size && i < walk_trace_size (&walk_trace);
+       ++i)
+    {
+      TEST_VERIFY (first_list[i].key == walk_trace_at (&walk_trace, i)->key);
+      TEST_COMPARE (first_list[i].which, walk_trace_at (&walk_trace, i)->which);
+      TEST_COMPARE (first_list[i].depth, walk_trace_at (&walk_trace, i)->depth);
+    }
+
+  walk_trace_free (&walk_trace);
+}
+
 /* Perform an operation on a tree.  */
 static void
 mangle_tree (enum order how, enum action what, void **root, int lag)