/* Test program for tsearch et al.
- Copyright (C) 1997-2014 Free Software Foundation, Inc.
+ Copyright (C) 1997-2019 Free Software Foundation, Inc.
This file is part of the GNU C Library.
The GNU C Library is free software; you can redistribute it and/or
You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, see
- <http://www.gnu.org/licenses/>. */
+ <https://www.gnu.org/licenses/>. */
#ifndef _GNU_SOURCE
# define _GNU_SOURCE 1
#include <string.h>
#include <search.h>
#include <tst-stack-align.h>
+#include <support/check.h>
#define SEED 0
#define BALANCED 1
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)
}
}
+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;
}
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)
{
}
}
+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);
+ TEST_VERIFY_EXIT (first_list != NULL);
+
+ walk_tree_with (root, expected_count, twalk_with_twalk_r);
+ TEST_VERIFY (!walk_trace_has_failed (&walk_trace));
+
+ /* 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)
}
-int
-main (int argc, char **argv)
+static int
+do_test (void)
{
int total_error = 0;
static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
return total_error;
}
+
+#define TEST_FUNCTION do_test ()
+#include "../test-skeleton.c"