diff options
Diffstat (limited to 'vppinfra/vppinfra/test_slist.c')
| -rw-r--r-- | vppinfra/vppinfra/test_slist.c | 211 |
1 files changed, 211 insertions, 0 deletions
diff --git a/vppinfra/vppinfra/test_slist.c b/vppinfra/vppinfra/test_slist.c new file mode 100644 index 00000000000..76ba5dc59aa --- /dev/null +++ b/vppinfra/vppinfra/test_slist.c @@ -0,0 +1,211 @@ +/* + * 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 = 10000000; + 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)8<<30); + + unformat_init_command_line (&i, argv); + ret = test_slist_main (&i); + unformat_free (&i); + + return ret; +} +#endif /* CLIB_UNIX */ |