diff options
Diffstat (limited to 'misc')
| -rw-r--r-- | misc/Versions | 5 | ||||
| -rw-r--r-- | misc/search.h | 7 | ||||
| -rw-r--r-- | misc/tsearch.c | 34 | ||||
| -rw-r--r-- | misc/tst-tsearch.c | 89 |
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) |