diff options
Diffstat (limited to 'src/vppinfra/test_slist.c')
| -rw-r--r-- | src/vppinfra/test_slist.c | 228 |
1 files changed, 228 insertions, 0 deletions
diff --git a/src/vppinfra/test_slist.c b/src/vppinfra/test_slist.c new file mode 100644 index 00000000000..3c3cbf73ca9 --- /dev/null +++ b/src/vppinfra/test_slist.c @@ -0,0 +1,228 @@ +/* + * Copyright (c) 2015 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifdef CLIB_UNIX +#include <unistd.h> +#include <stdlib.h> +#include <stdio.h> +#endif + +#include <vppinfra/slist.h> + +typedef struct +{ + u32 *random_pool; + u32 seed; + u32 iter; + u32 verbose; + f64 branching_factor; + clib_slist_t slist; +} test_main_t; + +test_main_t test_main; + +#define foreach_simple_test \ +_(2) \ +_(4) \ +_(3) \ +_(1) + + +void +run_test (test_main_t * tm) +{ + int i; + u32 *tv; + u32 ncompares; + u64 total_compares = 0; + + if (1) + { + /* + * Add a bunch of random numbers to the skip-list, + * sorting them. + */ + for (i = 0; i < tm->iter; i++) + { + pool_get (tm->random_pool, tv); + *tv = random_u32 (&tm->seed); + clib_slist_add (&tm->slist, tv, tv - tm->random_pool); + } + /* make sure we can find each one */ + for (i = 0; i < tm->iter; i++) + { + u32 search_result; + tv = pool_elt_at_index (tm->random_pool, i); + + search_result = clib_slist_search (&tm->slist, tv, &ncompares); + ASSERT (search_result == i); + + total_compares += ncompares; + } + + fformat (stdout, "%.2f avg compares/search\n", + (f64) total_compares / (f64) i); + + fformat (stdout, "%U\n", format_slist, &tm->slist, + tm->iter < 1000 /* verbose */ ); + + /* delete half of them */ + for (i = tm->iter / 2; i < tm->iter; i++) + { + tv = pool_elt_at_index (tm->random_pool, i); + (void) clib_slist_del (&tm->slist, tv); + } + + /* make sure we can find the set we should find, and no others */ + for (i = 0; i < tm->iter; i++) + { + u32 search_result; + tv = pool_elt_at_index (tm->random_pool, i); + + search_result = clib_slist_search (&tm->slist, tv, &ncompares); + if (i >= tm->iter / 2) + ASSERT (search_result == (u32) ~ 0); + else + ASSERT (search_result == i); + + } + + fformat (stdout, "%U\n", format_slist, &tm->slist, + tm->iter < 1000 /* verbose */ ); + + /* delete the rest */ + for (i = 0; i < tm->iter; i++) + { + tv = pool_elt_at_index (tm->random_pool, i); + + (void) clib_slist_del (&tm->slist, tv); + } + + fformat (stdout, "%U\n", format_slist, &tm->slist, + tm->iter < 1000 /* verbose */ ); + } + else + { + +#define _(n) \ + do { \ + pool_get (tm->random_pool, tv); \ + *tv = n; \ + clib_slist_add (&tm->slist, tv, tv - tm->random_pool); \ + fformat(stdout, "%U\n", format_slist, &tm->slist, 1 /* verbose */); \ + } while (0); + foreach_simple_test; +#undef _ + } + + return; +} + +word +test_compare (void *key, u32 elt_index) +{ + u32 *k = (u32 *) key; + u32 elt = test_main.random_pool[elt_index]; + + if (*k < elt) + return -1; + if (*k > elt) + return 1; + return 0; +} + +u8 * +test_format (u8 * s, va_list * args) +{ + u32 elt_index = va_arg (*args, u32); + u32 elt = test_main.random_pool[elt_index]; + + return format (s, "%u", elt); +} + +void +initialize_slist (test_main_t * tm) +{ + clib_slist_init (&tm->slist, tm->branching_factor, + test_compare, test_format); +} + +int +test_slist_main (unformat_input_t * input) +{ + test_main_t *tm = &test_main; + u32 tmp; + + tm->seed = 0xbabeb00b; + tm->iter = 100000; + tm->verbose = 1; + tm->branching_factor = 1.0 / 5.0; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) + { + if (unformat (input, "seed %d", &tm->seed)) + continue; + else if (unformat (input, "iter %d", &tm->iter)) + continue; + else if (unformat (input, "verbose")) + tm->verbose = 1; + else if (unformat (input, "branch %d", &tmp)) + { + if (tmp > 0) + tm->branching_factor = 1.0 / (f64) tmp; + else + fformat (stderr, "warning: branch = 0, ignored\n"); + } + else + { + clib_error ("unknown input `%U'", format_unformat_error, input); + goto usage; + } + } + initialize_slist (tm); + run_test (tm); + + return 0; + +usage: + fformat (stderr, "usage: test_slist seed <seed> iter <iter> [verbose]\n"); + return 1; + +} + +#ifdef CLIB_UNIX +int +main (int argc, char *argv[]) +{ + unformat_input_t i; + int ret; + + clib_mem_init (0, (u64) 4 << 30); + + unformat_init_command_line (&i, argv); + ret = test_slist_main (&i); + unformat_free (&i); + + return ret; +} +#endif /* CLIB_UNIX */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |