summaryrefslogtreecommitdiff
path: root/misc
diff options
context:
space:
mode:
authorFlorian Weimer <fweimer@redhat.com>2019-05-02 11:42:51 +0200
committerFlorian Weimer <fweimer@redhat.com>2019-05-02 11:42:51 +0200
commit7b807a35a8dc63f9742cecf0fc3db46c30e28b0d (patch)
tree0dce83854245814394b46373b4c8316ab7610b0c /misc
parent20aa5819586ac7ad11f711bab64feda307965191 (diff)
downloadglibc-7b807a35a8dc63f9742cecf0fc3db46c30e28b0d.tar.gz
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>
Diffstat (limited to 'misc')
-rw-r--r--misc/Versions5
-rw-r--r--misc/search.h7
-rw-r--r--misc/tsearch.c34
-rw-r--r--misc/tst-tsearch.c89
4 files changed, 132 insertions, 3 deletions
diff --git a/misc/Versions b/misc/Versions
index 900e4ffb79..e749582369 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 47e8a43436..4659c59877 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 5c19082a59..edf0fec971 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 5803a456e0..9a570dd6c9 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)