+++ /dev/null
-/*
- * 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:
- */
Code Review / vpp.git / blobdiff